Average performance of the approximation in a dictionary using an $ {\ell }_{0}$ objective

François Malgouyres; Mila Nikolova

doi:10.1016/j.crma.2009.02.026

Numerical Analysis

Average performance of the approximation in a dictionary using an

ℓ_{0}

objective
[Performance moyenne de l'approximation la plus parcimonieuse avec un dictionnaire]

Présenté par : Yves Meyer

François Malgouyres ¹ ; Mila Nikolova ²

¹ Université Paris 13, CNRS UMR 7539 LAGA, 99, avenue J.B. Clément, 93430 Villetaneuse, France
² CMLA, ENS Cachan, CNRS, PRES UniverSud, 61, avenue President Wilson, 94230 Cachan, France

Comptes Rendus. Mathématique, Volume 347 (2009) no. 9-10, pp. 565-570.

Résumé
Abstract

Nous étudions la minimisation du nombre de coefficients non-nuls (la « norme » $ℓ_{0}$ ) de la représentation d'un ensemble de données dans un dictionnaire arbitraire sous une contrainte de fidélité. Ce problème d'optimisation (non-convexe) mène naturellement aux représentations les plus parcimonieuses. La performance moyenne du modèle est décrite par la probablilité que les données mènent à une solution K-parcimonieuse – contenant pas plus de K composantes non-nulles – en supposant que les données sont uniformément distribuées sur un domaine. Ces probabilités s'expriment en fonction des paramètres du modèle et de la précision de l'approximation. Nous commentons les formules obtenues et fournissons une illustration.

We consider the minimization of the number of non-zero coefficients (the $ℓ_{0}$ “norm”) of the representation of a data set in a general dictionary under a fidelity constraint. This (nonconvex) optimization problem leads to the sparsest approximation. The average performance of the model consists in the probability (on the data) to obtain a K-sparse solution—involving at most K nonzero components—from data uniformly distributed on a domain. These probabilities are expressed in terms of the parameters of the model and the accuracy of the approximation. We comment the obtained formulas and give a simulation.

Reçu le : 2008-10-31
Accepté le : 2009-02-16
Publié le : 2009-04-05

DOI : 10.1016/j.crma.2009.02.026

Affiliations des auteurs :

François Malgouyres ¹ ; Mila Nikolova ²

¹ Université Paris 13, CNRS UMR 7539 LAGA, 99, avenue J.B. Clément, 93430 Villetaneuse, France
² CMLA, ENS Cachan, CNRS, PRES UniverSud, 61, avenue President Wilson, 94230 Cachan, France

@article{CRMATH_2009__347_9-10_565_0,
     author = {Fran\c{c}ois Malgouyres and Mila Nikolova},
     title = {Average performance of the approximation in a dictionary using an $ {\ell }_{0}$ objective},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {565--570},
     publisher = {Elsevier},
     volume = {347},
     number = {9-10},
     year = {2009},
     doi = {10.1016/j.crma.2009.02.026},
     language = {en},
}

TY  - JOUR
AU  - François Malgouyres
AU  - Mila Nikolova
TI  - Average performance of the approximation in a dictionary using an $ {\ell }_{0}$ objective
JO  - Comptes Rendus. Mathématique
PY  - 2009
SP  - 565
EP  - 570
VL  - 347
IS  - 9-10
PB  - Elsevier
DO  - 10.1016/j.crma.2009.02.026
LA  - en
ID  - CRMATH_2009__347_9-10_565_0
ER  -

%0 Journal Article
%A François Malgouyres
%A Mila Nikolova
%T Average performance of the approximation in a dictionary using an $ {\ell }_{0}$ objective
%J Comptes Rendus. Mathématique
%D 2009
%P 565-570
%V 347
%N 9-10
%I Elsevier
%R 10.1016/j.crma.2009.02.026
%G en
%F CRMATH_2009__347_9-10_565_0

François Malgouyres; Mila Nikolova. Average performance of the approximation in a dictionary using an $ {\ell }_{0}$ objective. Comptes Rendus. Mathématique, Volume 347 (2009) no. 9-10, pp. 565-570. doi : 10.1016/j.crma.2009.02.026. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2009.02.026/

Bibliographie
Cité par

[1] E. Candes; J. Romberg; T. Tao Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. on Information Theory, Volume 52 (2006) no. 2, pp. 489-509

[2] G. Davis; S. Mallat; M. Avellaneda Adaptive greedy approximations, Constructive Approximation, Volume 13 (1997) no. 1, pp. 57-98

[3] R.A. Devore Nonlinear approximation, Acta Numerica, Volume 7 (1998), pp. 51-150

[4] J.J. Fuchs Recovery of exact sparse representations in the presence of bounded noise, IEEE Trans. on Information Theory, Volume 51 (2005) no. 10, pp. 3601-3608

[5] F. Malgouyres Rank related properties for basis pursuit and total variation regularization, Signal Processing, Volume 87 (2007) no. 11, pp. 2695-2707

[6] F. Malgouyres, M. Nikolova, Average performance of the sparsest approximation using a general dictionary, Report HAL-00260707 and CMLA n.2008-08

[7] G. Pisier The Volume of Convex Bodies and Banach Space Geometry, Cambridge University Press, 1989

[8] J.A. Tropp Greed is good: algorithmic results for sparse approximation, IEEE Trans. on Information Theory, Volume 50 (2004) no. 10, pp. 2231-2242

[9] J.A. Tropp Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. on Information Theory, Volume 52 (2006) no. 3, pp. 1030-1051

Cité par Sources :

Commentaires - Politique