Sampling Techniques for the Nystrom Method

Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar
Proceedings of the Twelfth 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 = {Kumar, Sanjiv and Mohri, Mehryar and Talwalkar, Ameet}, booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics}, pages = {304--311}, year = {2009}, editor = {van Dyk, David and Welling, Max}, 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 = {https://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 Twelfth 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 %P 304--311 %U https://proceedings.mlr.press/v5/kumar09a.html %V 5 %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 Twelfth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-kumar09a PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 304 EP - 311 L1 - http://proceedings.mlr.press/v5/kumar09a/kumar09a.pdf UR - https://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 Twelfth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:304-311 Available from https://proceedings.mlr.press/v5/kumar09a.html.

Related Material