論文の概要: Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing

• arxiv url: http://arxiv.org/abs/2208.07469v1
• Date: Mon, 15 Aug 2022 23:21:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-17 13:01:40.800276
• Title: Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing
• Title（参考訳）: マトリックスセンシングにおける半定値プログラミングとBler-Monteiro因子化
• Authors: Baturalp Yalcin, Ziye Ma, Javad Lavaei, Somayeh Sojoudi
• Abstract要約: 行列センシングの2つの主要なアプローチは、半定値プログラミング(SDP)とブラー・モンテイロ(B-M)の分解に基づいている。 本稿では,この2つの方法の主な違いについて述べる。
• 参考スコア（独自算出の注目度）: 17.149804263692452
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Many fundamental low-rank optimization problems, such as matrix completion, phase synchronization/retrieval, power system state estimation, and robust PCA, can be formulated as the matrix sensing problem. Two main approaches for solving matrix sensing are based on semidefinite programming (SDP) and Burer-Monteiro (B-M) factorization. The SDP method suffers from high computational and space complexities, whereas the B-M method may return a spurious solution due to the non-convexity of the problem. The existing theoretical guarantees for the success of these methods have led to similar conservative conditions, which may wrongly imply that these methods have comparable performances. In this paper, we shed light on some major differences between these two methods. First, we present a class of structured matrix completion problems for which the B-M methods fail with an overwhelming probability, while the SDP method works correctly. Second, we identify a class of highly sparse matrix completion problems for which the B-M method works and the SDP method fails. Third, we prove that although the B-M method exhibits the same performance independent of the rank of the unknown solution, the success of the SDP method is correlated to the rank of the solution and improves as the rank increases. Unlike the existing literature that has mainly focused on those instances of matrix sensing for which both SDP and B-M work, this paper offers the first result on the unique merit of each method over the alternative approach.
• Abstract（参考訳）: 行列の完全性、位相同期/再帰性、電力系統状態推定、ロバストpcaなど、多くの基本的な低ランク最適化問題を行列センシング問題として定式化することができる。 行列センシングの2つの主要なアプローチは半定値プログラミング(SDP)とB-M因子化に基づいている。 SDP法は計算量と空間の複雑さに悩まされるが、B-M法は問題の非凸性のために急激な解を返す。 これらの手法の成功に対する既存の理論的保証は、同様の保守的な条件を導いており、これはこれらの手法が同等の性能を持つことを誤って示唆しているかもしれない。 本稿では,これら2つの方法の相違点について概説する。 まず、SDP法が正しく動作するのに対して、B-M法は圧倒的な確率で失敗する構造的行列完備問題のクラスを示す。 次に,B-M法が機能し,SDP法が失敗する,高度にスパースな行列補完問題のクラスを特定する。 第三に,B-M法は未知解のランクに依存しない性能を示すが,SDP法の成功は解のランクと相関し,階数が増加するにつれて向上することを示す。 SDPとB-Mの両方が動作する行列センシングの事例に主に焦点をあてた既存の文献とは異なり、本論文は代替手法よりも各手法の独特な利点を第一に提示する。

関連論文リスト

• Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion [14.542166904874147]
  similarity Completion Matrixは多くの機械学習タスクの中核にある基本的なツールとして機能する。 この問題に対処するために、類似行列理論(SMC)法が提案されているが、それらは複雑である。 提案手法は,PSD特性を解析して推定プロセスを導出し,低ランク解を保証するために非低ランク正規化器を組み込む2つの新しい,スケーラブルで効果的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-29T04:27:23Z)
• Matrix Completion with Convex Optimization and Column Subset Selection [0.0]
  本稿では,カラム選択行列補完法(CSMC)を実装した2つのアルゴリズムを提案する。 本研究では, 行列サイズ, ランク計算, 欠落要素の割合が解の質と時間に与える影響について検討するため, 合成データについて実験を行った。 我々の徹底的な分析により,CSMCは凸最適化に基づく行列補完アルゴリズムに匹敵する品質のソリューションを提供することが示された。
  論文  参考訳（メタデータ） (2024-03-04T10:36:06Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。 これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。 我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
  論文  参考訳（メタデータ） (2022-07-26T04:38:47Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。 本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。 いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-07-14T18:18:02Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization [71.57324258813674]
  位相探索(PR)とアフィンランク最小化(ARM)アルゴリズムに基づいてPSDMFアルゴリズムを設計可能であることを示す。 このアイデアに触発され、反復的ハードしきい値(IHT)に基づくPSDMFアルゴリズムの新たなファミリーを導入する。
  論文  参考訳（メタデータ） (2020-07-24T06:10:19Z)

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

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