論文の概要: 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の点で, 既存の最先端手法よりも優れていることがわかった。
関連論文リスト
- 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) - Compressed Sensing: A Discrete Optimization Approach [6.943816076962257]
圧縮センシング(CS)問題(Compressed Sensing, CS)は、線形測定の集合をある程度の数値耐性まで満たす最もスパースなベクトルを見つける問題である。
CSは、信号処理、データ圧縮、画像再構成などのアプリケーションで発生する統計学、オペレーションリサーチ、機械学習において中心的な問題である。
論文 参考訳(メタデータ) (2023-06-05T01:29:24Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - Dictionary-based Low-Rank Approximations and the Mixed Sparse Coding
problem [7.132368785057316]
本稿では、LASSOに基づく効率的なMSC解法を用いて、辞書に基づく行列分解と正準多進分解を計算する方法を示す。
超スペクトル画像処理と化学計測の文脈における辞書に基づく行列分解と正準多進分解の計算に、LASSOに基づく効率的なMSC解法を適用する方法を示す。
論文 参考訳(メタデータ) (2021-11-24T10:32:48Z) - 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) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-09-30T19:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。