On the role of total variation in compressed sensing

DOI10.1137/140978569zbMATH Open1381.94038arXiv1407.5339OpenAlexW2107034604MaRDI QIDQ5250010FDOQ5250010

Clarice Poon

Publication date: 15 May 2015

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

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$.

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

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

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)

Cites Work

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

Cited In (17)

• Hyperbolic Wavelet Frames and Multiresolution in the Weighted Bergman Spaces
• \(\boldsymbol{L_1-\beta L_q}\) Minimization for Signal and Image Recovery
• Compressed Sensing Photoacoustic Tomography Reduces to Compressed Sensing for Undersampled Fourier Measurements
• BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING
• Reconstruction Methods in THz Single-Pixel Imaging
• Compressive Sensing with Redundant Dictionaries and Structured Measurements
• WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions
• Short Communication: Localized Adversarial Artifacts for Compressed Sensing MRI
• Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
• Improved Recovery Guarantees and Sampling Strategies for TV Minimization in Compressive Imaging
• NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems
• High-Accuracy Total Variation With Application to Compressed Video Sensing
• Stable Image Reconstruction Using Transformed Total Variation Minimization
• Geometric properties of solutions to the total variation denoising problem
• Enhanced total variation minimization for stable image reconstruction
• Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
• Compressive time-of-flight 3D imaging using block-structured sensing matrices

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)