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

DOI10.1109/TIT.2005.862083zbMath1231.94017DBLPjournals/tit/CandesRT06arXivmath/0409186OpenAlexW2145096794WikidataQ55895078 ScholiaQ55895078MaRDI QIDQ3546643

Emmanuel J. Candès, Justin Romberg, Terence C. 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 optimization random matrices uncertainty principle image reconstruction free probability sparsity trigonometric expansions duality in optimization total-variation minimization

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

Solution of the problem on image reconstruction in computed tomography ⋮ Optimal sampling points in reproducing kernel Hilbert spaces ⋮ Wavelet frame based image restoration via combined sparsity and nonlocal prior of coefficients ⋮ Wavelet inpainting with the \(\ell_{0}\) sparse regularization ⋮ Image reconstruction from undersampled Fourier data using the polynomial annihilation transform ⋮ 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 ⋮ 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 ⋮ Deterministic convolutional compressed sensing matrices ⋮ Coherence of sensing matrices coming from algebraic-geometric codes ⋮ Matrix sparsification and the sparse null space problem ⋮ 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 ⋮ Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods ⋮ 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory ⋮ Robust sparse phase retrieval made easy ⋮ A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions ⋮ Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies ⋮ Block sparse recovery via mixed \(l_2/l_1\) minimization ⋮ Waveform design and high-resolution imaging of cognitive radar based on compressive sensing ⋮ Reweighted minimization model for MR image reconstruction with split Bregman method ⋮ Sparse microwave imaging: principles and applications ⋮ Sparse SAR imaging based on \(L_{1/2}\) regularization ⋮ Compressed sensing SAR imaging based on sparse representation in fractional Fourier domain ⋮ 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 ⋮ The geometry of least squares in the 21st century ⋮ Fast alternating linearization methods for minimizing the sum of two convex functions ⋮ Sparse solutions to random standard quadratic optimization problems ⋮ Simple bounds for recovering low-complexity models ⋮ Improved compressed sensing-based algorithm for sparse-view CT image reconstruction ⋮ Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions ⋮ Parameter estimation for nonincreasing exponential sums by Prony-like methods ⋮ Sparse nonnegative matrix underapproximation and its application to hyperspectral image analysis ⋮ Reconstruction of a low-rank matrix in the presence of Gaussian noise ⋮ Systems of MDS codes from units and idempotents ⋮ Remote sensing via \(\ell_1\)-minimization ⋮ Sharp recovery bounds for convex demixing, with applications ⋮ Nonconvex compressed sampling of natural images and applications to compressed MR imaging ⋮ Wavelet compressive sampling signal reconstruction using upside-down tree structure ⋮ Restricted isometries for partial random circulant matrices ⋮ Recovery of sparsest signals via \(\ell^q \)-minimization ⋮ An empirical feature-based learning algorithm producing sparse approximations ⋮ SpicyMKL: a fast algorithm for multiple kernel learning with thousands of kernels ⋮ An approximation theory of matrix rank minimization and its application to quadratic equations ⋮ Smoothed state estimates under abrupt changes using sum-of-norms regularization ⋮ Sparse Legendre expansions via \(\ell_1\)-minimization ⋮ The residual method for regularizing ill-posed problems ⋮ Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization ⋮ Two are better than one: fundamental parameters of frame coherence ⋮ Sparsity enforcing edge detection method for blurred and noisy Fourier data ⋮ Uniform estimates for order statistics and Orlicz functions ⋮ Compressed labeling on distilled labelsets for multi-label learning ⋮ 2D sparse signal recovery via 2D orthogonal matching pursuit ⋮ Exact reconstruction using Beurling minimal extrapolation ⋮ Uniqueness conditions for low-rank matrix recovery ⋮ Convex feasibility modeling and projection methods for sparse signal recovery ⋮ Average best \(m\)-term approximation ⋮ Compressive sensing of analog signals using discrete prolate spheroidal sequences ⋮ Particle swarm optimization of compression measurement for signal detection ⋮ Iterative design of concentration factors for jump detection ⋮ New bounds for RIC in compressed sensing ⋮ Alternating direction method of multipliers for sparse principal component analysis ⋮ Scalable anomaly detection in large homogeneous populations ⋮ An infeasible-point subgradient method using adaptive approximate projections ⋮ 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 ⋮ On block coherence of frames ⋮ Inexact alternating-direction-based contraction methods for separable linearly constrained convex optimization ⋮ First-order optimality condition of basis pursuit denoise problem ⋮ Sparse recovery on Euclidean Jordan algebras ⋮ Subband adaptive filtering with \(l_1\)-norm constraint for sparse system identification ⋮ Nonmonotone Barzilai-Borwein gradient algorithm for \(\ell_1\)-regularized nonsmooth minimization in compressive sensing ⋮ Sparse time-frequency representation of nonlinear and nonstationary data ⋮ Robustness of orthogonal matching pursuit under restricted isometry property ⋮ Analysis of orthogonal multi-matching pursuit under restricted isometry property ⋮ 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 ⋮ Latent variable graphical model selection via convex optimization ⋮ Discovering governing equations from data by sparse identification of nonlinear dynamical systems ⋮ Random projections for Bayesian regression ⋮ Empirical average-case relation between undersampling and sparsity in X-ray CT ⋮ 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

Cites Work

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