Aryan Gupta, IIT Bombay

Description

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.

Location
Ramanujan Hall
Date
Thu, April 23, 2026
Start Time
10:00am-11:00am IST
Duration
1 hour
Priority
5-Medium
Access
Public
Updated
Wed, April 22, 2026 2:31pm IST