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)

• Recovering network topologies via Taylor expansion and compressive sensing
• Empirical average-case relation between undersampling and sparsity in X-ray CT
• Iterative hard thresholding for compressed sensing
• A simple proof of the restricted isometry property for random matrices
• Title not available (Why is that?)
• Sparse Legendre expansions via \(\ell_1\)-minimization
• A note on the complexity of proximal iterative hard thresholding algorithm
• The first-order necessary conditions for sparsity constrained optimization
• Strong convergence of a modified proximal algorithm for solving the lasso
• Sparsity Based Nonlocal Image Restoration: An Alternating Optimization Approach
• Inexact alternating-direction-based contraction methods for separable linearly constrained convex optimization
• Fixed point and Bregman iterative methods for matrix rank minimization
• Recovery of sparsest signals via \(\ell^q \)-minimization
• SpicyMKL: a fast algorithm for multiple kernel learning with thousands of kernels
• Approximation accuracy, gradient methods, and error bound for structured convex optimization
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• A unified primal-dual algorithm framework based on Bregman iteration
• Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
• A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
• Iterative hard thresholding methods for \(l_0\) regularized convex cone programming
• Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming
• An efficient augmented Lagrangian method with applications to total variation minimization
• A new generalized shrinkage conjugate gradient method for sparse recovery
• Solution of the problem on image reconstruction in computed tomography
• Optimal sampling points in reproducing kernel Hilbert spaces
• Reconstruction of a low-rank matrix in the presence of Gaussian noise
• A primal dual active set with continuation algorithm for the \(\ell^0\)-regularized optimization problem
• Variational Bayesian strategies for high-dimensional, stochastic design problems
• Properties and iterative methods for the lasso and its variants
• Discussion: Latent variable graphical model selection via convex optimization
• Segmentation of ARX-models using sum-of-norms regularization
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Sparse recovery by non-convex optimization - instance optimality
• Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Sparse recovery under weak moment assumptions
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Wavelet frame based image restoration via combined sparsity and nonlocal prior of coefficients
• Wavelet inpainting with the \(\ell_{0}\) sparse regularization
• Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing
• Matrix estimation by universal singular value thresholding
• Rejoinder: Latent variable graphical model selection via convex optimization
• High-dimensional change-point estimation: combining filtering with convex optimization
• The geometry of least squares in the 21st century
• Random projections of smooth manifolds
• Combinatorial sublinear-time Fourier algorithms
• Parameter estimation for nonincreasing exponential sums by Prony-like methods
• Towards a Mathematical Theory of Super‐resolution
• Fast Phase Retrieval from Local Correlation Measurements
• Accelerating gradient projection methods for \(\ell _1\)-constrained signal recovery by steplength selection rules
• Total variation wavelet inpainting
• Discussion: Latent variable graphical model selection via convex optimization
• Spectral compressive sensing
• Theory and applications of compressed sensing
• Local linear convergence for alternating and averaged nonconvex projections
• Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
• Exact matrix completion via convex optimization
• An efficient algorithm for \(\ell_{0}\) minimization in wavelet frame based image restoration
• Proximity algorithms for the L1/TV image denoising model
• Primal and dual alternating direction algorithms for \(\ell _{1}\)-\(\ell _{1}\)-norm minimization problems in compressive sensing
• Sparse polynomial chaos expansions via compressed sensing and D-optimal design
• Properties and iterative methods for the \(Q\)-lasso
• Variations on a theorem of Candès, Romberg and Tao
• A numerical exploration of compressed sampling recovery
• Alternating proximal gradient method for convex minimization
• The convex geometry of linear inverse problems
• Compressed sensing and matrix completion with constant proportion of corruptions
• On a unified view of nullspace-type conditions for recoveries associated with general sparsity structures
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Robust sparse phase retrieval made easy
• Efficient algorithms for robust and stable principal component pursuit problems
• TV-based reconstruction of periodic functions
• A framelet-based image inpainting algorithm
• Data-driven time-frequency analysis
• Linearized Bregman iterations for compressed sensing
• Necessary and sufficient conditions for linear convergence of ℓ1-regularization
• Compressed sensing and best 𝑘-term approximation
• The asymptotic distribution and Berry-Esseen bound of a new test for independence in high dimension with an application to stochastic optimization
• IMRO: A Proximal Quasi-Newton Method for Solving $\ell_1$-Regularized Least Squares Problems
• Title not available (Why is that?)
• Exact low-rank matrix recovery via nonconvex Schatten \(p\)-minimization
• The geometry of off-the-grid compressed sensing
• Fast alternating linearization methods for minimizing the sum of two convex functions
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Alternating direction method of multipliers for sparse principal component analysis
• Noncommutative Bennett and Rosenthal inequalities
• Iteratively reweighted least squares minimization for sparse recovery
• Latent variable graphical model selection via convex optimization
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Compressed modes for variational problems in mathematics and physics
• Sparse dynamics for partial differential equations
• A Continuous Exact $\ell_0$ Penalty (CEL0) for Least Squares Regularized Problem
• Discovering governing equations from data by sparse identification of nonlinear dynamical systems
• Random projections for Bayesian regression
• On the Compressive Spectral Method
• Estimating the dimension of a model
• Nuclear norm minimization for the planted clique and biclique problems
• The Dantzig selector and sparsity oracle inequalities
• $\ell _0$ Minimization for wavelet frame based image restoration
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation

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)