|
Abstract:
|
Randomized singular value decomposition (RSVD) is a class of computationally efficient randomized algorithms for computing the truncated SVD of large data matrices. In this paper, we study the statistical properties of RSVD under a general ``signal-plus-noise'' framework. We first derive upper bounds for the two-norm and two-to-infinity distance between the approximate singular vectors of the observed matrix by RSVD, and the true singular vectors of the signal matrix. A phase transition phenomenon is observed in which the perturbation error decreases as the number of power iterations used by the RSVD increases. We then show that the thresholds at which the phase transition occurs are sharp whenever the trace of the noise matrices satisfy a certain growth condition. We illustrate our theoretical results by deriving nearly-optimal performance guarantees for RSVD when applied to three statistical inference problems, namely, community detection, matrix completion, and principal component analysis with missing data.
|
