Sampling Techniques for the Nystrom Method

Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar
; Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:304-311, 2009.

Abstract

The Nystrom 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 Nystrom method. Our analysis includes both empirical and theoretical components. We first present novel experiments with several real world datasets, comparing the performance of the Nystrom 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 Nystrom method precisely when used with uniform sampling without replacement.

Cite this Paper


BibTeX
@InProceedings{pmlr-v5-kumar09a, title = {Sampling Techniques for the Nystrom Method}, author = {Sanjiv Kumar and Mehryar Mohri and Ameet Talwalkar}, booktitle = {Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics}, pages = {304--311}, year = {2009}, editor = {David van Dyk and Max Welling}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/kumar09a/kumar09a.pdf}, url = {http://proceedings.mlr.press/v5/kumar09a.html}, abstract = {The Nystrom 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 Nystrom method. Our analysis includes both empirical and theoretical components. We first present novel experiments with several real world datasets, comparing the performance of the Nystrom 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 Nystrom method precisely when used with uniform sampling without replacement.} }
Endnote
%0 Conference Paper %T Sampling Techniques for the Nystrom Method %A Sanjiv Kumar %A Mehryar Mohri %A Ameet Talwalkar %B Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-kumar09a %I PMLR %J Proceedings of Machine Learning Research %P 304--311 %U http://proceedings.mlr.press %V 5 %W PMLR %X The Nystrom 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 Nystrom method. Our analysis includes both empirical and theoretical components. We first present novel experiments with several real world datasets, comparing the performance of the Nystrom 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 Nystrom method precisely when used with uniform sampling without replacement.
RIS
TY - CPAPER TI - Sampling Techniques for the Nystrom Method AU - Sanjiv Kumar AU - Mehryar Mohri AU - Ameet Talwalkar BT - Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics PY - 2009/04/15 DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-kumar09a PB - PMLR SP - 304 DP - PMLR EP - 311 L1 - http://proceedings.mlr.press/v5/kumar09a/kumar09a.pdf UR - http://proceedings.mlr.press/v5/kumar09a.html AB - The Nystrom 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 Nystrom method. Our analysis includes both empirical and theoretical components. We first present novel experiments with several real world datasets, comparing the performance of the Nystrom 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 Nystrom method precisely when used with uniform sampling without replacement. ER -
APA
Kumar, S., Mohri, M. & Talwalkar, A.. (2009). Sampling Techniques for the Nystrom Method. Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, in PMLR 5:304-311

Related Material