Compressed sensing and best 𝑘-term approximation

DOI10.1090/S0894-0347-08-00610-3zbMath1206.94008WikidataQ56688856 ScholiaQ56688856MaRDI QIDQ3079195

Albert Cohen, Wolfgang Dahmen, Ronald A. DeVore

Publication date: 2 March 2011

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

random matrices compressed sensing restricted isometry property null space property Gelfand width instance optimality in probability $\ell _1$-minimization best $k$-term approximation Gaussian and Bernoulli ensembles instance optimal decoders mixed instance optimality

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) Random matrices (algebraic aspects) (15B52) Information theory (general) (94A15) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

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

Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method ⋮ Refined analysis of sparse MIMO radar ⋮ One condition for solution uniqueness and robustness of both $\ell_1$-synthesis and $\ell_1$-analysis minimizations ⋮ Average Performance of the Sparsest Approximation Using a General Dictionary ⋮ Improved sparse Fourier approximation results: Faster implementations and stronger guarantees ⋮ Computing a quantity of interest from observational data ⋮ A Survey of Compressed Sensing ⋮ Two Algorithms for Compressed Sensing of Sparse Tensors ⋮ Unnamed Item ⋮ Deterministic construction of compressed sensing matrices with characters over finite fields ⋮ Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property ⋮ Recovery analysis for weighted $\ell_{1}$-minimization using the null space property ⋮ Error bounds for compressed sensing algorithms with group sparsity: A unified approach ⋮ A new bound on the block restricted isometry constant in compressed sensing ⋮ Compressed sensing for finite-valued signals ⋮ Sparsest representations and approximations of an underdetermined linear system ⋮ Compressive statistical learning with random feature moments ⋮ Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields ⋮ The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials ⋮ Optimal stable nonlinear approximation ⋮ Robust recovery of a kind of weighted l1-minimization without noise level ⋮ Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries ⋮ Recovery of low-rank matrices based on the rank null space properties ⋮ The null space property of the weighted ℓr − ℓ1 minimization ⋮ Heuristics for Finding Sparse Solutions of Linear Inequalities ⋮ Block sparse signal recovery via minimizing the block $q$-ratio sparsity ⋮ A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees ⋮ Sparse reconstruction via the mixture optimization model with iterative support estimate ⋮ Study on $L_1$ over $L_2$ Minimization for nonnegative signal recovery ⋮ A wonderful triangle in compressed sensing ⋮ Binary generalized orthogonal matching pursuit ⋮ Stable recovery of weighted sparse signals from phaseless measurements via weighted l₁ minimization ⋮ Sampling rates for $\ell^1$-synthesis ⋮ Optimal learning ⋮ A non-convex piecewise quadratic approximation of $\ell_0$ regularization: theory and accelerated algorithm ⋮ Capturing ridge functions in high dimensions from point queries ⋮ Unnamed Item ⋮ Complexity of approximation of functions of few variables in high dimensions ⋮ Compressive Sensing ⋮ Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing ⋮ BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING ⋮ Posterior information-based image measurement matrix optimization ⋮ Flavors of Compressive Sensing ⋮ Stability and robustness of $\ell_1$-minimizations with Weibull matrices and redundant dictionaries ⋮ On deterministic sketching and streaming for sparse recovery and norm estimation ⋮ On the sparsity of Lasso minimizers in sparse data recovery ⋮ Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets ⋮ Exact recovery of non-uniform splines from the projection onto spaces of algebraic polynomials ⋮ Stability analysis of a class of sparse optimization problems ⋮ An Introduction to Compressed Sensing ⋮ Sparse approximation based on a random overcomplete basis ⋮ Deterministic constructions of compressed sensing matrices ⋮ Deterministic Heavy Hitters with Sublinear Query Time ⋮ Mathematics of Analog‐to‐Digital Conversion ⋮ The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penalty ⋮ Necessary and sufficient conditions of solution uniqueness in 1-norm minimization ⋮ Stability and instance optimality for Gaussian measurements in compressed sensing ⋮ An interpretable classification method for predicting drug resistance in $M. tuberculosis$ ⋮ Dictionary-based model reduction for state estimation ⋮ A Multiple Measurement Vector Approach to Synthetic Aperture Radar Imaging ⋮ A Scale-Invariant Approach for Sparse Signal Recovery ⋮ Construction of Sparse Binary Sensing Matrices Using Set Systems ⋮ On the differences between $L_2$ boosting and the Lasso ⋮ Robust multi-image processing with optimal sparse regularization ⋮ Nonconvex sorted $\ell_1$ minimization for sparse approximation ⋮ Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation ⋮ Weak Stability of ℓ₁-Minimization Methods in Sparse Data Reconstruction ⋮ Deterministic constructions of compressed sensing matrices based on codes ⋮ New conditions on stable recovery of weighted sparse signals via weighted $l_1$ minimization ⋮ Unnamed Item ⋮ Solving inverse problems using data-driven models ⋮ SPARSE TEMPLATE-BASED VARIATIONAL IMAGE SEGMENTATION ⋮ Remarks on the spark of a matrix and the null space property ⋮ Sparse reconstruction with multiple Walsh matrices ⋮ Truncated sparse approximation property and truncated $q$-norm minimization ⋮ Iteratively reweighted least squares minimization for sparse recovery ⋮ Binary sparse signal recovery with binary matching pursuit ^* ⋮ Sampling strategies for uncertainty reduction in categorical random fields: formulation, mathematical analysis and application to multiple-point simulations ⋮ EXACT LOW-RANK MATRIX RECOVERY VIA NONCONVEX SCHATTEN p-MINIMIZATION ⋮ SPARSE RECONSTRUCTION OF HARDY SIGNAL AND APPLICATIONS TO TIME-FREQUENCY DISTRIBUTION ⋮ Sparse Representation of Signals in Hardy Space ⋮ Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit ⋮ Minimization of $\ell_{1-2}$ for Compressed Sensing ⋮ Sampling, Metric Entropy, and Dimensionality Reduction ⋮ Efficiency of the weak Rescaled Pure Greedy Algorithm ⋮ A New Computational Method for the Sparsest Solutions to Systems of Linear Equations ⋮ Theory and applications of compressed sensing ⋮ On some aspects of approximation of ridge functions ⋮ On sparse representation of analytic signal in Hardy space ⋮ Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing ⋮ New analysis of manifold embeddings and signal recovery from compressive measurements ⋮ Sparse Solutions of a Class of Constrained Optimization Problems ⋮ On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels ⋮ Multilinear Compressive Sensing and an Application to Convolutional Linear Networks ⋮ Nonlinear approximation spaces for inverse problems ⋮ The gap between the null space property and the restricted isometry property ⋮ Relationship between the optimal solutions of least squares regularized with $\ell_{0}$-norm and constrained by $k$-sparsity ⋮ Signal recovery under cumulative coherence ⋮ Stable signal recovery from phaseless measurements ⋮ Carl's inequality for quasi-Banach spaces

Cites Work

This page was built for publication: Compressed sensing and best 𝑘-term approximation