Algorithm 844

Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices 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. {it G. W. Stewart} [Numer. Math. 83, No. 2, 313--323 (1999; Zbl 0957.65031)] 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 $Acong 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. (Source:

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 15 articles , 1 standard article )

Showing results 1 to 15 of 15.
Sorted by year (citations)

  1. Boutsidis, Christos; Woodruff, David P.: Optimal CUR matrix decompositions (2017)
  2. Fan, H.-Y.; Zhang, L.; Chu, E.K.-w.; Wei, Y.: Q-less QR decomposition in inner product spaces (2016)
  3. Trendafilov, Nickolay T.; Unkel, Steffen; Krzanowski, Wojtek: Exploratory factor and principal component analyses: some new aspects (2013)
  4. Wang, Jianzhong: Geometric structure of high-dimensional data and dimensionality reduction (2012)
  5. Mahoney, Michael W.: Randomized algorithms for matrices and data (2011)
  6. Martinsson, Per-Gunnar; Rokhlin, Vladimir; Tygert, Mark: A randomized algorithm for the decomposition of matrices (2011)
  7. Mahoney, Michael W.; Drineas, Petros: CUR matrix decompositions for improved data analysis (2009)
  8. Miettinen, Pauli: The Boolean column and column-row matrix decompositions (2008)
  9. Woolfe, Franco; Liberty, Edo; Rokhlin, Vladimir; Tygert, Mark: A fast randomized algorithm for the approximation of matrices (2008)
  10. Drineas, Petros; Mahoney, Michael W.: A randomized algorithm for a tensor-based generalization of the singular value decomposition (2007)
  11. Aswani Kumar, Cherukuri; Srinivas, Suripeddi: Latent semantic indexing using eigenvalue analysis for efficient information retrieval (2006)
  12. Drineas, Petros; Kannan, Ravi; Mahoney, Michael W.: Fast Monte Carlo algorithms for matrices. III: Computing a compressed approximate matrix decomposition (2006)
  13. Drineas, Petros; Mahoney, Michael W.; Muthukrishnan, S.: Subspace sampling and relative-error matrix approximation: Column-row-based methods (2006)
  14. Berry, Michael W.; Pulatova, Shakhina A.; Stewart, G.W.: Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices (2005)
  15. Stewart, G.W.: Error analysis of the quasi-Gram-Schmidt algorithm (2005)