Efficient Algorithms and Error Analysis for the Modified Nystrom Method
Many kernel methods suffer from high time and space complexities and are thus prohibitive in big-data applications. To tackle the computational challenge, the Nyström method has been extensively used to reduce time and space complexities by sacrificing some accuracy. The Nyström method speedups comp...
Main Authors: | , |
---|---|
Format: | Report |
Language: | unknown |
Published: |
arXiv
2014
|
Subjects: | |
Online Access: | https://dx.doi.org/10.48550/arxiv.1404.0138 https://arxiv.org/abs/1404.0138 |
id |
ftdatacite:10.48550/arxiv.1404.0138 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.1404.0138 2023-05-15T16:50:51+02:00 Efficient Algorithms and Error Analysis for the Modified Nystrom Method Wang, Shusen Zhang, Zhihua 2014 https://dx.doi.org/10.48550/arxiv.1404.0138 https://arxiv.org/abs/1404.0138 unknown arXiv arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ Machine Learning cs.LG FOS Computer and information sciences Preprint Article article CreativeWork 2014 ftdatacite https://doi.org/10.48550/arxiv.1404.0138 2022-04-01T12:55:33Z Many kernel methods suffer from high time and space complexities and are thus prohibitive in big-data applications. To tackle the computational challenge, the Nyström method has been extensively used to reduce time and space complexities by sacrificing some accuracy. The Nyström method speedups computation by constructing an approximation of the kernel matrix using only a few columns of the matrix. Recently, a variant of the Nyström method called the modified Nyström method has demonstrated significant improvement over the standard Nyström method in approximation accuracy, both theoretically and empirically. In this paper, we propose two algorithms that make the modified Nyström method practical. First, we devise a simple column selection algorithm with a provable error bound. Our algorithm is more efficient and easier to implement than and nearly as accurate as the state-of-the-art algorithm. Second, with the selected columns at hand, we propose an algorithm that computes the approximation in lower time complexity than the approach in the previous work. Furthermore, we prove that the modified Nyström method is exact under certain conditions, and we establish a lower error bound for the modified Nyström method. : 9-page paper plus appendix. In Proceedings of the 17th International Conference on Artificial Intelligence and Statistics (AISTATS) 2014, Reykjavik, Iceland. JMLR: W&CP volume 33 Report Iceland DataCite Metadata Store (German National Library of Science and Technology) |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Machine Learning cs.LG FOS Computer and information sciences |
spellingShingle |
Machine Learning cs.LG FOS Computer and information sciences Wang, Shusen Zhang, Zhihua Efficient Algorithms and Error Analysis for the Modified Nystrom Method |
topic_facet |
Machine Learning cs.LG FOS Computer and information sciences |
description |
Many kernel methods suffer from high time and space complexities and are thus prohibitive in big-data applications. To tackle the computational challenge, the Nyström method has been extensively used to reduce time and space complexities by sacrificing some accuracy. The Nyström method speedups computation by constructing an approximation of the kernel matrix using only a few columns of the matrix. Recently, a variant of the Nyström method called the modified Nyström method has demonstrated significant improvement over the standard Nyström method in approximation accuracy, both theoretically and empirically. In this paper, we propose two algorithms that make the modified Nyström method practical. First, we devise a simple column selection algorithm with a provable error bound. Our algorithm is more efficient and easier to implement than and nearly as accurate as the state-of-the-art algorithm. Second, with the selected columns at hand, we propose an algorithm that computes the approximation in lower time complexity than the approach in the previous work. Furthermore, we prove that the modified Nyström method is exact under certain conditions, and we establish a lower error bound for the modified Nyström method. : 9-page paper plus appendix. In Proceedings of the 17th International Conference on Artificial Intelligence and Statistics (AISTATS) 2014, Reykjavik, Iceland. JMLR: W&CP volume 33 |
format |
Report |
author |
Wang, Shusen Zhang, Zhihua |
author_facet |
Wang, Shusen Zhang, Zhihua |
author_sort |
Wang, Shusen |
title |
Efficient Algorithms and Error Analysis for the Modified Nystrom Method |
title_short |
Efficient Algorithms and Error Analysis for the Modified Nystrom Method |
title_full |
Efficient Algorithms and Error Analysis for the Modified Nystrom Method |
title_fullStr |
Efficient Algorithms and Error Analysis for the Modified Nystrom Method |
title_full_unstemmed |
Efficient Algorithms and Error Analysis for the Modified Nystrom Method |
title_sort |
efficient algorithms and error analysis for the modified nystrom method |
publisher |
arXiv |
publishDate |
2014 |
url |
https://dx.doi.org/10.48550/arxiv.1404.0138 https://arxiv.org/abs/1404.0138 |
genre |
Iceland |
genre_facet |
Iceland |
op_rights |
arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
op_doi |
https://doi.org/10.48550/arxiv.1404.0138 |
_version_ |
1766040974085062656 |