randomized SVD

When a matrix is enormous — millions of rows and columns — computing the full SVD is hopeless, and you usually only want the top k singular triples anyway. Randomized SVD is a beautifully simple shortcut: instead of probing every direction, throw a handful of random vectors at the matrix and let them reveal where the action is. With high probability they land mostly in the dominant subspace.

The recipe has two stages. Stage one (find the range): draw a random n-by-(k+p) Gaussian matrix Omega (with p a small oversampling pad, say 5 to 10), form Y = A Omega, and orthonormalize Y with QR to get an m-by-(k+p) matrix Q whose columns approximately span the top left-singular subspace of A. Stage two (solve the small problem): form the small matrix B = Q^T A, take its exact SVD B = U_tilde Sigma V^T, and set U = Q U_tilde. The result U Sigma V^T approximates the truncated SVD of A.

The win is cost. The heavy SVD is done only on the tiny (k+p)-by-n matrix B, never on the full A; A itself is touched only through a couple of matrix multiplications, which are fast and parallelize beautifully. For a matrix with a rapidly decaying singular spectrum, this delivers the top-k factors in a fraction of the time of a classical SVD.

The accuracy is provably good. The expected error is close to the optimal Eckart-Young bound sigma_{k+1}, and oversampling plus an optional power iteration (replacing Y = A Omega with Y = (A A^T)^q A Omega to sharpen the spectral gap) tightens it further. Randomized SVD is the standard engine behind large-scale PCA, recommender systems, and modern data-science pipelines.