Michael W. Berry, Shakhina A. Pulatova, G. W. Stewart

Code and Data Abstract

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 (XR11−1)(R11 R12), where X consists of columns of A. The second, the SCR approximation, is of the form the form A ≅ XTYT, 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.

Download Code

Please remember to cite code and data.

Michael W. Berry,
Shakhina A. Pulatova,
G. W. Stewart,
et al.
"Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices."
Journal ACM Transactions on Mathematical Software (TOMS).
doi:10.1145/1067967.1067972.
Retrieved 11/17/2019 from researchcompendia.org/compendia/2013.6/

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 (XR11−1)(R11 R12), where X consists of columns of A. The second, the SCR approximation, is of the form the form A ≅ XTYT, 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.

Michael W. Berry,
Shakhina A. Pulatova,
G. W. Stewart,
et al.
"Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices."
Journal ACM Transactions on Mathematical Software (TOMS).
doi:10.1145/1067967.1067972.
Retrieved 11/17/2019 from researchcompendia.org/compendia/2013.6/

Compendium Type: Published Papers Primary Research Field: Computer and Information Sciences Secondary Research Field: Mathematics Content License: Public Domain Mark Code License: MIT License