Algorithm 844: Computing Sparse Reduced-Rank Approximations • 269

In many applications—latent semantic indexing, for example—it is required to obtain a reduced rank approximation to a sparse matrix A. Unfortunately, the approximations based on traditional decompositions, like the singular value and QR decompositions, are not in general sparse. Stewart [(1999), 313–323] has shown how to use a variant of the classical Gram–Schmidt algorithm, called the quasi–Gram-Schmidt–algorithm, to obtain two kinds of low-rank approximations. The first, the SPQR, approximation, is a pivoted, Q-less QR approximation of the form (XR−111)(R11 R12), where X consists of columns of A. The second, the SCR approximation, is of the form the form A ∼ = XTY T, where X and Y consist of columns and rows A and T, is small. In this article we treat the computational details of these algorithms and describe a MATLAB implementation