Fast Length-Squared Sampling for Positive-Semidefinite Matrices

Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco +1

We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n\times n$ positive-semidefinite (psd) matrix: that is, to sample a column with p…