論文の概要: Matrix Completion with Convex Optimization and Column Subset Selection
- arxiv url: http://arxiv.org/abs/2403.01919v3
- Date: Sun, 06 Oct 2024 08:21:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-08 13:11:17.016326
- Title: Matrix Completion with Convex Optimization and Column Subset Selection
- Title（参考訳）: 凸最適化とカラムサブセット選択による行列補完
- Authors: Antonina Krajewska, Ewa Niewiadomska-Szynkiewicz,
- Abstract要約: 本稿では,カラム選択行列補完法(CSMC)を実装した2つのアルゴリズムを提案する。
本研究では, 行列サイズ, ランク計算, 欠落要素の割合が解の質と時間に与える影響について検討するため, 合成データについて実験を行った。
我々の徹底的な分析により,CSMCは凸最適化に基づく行列補完アルゴリズムに匹敵する品質のソリューションを提供することが示された。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: We introduce a two-step method for the matrix recovery problem. Our approach combines the theoretical foundations of the Column Subset Selection and Low-rank Matrix Completion problems. The proposed method, in each step, solves a convex optimization task. We present two algorithms that implement our Columns Selected Matrix Completion (CSMC) method, each dedicated to a different size problem. We performed a formal analysis of the presented method, in which we formulated the necessary assumptions and the probability of finding a correct solution. In the second part of the paper, we present the results of the experimental work. Numerical experiments verified the correctness and performance of the algorithms. To study the influence of the matrix size, rank, and the proportion of missing elements on the quality of the solution and the computation time, we performed experiments on synthetic data. The presented method was applied to two real-life problems problems: prediction of movie rates in a recommendation system and image inpainting. Our thorough analysis shows that CSMC provides solutions of comparable quality to matrix completion algorithms, which are based on convex optimization. However, CSMC offers notable savings in terms of runtime.
- Abstract（参考訳）: 本稿では,行列回復問題に対する2段階法を提案する。
提案手法は,カラムサブセット選択と低ランク行列補完問題の理論的基礎を組み合わさったものである。
提案手法は各ステップで凸最適化タスクを解く。
本稿では,カラム選択行列補完法(CSMC)を実装した2つのアルゴリズムを提案する。
提案手法の形式解析を行い、必要な仮定と正しい解を見つける確率を定式化した。
本論文の第2部では,実験結果について述べる。
数値実験によりアルゴリズムの正しさと性能が検証された。
本研究では, 行列サイズ, ランク, 欠落要素の割合が解の質や計算時間に与える影響について検討するため, 合成データについて実験を行った。
提案手法は,レコメンデーションシステムにおける映画レートの予測とイメージインペイントという,現実的な2つの問題に適用した。
我々の徹底的な分析により,CSMCは凸最適化に基づく行列補完アルゴリズムに匹敵する品質のソリューションを提供することが示された。
しかし、CSMCは実行時の大幅な節約を提供している。
関連論文リスト
- Orthogonally weighted $\ell_{2,1}$ regularization for rank-aware joint
sparse recovery: algorithm and analysis [7.7001263654719985]
我々は,新たな正規化法である $ell_2,1$$(mathitowell_2,1$) を用いて,結合スパース回復問題の効率的な解法を提案し,解析する。
この手法は特徴抽出、行列列選択、辞書学習に応用され、一般的な$ell_2,1$正規化とは異なる。
提案手法のランク認識の証明を行い,提案手法の最適化問題に対する解が存在することを証明し,収束を解析した効率的な解法を開発した。
論文 参考訳（メタデータ） (2023-11-21T01:52:15Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
我々はロバスト成分分析のためのアルゴリズムを設計する(A)
行列を低主行列とスパース主行列の和に分解する。
論文 参考訳（メタデータ） (2023-07-12T03:48:26Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Matrix Reordering for Noisy Disordered Matrices: Optimality and
Computationally Efficient Algorithms [9.245687221460654]
単細胞生物学とメダゲノミクスの応用により,ノイズモノトンToeplitz行列モデルに基づく行列化の問題を考察した。
我々は、決定理論の枠組みでこの問題の基本的な統計的限界を確立し、制約付き最小二乗率を示す。
そこで本研究では,性能向上を保証した新しい時間適応ソートアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-01-17T14:53:52Z) - Fast Projected Newton-like Method for Precision Matrix Estimation under
Total Positivity [15.023842222803058]
現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。
本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。
合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
論文 参考訳（メタデータ） (2021-12-03T14:39:10Z) - Boolean Matrix Factorization via Nonnegative Auxiliary Optimization [0.5459797813771498]
BMF問題を直接解く代わりに、補助行列上の制約で非負の最適化問題を解く。
二つの解空間の同値性の証明を、厳密な解の存在下で提供する。
アルゴリズムの有効性と複雑さを示すために,合成データセットと実データセットの実験を行った。
論文 参考訳（メタデータ） (2021-06-08T21:55:49Z) - Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank
Constraints [3.179831861897336]
低ランク最適化問題を証明可能な最適性に解決するためのフレームワークを提供する。
我々のフレームワークは、ラウンドリングや局所探索技術を通じて、ほぼ最適のソリューションを提供する。
論文 参考訳（メタデータ） (2020-09-22T08:59:06Z) - Robust Low-rank Matrix Completion via an Alternating Manifold Proximal
Gradient Continuation Method [47.80060761046752]
ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。
この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。
RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。
本稿では、近年のローワークの動機付けについて述べる。
論文 参考訳（メタデータ） (2020-08-18T04:46:22Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。