Compressive sensing for cut improvement and local clustering

Joint with Ming-Jun Lai

We show how one can phrase the cut improvement problem for graphs as a sparse recovery problem, whence one can use algorithms originally developed for use in compressive sensing. We use this new cut improvement approach as an algorithmic primitive to design new methods for local clustering and semi-supervised clustering.

Arxiv version

Journal version