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 \(\ell^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)

• Exact reconstruction using Beurling minimal extrapolation
• Design of structured dynamic output-feedback controllers for interconnected systems
• A non-adapted sparse approximation of PDEs with stochastic inputs
• Compressive sensing based machine learning strategy for characterizing the flow around a cylinder with limited pressure measurements
• Compressive Sensing
• Sparse fusion frames: existence and construction
• Computational and statistical tradeoffs via convex relaxation
• On the conditioning of random subdictionaries
• 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
• Subband adaptive filtering with \(l_1\)-norm constraint for sparse system identification
• Null space conditions and thresholds for rank minimization
• A review of numerical methods for nonlinear partial differential equations
• Image reconstruction from undersampled Fourier data using the polynomial annihilation transform
• A new computational method for the sparsest solutions to systems of linear equations
• Improved compressed sensing-based algorithm for sparse-view CT image reconstruction
• Simple bounds for recovering low-complexity models
• MR image reconstruction based on iterative split Bregman algorithm and nonlocal total variation
• Equivalence and strong equivalence between the sparsest and least \(\ell _1\)-norm nonnegative solutions of linear systems and their applications
• Exact recovery of non-uniform splines from the projection onto spaces of algebraic polynomials
• Deterministic construction of compressed sensing matrices from codes
• Deep Learning--Based Dictionary Learning and Tomographic Image Reconstruction
• A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions
• RIPless compressed sensing from anisotropic measurements
• Compressed sensing from a harmonic analysis point of view
• Analysis of orthogonal multi-matching pursuit under restricted isometry property
• Robustness of orthogonal matching pursuit under restricted isometry property
• Suprema of chaos processes and the restricted isometry property
• The \(L^1\)-Potts functional for robust jump-sparse reconstruction
• Probability of unique integer solution to a system of linear equations
• A new proximal iterative hard thresholding method with extrapolation for \(\ell _0\) minimization
• Accelerated iterative hard thresholding algorithm for \(l_0\) regularized regression problem
• A constrained optimization reformulation and a feasible descent direction method for \(L_{1/2}\) regularization
• Some greedy algorithms for sparse polynomial chaos expansions
• Efficient block-coordinate descent algorithms for the group Lasso
• A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization
• Bayesian signal detection with compressed measurements
• Non-smooth equations based method for \(\ell_1\)-norm problems with applications to compressed sensing
• Restricted isometries for partial random circulant matrices
• Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies
• Typical reconstruction limits for distributed compressed sensing based on \(\ell_{2,1} \)-norm minimization and Bayesian optimal reconstruction
• Block sparse recovery via mixed \(l_2/l_1\) minimization
• On the continuity of characteristic functionals and sparse stochastic modeling
• Randomization of data acquisition and \(\ell_{1}\)-optimization (recognition with compression)
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• On uncertainty principles in the finite dimensional setting
• Compressed sensing with coherent and redundant dictionaries
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
• An alternating minimization method for matrix completion problems
• Two are better than one: fundamental parameters of frame coherence
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation
• Nonlinear residual minimization by iteratively reweighted least squares
• Undersampled MR image reconstruction with data-driven tight frame
• A Bayesian compressed-sensing approach for reconstructing neural connectivity from subsampled anatomical data
• Detecting Fourier subspaces
• Random sampling of sparse trigonometric polynomials
• Iterative image reconstruction for limited-angle CT using optimized initial image
• Carl's inequality for quasi-Banach spaces
• A model of regularization parameter determination in low-dose X-ray CT reconstruction based on dictionary learning
• Accelerated compressed sensing based CT image reconstruction
• Data-driven design of two degree-of-freedom nonlinear controllers: the \(\operatorname{D}^2\)-IBC approach
• Compressive wave computation
• On the existence of optimal unions of subspaces for data modeling and clustering
• Sparse solutions of linear complementarity problems
• Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere
• Approximate sparse linear regression
• Conjugate gradient acceleration of iteratively re-weighted least squares methods
• Improved adaptive sparse channel estimation using mixed square/fourth error criterion
• Compressed sensing and dynamic mode decomposition
• On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization
• Empirical processes with a bounded \(\psi_1\) diameter
• Off-grid DOA estimation via real-valued sparse Bayesian method in compressed sensing
• Compressed blind signal reconstruction model and algorithm
• Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery
• Convergence of fixed-point continuation algorithms for matrix rank minimization
• On Convex Finite-Dimensional Variational Methods in Imaging Sciences and Hamilton--Jacobi Equations
• Anomaly detection in large-scale data stream networks
• Phase retrieval for sparse signals
• Accelerated projected gradient method for linear inverse problems with sparsity constraints
• Optimal non-linear models for sparsity and sampling
• An algorithm solving compressive sensing problem based on maximal monotone operators
• Deterministic convolutional compressed sensing matrices
• Coherence of sensing matrices coming from algebraic-geometric codes
• Full spark frames
• Sharp MSE bounds for proximal denoising
• Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
• Effective band-limited extrapolation relying on Slepian series and \(\ell^1\) regularization
• Image denoising by generalized total variation regularization and least squares fidelity
• MultiDimensional Sparse Super-Resolution
• Guarantees of total variation minimization for signal recovery
• Super-resolution of point sources via convex programming
• Distributed compressed sensing for multi-sourced fusion and secure signal processing in private cloud
• On block coherence of frames
• The residual method for regularizing ill-posed problems
• Analysis \(\ell_1\)-recovery with frames and Gaussian measurements
• A survey of compressed sensing
• Multicontrast MRI reconstruction with structure-guided total variation
• Quasi-linear compressed sensing
• Minimization of \(\ell_{1-2}\) for compressed sensing
• Two-dimensional digital filters with sparse coefficients

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)