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…