Near-optimal compressed sensing guarantees for total variation minimization
arXiv:1210.3098 · doi:10.1109/TIP.2013.2264681
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.
References in corpus (2)
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 -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