論文の概要: Perturbation Analysis of Randomized SVD and its Applications to Statistics
- arxiv url: http://arxiv.org/abs/2203.10262v3
- Date: Sun, 25 May 2025 18:22:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-28 14:37:17.975609
- Title: Perturbation Analysis of Randomized SVD and its Applications to Statistics
- Title（参考訳）: ランダム化SVDの摂動解析と統計学への応用
- Authors: Yichi Zhang, Minh Tang,
- Abstract要約: RSVD(英: RSVD)は、大規模データ行列の切り詰められたSVDを計算するための計算効率のよいアルゴリズムのクラスである。
本稿では、$ell$ と $ell_2,infty$ の正則特異ベクトル $widehatmathbfU$ と $widehatmathbfM$ の上限を導出する。
理論結果を、$widehatmathbfM$ が観測されていない信号行列 $mathbfM$ の加法摂動であるような設定に適用する。
- 参考スコア（独自算出の注目度）: 8.731676546744353
- 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 an $m \times n$ matrix $\widehat{{\mathbf M}}$, the prototypical RSVD algorithm outputs an approximation of the $k$ leading left singular vectors of $\widehat{\mathbf{M}}$ by computing the SVD of $\widehat{\mathbf{M}} (\widehat{{\mathbf M}}^{\top} \widehat{\mathbf{M}})^{g} \mathbf G$; here $g \geq 1$ is an integer and $\mathbf G \in \mathbb{R}^{n \times \widetilde{k}}$ is a random Gaussian sketching matrix with $\widetilde{k} \geq k$. In this paper we derive upper bounds for the $\ell_2$ and $\ell_{2,\infty}$ distances between the exact left singular vectors $\widehat{\mathbf{U}}$ of $\widehat{\mathbf{M}}$ and its approximation $\widehat{\mathbf{U}}_g$ (obtained via RSVD), as well as entrywise error bounds when $\widehat{\mathbf{M}}$ is projected onto $\widehat{\mathbf{U}}_g \widehat{\mathbf{U}}_g^{\top}$. These bounds depend on the singular values gap and number of power iterations $g$, and smaller gap requires larger values of $g$ to guarantee the convergences of the $\ell_2$ and $\ell_{2,\infty}$ distances. We apply our theoretical results to settings where $\widehat{\mathbf{M}}$ is an additive perturbation of some unobserved signal matrix $\mathbf{M}$. In particular, we obtain the nearly-optimal convergence rate and asymptotic normality for RSVD on three inference problems, namely, subspace estimation and community detection in random graphs, noisy matrix completion, and PCA with missing data.
- Abstract（参考訳）: ランダム化特異値分解(英: Randomized singular value decomposition、RSVD)は、大規模データ行列の切り詰められたSVDを計算するための計算効率のよいアルゴリズムのクラスである。
m \times n$ matrix $\widehat{{\mathbf M}}$を与えられたとき、プロトプレマルなRSVDアルゴリズムは$k$の左特異ベクトルを$\widehat{\mathbf{M}}$の算術演算により出力し、$\widehat{\mathbf{M}} (\widehat{{\mathbf M}}^{\top} \widehat{\mathbf{M}})^{g} \mathbf G$; $g \geq 1$は整数、$\mathbf G \in \mathbb{R}^{n \times \widetilde{k}}$は$\widehat{\mathbf{M}} のランダムなガウススケッチ行列である。
本稿では、$\ell_2$ と $\ell_{2,\infty}$ の正確な左特異ベクトル $\widehat{\mathbf{U}}$ と $\widehat{\mathbf{M}}$ の近似 $\widehat{\mathbf{U}}_g$ と、$\widehat{\mathbf{M}}$ が $\widehat{\mathbf{U}}_g \widehat{\mathbf{U}}_g^{\top}$ の入射誤差境界を導出する。
これらの境界は特異値ギャップとパワー反復数$g$に依存し、小さなギャップは$\ell_2$と$\ell_{2,\infty}$距離の収束を保証するために$g$のより大きな値を必要とする。
理論的結果を適用すると、$\widehat{\mathbf{M}}$ は観測されていない信号行列 $\mathbf{M}$ の加法摂動である。
特に、乱数グラフにおける部分空間推定とコミュニティ検出、ノイズ行列補完、欠落データを含むPCAの3つの推論問題に基づいて、RSVDのほぼ最適収束率と漸近正規性を求める。
関連論文リスト
- Bivariate Matrix-valued Linear Regression (BMLR): Finite-sample performance under Identifiability and Sparsity Assumptions [0.0]
行列値線形回帰モデルでは, mathbbRn×p$の$T$応答$(Y_t)_t=1Tと, mathbbRm×q$の予測子$(X_t)_t=1Tを推定する。
最適化のない明示的な推定器を提案し、その性能を定量化するために非漸近収束率を確立する。
論文 参考訳（メタデータ） (2024-12-23T18:03:34Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。