論文の概要: Disjunctive Branch-And-Bound for Certifiably Optimal Low-Rank Matrix Completion

• arxiv url: http://arxiv.org/abs/2305.12292v3
• Date: Wed, 07 May 2025 15:40:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-08 19:07:35.638039
• Title: Disjunctive Branch-And-Bound for Certifiably Optimal Low-Rank Matrix Completion
• Title（参考訳）: 最適最適低ランク行列補完のための分枝結合
• Authors: Dimitris Bertsimas, Ryan Cory-Wright, Sean Lo, Jean Pauphilet,
• Abstract要約: 2つの未成年者の和として低ランク行列を分解することにより、新しく、しばしばほぼ一致する凸緩和のクラスを提示する。 数値実験では、新しい凸緩和は、$max m, n q$ および $r leq$ の最適性またはほぼ最適性を減少させる。
• 参考スコア（独自算出の注目度）: 6.537257913467247
• 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. Unfortunately, existing methods for 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. We reformulate low-rank matrix completion problems as convex problems over the non-convex set of projection matrices and implement a disjunctive branch-and-bound scheme that solves them to certifiable optimality. Further, we derive a novel and often near-exact class of convex relaxations by decomposing a low-rank matrix as a sum of rank-one matrices and incentivizing that two-by-two minors in each rank-one matrix have determinant zero. In numerical experiments, our new convex relaxations decrease the optimality gap by two orders of magnitude compared to existing attempts, and our disjunctive branch-and-bound scheme solves $n \times m$ rank-$r$ matrix completion problems to certifiable optimality or near optimality in hours for $\max \{m, n\} \leq 2500$ and $r \leq 5$. Moreover, this improvement in the training error translates into an average $2\%$--$50\%$ improvement in the test set error.
• Abstract（参考訳）: 低ランク行列補完は、与えられた観測セットを可能な限り正確に回復する最小の複雑さの行列を演算する。 残念ながら、行列完備化のための既存の手法は、高度にスケーラブルで、しばしば高品質な解を識別するが、最適性を保証するものを持っていないヒューリスティックスである。 我々は最適性指向眼で行列補完を再検討する。 我々は、非凸な射影行列の集合上の凸問題として低ランク行列完備化問題を再構成し、それらを証明可能な最適性に解決する分枝有界スキームを実装した。 さらに,低ランク行列をランク1行列の和として分解し,各ランク1行列の2～2個の未成年者が決定性ゼロであることにインセンティブを与えることにより,新しい凸緩和のクラスを導出する。 数値実験では、新しい凸緩和は既存の試みと比較して2桁の最適性ギャップを減少させ、この解法は、$n \times m$ rank-$r$行列完備化問題から、$\max \{m, n\} \leq 2500$および$r \leq 5$に対して、証明可能な最適性またはほぼ最適性を数時間で解決する。 さらに、このトレーニングエラーの改善は、平均2\%$--50\%$テストセットエラーの改善に変換される。

関連論文リスト

• 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)

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

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