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.