# Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG

arXiv: https://arxiv.org/abs/1910.06517 · HTML: https://mlsanity.com/paper/1910.06517/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2019.

## Built on by (most cited first, 3 of 3)

- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Feature Grouping and Sparse Principal Component Analysis with Truncated Regularization](https://mlsanity.com/paper/2106.13685/) (2021)

## Abstract (arXiv)

Given a data matrix A ∈ ℝn × d, principal component projection (PCP) and principal component regression (PCR), i.e. projection and regression restricted to the top-eigenspace of 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.