论文标题
压缩感测和1D总变化：通过不均匀恢复破坏样品复杂性屏障
Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery
论文作者
论文摘要
本文研究了一个空间维度中的总变异最小化，以从不足采样的高斯测量值中恢复梯度 - 帕克斯信号。最近确定了所需的采样率状态的界限，即只有$ m \ gtrsim \ sqrt {s n} \ cdot \ cdot \ cdot \ cdot \ cdot \ text {polylog}（polylog}（n）$测量，只有$ \ mathbb {r}^n $在$ \ mathbb {r}^n $中均匀恢复的范围。对于高维问题，这种情况尤其高于$ n $。但是，以前的经验发现似乎表明，这种抽样率并不能反映总变异最小化的典型行为。目前的工作提供了严格的分析，该分析破坏了$ \ sqrt {s n} $ - 瓶颈，用于大型“自然”信号。主要结果表明，如果信号矢量的跳转不连续性足够良好，则非均匀恢复成功，对于$ M \ gtrsim s \ cdot \ cdot \ text {polylog}（n）$测量的可能性很高。特别是，此保证允许通过在间隔定义的分段常数函数的离散化引起的信号。证明的关键要素是针对相关的圆锥高斯平均宽度的新型上限，该结合基于信号依赖性的，非Yadic Haar小波变换。此外，解决了稳定恢复的自然扩展。
This paper investigates total variation minimization in one spatial dimension for the recovery of gradient-sparse signals from undersampled Gaussian measurements. Recently established bounds for the required sampling rate state that uniform recovery of all $s$-gradient-sparse signals in $\mathbb{R}^n$ is only possible with $m \gtrsim \sqrt{s n} \cdot \text{PolyLog}(n)$ measurements. Such a condition is especially prohibitive for high-dimensional problems, where $s$ is much smaller than $n$. However, previous empirical findings seem to indicate that this sampling rate does not reflect the typical behavior of total variation minimization. The present work provides a rigorous analysis that breaks the $\sqrt{s n}$-bottleneck for a large class of "natural" signals. The main result shows that non-uniform recovery succeeds with high probability for $m \gtrsim s \cdot \text{PolyLog}(n)$ measurements if the jump discontinuities of the signal vector are sufficiently well separated. In particular, this guarantee allows for signals arising from a discretization of piecewise constant functions defined on an interval. The key ingredient of the proof is a novel upper bound for the associated conic Gaussian mean width, which is based on a signal-dependent, non-dyadic Haar wavelet transform. Furthermore, a natural extension to stable and robust recovery is addressed.
