A Novel Greedy Algorithm for Nyström Approximation
Abstract
The Nyström method is an efficient technique for obtaining a low-rank approximation of a large kernel matrix based on a subset of its columns. The quality of the Nyström approximation highly depends on the subset of columns used, which are usually selected using random sampling. This paper presents a novel recursive algorithm for calculating the Nyström approximation, and an effective greedy criterion for column selection. Further, a very efficient variant is proposed for greedy sampling, which works on random partitions of data instances. Experiments on benchmark data sets show that the proposed greedy algorithms achieve significant improvements in approximating kernel matrices, with minimum overhead in run time.
Cite
Text
Farahat et al. "A Novel Greedy Algorithm for Nyström Approximation." Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011.Markdown
[Farahat et al. "A Novel Greedy Algorithm for Nyström Approximation." Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011.](https://mlanthology.org/aistats/2011/farahat2011aistats-novel/)BibTeX
@inproceedings{farahat2011aistats-novel,
title = {{A Novel Greedy Algorithm for Nyström Approximation}},
author = {Farahat, Ahmed and Ghodsi, Ali and Kamel, Mohamed},
booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics},
year = {2011},
pages = {269-277},
volume = {15},
url = {https://mlanthology.org/aistats/2011/farahat2011aistats-novel/}
}