Average Performance of the Sparsest Approximation Using a General Dictionary

DOI10.1080/01630563.2011.580876zbMATH Open1243.68313arXiv0803.0524OpenAlexW2105111192MaRDI QIDQ3173502FDOQ3173502

François Malgouyres, Mila Nikolova

Publication date: 10 October 2011

Published in: Numerical Functional Analysis and Optimization (Search for Journal in Brave)

Abstract: We consider the minimization of the number of non-zero coefficients (the $el{l}_0$ "norm") of the representation of a data set in terms of a dictionary under a fidelity constraint. (Both the dictionary and the norm defining the constraint are arbitrary.) This (nonconvex) optimization problem naturally leads to the sparsest representations, compared with other functionals instead of the $el{l}_0$ "norm". Our goal is to measure the sets of data yielding a $K$-sparse solution--i.e. involving $K$ non-zero components. Data are assumed uniformly distributed on a domain defined by any norm--to be chosen by the user. A precise description of these sets of data is given and relevant bounds on the Lebesgue measure of these sets are derived. They naturally lead to bound the probability of getting a $K$-sparse solution. We also express the expectation of the number of non-zero components. We further specify these results in the case of the Euclidean norm, the dictionary being arbitrary.

Full work available at URL: https://arxiv.org/abs/0803.0524

zbMATH Keywords

estimationapproximationconstrained minimizationmeasure theorysparse representationnonsmooth functionsdictionarynonconvex functionsbest \(K\)-term approximation

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Computing methodologies for image processing (68U10) Optimality conditions for solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.) (49K30) Algorithms for approximation of functions (65D15) Rate of convergence, degree of approximation (41A25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• Matching pursuits with time-frequency dictionaries
• Entropy-based algorithms for best basis selection
• Just relax: convex programming methods for identifying sparse signals in noise
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Iterative hard thresholding for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Compressed sensing and best 𝑘-term approximation
• Recovery of Exact Sparse Representations in the Presence of Bounded Noise
• Greed is Good: Algorithmic Results for Sparse Approximation
• Adaptive greedy approximations
• Atomic decomposition by basis pursuit
• Subspace Pursuit for Compressive Sensing Signal Reconstruction

Cited In (2)

• On some deterministic dictionaries supporting sparsity
• Average performance of the approximation in a dictionary using an \(\ell _0\) objective

Uses Software

• CoSaMP

Recommendations

• Title not available (Why is that?) 👍 👎
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization 👍 👎
• Sparse representations and approximation theory 👍 👎
• Computable Performance Bounds on Sparse Recovery 👍 👎
• Sparse approximation is provably hard under coherent dictionaries 👍 👎
• Sparse Approximation by Greedy Algorithms 👍 👎
• Computing sparse approximations deterministically 👍 👎
• On some deterministic dictionaries supporting sparsity 👍 👎
• Average performance of the approximation in a dictionary using an \(\ell _0\) objective 👍 👎
• Optimal dictionary for least squares representation 👍 👎

This page was built for publication: Average Performance of the Sparsest Approximation Using a General Dictionary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3173502)