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. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1145/1067967.1067972 | ACM Trans. Math. Softw. |
Keywords | Field | DocType |
reduced rank approximation,sparse approximations,computing sparse reduced-rank approximation,scr approximation,low-rank approximation,q-less qr approximation,schmidt algorithm,general sparse,r11 r12,sparse matrix,matlab implementation,qr decomposition,matlab,gram--schmidt algorithm,latent semantic indexing,sparse approximation,singular value,low rank approximation,sparse matrices | Linear algebra,Singular value,MATLAB,Search engine indexing,Theoretical computer science,Sparse matrix,Row,Discrete mathematics,Mathematical optimization,Combinatorics,Sparse approximation,Algorithm,Numerical linear algebra,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 2 | 0098-3500 |
Citations | PageRank | References |
26 | 2.23 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael W. Berry | 1 | 1852 | 200.54 |
Shakhina A. Pulatova | 2 | 26 | 2.23 |
G. W. Stewart | 3 | 62 | 8.15 |