論文の概要: Compact Lifted Relaxations for Low-Rank Optimization

• arxiv url: http://arxiv.org/abs/2603.20228v1
• Date: Thu, 05 Mar 2026 17:05:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-06 02:36:12.91487
• Title: Compact Lifted Relaxations for Low-Rank Optimization
• Title（参考訳）: 低ランク最適化のためのコンパクトリフテッド緩和
• Authors: Ryan Cory-Wright, Jean Pauphilet,
• Abstract要約: 階数制約付き二次最適化問題に対して,n 倍 m$ の行列に対してトラクタブル凸緩和法を開発する。 そのようなスペクトル項を必要としない半定値緩和を導出する。 全体として、我々は幅広い低ランク二次問題のクラスに対してスケーラブルな半定値境界を得る。
• 参考スコア（独自算出の注目度）: 2.0052993723676895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop tractable convex relaxations for rank-constrained quadratic optimization problems over $n \times m$ matrices, a setting for which tractable relaxations are typically only available when the objective or constraints admit spectral (permutation-invariant) structure. We derive lifted semidefinite relaxations that do not require such spectral terms. Although a direct lifting introduces a large semidefinite constraint in dimension $n^2 + nm + 1$, we prove that many blocks of moment matrix are redundant and derive an equivalent compact relaxation that only involves two semidefinite constraints of dimension $nm + 1$ and $n+m$ respectively. For matrix completion, basis pursuit, and reduced-rank regression problems, we exploit additional structure to obtain even more compact formulations involving semidefinite matrices of dimension at most $2\max(n,m)$. Overall, we obtain scalable semidefinite bounds for a broad class of low-rank quadratic problems.
• Abstract（参考訳）: 次数制約付き2次最適化問題に対して,次数制約付き2次最適化問題に対するトラクタブル凸緩和法を,スペクトル(置換不変)構造を許容する目的や制約が典型的に利用可能となるような,トラクタブル緩和法(トラクタブル緩和法)を考案する。 そのようなスペクトル項を必要としない半定値緩和を導出する。 直接持ち上げは次元 $n^2 + nm + 1$ の大きな半定値制約を導入するが、モーメント行列の多くのブロックは冗長であり、それぞれ次元 $nm + 1$ と $n+m$ の2つの半定値制約のみを含む同値なコンパクト緩和を導出することを証明する。 行列の完備化、基底探索、低階回帰問題に対して、次元の半定値行列を少なくとも2\max(n,m)$で含むよりコンパクトな定式化を得るために、追加構造を利用する。 全体として、我々は幅広い低ランク二次問題のクラスに対してスケーラブルな半定値境界を得る。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization [2.0052993723676895]
  そこで我々は,低ランク最適化問題に対する類似の緩和戦略を構築した。 与えられた$n × m$ の半直交行列に対して、我々はアルゴリズムに対して純粋に乗法的近似比を導出する。 我々は、新しい半有限緩和法を開発することにより、一般の低ランク最適化問題にアプローチを拡張した。
  論文  参考訳（メタデータ） (2025-01-06T11:31:41Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Disjunctive Branch-And-Bound for Certifiably Optimal Low-Rank Matrix Completion [6.537257913467247]
  2つの未成年者の和として低ランク行列を分解することにより、新しく、しばしばほぼ一致する凸緩和のクラスを提示する。 数値実験では、新しい凸緩和は、$max m, n q$ および $r leq$ の最適性またはほぼ最適性を減少させる。
  論文  参考訳（メタデータ） (2023-05-20T22:04:34Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
  この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。 その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
  論文  参考訳（メタデータ） (2020-07-18T15:36:11Z)
• Competitive Mirror Descent [67.31015611281225]
  制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。 本稿では, 競合ミラー降下法(CMD)を提案する。 特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-06-17T22:11:35Z)

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

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