論文の概要: Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions

• arxiv url: http://arxiv.org/abs/2305.12292v1
• Date: Sat, 20 May 2023 22:04:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-23 23:10:24.943185
• Title: Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions
• Title（参考訳）: 最適低ランク行列補完:半有限緩和と固有ベクトル解法
• Authors: Dimitris Bertsimas, Ryan Cory-Wright, Sean Lo, and Jean Pauphilet
• Abstract要約: 我々は、ランク1行列の和として低ランク行列による新しい、しばしば厳密な凸緩和のクラスを示し、ショア緩和を通じて各ランク1行列の各2つのマイナーが等級0であることを示す。 数値実験では, 新たな凸緩和法により, 既存の試みと比較して, 最適ギャップを2桁減らした。
• 参考スコア（独自算出の注目度）: 2.589904091148018
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible, and has numerous applications such as product recommendation. Unfortunately, existing methods for solving low-rank matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not possess any optimality guarantees. We reexamine matrix completion with an optimality-oriented eye, by reformulating low-rank problems as convex problems over the non-convex set of projection matrices and implementing a disjunctive branch-and-bound scheme that solves them to certifiable optimality. Further, we derive a novel and often tight class of convex relaxations by decomposing a low-rank matrix as a sum of rank-one matrices and incentivizing, via a Shor relaxation, that each two-by-two minor in each rank-one matrix has determinant zero. In numerical experiments, our new convex relaxations decrease the optimality gap by two orders of magnitude compared to existing attempts. Moreover, we showcase the performance of our disjunctive branch-and-bound scheme and demonstrate that it solves matrix completion problems over 150x150 matrices to certifiable optimality in hours, constituting an order of magnitude improvement on the state-of-the-art for certifiably optimal methods.
• Abstract（参考訳）: 低ランク行列の完成は、与えられた観測のセットを可能な限り正確に復元する最小限の複雑さの行列を計算し、製品推奨のような多くのアプリケーションを持つ。 残念なことに、既存の低ランク行列完全解法は、高度にスケーラブルでしばしば高品質な解を識別するが、最適性保証を持たないヒューリスティックである。 我々は, 射影行列の非凸集合上の凸問題として低ランク問題を再検討し, それらを検証可能な最適性に解く連結分岐・束縛スキームを実装することにより, 最適性指向眼で行列完成を再検討する。 さらに、階数 1 の行列の和として低階行列を分解し、ショア緩和を通じて各階数 1 の行列内の各 2 対 2 個のマイナーが決定式 0 を持つようにインセンティブを与えることにより、新規でしばしば密接な凸緩和のクラスを導出する。 数値実験では,新しい凸緩和により,既存の試みに比べて2桁の最適性ギャップが減少する。 さらに,本手法の性能を実証し,150×150行列以上の行列完成問題を数時間で解き明かし,検証可能な最適法として最先端の改良を構成することを実証した。

関連論文リスト

• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems [19.930021245647705]
  低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。 本稿では,このような問題に対する標準凸緩和について考察する。 本研究は, テクスト性相補性条件の下で, 比較的軽度な仮定の下では, 非滑らかな目的が2つの一般的なテクストミラー-プロキシ法の近似変種であるスムーズな関数の最大値として記述できることを証明した。
  論文  参考訳（メタデータ） (2022-06-23T08:10:54Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
  本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。 交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
  論文  参考訳（メタデータ） (2021-09-13T16:13:13Z)
• 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)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  そこで我々は,適応的かつ音質の高い"核フロベニウスノルム"と呼ばれる新しい非スケーラブルな低ランク正規化器を提案する。 特異値の計算をバイパスし、アルゴリズムによる高速な最適化を可能にする。 既存の行列学習手法では最速でありながら、最先端の回復性能が得られる。
  論文  参考訳（メタデータ） (2020-08-14T18:47:58Z)
• Solving the Robust Matrix Completion Problem via a System of Nonlinear Equations [28.83358353043287]
  低階行列 $L_*$ とスパース行列 $S_*$ をそれらの和 $M=L_*+S_*inmathbbRmtimes n$ の不完全観測から回復することを目的としたロバスト行列完備化の問題を考える。 このアルゴリズムは並列性が高く、大規模な問題に適している。 数値シミュレーションにより、単純な手法は期待通りに動作し、最先端の手法に匹敵することを示した。
  論文  参考訳（メタデータ） (2020-03-24T17:28:15Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  我々は、原子核ノルム正規化行列補完に対する相対誤差を開発する。 未知行列の最適低ランク近似を回復するための相対上界を導出する。
  論文  参考訳（メタデータ） (2015-04-26T13:12:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。