@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} }