# Compressive Sensing for cut improvement and local clustering

arXiv: https://arxiv.org/abs/1808.05780 · HTML: https://mlsanity.com/paper/1808.05780/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2018.

## Built on by (most cited first, 3 of 3)

- [Local Clustering for Lung Cancer Image Classification via Sparse Solution Technique](https://mlsanity.com/paper/2407.08800/) (2024)
- [Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods](https://mlsanity.com/paper/2504.19419/) (2025)
- [Scalable Graph Coreset Selection via Greedy Sampling](https://mlsanity.com/paper/2607.27602/) (2026)

## Abstract (arXiv)

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 (such as SubspacePursuit or CoSaMP) to solve it. We show that this approach to cut improvement is fast, both in theory and practice and moreover enjoys statistical guarantees of success when applied to graphs drawn from probabilistic models such as the Stochastic Block Model. Using this new cut improvement approach, which we call ClusterPursuit, as an algorithmic primitive we then propose new methods for local clustering and semi-supervised clustering, which enjoy similar guarantees of success and speed. Finally, we verify the promise of our approach with extensive numerical benchmarking.