Abstract
The Nyström method is an efficient technique to generate low-rank matrix approximations and is used in several large-scale learning applications. A key aspect of this method is the distribution according to which columns are sampled from the original matrix. In this work, we present an analysis of different sampling techniques for the Nyström method. Our analysis includes both empirical and theoretical components. We first present novel experiments with several real world datasets, comparing the performance of the Nyström method when used with uniform versus non-uniform sampling distributions. Our results suggest that uniform sampling without replacement, in addition to being more efficient both in time and space, produces more effective approximations. This motivates the theoretical part of our analysis which gives the first performance bounds for the Nyström method precisely when used with uniform sampling without replacement.
Original language | English (US) |
---|---|
Pages (from-to) | 304-311 |
Number of pages | 8 |
Journal | Journal of Machine Learning Research |
Volume | 5 |
State | Published - 2009 |
Event | 12th International Conference on Artificial Intelligence and Statistics, AISTATS 2009 - Clearwater, FL, United States Duration: Apr 16 2009 → Apr 18 2009 |
ASJC Scopus subject areas
- Software
- Artificial Intelligence
- Control and Systems Engineering
- Statistics and Probability