論文の概要: Unique sparse decomposition of low rank matrices
- arxiv url: http://arxiv.org/abs/2106.07736v1
- Date: Mon, 14 Jun 2021 20:05:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-16 14:53:17.085039
- Title: Unique sparse decomposition of low rank matrices
- Title（参考訳）: 低階行列の特異なスパース分解
- Authors: Dian Jin, Xin Bing and Yuqian Zhang
- Abstract要約: 低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。
我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
- 参考スコア（独自算出の注目度）: 17.037882881652617
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of finding the unique low dimensional decomposition of a given
matrix has been a fundamental and recurrent problem in many areas. In this
paper, we study the problem of seeking a unique decomposition of a low rank
matrix $Y\in \mathbb{R}^{p\times n}$ that admits a sparse representation.
Specifically, we consider $Y = A X\in \mathbb{R}^{p\times n}$ where the matrix
$A\in \mathbb{R}^{p\times r}$ has full column rank, with $r < \min\{n,p\}$, and
the matrix $X\in \mathbb{R}^{r\times n}$ is element-wise sparse. We prove that
this sparse decomposition of $Y$ can be uniquely identified, up to some
intrinsic signed permutation. Our approach relies on solving a nonconvex
optimization problem constrained over the unit sphere. Our geometric analysis
for the nonconvex optimization landscape shows that any {\em strict} local
solution is close to the ground truth solution, and can be recovered by a
simple data-driven initialization followed with any second order descent
algorithm. At last, we corroborate these theoretical results with numerical
experiments.
- Abstract（参考訳）: 与えられた行列の特異な低次元分解を見つける問題は、多くの領域において基礎的かつ再帰的な問題であった。
本稿では、疎表現を許容する低階行列 $Y\in \mathbb{R}^{p\times n}$ のユニークな分解を求める問題を考察する。
具体的には、$Y = A X\in \mathbb{R}^{p\times n}$ ここで、行列 $A\in \mathbb{R}^{p\times r}$ は $r < \min\{n,p\}$ の完全列ランクを持ち、行列 $X\in \mathbb{R}^{r\times n}$ は要素的にスパースである。
我々は、この$Y$のスパース分解が固有の符号付き置換まで一意に識別できることを証明した。
提案手法は,単位球面上の非凸最適化問題の解法に依存する。
非凸最適化ランドスケープの幾何学的解析は、任意の厳密な局所解が基底真理解に近づき、単純なデータ駆動初期化とそれに続く二階降下アルゴリズムによって復元可能であることを示している。
最終的に、これらの理論結果を数値実験で裏付ける。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。
本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
論文 参考訳（メタデータ） (2023-03-22T04:07:26Z) - Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。
シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
論文 参考訳（メタデータ） (2021-10-15T09:27:50Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳（メタデータ） (2021-06-27T17:25:24Z) - Local Search Algorithms for Rank-Constrained Convex Optimization [7.736462653684946]
階数制約付き凸最適化のための欲望と局所探索アルゴリズムを提案する。
我々は、$R$のランク制限条件番号が$kappa$であれば、$A$のランク$O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon、kappa2)$と$R(A)leq R(A*)+epsilon$のソリューションが回復できることを示しています。
論文 参考訳（メタデータ） (2021-01-15T18:52:02Z) - Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。
その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
論文 参考訳（メタデータ） (2020-07-18T15:36:11Z) - Optimal Exact Matrix Completion Under new Parametrization [0.0]
適応サンプリング法を用いて、$m倍 n$ の階数 $r$ の行列の正確な完備化の問題を研究した。
対象行列を正確に復元する行列補完アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-06T18:31:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。