Spotlight
Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing
Arun Jambulapati · Jerry Li · Kevin Tian
Orals & Spotlights: Deep Learning/Theory
Abstract:
We develop two methods for the following fundamental statistical task: given an -corrupted set of samples from a -dimensional sub-Gaussian distribution, return an approximate top eigenvector of the covariance matrix. Our first robust PCA algorithm runs in polynomial time, returns a -approximate top eigenvector, and is based on a simple iterative filtering approach. Our second, which attains a slightly worse approximation factor, runs in nearly-linear time and sample complexity under a mild spectral gap assumption. These are the first polynomial-time algorithms yielding non-trivial information about the covariance of a corrupted sub-Gaussian distribution without requiring additional algebraic structure of moments. As a key technical tool, we develop the first width-independent solvers for Schatten- norm packing semidefinite programs, giving a -approximate solution in input-sparsity time iterations (where , are problem dimensions).
Chat is not available.