Skip to Main content Skip to Navigation
New interface
Journal articles

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
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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00567801
Contributor : Rémi Gribonval Connect in order to contact the contributor
Submitted on : Monday, February 21, 2011 - 10:22:21 PM
Last modification on : Thursday, January 20, 2022 - 5:33:23 PM
Long-term archiving on: : Sunday, May 22, 2011 - 3:20:11 AM

Files

RR-7548.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

299

Files downloads

317