On the role of total variation in compressed sensing

DOI10.1137/140978569MaRDI QIDQ5250010zbMATH OpenOpenAlexFDO

Authors Clarice Poon

Publication date 15 May 2015

Published in SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.5339

zbMATH Keywords

compressed sensingtotal variation minimization

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Abstract: This paper considers the problem of recovering a one or two dimensional discrete signal which is approximately sparse in its discrete gradient from an incomplete subset of its discrete Fourier coefficients which have been corrupted with noise. We prove that in order to obtain a reconstruction which is robust to noise and stable to inexact gradient sparsity of order $s$ with high probability, it suffices to draw $mathcalO(slogN)$ of the available Fourier coefficients uniformly at random. However, we also show that if one draws $mathcalO(slogN)$ samples in accordance to a particular distribution which concentrates on the low Fourier frequencies, then the stability bounds which can be guaranteed are optimal up to $log$ factors. Finally, we prove that in the one dimensional case where the underlying signal is gradient sparse and its sparsity pattern satisfies a minimum separation condition, then to guarantee exact recovery with high probability, for some $M<N$, it suffices to draw $mathcalO(slogMlogs)$ samples uniformly at random from the Fourier coefficients whose frequencies are no greater than $M$.

Recommendations

• Compressed sensing with 1D total variation: breaking sample complexity barriers via non-uniform recovery
• Guarantees of total variation minimization for signal recovery
• Stable signal recovery from incomplete and inaccurate measurements
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Stable image reconstruction using total variation minimization

Cites work

• A consistent and stable approach to generalized sampling
• A mathematical introduction to compressive sensing
• A Probabilistic and RIPless Theory of Compressed Sensing
• A wavelet tour of signal processing. The sparse way.
• An introduction to total variation for image analysis
• Breaking the coherence barrier: a new theory for compressed sensing
• Compressed Sensing Off the Grid
• scientific article; zbMATH DE number 3944477 (Why is no real title available?)
• scientific article; zbMATH DE number 3551404 (Why is no real title available?)
• scientific article; zbMATH DE number 1448982 (Why is no real title available?)
• scientific article; zbMATH DE number 5180707 (Why is no real title available?)
• Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Nonlinear approximation and the space BV[inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="01i" /]
• Nonlinear total variation based noise removal algorithms
• On sparse reconstruction from Fourier and Gaussian measurements
• Parameter estimation for exponential sums by approximate prony method
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• RIPless compressed sensing from anisotropic measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Stable and Robust Sampling Strategies for Compressive Imaging
• Stable image reconstruction using total variation minimization
• Super-resolution from noisy data
• The Split Bregman Method for L1-Regularized Problems
• Towards a Mathematical Theory of Super‐resolution
• User-friendly tail bounds for sums of random matrices

Cited in

(23)

• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Variations on a theorem of Candès, Romberg and Tao
• Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
• Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
• NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems
• Breaking the coherence barrier: a new theory for compressed sensing
• Geometric properties of solutions to the total variation denoising problem
• Reconstruction methods in THz single-pixel imaging
• Compressive sensing with redundant dictionaries and structured measurements
• High-Accuracy Total Variation With Application to Compressed Video Sensing
• Guarantees of total variation minimization for signal recovery
• On oracle-type local recovery guarantees in compressed sensing
• WARPd: a linearly convergent first-order primal-dual algorithm for inverse problems with approximate sharpness conditions
• Compressed sensing with 1D total variation: breaking sample complexity barriers via non-uniform recovery
• Stable image reconstruction using transformed total variation minimization
• Performance bounds for co-/sparse box constrained signal recovery
• Hyperbolic wavelet frames and multiresolution in the weighted Bergman spaces
• Compressive time-of-flight 3D imaging using block-structured sensing matrices
• Compressed sensing photoacoustic tomography reduces to compressed sensing for undersampled Fourier measurements
• Improved Recovery Guarantees and Sampling Strategies for TV Minimization in Compressive Imaging
• Short Communication: Localized Adversarial Artifacts for Compressed Sensing MRI
• \(\boldsymbol{L_1-\beta L_q}\) Minimization for Signal and Image Recovery
• Enhanced total variation minimization for stable image reconstruction

This page was built for publication: On the role of total variation in compressed sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5250010)