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

• arxiv url: http://arxiv.org/abs/2109.12701v1
• Date: Sun, 26 Sep 2021 20:49:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-28 15:42:55.494183
• 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の定式化を導入する。 提案手法は, 低位行列のMSEとスパース行列のMSEにおいて, 既存の最先端手法よりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 3.136861161060885
• 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 $\mathbf{D}$ into a sparse matrix $\mathbf{Y}$ containing the perturbations plus a low rank matrix $\mathbf{X}$. SLR is a fundamental problem in Operations Research and Machine Learning arising in many applications such as data compression, latent semantic indexing, collaborative filtering and medical imaging. We introduce a novel formulation for SLR that directly models the underlying discreteness of the problem. For this formulation, we develop an alternating minimization heuristic to compute high quality solutions and a novel semidefinite relaxation that provides meaningful bounds for the solutions returned by our heuristic. We further develop a custom branch and bound routine that leverages our heuristic and convex relaxation that solves small instances of SLR to certifiable near-optimality. Our heuristic can scale to $n=10000$ in hours, our relaxation can scale to $n=200$ in hours, and our branch and bound algorithm can scale to $n=25$ in minutes. Our numerical results demonstrate that our approach outperforms existing state-of-the-art approaches in terms of the MSE of the low rank matrix and that of the sparse matrix.
• Abstract（参考訳）: SLR(Sparse Plus Low Rank decomposition problem)は、破損したデータ行列 $\mathbf{D}$ を摂動と低階行列 $\mathbf{X}$ を含むスパース行列 $\mathbf{Y}$ に分解する問題である。 SLRは、データ圧縮、潜時セマンティックインデックス、協調フィルタリング、医用画像など、多くのアプリケーションで発生するオペレーションリサーチと機械学習の基本的な問題である。 問題の基本となる離散性を直接モデル化する新しいSLRの定式化を導入する。 この定式化のために、高品質な解を計算するための交互最小化ヒューリスティックと、ヒューリスティックによって返される解に有意義な境界を与える新しい半定緩和を開発する。 我々はさらに、SLRの小さなインスタンスを証明可能な準最適に解決する、ヒューリスティックかつ凸緩和を利用するカスタムブランチとバウンドルーチンを開発する。 私たちのヒューリスティックは時間で$n=10000$に、リラクゼーションは時間で$n=200$に、ブランチとバウンドアルゴリズムは分で$n=25$にスケールできます。 その結果, この手法は, 低階行列のmseとスパース行列のmseの点で, 既存の最先端手法よりも優れていることがわかった。

関連論文リスト

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

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

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