SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More

Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia +1

We study $\text{sparse singular value certificates}$ for random rectangular matrices. If $M$ is an $n\times d$ matrix with independent Gaussian entries, we give a new family of…