Improved Approximation Algorithms for Large Matrices via Random Projections

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…