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

• 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?)
• A Probabilistic and RIPless Theory of Compressed Sensing
• A consistent and stable approach to generalized sampling
• A mathematical introduction to compressive 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
• 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
• RIPless compressed sensing from anisotropic measurements
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• 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)

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

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)