論文の概要: 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は実行時の大幅な節約を提供している。
関連論文リスト
- Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion [14.542166904874147]
similarity Completion Matrixは多くの機械学習タスクの中核にある基本的なツールとして機能する。
この問題に対処するために、類似行列理論(SMC)法が提案されているが、それらは複雑である。
提案手法は,PSD特性を解析して推定プロセスを導出し,低ランク解を保証するために非低ランク正規化器を組み込む2つの新しい,スケーラブルで効果的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-09-29T04:27:23Z) - Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [1.991322361612643]
対称非負行列因子化(SymNMF)は、データ解析と機械学習における技術である。
計算のためのランダム化アルゴリズムを2つ開発した。
提案手法は, 解法の品質を概ね維持し, 大規模疎水化問題と大規模疎水化問題の両方に対して, 大幅な高速化を実現する。
論文 参考訳(メタデータ) (2024-02-13T00:02:05Z) - 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) - Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and
Eigenvector Disjunctions [6.537257913467247]
低ランク行列の完備化は、与えられた観測セットをできるだけ正確に回復する最小の複雑さの行列からなる。
新たな凸緩和は、既存の方法に比べて最大値を大幅に下げる。
論文 参考訳(メタデータ) (2023-05-20T22:04:34Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳(メタデータ) (2020-12-29T04:08:38Z) - Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank
Constraints [3.179831861897336]
低ランク最適化問題を証明可能な最適性に解決するためのフレームワークを提供する。
我々のフレームワークは、ラウンドリングや局所探索技術を通じて、ほぼ最適のソリューションを提供する。
論文 参考訳(メタデータ) (2020-09-22T08:59:06Z) - PCA Reduced Gaussian Mixture Models with Applications in Superresolution [1.885698488789676]
本稿は、このトピックに2倍のコントリビューションを提供する。
まず,モデルの各成分におけるデータ次元の減少と合わせてガウス混合モデルを提案する。
第2に,サンディープとヤコブのアプローチに基づく2次元および3次元材料画像の超解像化にPCA-GMMを適用した。
論文 参考訳(メタデータ) (2020-09-16T07:33:56Z) - Multi-View Spectral Clustering with High-Order Optimal Neighborhood
Laplacian Matrix [57.11971786407279]
マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。
本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。
提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
論文 参考訳(メタデータ) (2020-08-31T12:28:40Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。