Faster Principal Component Regression and Stable Matrix Chebyshev Approximation
share
We solve principal component regression (PCR), up to a multiplicative accuracy 1+γ, by reducing the problem to Õ(γ^-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 Õ(γ^-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. Our techniques may be of independent interests, especially when designing iterative methods.
READ FULL TEXT