Computationally Efficient Decompositions of Oblique Projection Matrices

Abstract

Oblique projection matrices arise in problems in weighted least squares, signal processing, and optimization. While these matrices can be potentially very large, their low-rank structure can be exploited for efficient computation. Here, we propose fast and scalable algorithms for computing their eigendecomposition and singular value decomposition (SVD). Numerical experiments that compare our proposed approaches to existing methods, including randomized SVD, are presented. In addition, we test their accuracy on linear systems from equality constrained optimization problems.