Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG
This work provides faster algorithms for fundamental problems in machine learning and data analysis, though it appears incremental as it builds on existing SVRG methods with rational approximations.
The paper tackles the problem of performing principal component projection and regression in nearly linear time for large datasets, achieving a significant speedup over previous superlinear-time methods when the number of top eigenvalues and inverse gap are large.
Given a data matrix $\mathbf{A} \in \mathbb{R}^{n \times d}$, principal component projection (PCP) and principal component regression (PCR), i.e. projection and regression restricted to the top-eigenspace of $\mathbf{A}$, are fundamental problems in machine learning, optimization, and numerical analysis. In this paper we provide the first algorithms that solve these problems in nearly linear time for fixed eigenvalue distribution and large n. This improves upon previous methods which have superlinear running times when both the number of top eigenvalues and inverse gap between eigenspaces is large. We achieve our results by applying rational approximations to reduce PCP and PCR to solving asymmetric linear systems which we solve by a variant of SVRG. We corroborate these findings with preliminary empirical experiments.