Iterative Alpha Expansion for estimating gradient‐sparse signals from linear measurements

We consider estimating a piecewise‐constant image, or a gradient‐sparse signal on a general graph, from noisy linear measurements. We propose and study an iterative algorithm to minimize a penalized least‐squares objective, with a penalty given by the “ℓ0‐norm” of the signal’s discrete graph gradient. The method uses a non‐convex variant of proximal gradient descent, applying the alpha‐expansion procedure to approximate the proximal mapping in each iteration, and using a geometric decay of the penalty parameter across iterations to ensure convergence. Under a cut‐restricted isometry property for the measurement design, we prove global recovery guarantees for the estimated signal. For standard Gaussian designs, the required number of measurements is independent of the graph structure, and improves upon worst‐case guarantees for total‐variation (TV) compressed sensing on the 1‐D line and 2‐D lattice graphs by polynomial and logarithmic factors respectively. The method empirically yields lower mean‐squared recovery error compared with TV regularization in regimes of moderate undersampling and moderate to high signal‐to‐noise, for several examples of changepoint signals and gradient‐sparse phantom images.