Title | Graph Approximation and Clustering on a Budget |
Publication Type | Conference Proceedings |
Year of Publication | 2015 |
Authors | Fetaya, E, Shamir, O, Ullman, S |
Conference Name | Artificial Intelligence and Statistics |
Volume | 38 |
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. |
Research Area:
CBMM Relationship:
- CBMM Related