Near-optimal compressed sensing guarantees for total variation minimization

Abstract

Consider the problem of reconstructing a multidimensional signal from an underdetermined set of measurements, as in the setting of compressed sensing. Without any additional assumptions, this problem is ill-posed. However, for signals such as natural images or movies, the minimal total variation estimate consistent with the measurements often produces a good approximation to the underlying signal, even if the number of measurements is far smaller than the ambient dimensionality. This paper extends recent reconstruction guarantees for two-dimensional images to signals of arbitrary dimension d>1 and to isotropic total variation problems. To be precise, we show that a multidimensional signal x can be reconstructed from O(sd*log(N^d)) linear measurements using total variation minimization to within a factor of the best s-term approximation of its gradient. The reconstruction guarantees we provide are necessarily optimal up to polynomial factors in the spatial dimension d.

Cited by in corpus (12)

• Guaranteed Tensor Recovery Fused Low-rankness and Smoothness
• Solving Inverse Problems With Deep Neural Networks -- Robustness Included?
• Jump-sparse and sparse recovery using Potts functionals
• How little data is enough? Phase-diagram analysis of sparsity-regularized X-ray CT
• Testable uniqueness conditions for empirical assessment of undersampling levels in total variation-regularized x-ray CT
• One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimizations
• Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery
• Convex recovery of continuous domain piecewise constant images from non-uniform Fourier samples
• Robust analysis ${\ell }_1$-recovery from Gaussian measurements and total variation minimization
• Living near the edge: A lower-bound on the phase transition of total variation minimization
• Enhanced total variation minimization for stable image reconstruction
• Efficient Least Residual Greedy Algorithms for Sparse Recovery