Perturbation Analysis of Randomized SVD and its Applications to Statistics

What the paper says

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 M̂, the prototypical RSVD algorithm outputs an approximation of the k leading left singular vectors of M̂ by computing the SVD of M̂(M̂⊤M̂)gG; here g≥1 is an integer and G∈Rn×k˜ is a random Gaussian sketching matrix with k˜≥k. In this paper we derive upper bounds for the l2 and l2,∞ distances between the exact left singular vectors Û of M̂ and its approximation Ûg (obtained via RSVD), as well as entrywise error bounds when M̂ is projected onto ÛgÛg⊤. 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 l2 and l2,∞ distances. We apply our theoretical results to settings where M̂ 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.