Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery
share
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 R^n is only possible with m ≳√(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 ≳ 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 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.
READ FULL TEXT