  The randomized singular value decomposition (R-SVD) is a popular
sketching-based algorithm for efficiently computing the partial SVD of a large
matrix. When the matrix is low-rank, the R-SVD produces its partial SVD
exactly; but when the rank is large, it only yields an approximation.
  Motivated by applications in data science and principal component analysis
(PCA), we analyze the R-SVD under a low-rank signal plus noise measurement
model; specifically, when its input is a spiked random matrix. The singular
values produced by the R-SVD are shown to exhibit a BBP-like phase transition:
when the SNR exceeds a certain detectability threshold, that depends on the
dimension reduction factor, the largest singular value is an outlier; below the
threshold, no outlier emerges from the bulk of singular values. We further
compute asymptotic formulas for the overlap between the ground truth signal
singular vectors and the approximations produced by the R-SVD.
  Dimensionality reduction has the adverse affect of amplifying the noise in a
highly nonlinear manner. Our results demonstrate the statistical advantage --
in both signal detection and estimation -- of the R-SVD over more naive
sketched PCA variants; the advantage is especially dramatic when the sketching
dimension is small. Our analysis is asymptotically exact, and substantially
more fine-grained than existing operator-norm error bounds for the R-SVD, which
largely fail to give meaningful error estimates in the moderate SNR regime. It
applies for a broad family of sketching matrices previously considered in the
literature, including Gaussian i.i.d. sketches, random projections, and the
sub-sampled Hadamard transform, among others.
  Lastly, we derive an optimal singular value shrinker for singular values and
vectors obtained through the R-SVD, which may be useful for applications in
matrix denoising.
