A RANDOMIZED ALGORITHM FOR PRINCIPAL COMPONENTANALYSIS

摘要

Principal component analysis (PCA) requires the computation of a low-rank approx-imation to a matrix containing the data being analyzed. In many applications of PCA, the bestpossible accuracy of any rank-deficient approximation is at most a few digits (measured in the spec-tral norm, relative to the spectral norm of the matrix being approximated). In such circumstances,efficient algorithms have riot come with guarantees of good accuracy, unless one or both dimensionsof the matrix being approximated are small. We describe an efficient algorithm for the low-rankapproximation of matrices that produces accuracy that is very close to the best possible accuracy,for matrices of arbitrary sizes. We illustrate our theoretical results via several numerical examples.