The restricted isometry property meets nonlinear approximation with redundant frames

Rémi Gribonval 1, 2 Morten Nielsen 3
1 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
Résumé : Il est maintenant bien établi que les vecteurs parcimonieux ou compressibles peuvent être estimés de façon stable à partir de leur projection en petite dimension, dès que la matrice de projection satisfait une Propriété d'Isométrie Restreinte (RIP). Nous établissons de nouvelles conséquences de la RIP vis à vis de l'approximation non-linéaire dans un espace de Hilbert avec un repère oblique (ou frame) redondant. Les principaux ingrédients de notre approche sont : a) des inégalités de Jackson et de Bernstein, associées à des caractérisations de certains espaces d'approximation en termes d'espaces d'interpolation ; b) la preuve que pour des repères obliques satisfaisant ladite inégalité de Bernstein, les espaces d'interpolation en question ne sont rien d'autres que l'ensemble des vecteurs ayant une représentation à coefficients compressibles dans le dictionnaire ; c) la preuve que la RIP implique des inégalités de Bernstein. Une conséquence de ces résultats est que la plupart des dictionnaires Gaussiens aléatoires de facteur de redondance fixé se comportent comme une base orthogonale du point de vue des espaces d'approximation : l'erreur optimale d'approximation à $m$ termes d'un vecteur décroît à une certaine vitesse en fonction de $m$ si, et seulement si, le vecteur admet une représentation compressible dans le dictionnaire. Toutefois, nous montrons qu'il existe aussi des dictionnaires de redondance minimale, dont le noyau est de dimension un, pour lesquels l'inégalité de Bernstein, bien que vérifiée, peut être mise en défaut lorsque le dictionnaire subit une perturbation arbitrairement petite.
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00567801
Contributeur : Rémi Gribonval <>
Soumis le : lundi 21 février 2011 - 22:22:21
Dernière modification le : vendredi 16 novembre 2018 - 01:32:16
Document(s) archivé(s) le : dimanche 22 mai 2011 - 03:20:11

Fichiers

RR-7548.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Rémi Gribonval, Morten Nielsen. The restricted isometry property meets nonlinear approximation with redundant frames. Journal of Approximation Theory, Elsevier, 2013, 165 (1), pp.1--19. 〈10.1016/j.jat.2012.09.008〉. 〈inria-00567801〉

Partager

Métriques

Consultations de la notice

1247

Téléchargements de fichiers

426