# The restricted isometry property meets nonlinear approximation with redundant frames

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.
Keywords :
Document type :
Journal articles
Domain :
Complete list of metadata

Cited literature [14 references]

https://hal.inria.fr/inria-00567801
Contributor : Rémi Gribonval <>
Submitted on : Monday, February 21, 2011 - 10:22:21 PM
Last modification on : Wednesday, June 16, 2021 - 3:42:13 AM
Long-term archiving on: : Sunday, May 22, 2011 - 3:20:11 AM

### Files

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

### 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⟩

Record views