Average performance of the sparsest approximation in a dictionary

Abstract : Given data d ∈ RN, we consider its representation u* involving the least number of non-zero elements (denoted by ℓ0(u*)) using a dictionary A (represented by a matrix) under the constraint kAu − dk ≤ τ, for τ > 0 and a norm k.k. This (nonconvex) optimization problem leads to the sparsest approximation of d. We assume that data d are uniformly distributed in θBfd (1) where θ>0 and Bfd (1) is the unit ball for a norm fd. Our main result is to estimate the probability that the data d give rise to a K−sparse solution u*: we prove that P (ℓ0(u*) ≤ K) = CK( τ θ )(N−K) + o(( τ θ )(N−K)), where u* is the sparsest approximation of the data d and CK > 0. The constants CK are an explicit function of k.k, A, fd and K which allows us to analyze the role of these parameters for the obtention of a sparsest K−sparse approximation. Consequently, given fd and θ, we have a tool to build A and k.k in such a way that CK (and hence P (ℓ0(u*) ≤ K)) are as large as possible for K small. In order to obtain the above estimate, we give a precise characterization of the set [\zigma τK] of all data leading to a K−sparse result. The main difficulty is to estimate accurately the Lebesgue measure of the sets {[\zigma τ K] ∩ Bfd (θ)}. We sketch a comparative analysis between our Average Performance in Approximation (APA) methodology and the well known Nonlinear Approximation (NA) which also assess the performance in approximation.
Type de document :
Communication dans un congrès
Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00369478
Contributeur : Ist Rennes <>
Soumis le : mardi 24 mars 2009 - 11:44:55
Dernière modification le : mardi 22 mai 2018 - 20:40:03
Document(s) archivé(s) le : jeudi 10 juin 2010 - 17:20:07

Fichier

23.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00369478, version 1

Citation

François Malgouyres, Mila Nikolova. Average performance of the sparsest approximation in a dictionary. Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009. 〈inria-00369478〉

Partager

Métriques

Consultations de la notice

156

Téléchargements de fichiers

68