On Sampling-Based Approximate Spectral Decomposition
Abstract
This paper addresses the problem of approximate singular value decomposition of large dense matrices that arises naturally in many machine learning applications. We discuss two recently introduced sampling-based spectral decomposition techniques: the Nystrom and the Column-sampling methods. We present a theoretical comparison between the two methods and provide novel insights regarding their suitability for various applications. We then provide experimental results motivated by this theory. Finally, we propose an efficient adaptive sampling technique to select informative columns from the original matrix. This novel technique outperforms standard sampling methods on a variety of datasets.
Cite
Text
Kumar et al. "On Sampling-Based Approximate Spectral Decomposition." International Conference on Machine Learning, 2009. doi:10.1145/1553374.1553446Markdown
[Kumar et al. "On Sampling-Based Approximate Spectral Decomposition." International Conference on Machine Learning, 2009.](https://mlanthology.org/icml/2009/kumar2009icml-sampling/) doi:10.1145/1553374.1553446BibTeX
@inproceedings{kumar2009icml-sampling,
title = {{On Sampling-Based Approximate Spectral Decomposition}},
author = {Kumar, Sanjiv and Mohri, Mehryar and Talwalkar, Ameet},
booktitle = {International Conference on Machine Learning},
year = {2009},
pages = {553-560},
doi = {10.1145/1553374.1553446},
url = {https://mlanthology.org/icml/2009/kumar2009icml-sampling/}
}