Graph Approximation and Clustering on a Budget

06/10/2014
by   Ethan Fetaya, et al.
0

We consider the problem of learning from a similarity matrix (such as spectral clustering and lowd imensional embedding), when computing pairwise similarities are costly, and only a limited number of entries can be observed. We provide a theoretical analysis using standard notions of graph approximation, significantly generalizing previous results (which focused on spectral clustering with two clusters). We also propose a new algorithmic approach based on adaptive sampling, which experimentally matches or improves on previous methods, while being considerably more general and computationally cheaper.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset