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