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 "l_0-norm" of the signal's discrete graph gradient. The
method proceeds by approximate proximal descent, applying the alpha-expansion
procedure to minimize a proximal gradient in each iteration, and using a
geometric decay of the penalty parameter across iterations. 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 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.
