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

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

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)

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
• Compressive sampling
• 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)

• Inexact accelerated augmented Lagrangian methods
• Structured random measurements in signal processing
• Sparse polynomial chaos expansions: literature survey and benchmark
• Systems of MDS codes from units and idempotents
• Remote sensing via \(\ell_1\)-minimization
• Sharp recovery bounds for convex demixing, with applications
• Convex feasibility modeling and projection methods for sparse signal recovery
• Non-convex sparse regularisation
• Nonconvex compressed sampling of natural images and applications to compressed MR imaging
• Wavelet compressive sampling signal reconstruction using upside-down tree structure
• Convergence of the linearized Bregman iteration for \(\ell _1\)-norm minimization
• On the linear independence of spikes and sines
• An improved fast iterative shrinkage thresholding algorithm for image deblurring
• Accelerated linearized Bregman method
• Random sampling in reproducing kernel subspaces of \(L^p(\mathbb{R}^n)\)
• A generalized inertial proximal alternating linearized minimization method for nonconvex nonsmooth problems
• Efficient algorithms for solving the \(p\)-Laplacian in polynomial time
• An empirical feature-based learning algorithm producing sparse approximations
• Smoothed state estimates under abrupt changes using sum-of-norms regularization
• First-order methods for convex optimization
• Reproducing kernel Banach spaces with the \(\ell^{1}\) norm. II: Error analysis for regularized least square regression
• A new approximation of the matrix rank function and its application to matrix rank minimization
• Generalized sampling and infinite-dimensional compressed sensing
• Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization
• Sparsity enforcing edge detection method for blurred and noisy Fourier data
• Uniform estimates for order statistics and Orlicz functions
• Iterative design of concentration factors for jump detection
• Tensor theta norms and low rank recovery
• An alternating minimization method for robust principal component analysis
• On deterministic sketching and streaming for sparse recovery and norm estimation
• Partial \(S\)-goodness for partially sparse signal recovery
• Three novel edge detection methods for incomplete and noisy spectral data
• Approximation error in regularized SVD-based Fourier continuations
• Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery
• Adaptive data analysis via sparse time-frequency representation
• A linearly convergent algorithm for solving a class of nonconvex/affine feasibility problems
• Compressed labeling on distilled labelsets for multi-label learning
• 2D sparse signal recovery via 2D orthogonal matching pursuit
• Instance-optimality in probability with an \(\ell _1\)-minimization decoder
• Uniqueness conditions for low-rank matrix recovery
• Average best \(m\)-term approximation
• Mixed linear system estimation and identification
• Optimal \(D\)-RIP bounds in compressed sensing
• A unified approach to uniform signal recovery from nonlinear observations
• A polynomial case of the cardinality-constrained quadratic optimization problem
• Compressive sensing of analog signals using discrete prolate spheroidal sequences
• Particle swarm optimization of compression measurement for signal detection
• Nonlinear least squares in \(\mathbb R^{N}\)
• Improved bounds for the RIP of subsampled circulant matrices
• A class of alternating linearization algorithms for nonsmooth convex optimization
• New bounds for RIC in compressed sensing
• Scalable anomaly detection in large homogeneous populations
• An infeasible-point subgradient method using adaptive approximate projections
• Low rank tensor recovery via iterative hard thresholding
• Where did the tumor start? An inverse solver with sparse localization for tumor growth models
• A bi‐level programming framework for identifying optimal parameters in portfolio selection
• Sparse estimation via lower-order penalty optimization methods in high-dimensional linear regression
• Inferring stable genetic networks from steady-state data
• Sparse reconstruction with multiple Walsh matrices
• Time-frequency localization and sampling of multiband signals
• First-order optimality condition of basis pursuit denoise problem
• Sparse recovery on Euclidean Jordan algebras
• Nonmonotone Barzilai-Borwein gradient algorithm for \(\ell_1\)-regularized nonsmooth minimization in compressive sensing
• A modified Newton projection method for \(\ell _1\)-regularized least squares image deblurring
• Sparse time-frequency representation of nonlinear and nonstationary data
• A sharp nonasymptotic bound and phase diagram of \(L_{1/2}\) regularization
• An ADMM algorithm for second-order TV-based MR image reconstruction
• Compressive optical deflectometric tomography: a constrained total-variation minimization approach
• Compressed sensing with coherent tight frames via \(l_q\)-minimization for \(0 < q \leq 1\)
• Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing
• A unified approach for minimizing composite norms
• Concave programming for finding sparse solutions to problems with convex constraints
• A convergent overlapping domain decomposition method for total variation minimization
• A variable fixing version of the two-block nonlinear constrained Gauss-Seidel algorithm for \(\ell_1\)-regularized least-squares
• Efficient dual ADMMs for sparse compressive sensing MRI reconstruction
• Recovery of low-rank matrices based on the rank null space properties
• Compressed sensing SAR imaging based on sparse representation in fractional Fourier domain
• Reweighted minimization model for MR image reconstruction with split Bregman method
• Waveform design and high-resolution imaging of cognitive radar based on compressive sensing
• Sparse microwave imaging: principles and applications
• Sparse SAR imaging based on \(L_{1/2}\) regularization
• An approximation theory of matrix rank minimization and its application to quadratic equations
• Solving basis pursuit: heuristic optimality check and solver comparison
• Three deterministic constructions of compressed sensing matrices with low coherence
• Compressed sensing of low-rank plus sparse matrices
• Exact optimization for the \(\ell ^{1}\)-compressive sensing problem using a modified Dantzig-Wolfe method
• The restricted isometry property for time-frequency structured random matrices
• Accelerated Bregman method for linearly constrained \(\ell _1-\ell _2\) minimization
• \(s\)-goodness for low-rank matrix recovery
• Uncertainty in time-frequency representations on finite Abelian groups and applications
• Sparse solutions to random standard quadratic optimization problems
• Restricted \(p\)-isometry property and its application for nonconvex compressive sensing
• On compressive sensing applied to radar
• Compressive sensing for subsurface imaging using ground penetrating radar
• A sharp RIP condition for orthogonal matching pursuit
• Sparse nonnegative matrix underapproximation and its application to hyperspectral image analysis
• Sparsity in time-frequency representations
• Breaking the coherence barrier: a new theory for compressed sensing
• A geometric analysis of subspace clustering with outliers
• Sobolev duals for random frames and \(\varSigma \varDelta \) quantization of compressed sensing measurements

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)