Iterative Alpha Expansion for estimating gradient-sparse signals from linear measurements
This work addresses signal recovery in compressed sensing for applications like image processing, but it is incremental as it builds upon existing total-variation methods with specific algorithmic improvements.
The paper tackles the problem of estimating gradient-sparse signals from noisy linear measurements by proposing an iterative algorithm that minimizes an l_0-norm penalized objective, achieving global recovery guarantees under certain conditions and empirically reducing mean-squared error compared to total-variation methods in moderate undersampling and signal-to-noise regimes.
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.