Title: Sampling-based Approximate SVD
Many popular machine learning techniques such as Kernel Methods require
spectral decomposition of dense matrices. The complexity of such
decomposition is O(n^3) where n is the number of data points. With
datasets containing millions of points becoming common, this computation
becomes infeasible both in time and space. In this talk, I will analyze
two sampling based approximate SVD techniques for large dense matrices
(Nystrom and Column-sampling), providing a theoretical and empirical
comparison between these techniques. The experiments reveal interesting
counter-intuitive behaviors of the two approximations. I will summarize
the talk with several open questions.
Parts of this work were done in collaboration with Ameet Talwalkar,
Henry Rowley and Mehryar Mohri.