論文の概要: Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach

• arxiv url: http://arxiv.org/abs/2109.12701v3
• Date: Mon, 2 Oct 2023 01:38:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-03 21:52:20.511444
• Title: Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach
• Title（参考訳）: スパースプラス低ランク行列分解:離散最適化アプローチ
• Authors: Dimitris Bertsimas, Ryan Cory-Wright and Nicholas A. G. Johnson
• Abstract要約: スパースプラス低ランク分解問題(SLR)について検討する。 SLRはオペレーションリサーチと機械学習の基本的な問題である。 本稿では,SLRの新たな定式化を導入し,その基礎となる離散性をモデル化する。
• 参考スコア（独自算出の注目度）: 6.952045528182883
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the Sparse Plus Low-Rank decomposition problem (SLR), which is the problem of decomposing a corrupted data matrix into a sparse matrix of perturbations plus a low-rank matrix containing the ground truth. SLR is a fundamental problem in Operations Research and Machine Learning which arises in various applications, including data compression, latent semantic indexing, collaborative filtering, and medical imaging. We introduce a novel formulation for SLR that directly models its underlying discreteness. For this formulation, we develop an alternating minimization heuristic that computes high-quality solutions and a novel semidefinite relaxation that provides meaningful bounds for the solutions returned by our heuristic. We also develop a custom branch-and-bound algorithm that leverages our heuristic and convex relaxations to solve small instances of SLR to certifiable (near) optimality. Given an input $n$-by-$n$ matrix, our heuristic scales to solve instances where $n=10000$ in minutes, our relaxation scales to instances where $n=200$ in hours, and our branch-and-bound algorithm scales to instances where $n=25$ in minutes. Our numerical results demonstrate that our approach outperforms existing state-of-the-art approaches in terms of rank, sparsity, and mean-square error while maintaining a comparable runtime.
• Abstract（参考訳）: 本研究では,劣化したデータ行列を摂動のスパース行列と基底真理を含むローランク行列に分解する問題であるスパースプラスローランク分解問題(slr)について検討する。 SLRは、データ圧縮、潜時セマンティックインデックス、協調フィルタリング、医用画像など、さまざまなアプリケーションで発生するオペレーションリサーチと機械学習の根本的な問題である。 基礎となる離散性を直接モデル化する新しいslrの定式化を提案する。 この定式化のために、高品質な解を計算する交互最小化ヒューリスティックと、ヒューリスティックによって返される解に有意な境界を与える新しい半定緩和を開発する。 我々はまた、我々のヒューリスティックかつ凸緩和を利用して、SLRの小さなインスタンスを証明可能な(ほぼ)最適性に解決する独自の分岐結合アルゴリズムを開発した。 入力$n$-by-$n$行列が与えられた場合、我々のヒューリスティックスケールは$n=10000$ in minutesのインスタンスを解決し、緩和スケールは$n=200$ in hoursのインスタンスにスケールし、分岐とバウンドのアルゴリズムは$n=25$ in minutesのインスタンスにスケールします。 数値計算の結果,我々のアプローチは,同等のランタイムを維持しながら,既存の最先端のアプローチよりもランク,スパーシティ,平均2乗誤差の点で優れていることがわかった。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Predictive Low Rank Matrix Learning under Partial Observations: Mixed-Projection ADMM [5.877778007271621]
  我々は、この問題を最適化問題として定式化し、再現の強度と観測項目とのバランスをとる。 我々は,高品質な実現可能な解を生成する乗算器アルゴリズムの効率的かつスケーラブルな交互方向法を設計する。 我々のアルゴリズムは、$n = 10000$行と$m = 10000$列を1分以内で解くことができる。
  論文  参考訳（メタデータ） (2024-07-18T17:33:14Z)
• Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data [17.657917523817243]
  この問題を条件付き最適化問題とみなして,器用変分回帰のためのアルゴリズムを開発し,解析する。 最小二乗変数回帰の文脈では、我々のアルゴリズムは行列逆転やミニバッチを必要としない。 任意の$iota>0$に対して$mathcalO(log T/T)$と$mathcalO(1/T1-iota)$の順の収束率を導出する。
  論文  参考訳（メタデータ） (2024-05-29T19:21:55Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives [9.593208961737572]
  本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。 本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。 提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
  論文  参考訳（メタデータ） (2021-04-14T19:21:59Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)

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

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