論文の概要: Compressed sensing of low-rank plus sparse matrices
- arxiv url: http://arxiv.org/abs/2007.09457v2
- Date: Wed, 27 Apr 2022 12:55:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 06:11:31.840633
- Title: Compressed sensing of low-rank plus sparse matrices
- Title（参考訳）: 低ランク+スパース行列の圧縮センシング
- Authors: Jared Tanner and Simon Vary
- Abstract要約: この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。
その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
- 参考スコア（独自算出の注目度）: 3.8073142980733
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Expressing a matrix as the sum of a low-rank matrix plus a sparse matrix is a
flexible model capturing global and local features in data popularized as
Robust PCA (Candes et al., 2011; Chandrasekaran et al., 2009). Compressed
sensing, matrix completion, and their variants (Eldar and Kutyniok, 2012;
Foucart and Rauhut, 2013) have established that data satisfying low complexity
models can be efficiently measured and recovered from a number of measurements
proportional to the model complexity rather than the ambient dimension. This
manuscript develops similar guarantees showing that $m\times n$ matrices that
can be expressed as the sum of a rank-$r$ matrix and a $s$-sparse matrix can be
recovered by computationally tractable methods from
$\mathcal{O}(r(m+n-r)+s)\log(mn/s)$ linear measurements. More specifically, we
establish that the low-rank plus sparse matrix set is closed provided the
incoherence of the low-rank component is upper bounded as
$\mu<\sqrt{mn}/(r\sqrt{s})$, and subsequently, the restricted isometry
constants for the aforementioned matrices remain bounded independent of problem
size provided $p/mn$, $s/p$, and $r(m+n-r)/p$ remain fixed. Additionally, we
show that semidefinite programming and two hard threshold gradient descent
algorithms, NIHT and NAHT, converge to the measured matrix provided the
measurement operator's RIC's are sufficiently small. These results also
provably solve convex and non-convex formulation of Robust PCA with the
asymptotically optimal fraction of corruptions $\alpha=\mathcal{O}\left(1/(\mu
r) \right)$, where $s = \alpha^2 mn$, and improve the previously best known
guarantees by not requiring that the fraction of corruptions is spread in every
column and row by being upper bounded by $\alpha$. Numerical experiments
illustrating these results are shown for synthetic problems,
dynamic-foreground/static-background separation, and multispectral imaging.
- Abstract（参考訳）: 低ランクマトリクスとスパースマトリクスの和としてマトリクスを表現することは、ロバストなpca(candes et al., 2011; chandrasekaran et al., 2009)として普及したデータのグローバルおよびローカルな特徴を捉える柔軟なモデルである。
圧縮センシング、行列補完、およびそれらの変種 (Eldar and Kutyniok, 2012; Foucart and Rauhut, 2013) は、低複雑性モデルを満たすデータは、周囲次元よりもモデル複雑さに比例した多くの測定値から効率的に測定および回収できることを確立した。
この写本は、ランク-$r$マトリクスと$s$-スパースマトリクスの和として表現できる$m\times n$行列が$\mathcal{o}(r(m+n-r)+s)\log(mn/s)$の線形測定から計算的に扱いやすい方法で復元できることを示す同様の保証を発達させる。
より具体的には、低ランク+スパース行列集合が閉であることは、低ランク成分の不整合が$\mu<\sqrt{mn}/(r\sqrt{s})$として上界であることから証明し、従って、上記の行列の制限等長定数は、問題のサイズから独立して、$p/mn$, $s/p$, $r(m+n-r)/p$ が固定される。
さらに, 半定値プログラミングと2つのハードしきい値勾配勾配アルゴリズム, NIHT, NAHTは, 測定演算子のRCCが十分に小さい場合, 測定行列に収束することを示した。
これらの結果はまた、ロバストなpcaの凸および非凸な定式化と、汚職の漸近的に最適な分数である$\alpha=\mathcal{o}\left(1/(\mu r) \right)$、ここでは$s = \alpha^2 mn$ が成立し、汚損の分数を$\alpha$ で上界することで各列と行に分散させることを必要とせず、既知の保証を改善することも証明できる。
これらの結果を示す数値実験により, 合成問題, 動的フォアグラウンド/静的バックグラウンド分離, マルチスペクトルイメージングが得られた。
関連論文リスト
- One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - On the well-spread property and its relation to linear regression [4.619541348328937]
頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。
与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
論文 参考訳（メタデータ） (2022-06-16T11:17:44Z) - Computationally Efficient Approximations for Matrix-based Renyi's
Entropy [33.72108955447222]
最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。
そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。
我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
論文 参考訳（メタデータ） (2021-12-27T14:59:52Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Unique sparse decomposition of low rank matrices [17.037882881652617]
低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。
我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
論文 参考訳（メタデータ） (2021-06-14T20:05:59Z) - 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) - Robust Low-rank Matrix Completion via an Alternating Manifold Proximal
Gradient Continuation Method [47.80060761046752]
ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。
この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。
RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。
本稿では、近年のローワークの動機付けについて述べる。
論文 参考訳（メタデータ） (2020-08-18T04:46:22Z) - Information-Theoretic Limits for the Matrix Tensor Product [8.206394018475708]
本稿では,ランダム行列の行列テンソル積を含む高次元推論問題について検討する。
本稿では,高次元行列保存信号の解析のための新しい手法を紹介する。
論文 参考訳（メタデータ） (2020-05-22T17:03:48Z) - Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
我々は、原子核ノルム正規化行列補完に対する相対誤差を開発する。
未知行列の最適低ランク近似を回復するための相対上界を導出する。
論文 参考訳（メタデータ） (2015-04-26T13:12:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。