Randomised SVD and matrix sketching: Definition & Examples

Randomised SVD approximates the leading singular components of a matrix by first finding a small subspace with random probes, then factorising the matrix compressed to that subspace. Matrix sketching is the broader idea of replacing a large matrix with a smaller representation designed to preserve information needed for a particular task.

For a quant compressing a large return panel into statistical factors, this can reduce the work needed to obtain a low-rank representation. The approximation error becomes an additional modelling input: a fast factorisation can still discard a direction that matters to a portfolio.

Find a range, then compute an SVD

Let $A$ be a real $m\times n$ matrix and $k$ the desired rank. Choose a sketch width $\ell\ge k$ , draw a random test matrix $\Omega\in\mathbb{R}^{n\times\ell}$ and form

Y=A\Omega,\qquad Q=\operatorname{orth}(Y),\qquad B=Q^\top A.

Here

Q

has orthonormal columns spanning the sampled range, with dependent columns removed if necessary. This is range finding. Its candidate approximation is the orthogonal projection

QQ^\top A

Next take the singular value decomposition of the smaller matrix $B$ . If $B_k=\widetilde U_k\Sigma_kV_k^\top$ retains its leading $k$ components, return

\widehat A_k=QB_k=(Q\widetilde U_k)\Sigma_kV_k^\top.

These are separate steps: random sampling chooses a subspace; deterministic SVD and truncation choose components inside it. A precise SVD of

B

cannot recover directions absent from

Q

. This two-stage construction is described in Halko, Martinsson and Tropp, §§4.1 and 5.1.

A legitimate draw with a visible error

Use the fictional, dimensionless matrix $A=\operatorname{diag}(5,2,1)$ , with $k=\ell=1$ . Suppose the independent Rademacher entries of the sketch—each equally likely to be $+1$ or $-1$ —realise as

\omega=\begin{pmatrix}1\\1\\1\end{pmatrix},\qquad Y=A\omega=\begin{pmatrix}5\\2\\1\end{pmatrix},\qquad Q=\frac{1}{\sqrt{30}}\begin{pmatrix}5\\2\\1\end{pmatrix}.

The range is a single line. Since $B$ already has one row, its rank-one SVD adds no further truncation error. The squared Frobenius norm of the residual is

\begin{aligned} \lVert A-QQ^\top A\rVert_F^2 &=\lVert A\rVert_F^2-\lVert Q^\top A\rVert_F^2\\ &=30-\frac{625+16+1}{30}=8.6. \end{aligned}

Thus the error is $\sqrt{8.6}\approx2.9326$ . By comparison, the best rank-one approximation keeps the singular value $5$ and discards $2$ and $1$ , giving error $\sqrt{2^2+1^2}=\sqrt5\approx2.2361$ . The sampled line mixes all three coordinate directions rather than retaining only the strongest one.

One power step instead samples the direction

AA^\top A\omega=\begin{pmatrix}125\\8\\1\end{pmatrix},\qquad Q_1=\frac{1}{\sqrt{15690}}\begin{pmatrix}125\\8\\1\end{pmatrix}.

Projecting the original

A

onto this new line gives

\lVert A-Q_1Q_1^\top A\rVert_F =\sqrt{30-\frac{390882}{15690}}\approx2.2555.

The direction is closer to the first coordinate axis and the error is closer to the optimum. This is one valid realised random draw, not evidence for a general success probability.

For a fictional dimensionless matrix with diagonal 5, 2 and 1, the rank-one Frobenius errors are 2.9326 for the realised one-column sketch, 2.2555 after one power step and 2.2361 for the optimal truncated SVD.

A fixed realised Rademacher sketch illustrates the mechanics. One power step improves this example, but the bars are observed errors, not a probability guarantee.

Three controls with different jobs

Oversampling uses

\ell=k+p

probes, with

p>0

, before truncating to rank

k

. It gives range finding extra room; it does not change the requested final rank.

Power iteration uses

Y=(AA^\top)^qA\Omega

. It amplifies the separation between large and small singular values, at the cost of additional applications of

A

and

A^\top

. For numerical stability, alternate these multiplications with orthonormalisation; explicitly forming matrix powers can lose weaker directions through rounding. The scikit-learn parameter documentation distinguishes oversampling, iteration count and stepwise normalisation; Halko, Martinsson and Tropp, Algorithm 4.4 gives the stable orthonormalised construction.

Error checking assesses the result actually obtained. The sketch distribution, width, spectrum and power steps affect theoretical bounds; a bound proved for Gaussian probes cannot simply be assigned to this one-column Rademacher example. Matrix sketching also covers tasks and constructions beyond this range finder. The basic formula for

B

revisits

A

; it is not automatically a single-pass streaming algorithm. See Martinsson and Tropp, §§11–12 and 15.

Check the final rank, not just the range

With $B=Q^\top A$ and orthonormal $Q$ , orthogonality gives the exact decomposition

\lVert A-QB_k\rVert_F^2 =\lVert A-QQ^\top A\rVert_F^2+\lVert B-B_k\rVert_F^2.

The first term measures what the range missed; the second measures what final truncation discarded. When $\ell>k$ , checking only the first can understate the delivered error.

For a manageable matrix, compute the final residual directly. For a large one, independent random probes can estimate its norm without constructing every residual entry; report the estimator's uncertainty and the norm being estimated (Martinsson and Tropp, §12.1). Reusing a probe that selected

Q

is misleading: in the example,

(I-QQ^\top)A\omega=0

by construction, even though the full residual is nonzero.

A small matrix residual also does not establish that an estimated return factor is stable out of sample. Centring, scaling, observation quality and the economic use of discarded directions remain separate decisions.

For the exact decomposition behind these checks, the SVD lesson develops the geometry and norm identity (membership required).

Sources

Halko, Martinsson and Tropp, Finding structure with randomness (2011), §§4.1, 4.3, 4.5 and 5.1: range finding, residual estimation, stable power iteration and compressed SVD.
Martinsson and Tropp, Randomized Numerical Linear Algebra: Foundations & Algorithms (2020; revised 2021), §§11, 12.1 and 15: sketches, independent error probes and single-view methods.
scikit-learn, randomized_svd documentation, parameter descriptions for oversampling, power iterations and normalisation (accessed 30 October 2026).

Find a range, then compute an SVD

A legitimate draw with a visible error

Three controls with different jobs

Check the final rank, not just the range

Sources

Related terms

Orthogonal projection