Average Performance of the Sparsest Approximation Using a General Dictionary

DOI10.1080/01630563.2011.580876MaRDI QIDQ3173502zbMATH OpenOpenAlexFDO

Authors François Malgouyres, Mila Nikolova

Publication date 10 October 2011

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

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)

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.

Recommendations

• Average performance of the approximation in a dictionary using an \(\ell _0\) objective
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• On some deterministic dictionaries supporting sparsity
• Sparse representation and performance analysis for LSP parameters via dictionary learning
• Computable Performance Bounds on Sparse Recovery
• Computing sparse approximations deterministically
• Optimal dictionary for least squares representation
• Sparse representations and approximation theory
• Sparse approximation by greedy algorithms
• Sparse approximation is provably hard under coherent dictionaries

Cites work

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

Cited in

(2)

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

Describes a project that uses

Uses Software

• CoSaMP

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)