Nyström Sketches
Abstract
Despite prolific success, kernel methods become difficult to use in many large scale unsupervised problems because of the evaluation and storage of the full Gram matrix. Here we overcome this difficulty by proposing a novel approach: compute the optimal small, out-of-sample Nyström sketch which allows for fast approximation of the Gram matrix via the Nyström method. We demonstrate and compare several methods for computing the optimal Nyström sketch and show how this approach outperforms previous state-of-the-art Nyström coreset methods of similar size. We further demonstrate how this method can be used in an online setting and explore a simple extension to make the method robust to outliers in the training data.
Cite
Text
Perry et al. "Nyström Sketches." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2017. doi:10.1007/978-3-319-71249-9_26Markdown
[Perry et al. "Nyström Sketches." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2017.](https://mlanthology.org/ecmlpkdd/2017/perry2017ecmlpkdd-nystrom/) doi:10.1007/978-3-319-71249-9_26BibTeX
@inproceedings{perry2017ecmlpkdd-nystrom,
title = {{Nyström Sketches}},
author = {Perry, Daniel J. and Osting, Braxton and Whitaker, Ross T.},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2017},
pages = {427-442},
doi = {10.1007/978-3-319-71249-9_26},
url = {https://mlanthology.org/ecmlpkdd/2017/perry2017ecmlpkdd-nystrom/}
}