# Perturbation Analysis of Randomized SVD and its Applications to Statistics

arXiv: https://arxiv.org/abs/2203.10262 · HTML: https://mlsanity.com/paper/2203.10262/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2022.

## Built on by (most cited first, 3 of 3)

- [Elliptic PDE learning is provably data-efficient](https://mlsanity.com/paper/2302.12888/) (2023)
- [On the Noise Sensitivity of the Randomized SVD](https://mlsanity.com/paper/2305.17435/) (2023)
- [Inference in Randomized Least Squares and PCA via Normality of Quadratic Forms](https://mlsanity.com/paper/2404.00912/) (2024)

## Abstract (arXiv)

Randomized singular value decomposition (RSVD) is a class of computationally efficient algorithms for computing the truncated SVD of large data matrices. Given an m × n matrix widehatmathbf M, the prototypical RSVD algorithm outputs an approximation of the k leading left singular vectors of widehatM by computing the SVD of widehatM (widehatmathbf Mtop widehatM)g mathbf G; here g ≥ 1 is an integer and mathbf G ∈ ℝ^n × widetildek is a random Gaussian sketching matrix with widetildek ≥ k. In this paper we derive upper bounds for the ℓ2 and ℓ2,∞ distances between the exact left singular vectors widehatU of widehatM and its approximation widehatUg (obtained via RSVD), as well as entrywise error bounds when widehatM is projected onto widehatUg widehatUgtop. 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 ℓ2 and ℓ2,∞ distances. We apply our theoretical results to settings where widehatM is an additive perturbation of some unobserved signal matrix 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.