Perturbation Analysis of Randomized SVD and its Applications to Statistics

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.