Spectral Clustering on a Budget
Abstract
Spectral clustering is a modern and well known method for performing data clustering. However, it depends on the availability of a similarity matrix, which in many applications can be non-trivial to obtain. In this paper, we focus on the problem of performing spectral clustering under a budget constraint, where there is a limit on the number of entries which can be queried from the similarity matrix. We propose two algorithms for this problem, and study them theoretically and experimentally. These algorithms allow a tradeoff between computational efficiency and actual performance, and are also relevant for the problem of speeding up standard spectral clustering.
Cite
Text
Shamir and Tishby. "Spectral Clustering on a Budget." Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011.Markdown
[Shamir and Tishby. "Spectral Clustering on a Budget." Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011.](https://mlanthology.org/aistats/2011/shamir2011aistats-spectral/)BibTeX
@inproceedings{shamir2011aistats-spectral,
title = {{Spectral Clustering on a Budget}},
author = {Shamir, Ohad and Tishby, Naftali},
booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics},
year = {2011},
pages = {661-669},
volume = {15},
url = {https://mlanthology.org/aistats/2011/shamir2011aistats-spectral/}
}