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: http://dl.acm.org/)

This software is also peer reviewed by journal TOMS.


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

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

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