論文の概要: Perturbation Analysis of Randomized SVD and its Applications to
High-dimensional Statistics
- arxiv url: http://arxiv.org/abs/2203.10262v1
- Date: Sat, 19 Mar 2022 07:26:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-22 19:28:03.570284
- Title: Perturbation Analysis of Randomized SVD and its Applications to
High-dimensional Statistics
- Title（参考訳）: ランダム化svdの摂動解析と高次元統計への応用
- Authors: Yichi Zhang and Minh Tang
- Abstract要約: 一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。
3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
- 参考スコア（独自算出の注目度）: 8.90202564665576
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Randomized singular value decomposition (RSVD) is a class of computationally
efficient algorithms for computing the truncated SVD of large data matrices.
Given a $n \times n$ symmetric matrix $\mathbf{M}$, the prototypical RSVD
algorithm outputs an approximation of the $k$ leading singular vectors of
$\mathbf{M}$ by computing the SVD of $\mathbf{M}^{g} \mathbf{G}$; here $g \geq
1$ is an integer and $\mathbf{G} \in \mathbb{R}^{n \times k}$ is a random
Gaussian sketching matrix. In this paper we study the statistical properties of
RSVD under a general "signal-plus-noise" framework, i.e., the observed matrix
$\hat{\mathbf{M}}$ is assumed to be an additive perturbation of some true but
unknown signal matrix $\mathbf{M}$. We first derive upper bounds for the
$\ell_2$ (spectral norm) and $\ell_{2\to\infty}$ (maximum row-wise $\ell_2$
norm) distances between the approximate singular vectors of $\hat{\mathbf{M}}$
and the true singular vectors of the signal matrix $\mathbf{M}$. These upper
bounds depend on the signal-to-noise ratio (SNR) and the number of power
iterations $g$. A phase transition phenomenon is observed in which a smaller
SNR requires larger values of $g$ to guarantee convergence of the $\ell_2$ and
$\ell_{2\to\infty}$ distances. We also show that the thresholds for $g$ where
these phase transitions occur are sharp whenever the noise matrices satisfy a
certain trace growth condition. Finally, we derive normal approximations for
the row-wise fluctuations of the approximate singular vectors and the entrywise
fluctuations of the approximate matrix. We illustrate our theoretical results
by deriving nearly-optimal performance guarantees for RSVD when applied to
three statistical inference problems, namely, community detection, matrix
completion, and principal component analysis with missing data.
- Abstract（参考訳）: ランダム化特異値分解(英: Randomized singular value decomposition、RSVD)は、大規模データ行列の切り詰められたSVDを計算するための計算効率のよいアルゴリズムである。
n \times n$ 対称行列 $\mathbf{m}$ が与えられると、原型的なrsvdアルゴリズムは、$\mathbf{m}^{g} \mathbf{g}$; ここで$g \geq 1$ は整数で$\mathbf{g} \in \mathbb{r}^{n \times k}$ はランダムガウスのスケッチ行列である。
本稿では、一般の「信号+ノイズ」の枠組みの下でRSVDの統計的性質を研究する。すなわち、観測行列 $\hat{\mathbf{M}}$ は、真だが未知の信号行列 $\mathbf{M}$ の加法摂動であると仮定する。
まず、$\ell_2$(スペクトルノルム)と$\ell_{2\to\infty}$(最大行幅$\ell_2$ノルム)距離について、$\hat{\mathbf{M}}$の近似特異ベクトルと信号行列$\mathbf{M}$の真の特異ベクトルの間の上限を導出する。
これらの上限はsnr(signal-to-noise ratio)と電力反復数(power iteration)に依存する。
位相遷移現象は、より小さな SNR が $\ell_2$ と $\ell_{2\to\infty}$ 距離の収束を保証するために$g$ のより大きな値を必要とするのが観察される。
また、ノイズ行列が特定のトレース成長条件を満たすと、これらの相転移が発生する$g$のしきい値がシャープであることを示す。
最後に、近似特異ベクトルの行方向のゆらぎと近似行列のエントリ方向のゆらぎに対する正規近似を導出する。
本研究では,3つの統計的推論問題,すなわちコミュニティ検出,マトリクス補完,欠落データを用いた主成分分析に適用し,rsvdの最適性能保証を導出して理論的結果を示す。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - 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) - On the computational and statistical complexity of over-parameterized
matrix sensing [30.785670369640872]
FGD法(Factorized Gradient Descend)を用いた低ランク行列検出の解法を検討する。
分解行列 $mathbff$ を分離列空間に分解することにより、$|mathbff_t - mathbff_t - mathbfx*|_f2$ が統計誤差に収束することを示す。
論文 参考訳（メタデータ） (2021-01-27T04:23:49Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Phase retrieval in high dimensions: Statistical and computational phase
transitions [27.437775143419987]
我々は$mathbfXstar$を$m$(おそらくノイズの多い)観測から再構成する問題を考察する。
特に、フルランク行列に対する情報理論上の完全回復への遷移は、$alpha=1$と$alpha=2$である。
我々の研究は、高次元位相探索における統計的およびアルゴリズム的しきい値の広範な分類を提供する。
論文 参考訳（メタデータ） (2020-06-09T13:03:29Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。