Paper accepted to SOSA 2027

Our paper, Fast Length-Squared Sampling for Positive-Semidefinite Matrices, has been accepted to SOSA 2027!

This is joint work with Rajarshi Bhattacharjee, Ethan Epperly, and Cameron Musco. We give a simple rejection-sampling algorithm that samples a column of an $n \times n$ positive-semidefinite matrix with probability proportional to its squared norm in optimal $O(n)$ expected time. The sampling technique allows us to run several existing matrix approximation algorithms in sublinear time on psd matrices, and we describe a number of such applications in the paper.