Compressed sensing and best 𝑘-term approximation

From MaRDI portal

Publication:3079195

Jump to:navigation, search

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

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 ⋮ Conjugate gradient acceleration of iteratively re-weighted least squares methods ⋮ The non-convex sparse problem with nonnegative constraint for signal reconstruction ⋮ Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods ⋮ 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory ⋮ Sparse approximate solution of fitting surface to scattered points by MLASSO model ⋮ Robust sparse phase retrieval made easy ⋮ A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions ⋮ On the robustness of noise-blind low-rank recovery from rank-one measurements ⋮ Real-valued group testing for quantitative molecular assays ⋮ Complex best \(r\)-term approximations almost always exist in finite dimensions ⋮ On exact recovery of sparse vectors from linear measurements ⋮ Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions ⋮ Unbounded violations of bipartite Bell inequalities via operator space theory ⋮ The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\) ⋮ Sparse nonnegative matrix underapproximation and its application to hyperspectral image analysis ⋮ Strengthening hash families and compressive sensing ⋮ Sparse signal reconstruction via the approximations of \(\ell_0\) quasinorm ⋮ A smoothing method for sparse optimization over convex sets ⋮ Exact asymptotic orders of various randomized widths on Besov classes ⋮ Sparse recovery with integrality constraints ⋮ Approximation of functions of few variables in high dimensions ⋮ Approximating sampled sinusoids and multiband signals using multiband modulated DPSS dictionaries ⋮ Restricted isometries for partial random circulant matrices ⋮ A hierarchical framework for recovery in compressive sensing ⋮ Recovery of sparsest signals via \(\ell^q \)-minimization ⋮ Block-sparse recovery of semidefinite systems and generalized null space conditions ⋮ Error estimates for orthogonal matching pursuit and random dictionaries ⋮ Deterministic construction of compressed sensing matrices from constant dimension codes ⋮ Sparse Legendre expansions via \(\ell_1\)-minimization ⋮ Deterministic construction of compressed sensing matrices based on semilattices ⋮ Effective zero-norm minimization algorithms for noisy compressed sensing ⋮ Exact optimization for the \(\ell ^{1}\)-compressive sensing problem using a modified Dantzig-Wolfe method ⋮ Geological facies recovery based on weighted \(\ell_1\)-regularization ⋮ Analysis \(\ell_1\)-recovery with frames and Gaussian measurements ⋮ A Rice method proof of the null-space property over the Grassmannian ⋮ Uniform estimates for order statistics and Orlicz functions ⋮ Testing the nullspace property using semidefinite programming ⋮ On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization ⋮ Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions ⋮ Sobolev duals for random frames and \(\varSigma \varDelta \) quantization of compressed sensing measurements ⋮ Interpolation via weighted \(\ell_{1}\) minimization ⋮ Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling ⋮ Learning functions of few arbitrary linear parameters in high dimensions ⋮ Exact reconstruction using Beurling minimal extrapolation ⋮ Perturbations of measurement matrices and dictionaries in compressed sensing ⋮ Average best \(m\)-term approximation ⋮ A class of null space conditions for sparse recovery via nonconvex, non-separable minimizations ⋮ A short note on compressed sensing with partially known signal support ⋮ Stable recovery of sparse signals via \(\ell_p\)-minimization ⋮ Compressed sensing with preconditioning for sparse recovery with subsampled matrices of Slepian prolate functions ⋮ Sparse recovery on Euclidean Jordan algebras ⋮ On the conditioning of random subdictionaries ⋮ Signal recovery under mutual incoherence property and oracle inequalities ⋮ On the null space property of \(l_q\)-minimization for \(0 < q \leq 1\) in compressed sensing ⋮ Compressive sensing using chaotic sequence based on Chebyshev map ⋮ A remark on compressed sensing ⋮ Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing ⋮ Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\) ⋮ On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery ⋮ Minimization of transformed \(L_1\) penalty: theory, difference of convex function algorithm, and robust application in compressed sensing ⋮ Orthogonal matching pursuit under the restricted isometry property ⋮ Generalized sampling and infinite-dimensional compressed sensing ⋮ Sparse decomposition by iterating Lipschitzian-type mappings ⋮ Uniqueness of the minimal \(l_1\)-norm solution to the monotone linear complementarity problem ⋮ Sparse approximation of fitting surface by elastic net ⋮ Sparse signal recovery using a new class of random matrices ⋮ Matrix recipes for hard thresholding methods ⋮ Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time ⋮ Restricted \(p\)-isometry property and its application for nonconvex compressive sensing ⋮ A non-adapted sparse approximation of PDEs with stochastic inputs ⋮ Deterministic constructions of compressed sensing matrices based on optimal codebooks and codes ⋮ Sparse approximate solution of partial differential equations ⋮ Estimation of (near) low-rank matrices with noise and high-dimensional scaling ⋮ Combinatorial sublinear-time Fourier algorithms ⋮ An efficient algorithm based on sparse optimization for the aircraft departure scheduling problem ⋮ Sparse recovery by non-convex optimization - instance optimality ⋮ On the sparseness of 1-norm support vector machines ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time ⋮ Instance-optimality in probability with an \(\ell _1\)-minimization decoder ⋮ A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing ⋮ Phase retrieval for sparse signals ⋮ CoSaMP: Iterative signal recovery from incomplete and inaccurate samples ⋮ Maximal spaces for approximation rates in \(\ell^1\)-regularization ⋮ Nonuniqueness of solutions of a class of \(\ell_0\)-minimization problems ⋮ Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit ⋮ A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size ⋮ Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables ⋮ Sparse solutions to underdetermined Kronecker product systems ⋮ A simple proof of the restricted isometry property for random matrices ⋮ The \(\ell_{2,q}\) regularized group sparse optimization: lower bound theory, recovery bound and algorithms ⋮ Robust sparse recovery via a novel convex model ⋮ GenMod: a generative modeling approach for spectral representation of PDEs with random inputs ⋮ Empirical average-case relation between undersampling and sparsity in X-ray CT ⋮ Locally sparse reconstruction using the \(\ell^{1,\infty}\)-norm ⋮ 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 ⋮ 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

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3079195&oldid=16141554"