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 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.

摘要来源：OpenAlex 索引摘要（稿件版本未注明）