# A novel greedy algorithm for NystrÃ¶m approximation

[edit]

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. [pdf][supplementary]

#### Related Material