A novel greedy algorithm for Nyström approximation

Ahmed Farahat, Ali Ghodsi, Mohamed Kamel
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:269-277, 2011.

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 this Paper

BibTeX
@InProceedings{pmlr-v15-farahat11a, title = {A novel greedy algorithm for {N}ystr\"om approximation}, author = {Farahat, Ahmed and Ghodsi, Ali and Kamel, Mohamed}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {269--277}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/farahat11a/farahat11a.pdf}, url = {https://proceedings.mlr.press/v15/farahat11a.html}, 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.} }
Endnote
%0 Conference Paper %T A novel greedy algorithm for Nyström approximation %A Ahmed Farahat %A Ali Ghodsi %A Mohamed Kamel %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-farahat11a %I PMLR %P 269--277 %U https://proceedings.mlr.press/v15/farahat11a.html %V 15 %X 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.
RIS
TY - CPAPER TI - A novel greedy algorithm for Nyström approximation AU - Ahmed Farahat AU - Ali Ghodsi AU - Mohamed Kamel BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-farahat11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 269 EP - 277 L1 - http://proceedings.mlr.press/v15/farahat11a/farahat11a.pdf UR - https://proceedings.mlr.press/v15/farahat11a.html AB - 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. ER -
APA
Farahat, A., Ghodsi, A. & Kamel, M.. (2011). A novel greedy algorithm for Nyström approximation. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:269-277 Available from https://proceedings.mlr.press/v15/farahat11a.html.

Related Material