論文の概要: 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乗誤差の点で優れていることがわかった。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。