Improved Approximation Algorithms for Large Matrices via Random Projections
Author:
Top Cited Papers
- 1 October 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 143-152
Abstract
Several results appeared that show significant reduction in time for matrix multiplication, singular value decomposition as well as linear (lscr 2 ) regression, all based on data dependent random sampling. Our key idea is that low dimensional embeddings can be used to eliminate data dependence and provide more versatile, linear time pass efficient matrix computation. Our main contribution is summarized as follows. 1) Independent of the results of Har-Peled and of Deshpande and Vempala, one of the first - and to the best of our knowledge the most efficient - relative error (1 + epsi) parA $A k par F approximation algorithms for the singular value decomposition of an m times n matrix A with M non-zero entries that requires 2 passes over the data and runs in time O((M(k/epsi+k log k) + (n+m)(k/epsi+k log k) 2 )log (1/sigma)). 2) The first o(nd 2 ) time (1 + epsi) relative error approximation algorithm for n times d linear (lscr 2 ) regression. 3) A matrix multiplication and norm approximation algorithm that easily applies to implicitly given matrices and can be used as a black box probability boosting toolKeywords
This publication has 32 references indexed in Scilit:
- Database-friendly random projections: Johnson-Lindenstrauss with binary coinsJournal of Computer and System Sciences, 2003
- An elementary proof of a theorem of Johnson and LindenstraussRandom Structures & Algorithms, 2002
- Tracking Join and Self-Join Sizes in Limited StorageJournal of Computer and System Sciences, 2002
- Latent Semantic Indexing: A Probabilistic AnalysisJournal of Computer and System Sciences, 2000
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- Approximating Matrix Multiplication for Pattern Recognition TasksJournal of Algorithms, 1999
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- The Johnson-Lindenstrauss lemma and the sphericity of some graphsJournal of Combinatorial Theory, Series B, 1988
- Extensions of Lipschitz mappings into a Hilbert space1984