8720 articles  [version française]

inria-00567801, version 1

## The restricted isometry property meets nonlinear approximation with redundant frames

Rémi Gribonval (, ) a12, Morten Nielsen () 3

Journal of Approximation Theory 165, 1 (2013) 1--19

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.

• a –  INRIA
• 1:  METISS (INRIA - IRISA)
• CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1
• 2:  PANAMA (INRIA - IRISA)
• INRIA – CNRS : UMR6074
• 3:  Department of Mathematical Sciences [Aalborg]
• Aalborg University
• Domain : Mathematics/Functional Analysis
Computer Science/Signal and Image Processing
Engineering Sciences/Signal and Image processing
• Keywords : Bernstein inequality – random dictionaries – restricted isometry condition
• Internal note : RR-7548

• inria-00567801, version 1
• oai:hal.inria.fr:inria-00567801
• From:
• Submitted on: Monday, 21 February 2011 22:22:21
• Updated on: Saturday, 4 January 2014 11:35:38