Faster Principal Component Regression and Stable Matrix Chebyshev Approximation

Understand

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, our algorithm does not require any explicit construction of the top principal components, and is suitable for large-scale PCR instances.
• In contrast, previous result requires $\tilde{O}(\gamma^{-2})$ such black-box calls.
• We obtain this result by developing a general stable recurrence formula for matrix Chebyshev polynomials, and a degree-optimal polynomial approximation to the matrix sign function.