The restricted isometry property meets nonlinear approximation with redundant frames - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Journal of Approximation Theory Year : 2013

The restricted isometry property meets nonlinear approximation with redundant frames

Abstract

It is now well known that sparse or compressible vectors can be stably recovered from their low-dimensional projection, provided the projection matrix satisfies a Restricted Isometry Property (RIP). We establish new implications of the RIP with respect to nonlinear approximation in a Hilbert space with a redundant frame. The main ingredients of our approach are: a) Jackson and Bernstein inequalities, associated to the characterization of certain approximation spaces with interpolation spaces; b) a new proof that for overcomplete frames which satisfy a Bernstein inequality, these interpolation spaces are nothing but the collection of vectors admitting a representation in the dictionary with compressible coefficients; c) the proof that the RIP implies Bernstein inequalities. As a result, we obtain that in most overcomplete random Gaussian dictionaries with fixed aspect ratio, just as in any orthonormal basis, the error of best $m$-term approximation of a vector decays at a certain rate if, and only if, the vector admits a compressible expansion in the dictionary. Yet, for mildly overcomplete dictionaries with a one-dimensional kernel, we give examples where the Bernstein inequality holds, but the same inequality fails for even the smallest perturbation of the dictionary.
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.
Fichier principal
Vignette du fichier
RR-7548.pdf (259.87 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00567801 , version 1 (21-02-2011)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More