論文の概要: On the Noise Sensitivity of the Randomized SVD
- arxiv url: http://arxiv.org/abs/2305.17435v1
- Date: Sat, 27 May 2023 10:15:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 19:14:52.414559
- Title: On the Noise Sensitivity of the Randomized SVD
- Title（参考訳）: ランダム化SVDの雑音感度について
- Authors: Elad Romanov
- Abstract要約: ランダム化特異値分解(R-SVD)は、大きな行列の部分的なSVDを効率的に計算するためのスケッチベースアルゴリズムである。
我々はR-SVDを低ランク信号と雑音測定モデルで解析する。
R-SVDによって生成される特異値は、BBPのような相転移を示す。
- 参考スコア（独自算出の注目度）: 8.98526174345299
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The randomized singular value decomposition (R-SVD) is a popular
sketching-based algorithm for efficiently computing the partial SVD of a large
matrix. When the matrix is low-rank, the R-SVD produces its partial SVD
exactly; but when the rank is large, it only yields an approximation.
Motivated by applications in data science and principal component analysis
(PCA), we analyze the R-SVD under a low-rank signal plus noise measurement
model; specifically, when its input is a spiked random matrix. The singular
values produced by the R-SVD are shown to exhibit a BBP-like phase transition:
when the SNR exceeds a certain detectability threshold, that depends on the
dimension reduction factor, the largest singular value is an outlier; below the
threshold, no outlier emerges from the bulk of singular values. We further
compute asymptotic formulas for the overlap between the ground truth signal
singular vectors and the approximations produced by the R-SVD.
Dimensionality reduction has the adverse affect of amplifying the noise in a
highly nonlinear manner. Our results demonstrate the statistical advantage --
in both signal detection and estimation -- of the R-SVD over more naive
sketched PCA variants; the advantage is especially dramatic when the sketching
dimension is small. Our analysis is asymptotically exact, and substantially
more fine-grained than existing operator-norm error bounds for the R-SVD, which
largely fail to give meaningful error estimates in the moderate SNR regime. It
applies for a broad family of sketching matrices previously considered in the
literature, including Gaussian i.i.d. sketches, random projections, and the
sub-sampled Hadamard transform, among others.
Lastly, we derive an optimal singular value shrinker for singular values and
vectors obtained through the R-SVD, which may be useful for applications in
matrix denoising.
- Abstract（参考訳）: ランダム化特異値分解(R-SVD)は、大きな行列の部分的なSVDを効率的に計算するためのスケッチベースアルゴリズムである。
行列が低ランクの場合、R-SVDはその部分SVDを正確に生成するが、ランクが大きいと近似しか得られない。
データサイエンスと主成分分析(PCA)の応用により、低ランク信号と雑音測定モデルの下でR-SVDを解析する。
R-SVD が生成した特異値は BBP のような相転移を示すことが示され、SNR が特定の検出可能性閾値を超えると、寸法減少係数に依存する最大の特異値は外れ値となる。
さらに、基底真理信号特異ベクトルとR-SVDによる近似との重なり合いに関する漸近公式を計算する。
次元の減少は、ノイズを非常に非線形に増幅する悪影響がある。
以上の結果から,R-SVDの信号検出と推定の両面での統計的優位性を示すとともに,スケッチ寸法が小さい場合には特に顕著である。
我々の分析は漸近的に正確であり、R-SVDの既存の作用素-ノルム誤差境界よりもかなり微細である。
これは、ガウスのi.d.スケッチ、ランダム・プロジェクション、サブサンプラート・アダマール変換など、以前に文献で考えられていたスケッチ行列の幅広いファミリーに適用される。
最後に、r-svd によって得られる特異値とベクトルに対する最適特異値縮小器を導出し、行列の除算への応用に有用である。
関連論文リスト
- Robust SVD Made Easy: A fast and reliable algorithm for large-scale data
analysis [0.0]
既存のロバストなSVDアルゴリズムは、ロバスト性のために速度を犠牲にしたり、わずかに外れ値が存在する場合に失敗することが多い。
本研究では,Spherally Normalized SVDというアルゴリズムを導入し,ロバストなSVD近似手法を提案する。
提案アルゴリズムは, 標準低ランクSVDアルゴリズムの2つの応用しか利用せず, 顕著な高速化を実現している。
論文 参考訳（メタデータ） (2024-02-15T07:08:11Z) - A Random Matrix Approach to Low-Multilinear-Rank Tensor Approximation [24.558241146742205]
本研究では,データテンソルの展開のスペクトルの多次元的挙動を特徴付け,信号の主方向の検出性を決定する関連信号-雑音比を示す。
その結果,非自明な状態下でのマルチリニアSVD (MLSVD) の再構成性能を正確に予測することができた。
論文 参考訳（メタデータ） (2024-02-05T16:38:30Z) - Risk Bounds of Accelerated SGD for Overparameterized Linear Regression [75.27846230182885]
加速度勾配降下(ASGD)は、深層学習におけるワークホースである。
既存の最適化理論は、ASGDのより高速な収束を説明することしかできないが、より優れた一般化を説明することはできない。
論文 参考訳（メタデータ） (2023-11-23T23:02:10Z) - Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled
Gradient Descent, Even with Overparameterization [48.65416821017865]
この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。
低ランク物体の条件数に依存しない定数速度で直線的に収束する。
様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
論文 参考訳（メタデータ） (2023-10-09T21:16:57Z) - Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood
Estimation for Latent Gaussian Models [69.22568644711113]
我々は,モンテカルロサンプリングと反復線形解法を組み合わせた確率的アンローリングを導入し,行列逆転を回避した。
理論的解析により,解法の繰り返しによる解法の解法と逆転が最大値推定の勾配推定を高速化することを示した。
シミュレーションおよび実データ実験において、確率的アンロールは、モデル性能の損失を最小限に抑えながら、勾配EMよりも桁違いに高速な潜在ガウスモデルを学習することを示した。
論文 参考訳（メタデータ） (2023-06-05T21:08:34Z) - On the Size and Approximation Error of Distilled Sets [57.61696480305911]
カーネル・インジェクション・ポイント(Kernel Inducing Points)などのデータセット蒸留のカーネル・リッジ回帰に基づく手法について理論的に考察する。
我々は、RFF空間におけるその解が元のデータの解と一致するように、元の入力空間に小さな一組のインスタンスが存在することを証明した。
KRR溶液は、全入力データに最適化されたKRR溶液に対して近似を与えるこの蒸留されたインスタンスセットを用いて生成することができる。
論文 参考訳（メタデータ） (2023-05-23T14:37:43Z) - Noise-cleaning the precision matrix of fMRI time series [2.6399022396257794]
いくつかの標準ノイズクリーニングアルゴリズムを考察し、2種類のデータセットと比較する。
各アルゴリズムの信頼性は、テストセット確率と、合成データの場合、真の精度行列からの距離で評価される。
パラメータの1つをクロスバリデーションにより最適化する最適回転不変量推定器の変種を提案する。
論文 参考訳（メタデータ） (2023-02-06T17:32:17Z) - Robust Singular Values based on L1-norm PCA [11.706222361809374]
Singular-Value Decomposition (SVD) は、工学、科学、統計学におけるユビキタスなデータ解析手法である。
本稿では,L1-ノルム(絶対値の仮定)の定式化に基づくSVDと特異値推定のための新しいロバストな非パラメトリック手法を提案する。
論文 参考訳（メタデータ） (2022-10-21T16:42:49Z) - Implicit Regularization Properties of Variance Reduced Stochastic Mirror
Descent [7.00422423634143]
離散VRSMD推定器列は線形回帰において最小ミラー補間子に収束することを示す。
我々は、真のモデルがスパースである場合に設定したモデル推定精度を導出する。
論文 参考訳（メタデータ） (2022-04-29T19:37:24Z) - Robust Differentiable SVD [117.35644933471401]
対称行列の固有分解は多くのコンピュータビジョンアルゴリズムの中心にある。
不安定性は互いに近い固有値の存在によって生じる。
SVD勾配のテイラー展開は、反復過程に依存することなくPIを用いて得られる勾配と理論的に等価であることを示す。
論文 参考訳（メタデータ） (2021-04-08T15:04:15Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳（メタデータ） (2021-03-23T17:15:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。