Fast algorithms speed up sparse pca and robust sparse estimation
Fast Algorithms for Sparse PCA and Robust Sparse Estimation
Data Structures and Algorithms
Summary
This work looks at speeding up a mathematical tool called sparse PCA, which helps find important patterns in large data while focusing on only a few variables. The authors created new algorithms that run much faster than previous methods, especially when the number of important variables is not too large. Their approach avoids heavy computations and cleverly reduces the problem to searching within smaller candidate sets. They also apply these faster routines to improve methods for estimating parameters in noisy or corrupted data settings.
What this means in practice
- •For machine learning engineers: Run faster sparse PCA to identify key features in high-dimensional data with fewer computational resources.
- •For data scientists working with noisy data: Improve robust sparse parameter estimation in datasets with corrupted or heavy-tailed noise using faster certification methods.
Authors
Giannis Iakovidis, Ankit Pensia
Abstract
We study fast algorithms for sparse-PCA certification. Given a positive semidefinite matrix $M$, the problem asks either to rule out a large $k$-sparse quadratic form or to return a high-value (relaxed) witness. The standard semidefinite relaxation provides such certificates, but existing general-purpose solvers require $Ω(d^4)$ time. We give a bicriteria algorithm running in $O(d^2+d k^{O(\log k)})$ time: if some $k$-sparse unit vector has quadratic form greater than $2$, it returns either an $O(k^2)$-sparse unit vector or an SDP-feasible matrix of value at least $1$. For $k\leq\exp(O(\sqrt{\log d}))$, this running time is $O(d^2)$. We also go below the quadratic barrier in the sample-access model: Given $n=d^{o(1)}$ samples, our algorithm obtains a related one-sided certificate in $d^{2 - Ω(1)}$ time for $k=\mathrm{polylog}(d)$, without forming the empirical covariance matrix. As an application, these certificate routines yield the first quadratic and subquadratic-time algorithms for robust sparse estimation for broad families of distributions. Our sparse-PCA algorithm reduces a high-value sparse direction to a bounded-radius set in the graph of large correlations and searches the resulting candidate supports. The subquadratic implementation constructs this graph using fast correlation detection.