Fast Low-Rank Approximation for Covariance Matrices

Computing an efficient low-rank approximation of a given positive definite matrix is a ubiquitous task in statistical signal processing and numerical linear algebra. The optimal solution is well known and is given by the singular value decomposition; however, its complexity scales as the cube of the matrix dimension. Here we introduce a low-complexity alternative which approximates this optimal low-rank solution, together with a bound on its worst-case error. Our methodology also reveals a connection between the approximation of matrix products and Schur complements. We present simulation results that verify performance improvements relative to contemporary randomized algorithms for low-rank approximation.