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 18 articles , 1 standard article )

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

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