Nyström method with Kernel K-means++ samples as landmarks
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...
| Main Authors: | , |
|---|---|
| Format: | Conference or Workshop Item |
| Published: |
Journal of Machine Learning Research
2017
|
| Online Access: | https://eprints.nottingham.ac.uk/43573/ |
| _version_ | 1848796718023311360 |
|---|---|
| author | Oglic, Dino Gaertner, Thomas |
| author_facet | Oglic, Dino Gaertner, Thomas |
| author_sort | Oglic, Dino |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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 Nystrom 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. |
| first_indexed | 2025-11-14T19:52:26Z |
| format | Conference or Workshop Item |
| id | nottingham-43573 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:52:26Z |
| publishDate | 2017 |
| publisher | Journal of Machine Learning Research |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-435732020-05-04T18:59:20Z https://eprints.nottingham.ac.uk/43573/ Nyström method with Kernel K-means++ samples as landmarks Oglic, Dino Gaertner, Thomas 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 Nystrom 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. Journal of Machine Learning Research 2017-08-06 Conference or Workshop Item PeerReviewed Oglic, Dino and Gaertner, Thomas (2017) Nyström method with Kernel K-means++ samples as landmarks. In: Proceedings of the 34th International Conference on Machine Learning, 6-11 August 2017, Sydney, Australia. http://proceedings.mlr.press/v70/oglic17a |
| spellingShingle | Oglic, Dino Gaertner, Thomas Nyström method with Kernel K-means++ samples as landmarks |
| title | Nyström method with Kernel K-means++ samples as landmarks |
| title_full | Nyström method with Kernel K-means++ samples as landmarks |
| title_fullStr | Nyström method with Kernel K-means++ samples as landmarks |
| title_full_unstemmed | Nyström method with Kernel K-means++ samples as landmarks |
| title_short | Nyström method with Kernel K-means++ samples as landmarks |
| title_sort | nyström method with kernel k-means++ samples as landmarks |
| url | https://eprints.nottingham.ac.uk/43573/ https://eprints.nottingham.ac.uk/43573/ |