← All Cracked Math projects
PM-I04NOT STARTEDINTERMEDIATEMATHPYTHONIMPACT ★★☆☆☆

Randomized SVD: 95% of the answer at 5% of the cost

Sketch, orthonormalise, project: the Halko-Martinsson-Tropp (HMT) recipe for fast approximate SVD, raced against ARPACK.

EST.10 h
REWARD+300 XP
AFTERHalko

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
||A - QQ^T A||_2 / sigma_(k+1) (your approximation error divided by the best error any rank-k approximation can reach) and wall time at k = 100
GOAL · Error ratio <= 1.1 with q = 2 power iterations; >= 10x faster than full SVD; within 1.5x of sklearn's time
sklearn.utils.extmath.randomized_svd and scipy.sparse.linalg.svds (ARPACK) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

Randomized SVD finds the top k singular vectors of a big matrix by first multiplying it by a random matrix (a sketch), which cheaply captures its most important directions. Implement the HMT randomized range finder with oversampling (use a few more random vectors than k) and power iterations (multiply by A^T A a few times to sharpen the result). Also implement a single-pass variant (reads the matrix only once) and block Krylov (keeps every intermediate product, not just the last one). Use your I03 QR for orthonormalisation. np.linalg.svd is allowed only on the small k x k core. Apply it to a 20k x 10k sparse term-document matrix (word counts per document) and to GPT-2's token-embedding matrix.

VICTORY CONDITIONS

  1. Error ratio <= 1.1 with q = 2 power iterations; >= 10x faster than full SVD; within 1.5x of sklearn's time (||A - QQ^T A||_2 / sigma_(k+1) (your approximation error divided by the best error any rank-k approximation can reach) and wall time at k = 100).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

Randomized range finder
Multiplying a matrix by a few random vectors and orthonormalising the result to get a basis Q for its most important column directions.
Oversampling
Using a few extra random vectors beyond the target rank k so the sketch is less likely to miss an important direction.
Power iterations (in randomized SVD)
Multiplying by A^T A a few extra times so large singular values dominate small ones and the sketch becomes more accurate.
Block Krylov
A variant that keeps the whole sequence of products A x, (A^T A) A x and so on, giving a richer subspace for the same number of passes.
sigma_(k+1)
The (k+1)-th singular value, which is exactly the smallest possible spectral-norm error of any rank-k approximation.

Why it rates ★★☆☆☆

Useful and well understood. This is the stepping stone; A03 is where it matters.