Guarantees of total variation minimization for signal recovery

DOI10.1093/IMAIAI/IAV009zbMATH Open1387.94028arXiv1301.6791OpenAlexW2568311054MaRDI QIDQ4603592FDOQ4603592

Authors: Jian-Feng Cai, Weiyu Xu 

Publication date: 16 February 2018

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: In this paper, we consider using total variation minimization to recover signals whose gradients have a sparse support, from a small number of measurements. We establish the proof for the performance guarantee of total variation (TV) minimization in recovering emph{one-dimensional} signal with sparse gradient support. This partially answers the open problem of proving the fidelity of total variation minimization in such a setting cite{TVMulti}. In particular, we have shown that the recoverable gradient sparsity can grow linearly with the signal dimension when TV minimization is used. Recoverable sparsity thresholds of TV minimization are explicitly computed for 1-dimensional signal by using the Grassmann angle framework. We also extend our results to TV minimization for multidimensional signals. Stability of recovering signal itself using 1-D TV minimization has also been established through a property called "almost Euclidean property for 1-dimensional TV norm". We further give a lower bound on the number of random Gaussian measurements for recovering 1-dimensional signal vectors with $N$ elements and $K$-sparse gradients. Interestingly, the number of needed measurements is lower bounded by $Omega((NK{)}^{frac12})$, rather than the $O(Klog(N/K))$ bound frequently appearing in recovering $K$-sparse signal vectors.

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

Recommendations

• A note on the guarantees of total variation minimization
• Compressed sensing with 1D total variation: breaking sample complexity barriers via non-uniform recovery
• Robust analysis ℓ₁-recovery from Gaussian measurements and total variation minimization
• On the role of total variation in compressed sensing
• Stable image reconstruction using total variation minimization

zbMATH Keywords

total variationphase transitionGaussian widthhigh dimensional geometry

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cites Work

• Nonlinear total variation based noise removal algorithms
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On total variation minimization and surface evolution using parametric maximum flows
• Decoding by Linear Programming
• The Split Bregman Method for L1-Regularized Problems
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Stable image reconstruction using total variation minimization
• Linear convergence rates for Tikhonov regularization with positively homogeneous functionals
• A mathematical introduction to compressive sensing
• Split Bregman methods and frame based image restoration
• Highly Robust Error Correction byConvex Programming
• Precise Stability Phase Transitions for $\ell_1$ Minimization: A Unified Geometric Framework
• Image restoration: total variation, wavelet frames, and beyond
• Neighborliness of randomly projected simplices in high dimensions
• High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
• On sparse reconstruction from Fourier and Gaussian measurements
• The restricted isometry property and its implications for compressed sensing
• The cosparse analysis model and algorithms
• The convex geometry of linear inverse problems
• Compressed Sensing and Redundant Dictionaries
• Title not available (Why is that?)
• Living on the edge: phase transitions in convex programs with random data
• Compressed sensing with coherent and redundant dictionaries
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• Robust Sparse Analysis Regularization
• Stable Signal Reconstruction via $\ell^1$-Minimization in Redundant, Non-Tight Frames
• Title not available (Why is that?)
• Total variation based convex filters for medical imaging
• Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization
• A total variation enhanced modified gradient algorithm for profile reconstruction
• Sparse Error Correction From Nonlinear Measurements With Applications in Bad Data Detection for Power Networks

Cited In (18)

• A note on the guarantees of total variation minimization
• Block-sparse recovery of semidefinite systems and generalized null space conditions
• On the role of total variation in compressed sensing
• Stable local-smooth principal component pursuit
• Compressed sensing with 1D total variation: breaking sample complexity barriers via non-uniform recovery
• Relation between total variation and persistence distance and its application in signal processing
• Signal Recovery With Certain Involved Convex Data-Fidelity Constraints
• Robust analysis ℓ₁-recovery from Gaussian measurements and total variation minimization
• A unified approach to uniform signal recovery from nonlinear observations
• Improved Recovery Guarantees and Sampling Strategies for TV Minimization in Compressive Imaging
• Iterative Potts minimization for the recovery of signals with discontinuities from indirect measurements: the multivariate case
• Signal Recovery on Graphs: Variation Minimization
• Stable image reconstruction using total variation minimization
• \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
• Sampling rates for \(\ell^1\)-synthesis
• Enhanced total variation minimization for stable image reconstruction
• Theory and fast learned solver for \(\ell^1\)-TV regularization
• Reconstruction methods in THz single-pixel imaging

This page was built for publication: Guarantees of total variation minimization for signal recovery

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