Efficient Algorithm for Minimal-Rank Matrix Approximations

For a given matrix H which has d singular values larger than ε, an expression for all rank-d approximants ˆH such that (H − ˆH) has 2-norm less than ε is derived. These approximants have minimal rank, and the set includes the usual ‘truncated SVD ’ low-rank approximation. The main step in the procedure is a generalized Schur algorithm, which requires only O(1/2 m 2 n) operations (for an m × n matrix H). The column span of the approximant is computed in this step, and updating and downdating of this space is straightforward. The algorithm is amenable to parallel implementation.