Randomized SVD and Sketching for Large Matrices

Computing the exact singular value decomposition (SVD) of a matrix with millions of rows and columns — a full universe-wide covariance matrix, or a huge panel of firm-level features across decades — can be prohibitively slow, especially when you only actually need its top few singular vectors (the handful of dominant directions that explain most of the structure). Randomized SVD sidesteps the expensive exact computation with a surprisingly effective shortcut: multiply the huge matrix by a small number of random vectors to compress it into a much smaller "sketch" that captures its dominant directions, and then run the exact, expensive decomposition only on that small sketch.

An analogy: summarizing a huge survey with a clever small sample

Suppose you have a million-row survey and want its dominant patterns of response — the handful of underlying "themes" that explain most of the variation across respondents. Instead of painstakingly analyzing every single respondent's full answer sheet, you could construct a modest number of cleverly randomized composite questions (each one a random blend of the original questions), collect everyone's answers to just those composite questions, and analyze that much smaller derived dataset instead. If the composite questions were built to capture the survey's dominant directions of variation — which random projections do, with high probability, as long as you use somewhat more composites than the number of true underlying themes — the small analysis recovers almost the same dominant themes as the exhaustive one would have, at a tiny fraction of the effort.

The algorithm, one symbol at a time

For a large matrix $A$ ($m \times n$) whose top $k$ singular vectors you want, choose a target sketch size $\ell$ slightly larger than $k$ (say $\ell = k+10$). Draw a random matrix $\Omega$ of size $n \times \ell$ with independent entries (e.g., standard normal), and compute

$$Y = A\Omega,$$

an $m \times \ell$ matrix — a random linear compression of $A$'s columns down to just $\ell$ of them. In plain English: multiply the big matrix by a small random matrix, producing a much narrower matrix $Y$ that, with high probability, still spans nearly the same dominant column space as $A$ itself, because a random projection is very unlikely to "miss" a genuinely dominant direction. Compute an orthonormal basis $Q$ for $Y$'s column space (via a cheap QR decomposition), form the small matrix $B = Q^\top A$ (size $\ell \times n$, much smaller than $A$), and run the exact SVD on $B$ instead of $A$. In plain English: once you've captured the dominant directions in a small basis $Q$, you only need the exact, expensive decomposition on the small compressed matrix $B$, and can translate its results back into approximate singular vectors of the original huge $A$.

Worked example 1: dramatic size reduction

A firm-characteristics panel is a $50{,}000 \times 50{,}000$ covariance-like matrix, and only the top 20 principal directions are needed for a risk model. Exact SVD on a matrix this size can require on the order of tens of minutes to hours depending on hardware, since standard SVD algorithms scale roughly cubically with matrix dimension in the worst case. Randomized SVD with $\ell = 30$ (just 10 more than the needed 20) shrinks the working matrix to $50{,}000 \times 30$ before the expensive exact step, cutting the expensive computation down to operate on a matrix 1,667 times narrower — typically finishing in seconds to a couple of minutes, with the recovered top 20 singular values and vectors accurate to within a small, well-quantified approximation error.

Worked example 2: accuracy versus oversampling

Testing randomized SVD on a matrix with a known top-10 signal buried in noise: using an oversampling of $\ell=10$ (no buffer beyond the target rank) recovers the top singular values with roughly 8% relative error on average across trials — usable but noticeably imprecise. Increasing oversampling to $\ell=20$ (a buffer of 10 beyond the target rank of 10) cuts the average relative error to about 1.5%, at only double the sketch size and still far cheaper than the exact computation. This illustrates the practical rule of thumb: a modest oversampling buffer (adding roughly 5–10 extra random directions beyond the number you actually need) dramatically improves accuracy at negligible extra cost, because it protects against the rare random draw that under-captures a borderline dominant direction.

What this means in practice

Randomized SVD is used whenever principal components, factor extraction, or low-rank approximations are needed on genuinely large matrices — a full-universe covariance matrix, a large panel of engineered features, or an image or tensor-based dataset — where exact SVD is too slow or memory-intensive to run directly. It's a standard tool in production quant pipelines processing large factor libraries, and its accuracy guarantees are well understood, making the tradeoff (small approximation error for large computational savings) a controllable, quantifiable choice rather than a blind shortcut.