Skip to Main content Skip to Navigation
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
IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE, Inria Rennes – Bretagne Atlantique
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 metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00567801
Contributor : Rémi Gribonval <>
Submitted on : Monday, February 21, 2011 - 10:22:21 PM
Last modification on : Wednesday, December 18, 2019 - 5:08:11 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, Elsevier, 2013, 165 (1), pp.1--19. ⟨10.1016/j.jat.2012.09.008⟩. ⟨inria-00567801⟩

Share

Metrics

Record views

1352

Files downloads

618