Student Seminar
Speaker: Aryan Gupta, IIT Bombay
Host: Manas Rachh
Title: Finding Structure with Randomness: The Randomized Rangefinder
Time, day and date: 10:00:00 AM – 11:00:00 AM, Thursday, April 23
Venue: Ramanujan Hall
Abstract: Computing the singular value decomposition of a large dense matrix costs O(n³) operations which is prohibitive when only the leading rank-k structure is needed. The randomized rangefinder (Halko–Martinsson Tropp, 2011) replaces this with an O(n²k) algorithm: multiply the matrix by a short, random Gaussian test matrix, orthogonalize, and project. The resulting approximation is provably close to the Eckart–Young optimum, and a single step of power iteration makes it near-optimal even on slowly decaying spectra.
This talk presents the algorithm, its error guarantee, and three experiments run on the IIT Bombay math cluster: (1) wall-clock scaling showing a 759× speedup at n = 15,000; (2) spectral-norm near-optimality across power iteration depths; and (3) a free adaptive stopping criterion via an exact Frobenius-norm identity. The talk closes with a brief look at how the same ideas extend to kernel matrices through randomly pivoted Cholesky.
No background beyond linear algebra is assumed.