Principal Component Projection with Low-Degree Polynomials
For researchers in dimensionality reduction and matrix computations, this provides a more efficient polynomial-based method for PCP approximation, though it is an incremental improvement over existing approaches.
The paper improves approximations of principal component projection (PCP) by replacing rational functions with optimized low-degree polynomials, achieving effective approximations without explicit principal component computation.
In this paper, we consider approximations of principal component projection (PCP) without explicitly computing principal components. This problem has been studied in several recent works. The main feature of existing approaches is viewing the PCP matrix as a matrix function. This underlying function is the composition of a step function with a rational function. To find an approximate PCP, the step function is approximated by a polynomial while the rational function is evaluated by a fast ridge regression solver. In this work, we further improve this process by replacing the rational function with carefully constructed polynomials of low degree. We characterize the properties of polynomials that are suitable for approximating PCP, and establish an optimization problem to select the optimal one from those polynomials. We show theoretically and confirm numerically that the resulting approximate PCP approach with optimal polynomials is indeed effective for approximations of principal component projection.