Double Nyström Method: An Efficient and Accurate Nyström Scheme for Large-Scale Data Sets
Woosang Lim, Minhwan Kim, Haesun Park, Kyomin Jung
Abstract
The Nyström method has been one of the most effective techniques for kernel-based approach that scales well to large data sets. Since its introduction, there has been a large body of work that improves the approximation accuracy while maintaining computational efficiency. In this paper, we present a novel Nyström method that improves both accuracy and efficiency based on a new theoretical analysis. We first provide a generalized sampling scheme, CAPS, that minimizes a novel error bound based on the subspace distance. We then present our double Nyström method that reduces the size of the decomposition in two stages. We show that our method is highly efficient and accurate compared to other state-of-the-art Nyström methods by evaluating them on a number of real data sets.
BibTeX
@InProceedings{pmlr-v37-lima15,
title = {Double Nystr\"om Method: An Efficient and Accurate Nystr\"om Scheme for Large-Scale Data Sets},
author = {Lim, Woosang and Kim, Minhwan and Park, Haesun and Jung, Kyomin},
booktitle = {Proceedings of the 32nd International Conference on Machine Learning},
pages = {1367--1375},
year = {2015},
editor = {Bach, Francis and Blei, David},
volume = {37},
series = {Proceedings of Machine Learning Research},
address = {Lille, France},
month = {07--09 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v37/lima15.pdf},
url = {https://proceedings.mlr.press/v37/lima15.html},
abstract = {The Nyström method has been one of the most effective techniques for kernel-based approach that scales well to large data sets. Since its introduction, there has been a large body of work that improves the approximation accuracy while maintaining computational efficiency. In this paper, we present a novel Nyström method that improves both accuracy and efficiency based on a new theoretical analysis. We first provide a generalized sampling scheme, CAPS, that minimizes a novel error bound based on the subspace distance. We then present our double Nyström method that reduces the size of the decomposition in two stages. We show that our method is highly efficient and accurate compared to other state-of-the-art Nyström methods by evaluating them on a number of real data sets.}
}