@proceedings {793, title = {Graph Approximation and Clustering on a Budget}, volume = {38}, year = {2015}, abstract = {
We consider the problem of learning from a\ similarity matrix (such as spectral cluster-\ ing and low-dimensional embedding), when\ computing pairwise similarities are costly,\ and only a limited number of entries can be\ observed. We provide a theoretical anal-\ ysis using standard notions of graph ap-\ proximation, significantly generalizing pre-\ vious results, which focused on spectral\ clustering with two clusters. We also pro-\ pose a new algorithmic approach based on\ adaptive sampling, which experimentally\ matches or improves on previous methods,\ while being considerably more general and\ computationally cheaper.
}, author = {Ethan Fetaya and Ohad Shamir and Shimon Ullman} }