Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix (Q1806006): Difference between revisions

The singular value and pivoted QR decompositions loose some of their appeal when the matrix is large and sparse. The problem is that the conventional algorithms for computing these decompositions proceed by transformations that quickly destroy the sparsity of the matrix. For the singular value decomposition, recourse must be had to iterative approximations. The purpose of this paper is to show that the pivoted QR decomposition can be implemented in such a way that the sparsity of the matrix is not compromised. Four algorithms are proposed in the paper. They are designed to compute truncated pivoted QR approximations to a sparse matrix. The key idea is to build up the \(Q\)-factor column by column and the \(R\)-factor row by row, leaving the original matrix unchanged. Only when a column of the matrix is needed to form a column of \(Q\) it is transformed. A key feature of the algorithms is the downloading of column norms to control pivoting. Three of the proposed algorithms are based on the Gram-Schmidt algorithm and the other on Householder triangularization. All four algorithms leave the original matrix unchanged, and the only additional storage requirements are arrays to contain the factorization itself. Thus, the algorithms are particularly suited to determining low-rank approximations to a sparse matrix.