Abstract
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. Our techniques may be of independent interests, especially when designing iterative methods.
Introduction
Principal Component Projection (PCP) and Regression (PCR) are fundamental tools in machine learning for noise reduction and dimensionality reduction. Traditionally, these methods rely on Principal Component Analysis (PCA) to identify the top components of a dataset. However, PCA solvers typically scale linearly with the number of components desired, making them computationally prohibitive for massive, high-dimensional datasets.
Recent advancements, notably by Frostig et al., demonstrated that PCA can be bypassed by reducing the projection problem to a series of black-box ridge regressions. While innovative, this approach suffered from two primary limitations: it required $O(\gamma^{-2})$ ridge regression calls (where $\gamma$ is the accuracy parameter) and relied on a restrictive "eigengap assumption"—the requirement that no singular values exist near the cutoff threshold. This paper introduces a method that quadratically improves complexity to $O(\gamma^{-1})$ calls while removing the eigengap requirement.
Approximating the Matrix Sign Function
The breakthrough lies in approximating the matrix sign function, $\text{sgn}(x)$. By applying a sign function to a shifted version of the data's covariance matrix, the algorithm acts as a filter: it preserves principal components above a specific threshold and eliminates those below it. Since computing the exact matrix sign function is as hard as PCA, the authors utilize a polynomial approximation.
Efficiency and Stability
To achieve the $O(\gamma^{-1})$ complexity, the authors construct a specific polynomial based on Chebyshev approximation. However, high-degree polynomials are notoriously unstable when applied to matrices, particularly when the underlying matrix-vector multiplications are approximate. To mitigate this, the authors generalized Clenshaw’s backward recurrence method to matrices. This ensures that errors do not accumulate or blow up during the iterative computation, even when using fast, inexact solvers like SVRG.
Gap-Free Robustness
Real-world data rarely exhibits a clean eigengap. To address this, the paper introduces "gap-free" definitions for approximate PCP and PCR. Instead of a binary cutoff, these definitions allow for a graceful transition where vectors with eigenvalues near the threshold are partially projected, ensuring the algorithm remains robust in dense spectral environments.
Experimental Evaluation
The algorithm was tested on both synthetic and real-world datasets:
- Synthetic Datasets (
random-a): Matrices were generated with controlled eigengaps to verify performance across varying spectral conditions. - Real-world Dataset (MNIST): The standard MNIST image dataset was used to simulate a realistic scenario where eigenvalues are densely packed and no clear gap exists.
In these experiments, the proposed method significantly outperformed the previous state-of-the-art (FMMS), converging faster to low regression and projection errors. Notably, the algorithm remained stable even when artificial noise ($10^{-6}$ per coordinate) was injected into the ridge regression subroutine. It also outperformed popular Krylov subspace heuristics, which often fail to converge or fluctuate in gap-free scenarios.
Key Insights and Future Work
This work demonstrates that evaluating a matrix sign function is a powerful "backdoor" to subspace projection that avoids the costs of explicit PCA. Beyond the speedup in PCR, the development of a stable matrix-adapted Clenshaw recurrence and the analysis of Chebyshev polynomials outside the standard $[-1, 1]$ interval provide valuable theoretical tools for the broader field of iterative matrix methods.
While the method is theoretically optimal, practical deployment requires specifying parameters like the accuracy $\gamma$. Future work may focus on automated parameter tuning to further simplify the application of these fast PCR techniques to diverse large-scale datasets.
Summary updated