The restricted isometry property meets nonlinear approximation with redundant frames (Q1935491)

The paper contains five sections and an appendix. In the introduction, detailed motivations and explanations of the main ideas are given together with applications and open questions. Section 2 uses the concept of the \(K\)-functional to study embedding properties (in particular, equality with equivalent norms) of approximation spaces \( \mathcal{A}_q^s(\boldsymbol{\Phi}) \) into the sparsity spaces \( \boldsymbol{\Phi}\ell^{\tau}. \) Here, \[ \mathcal{A}_q^s(\boldsymbol{\Phi})=\left\{ f\in\mathcal{H} ,\left(\sum_{k\geq 1}\left[k^s\sigma_k(f,\boldsymbol{\Phi})\right]^qk^{-1}\right)^{1/q}<\infty\right\}, \] where \(\sigma_k(f,\boldsymbol{\Phi})\) is the error of best \(k\)-term approximation by a dictionary \(\boldsymbol{\Phi} \) in a Hilbert space \(\mathcal{H}. \) The embedding holds under the suppositions that \(\boldsymbol{\Phi} \) is a frame dictionary and the Bernstein inequality \[ \| f_k\|_{\boldsymbol{\Phi}\ell^{\tau}} \leq C k^r\| f_k\|_{\boldsymbol{\Phi}}\quad \quad (1) \] holds for all \(k\) and \(k\)-term expansions \(f_k\) in \(\boldsymbol{\Phi}\). Section 3 is devoted to the study of (1) for \(\tau =1\) (then \(r=1/2).\) The authors show that (1) is closely linked to properties of the kernel \(N(\boldsymbol{\Phi})=\{z\in\ell^2:\,\boldsymbol{\Phi}z=0\}.\) Firstly, they give a sufficient condition for (1) to hold, then they present a more refined analysis in the case that \(\dim N(\boldsymbol{\Phi})=1\). As an application, they give two examples which show that one can always perturb a nice dictionary with (1) ever so slightly as to make (1) collapse. In Section 4, relations between the Bernstein inequality and the lower restricted isometry property (LRIP) \[ \|\boldsymbol{\Phi}c\|_{\mathcal{H}}^2\geq\| c\|_2^2 \] for any coefficient sequence \(c\) with at most \(k\) non-zero terms are studied for \(\mathcal{H}=\mathbb{R}^N\) and \(\boldsymbol{\Phi} \) an \(m\times N\) frame. The main result (Theorem 1.5) is about the coincidence of the approximation and the sparsity spaces with universal constants for the equivalence of the norms for the case when \( \boldsymbol{\Phi} \) is an \(m\times N\) matrix with i.i.d. Gaussian entries. This result shows that the majority of incoherent dictionaries has a much better behaviour with respect to Bernstein estimates comparing to a ``worst case'' behaviour found in [the authors, Constructive Approximation 24, No. 2, 157--173 (2006; Zbl 1116.41018)].