Perturbation Analysis of Randomized SVD and its Applications to Statistics

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 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)^g G; here g 1 is an integer and G R^n k is a random Gaussian sketching matrix with k k. In this paper we derive upper bounds for the _2 and _2, distances between the exact left singular vectors U of M and its approximation U_g (obtained via RSVD), as well as entrywise error bounds when M is projected onto U_g U_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 _2 and _2, 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.

Tasks

Reproductions