Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

DOI10.1109/TIT.2005.862083MaRDI QIDQ3546643zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Emmanuel J. Candès, Justin Romberg, Terence Tao

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationsparsityimage reconstructionrandom matricesuncertainty principlefree probabilitytrigonometric expansionsduality in optimizationtotal-variation minimization

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Detection theory in information and communication theory (94A13) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Sampling theory in information and communication theory (94A20)

Abstract: This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal $fin{C}^N$ and a randomly chosen set of frequencies $Omega$ of mean size $auN$. Is it possible to reconstruct $f$ from the partial knowledge of its Fourier coefficients on the set $Omega$? A typical result of this paper is as follows: for each $M>0$, suppose that $f$ obeys ${\displaystyle }$ # {t, f(t) eq 0 } le alpha(M) cdot (log N)^{-1} cdot # Omega, ${\displaystyle }$ then with probability at least $1-O(N^{-M})$, $f$ can be reconstructed exactly as the solution to the $el{l}_1$ minimization problem ${\displaystyle }$ min_g sum_{t = 0}^{N-1} |g(t)|, quad ext{s.t.} hat g(omega) = hat f(omega) ext{for all} omega in Omega. ${\displaystyle }$ In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for $alpha$ which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp. The methodology extends to a variety of other setups and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one or two-dimensional) object from incomplete frequency samples--provided that the number of jumps (discontinuities) obeys the condition above--by minimizing other convex functionals such as the total-variation of $f$.

Recommendations

• Uncertainty Principles and Signal Recovery
• Stable signal recovery from incomplete and inaccurate measurements
• On robust signal reconstruction in noisy filter banks
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Reconstruction of signals: uniqueness and stable sampling
• Signal Reconstruction From Noisy Random Projections
• Discrete uncertainty principles and sparse signal processing
• Robust reconstruction of a signal from its unthresholded recurrence plot subject to disturbances
• Estimation and Uncertainty Quantification for Piecewise Smooth Signal Recovery
• Frequency domain analysis of robust signal estimators

Cites work

• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• An affine scaling methodology for best basis selection
• Atomic Decomposition by Basis Pursuit
• Breakdown of equivalence between the minimal ^1-norm solution and the sparsest solution
• Compressed sensing
• Compressive sampling
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• High-Resolution Radar via Compressed Sensing
• Quantitative robust uncertainty principles and optimally sparse decompositions
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• The gradient projection method with exact line search

Cited in

(only showing first 100 items - show all)

• Estimation and Uncertainty Quantification for Piecewise Smooth Signal Recovery
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• A new computational method for the sparsest solutions to systems of linear equations
• Compressive sensing with cross-validation and stop-sampling for sparse polynomial chaos expansions
• Inexact accelerated augmented Lagrangian methods
• Approximation methods for the recovery of shapes and images from gradients
• From linear system of equations to artificial intelligence -- the evolution journey of computer tomographic image reconstruction algorithms
• Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
• On recovery of discrete time signals with single-point spectrum degeneracy
• Typical reconstruction performance for distributed compressed sensing based on \(\ell_{2,1} \)-norm regularized least square and Bayesian optimal reconstruction: influences of noise
• Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction
• High-resolution signal recovery via generalized sampling and functional principal component analysis
• Compressed sensing reconstruction using expectation propagation
• Newton method for \(\ell_0\)-regularized optimization
• Empirical average-case relation between undersampling and sparsity in X-ray CT
• Compressive Sensing
• Modern Koopman theory for dynamical systems
• Newton-type optimal thresholding algorithms for sparse optimization problems
• MR image reconstruction based on iterative split Bregman algorithm and nonlocal total variation
• _1DecNet+: a new architecture framework by _1 decomposition and iteration unfolding for sparse feature segmentation
• $\ell _0$ Minimization for wavelet frame based image restoration
• Compressed sparse tensor based quadrature for vibrational quantum mechanics integrals
• A simple and flexible model order reduction method for FFT-based homogenization problems using a sparse sampling technique
• Convergence of a data-driven time-frequency analysis method
• Sparse low rank approximation of potential energy surfaces with applications in estimation of anharmonic zero point energies and frequencies
• Compressed-sensing-based gradient reconstruction for ghost imaging
• Compressive total variation for image reconstruction and restoration
• Iterative hard thresholding for compressed sensing
• Sparsest piecewise-linear regression of one-dimensional data
• Huberization image restoration model from incomplete multiplicative noisy data
• A Variable Density Sampling Scheme for Compressive Fourier Transform Interferometry
• Data-driven methods for quantitative imaging
• Super-resolution by means of Beurling minimal extrapolation
• Recovering network topologies via Taylor expansion and compressive sensing
• A simple proof of the restricted isometry property for random matrices
• On some aspects of approximation of ridge functions
• Signal reconstruction by conjugate gradient algorithm based on smoothing l₁-norm
• Sparse optimization of mutual synchronization in collectively oscillating networks
• A compressive sensing based privacy preserving outsourcing of image storage and identity authentication service in cloud
• Uncertainty relations for the support of quantum states
• Tensor sparse representation via Einstein product
• scientific article; zbMATH DE number 7370536 (Why is no real title available?)
• L2SR: learning to sample and reconstruct for accelerated MRI via reinforcement learning
• A nonconvex penalization algorithm with automatic choice of the regularization parameter in sparse imaging
• Systems of MDS codes from units and idempotents
• Remote sensing via _1-minimization
• Sharp recovery bounds for convex demixing, with applications
• Regularized least absolute deviation-based sparse identification of dynamical systems
• CS-MRI reconstruction based on the constrained TGV-shearlet scheme
• Structured random measurements in signal processing
• Compressive sensing based machine learning strategy for characterizing the flow around a cylinder with limited pressure measurements
• Spectral dynamics and regularization of incompletely and irregularly measured data
• Sparse estimation: an MMSE approach
• A new subband adaptive filtering algorithm for sparse system identification with impulsive noise
• Spectral Compressed Sensing via Projected Gradient Descent
• Linear total variation approximate regularized nuclear norm optimization for matrix completion
• Wavelet frame based scene reconstruction from range data
• Alternative fan-beam backprojection and adjoint operators
• Convex feasibility modeling and projection methods for sparse signal recovery
• Reconstruction of jointly sparse vectors via manifold optimization
• A note on the complexity of proximal iterative hard thresholding algorithm
• The first-order necessary conditions for sparsity constrained optimization
• Sparse Legendre expansions via _1-minimization
• Strong convergence of a modified proximal algorithm for solving the lasso
• Block-sparse compressed sensing: non-convex model and iterative re-weighted algorithm
• Nonconvex nonsmooth optimization via convex-nonconvex majorization-minimization
• Sparse polynomial chaos expansions: literature survey and benchmark
• The modified accelerated Bregman method for regularized basis pursuit problem
• Improved unitary uncertainty relations
• Compressed sensing in the spherical near-field to far-field transformation
• Elastic-Net Regularization: Iterative Algorithms and Asymptotic Behavior of Solutions
• Unbiasing in iterative reconstruction algorithms for discrete compressed sensing
• Tighter uncertainty principles for periodic signals in terms of frequency
• Inexact alternating-direction-based contraction methods for separable linearly constrained convex optimization
• Greedy approximate projection for magnetic resonance fingerprinting with partial volumes
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Nonsmoothness in machine learning: specific structure, proximal identification, and applications
• Sparse modeling approach to obtaining the shear viscosity from smeared correlation functions
• Minimizers of sparsity regularized Huber loss function
• Inverse potential problems for divergence of measures with total variation regularization
• Stability of 1-bit compressed sensing in sparse data reconstruction
• Temporal Huber regularization for DCE-MRI
• Convolution random sampling in multiply generated shift-invariant spaces of \(L^p(\mathbb{R}^d)\)
• Convergence and stability analysis of the half thresholding based few-view CT reconstruction
• Noncommutative uncertainty principles
• Tight and full spark Chebyshev frames with real entries and worst-case coherence analysis
• An unbiased approach to compressed sensing
• scientific article; zbMATH DE number 7053345 (Why is no real title available?)
• A diagonally scaled Newton-type proximal method for minimization of the models with nonsmooth composite cost functions
• Superiorization of EM algorithm and its application in single-photon emission computed tomography (SPECT)
• Sampling strategies for uncertainty reduction in categorical random fields: formulation, mathematical analysis and application to multiple-point simulations
• Compressive sensing adaptation for polynomial chaos expansions
• A preconditioning technique for first-order primal-dual splitting method in convex optimization
• Uniqueness of the minimal \(l_1\)-norm solution to the monotone linear complementarity problem
• Sparse approximation of fitting surface by elastic net
• Descending iterative hard thresholding: a robust approach to sparse recovery under heavy-tailed noise
• Gradient projection Newton pursuit for sparsity constrained optimization
• Convergence Results for Primal-Dual Algorithms in the Presence of Adjoint Mismatch
• An efficient radiation analysis approach through compressive model for laser driven inertial confinement fusion
• A new linearized split Bregman iterative algorithm for image reconstruction in sparse-view X-ray computed tomography

This page was built for publication: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

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