Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices

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⁻¹)(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.

REFERENCES

• 1: Michael W. Berry , Murray Browne, Understanding search engines: mathematical modeling and text retrieval, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: Michael W. Berry , Zlatko Drmac , Elizabeth R. Jessup, Matrices, Vector Spaces, and Information Retrieval, SIAM Review, v.41 n.2, p.335-362, June 1999 [doi>10.1137/S0036144598347035]
• 3: Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
• 4: Berry, M. W. and Martin, D. I. 2004. Principal component analysis for information retrieval. In Handbook of Parallel Computing and Statistics. Marcel Dekker, New York. To appear.
• 5: Björck, Å. 1996. Numerical Methods for Least Squares Problems. SIAM, Philadelphia.
• 6: Deerwester, S., Dumais, S., Furnas, G., Landauer, T., and Harshman, R. 1990. Indexing by latent semantic analysis. J. Amer. Soc. Info. Sci. 41, 391--407.
• 7: Jiang, P. and Berry, M. W. 2000. Solving total least squares problems in information retrieval. Lin. Alg. Appl. 316, 137--156.
• 8: Saad, Y. 1994. SPARSEKIT: A basic tool kit for sparse matrix computations. Available at www-users.cs.umn.edu/~saad/software/SPARSKIT/sparskit.html.
• 9: Stewart, G. W. 1980. The efficient generation of random orthogonal matrices with an application to condition estimators. SIAM J. Num. Anal. 17, 403--409.
• 10: Stewart, G. W. 1998. Matrix Algorithms I: Basic Decompositions. SIAM, Philadelphia.
• 11: Stewart, G. W. 1999. Four algorithms for the the efficient computation of truncated pivoted qr approximations to a sparse matrix. Numerische Mathematik 83, 313--323.
• 12: G. W. Stewart, Matrix algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 13: Stewart, G. W. 2004. Error analysis of the quasi-Gram--Schmidt algorithm. Tech. Rep. CMSC TR-4572, Department of Computer Science, University of Maryland.
• 14: Stuart, G. W. and Berry, M. W. 2003. A comprehensive whole genome bacterial phylogeny using correlated peptide motifs defined in a high dimensional vector space. J. Bioinformatics and Computational Bio. 1, 475--493.
• 15: Zhenyue Zhang , Hongyuan Zha , Horst Simon, Low-Rank Approximations with Sparse Factors I: Basic Algorithms and Error Analysis, SIAM Journal on Matrix Analysis and Applications, v.23 n.3, p.706-727, 2001 [doi>10.1137/S0895479899359631]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Keywords:
Gram--Schmidt algorithm, MATLAB, Sparse approximations