Nyström Method with Kernel K-means++ Samples as Landmarks

Dino Oglic, Thomas Gärtner
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2652-2660, 2017.

Abstract

We investigate, theoretically and empirically, the effectiveness of kernel K-means++ samples as landmarks in the Nyström method for low-rank approximation of kernel matrices. Previous empirical studies (Zhang et al., 2008; Kumar et al.,2012) observe that the landmarks obtained using (kernel) K-means clustering define a good low-rank approximation of kernel matrices. However, the existing work does not provide a theoretical guarantee on the approximation error for this approach to landmark selection. We close this gap and provide the first bound on the approximation error of the Nyström method with kernel K-means++ samples as landmarks. Moreover, for the frequently used Gaussian kernel we provide a theoretically sound motivation for performing Lloyd refinements of kernel K-means++ landmarks in the instance space. We substantiate our theoretical results empirically by comparing the approach to several state-of-the-art algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-oglic17a, title = {{N}ystr{\"o}m Method with Kernel K-means++ Samples as Landmarks}, author = {Dino Oglic and Thomas G{\"a}rtner}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2652--2660}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/oglic17a/oglic17a.pdf}, url = {https://proceedings.mlr.press/v70/oglic17a.html}, abstract = {We investigate, theoretically and empirically, the effectiveness of kernel K-means++ samples as landmarks in the Nyström method for low-rank approximation of kernel matrices. Previous empirical studies (Zhang et al., 2008; Kumar et al.,2012) observe that the landmarks obtained using (kernel) K-means clustering define a good low-rank approximation of kernel matrices. However, the existing work does not provide a theoretical guarantee on the approximation error for this approach to landmark selection. We close this gap and provide the first bound on the approximation error of the Nyström method with kernel K-means++ samples as landmarks. Moreover, for the frequently used Gaussian kernel we provide a theoretically sound motivation for performing Lloyd refinements of kernel K-means++ landmarks in the instance space. We substantiate our theoretical results empirically by comparing the approach to several state-of-the-art algorithms.} }
Endnote
%0 Conference Paper %T Nyström Method with Kernel K-means++ Samples as Landmarks %A Dino Oglic %A Thomas Gärtner %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-oglic17a %I PMLR %P 2652--2660 %U https://proceedings.mlr.press/v70/oglic17a.html %V 70 %X We investigate, theoretically and empirically, the effectiveness of kernel K-means++ samples as landmarks in the Nyström method for low-rank approximation of kernel matrices. Previous empirical studies (Zhang et al., 2008; Kumar et al.,2012) observe that the landmarks obtained using (kernel) K-means clustering define a good low-rank approximation of kernel matrices. However, the existing work does not provide a theoretical guarantee on the approximation error for this approach to landmark selection. We close this gap and provide the first bound on the approximation error of the Nyström method with kernel K-means++ samples as landmarks. Moreover, for the frequently used Gaussian kernel we provide a theoretically sound motivation for performing Lloyd refinements of kernel K-means++ landmarks in the instance space. We substantiate our theoretical results empirically by comparing the approach to several state-of-the-art algorithms.
APA
Oglic, D. & Gärtner, T.. (2017). Nyström Method with Kernel K-means++ Samples as Landmarks. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2652-2660 Available from https://proceedings.mlr.press/v70/oglic17a.html.

Related Material