Faster Principal Component Regression and Stable Matrix Chebyshev Approximation

Zeyuan Allen-Zhu, Yuanzhi Li

We solve principal component regression (PCR), up to a multiplicative accuracy $1+\gamma$, by reducing the problem to $\tilde{O}({\gamma }^{-1})$ black-box calls of ridge regression. Therefore,…