Randomized range finding and sketching

For a real m-by-n matrix A, choose a test matrix Ω with n rows and ℓ columns and form Y=AΩ. An orthonormal basis Q for the sampled range gives the approximation QQᵀA. The small matrix B=QᵀA can then be factored deterministically; for example an SVD of B lifts to an approximate SVD of A by multiplying its left singular vectors by Q. The multiplication QᵀA is a separate operation and may require another pass over data. A range sample alone does not magically contain every later compressed quantity.

Using ℓ=k+p columns for target rank k supplies p oversampling directions. Independent standard Gaussian entries give rotational invariance, which helps control how the probes intersect the dominant right-singular subspace. For an exactly rank-r matrix and at least r Gaussian columns, the sampled range equals the true range with probability one in exact arithmetic. This is not an absolute every-input-probe guarantee: special deterministic probes can miss it, and floating-point rank decisions can lose weak directions. For approximately low-rank matrices, tail singular values govern the achievable residual.

A useful Gaussian theorem bounds the expected Frobenius residual of the range projection by a factor times the optimal rank-k Frobenius tail. Its assumptions include a fixed real matrix, target rank at least two, oversampling at least two, and enough ambient dimensions for all probe columns. The expectation is over the independent Gaussian probes. The projection can have rank as large as k+p, so this statement is not an error guarantee for every subsequently truncated rank-k output. Additional compression or truncation needs its own analysis.

Expectation and high-probability statements answer different questions. An expected error bound permits individual draws with larger error, whereas a tail bound quantifies how likely a specified excess is. Neither is automatically a measured certificate for one run. Independent test probes can provide probabilistic residual checks if their own assumptions are respected; reusing only the training probes can miss directions that the original sample failed to capture. A fully computed residual norm is stronger direct evidence but may defeat the intended storage or pass budget.

For a nonnegative integer q, a powered sample uses (AAᵀ) to the power q times AΩ. In exact singular coordinates this raises gains to the power 2q+1, increasing the separation between dominant and weak directions. Forming raw matrix powers is unnecessary and unsafe. Alternate matrix and transpose applications with intermediate orthonormalization to avoid losing weaker retained directions to rounding. Every application can require a data pass or substantial communication. More power iterations can improve approximation while making the procedure slower or impossible under a strict one-pass constraint.

Sketching is a broader idea than range finding. A left sketch can compress rows in a least-squares problem, but preserving all relevant residual norms requires an appropriate subspace-embedding guarantee, not merely a small sampled range error. Keep those tasks distinct. Record probe dimension, random seed for reproducibility, power count, orthogonalization strategy, and validation method. A reproducible seed does not prove accuracy, yet it makes a failure diagnosable. Compare total data movement and approximation quality against a deterministic alternative before claiming that randomization has improved the computation.