This is an announcement for the paper "The restricted isometry property meets nonlinear approximation with redundant frames" by Remi Gribonval and Morten Nielsen.

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.

Archive classification: math.FA

Report Number: RR-7548

Remarks: This work has been submitted for possible publication. Copyright be transferred without notice, after which this version may no longer be accessible.

Submitted from: remi.gribonval@inria.fr

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/1102.5324

or

http://arXiv.org/abs/1102.5324