# Approximate l0-penalized estimation of piecewise-constant signals on graphs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2017.

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

- [Lattice partition recovery with dyadic CART](https://mlsanity.com/paper/2105.13504/) (2021)
- [Variance estimation in graphs with the fused lasso](https://mlsanity.com/paper/2207.12638/) (2022)
- [T-LoHo: A Bayesian Regularization Model for Structured Sparsity and Smoothness on Graphs](https://mlsanity.com/paper/2107.02510/) (2021)
- [Inferring Change Points in High-Dimensional Regression via Approximate Message Passing](https://mlsanity.com/paper/2404.07864/) (2024)
- [Graph-dependent shrinkage priors for Bayesian trend filtering](https://mlsanity.com/paper/2608.23802/) (2026)

## Abstract (arXiv)

We study recovery of piecewise-constant signals on graphs by the estimator minimizing an l0-edge-penalized objective. Although exact minimization of this objective may be computationally intractable, we show that the same statistical risk guarantees are achieved by the α-expansion algorithm which computes an approximate minimizer in polynomial time. We establish that for graphs with small average vertex degree, these guarantees are minimax rate-optimal over classes of edge-sparse signals. For spatially inhomogeneous graphs, we propose minimization of an edge-weighted objective where each edge is weighted by its effective resistance or another measure of its contribution to the graph's connectivity. We establish minimax optimality of the resulting estimators over corresponding edge-weighted sparsity classes. We show theoretically that these risk guarantees are not always achieved by the estimator minimizing the l1/total-variation relaxation, and empirically that the l0-based estimates are more accurate in high signal-to-noise settings.