2020/09/07 by Martin Genzel, Genzel, Martin, Maximilian März +3
Engineering · #Electrical and Bioimpedance Tomography #FOS: Computer and information sciences #Information Theory (cs.IT) #Photoacoustic and Ultrasonic Imaging #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2009.03694
openalex publication_date 2020/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℝn is only possible with m \gtrsim √(s n) ⋅ 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 √(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 ⋅ 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].