Fast computation of low rank matrix approximations. (English) Zbl 1311.94032
Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6–8, 2001. New York, NY: ACM Press (ISBN 1-581-13349-9). 611-618 (2001).
MSC:
| 94A20 | Sampling theory in information and communication theory |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 68W40 | Analysis of algorithms |
References:
| [1] | Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry, and Jared Saia, Data mining through spectral analysis, These Proceedings. |
| [2] | Michael W. Berry, Zlatko Drmac, and Elizabeth R. Jessup, Matrices, vector spaces, and information retrieval, SIAM Rev. 41 (1999), no. 2, 335-362 (electronic). 10.1137/S0036144598347035 · Zbl 0924.68069 |
| [3] | Michael W. Berry, Susan T. Dumais, and Gavin W. O’Brien, Using linear algebra for intelligent information retrieval, SIAM Rev. 37 (1995), no. 4, 573-595. 10.1137/1037127 · Zbl 0842.68026 |
| [4] | Scott Deerwester, Susan T. Dumais, Thomas K. Landauer, George W. Furnas, and Richard A. Harshman, Indexing by latent semantic analysis, J. Soc. Inf. Sci. 41 (1990), no. 6, 391-407. |
| [5] | Petros Drineas, Alan Frieze, Ravi Kannan, Santosh Vempala, and V. Vinay, Clustering in large graphs and matrices, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 1999), 1999, pp. 291-299. · Zbl 0938.68068 |
| [6] | Alan Frieze, Ravi Kannan, and Santosh Vempala, Fast monte-carlo algorithms for finding low-rank approximations, 39th Annual Symposium on Foundations of Computer Science (Palo Alto, CA, 1998), 1998, pp. 370-378. |
| [7] | Zoltan F.uredi and Janos Komlos, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233-241. · Zbl 0494.15010 |
| [8] | Gene H. Golub and Charles F. Van Loan, Matrix computations, third ed., Johns Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009 |
| [9] | Ferenc Juhasz, On the spectrum of a random graph, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), North-Holland, Amsterdam, 1981, pp. 313-316. · Zbl 0475.05060 |
| [10] | Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, J.ACM 46 (1999), no. 5, 604-632. 10.1145/324133.324140 · Zbl 1065.68660 |
| [11] | Michael Krivelevich and Van H. Vu, On the concentration of eigenvalues of random symmetric matrices, Tech. Report 60, Microsoft Research, 2000. |
| [12] | Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, and Santosh Vempala, Latent semantic indexing: A probabilistic analysis, 17th Annual Symposium on Principles of Database Systems (Seattle, WA, 1998), 1998, pp. 159-168. 10.1145/275487.275505 |
| [13] | Matthew Turk and Alex Pentland, Eigenfaces for recognition, J. Cogn. Neurosci. 3 (1991), no. 1, 71-86. |
| [14] | Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325-327. · Zbl 0085.13203 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
