Iterative Alpha Expansion for estimating gradient‐sparse signals from linear measurements
Iterative Alpha Expansion for estimating gradient‐sparse signals from linear measurements
复制标题
DOI：
10.1111/rssb.12407
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Sheng Xu;Z. Fan
中科院分区：
文献类型：
--
作者：
Sheng Xu;Z. Fan
我们考虑从含噪线性测量中估计一个分段常数图像，或一般图上的梯度稀疏信号。我们提出并研究一种迭代算法，以最小化一个惩罚最小二乘目标，其中惩罚由信号的离散图梯度的“$\ell_0$ -范数”给出。该方法使用近端梯度下降的非凸变体，在每次迭代中应用$\alpha$-扩展过程来近似近端映射，并在迭代过程中使用惩罚参数的几何衰减来确保收敛。在测量设计满足割限制等距性质的条件下，我们证明了估计信号的全局恢复保证。对于标准高斯设计，所需的测量次数与图结构无关，并且分别通过多项式和对数因子改进了在一维直线和二维晶格图上总变差（TV）压缩感知的最坏情况保证。对于一些变点信号和梯度稀疏幻影图像的例子，在中等欠采样以及中等到高信噪比的情况下，与TV正则化相比，该方法在经验上产生了更低的均方恢复误差。
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.