Stability and instance optimality for Gaussian measurements in compressed sensing

DOI10.1007/s10208-009-9046-4zbMath1189.68060OpenAlexW2036850226MaRDI QIDQ2269902

Przemysław Wojtaszczyk

Publication date: 12 March 2010

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-009-9046-4

zbMATH Keywords

signal recoverysparse approximationcompressed sensing\(\ell _{1}\)-minimizationrestricted isometry conditionGaussian measurement matrix

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Randomized algorithms (68W20)

Related Items (22)

Sparse recovery from inaccurate saturated measurements ⋮ Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames ⋮ An orthogonal method for measurement matrix optimization ⋮ On the geometry of polytopes generated by heavy-tailed random vectors ⋮ On the robustness of noise-blind low-rank recovery from rank-one measurements ⋮ Robust recovery of a kind of weighted l1-minimization without noise level ⋮ Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations ⋮ Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing ⋮ Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries ⋮ Democracy in action: quantization, saturation, and compressive sensing ⋮ Signal recovery under mutual incoherence property and oracle inequalities ⋮ Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\) ⋮ Restricted \(p\)-isometry property and its application for nonconvex compressive sensing ⋮ Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization ⋮ Sparse recovery by non-convex optimization - instance optimality ⋮ Restricted isometry property for matrices whose entries are random variables belonging to some Orlicz spaces $L_U(\Omega )$ ⋮ Gabor Analysis for Imaging ⋮ Instance-optimality in probability with an \(\ell _1\)-minimization decoder ⋮ Hard thresholding pursuit algorithms: number of iterations ⋮ One-Bit Compressed Sensing by Linear Programming ⋮ On the robustness of minimum norm interpolators and regularized empirical risk minimizers ⋮ AdaBoost and robust one-bit compressed sensing

Cites Work

• Instance-optimality in probability with an \(\ell _1\)-minimization decoder
• The restricted isometry property and its implications for compressed sensing
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• A simple proof of the restricted isometry property for random matrices
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Smallest singular value of random matrices and geometry of random polytopes
• Reconstruction and subgaussian processes
• Compressed sensing and best 𝑘-term approximation
• Decoding by Linear Programming
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Compact Groups of Operators on Subproportional Quotients of l₁^m
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• Unnamed Item
• Unnamed Item

This page was built for publication: Stability and instance optimality for Gaussian measurements in compressed sensing