nips nips2008 nips2008-188 nips2008-188-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Michael P. Holmes, Jr. Isbell, Charles Lee, Alexander G. Gray
Abstract: The Singular Value Decomposition is a key operation in many machine learning methods. Its computational cost, however, makes it unscalable and impractical for applications involving large datasets or real-time responsiveness, which are becoming increasingly common. We present a new method, QUIC-SVD, for fast approximation of the whole-matrix SVD based on a new sampling mechanism called the cosine tree. Our empirical tests show speedups of several orders of magnitude over exact SVD. Such scalability should enable QUIC-SVD to accelerate and enable a wide array of SVD-based methods and applications. 1
[1] S. Friedland, A. Niknejad, M. Kaveh, and H. Zare. Fast Monte-Carlo Low Rank Approximations for Matrices. In Proceedings of Int. Conf. on System of Systems Engineering, 2006.
[2] A. Deshpande and S. Vempala. Adaptive Sampling and Fast Low-Rank Matrix Approximation. In 10th International Workshop on Randomization and Computation (RANDOM06), 2006.
[3] A. M. Frieze, R. Kannan, and S. Vempala. Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. In IEEE Symposium on Foundations of Computer Science, pages 370–378, 1998.
[4] P. Drineas, R. Kannan, and M. W. Mahoney. Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix. SIAM Journal on Computing, 36(1):158–183, 2006.
[5] P. Drineas, E. Drinea, and P. S. Huggins. An Experimental Evaluation of a Monte-Carlo Algorithm for Singular Value Decomposition. Lectures Notes in Computer Science, 2563:279–296, 2003.
[6] T. Sarlos. Improved Approximation Algorithms for Large Matrices via Random Projections. In 47th IEEE Symposium on Foundations of Computer Science (FOCS), pages 143–152, 2006.
[7] D. Achlioptas, F. McSherry, and B. Scholkopf. Sampling Techniques for Kernel Methods. In Advances in Neural Information Processing Systems (NIPS) 17, 2002.
[8] M. P. Holmes, A. G. Gray, and C. L.Isbell, Jr. Ultrafast Monte Carlo for Kernel Estimators and Generalized Statistical Summations. In Advances in Neural Information Processing Systems (NIPS) 21, 2008.
[9] J. Audibert, R. Munos, and C. Szepesvari. Variance estimates and exploration function in multi-armed bandits. Technical report, CERTIS, 2007. 8