论文标题
压缩感应具有一维总变化：通过不均匀恢复打破样品复杂性屏障（ITWIST'20）
Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery (iTWIST'20)
论文作者
论文摘要
本文研究了一个空间维度中的总变异最小化，以从不足采样的高斯测量值中恢复梯度 - 帕克斯信号。最近确定了所需的采样率状态的界限，即只有$ 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）$测量的可能性很高。特别是，此保证允许通过在间隔定义的分段常数函数的离散化引起的信号。本文是我们最近工作的主要结果的简短摘要[ARXIV：2001.09952]。
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 the latter sampling rate does not reflect the typical behavior of total variation minimization. Indeed, this 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 present paper serves as a short summary of the main results in our recent work [arxiv:2001.09952].
