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

DOI10.1109/TIT.2005.862083zbMATH Open1231.94017DBLPjournals/tit/CandesRT06arXivmath/0409186OpenAlexW2145096794WikidataQ55895078 ScholiaQ55895078MaRDI QIDQ3546643FDOQ3546643

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

Publication date: 21 December 2008

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

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

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

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

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)

Cites Work

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

Cited In (only showing first 100 items - show all)

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

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)