An adaptive compression algorithm in Besov spaces (Q1968776): Difference between revisions

Let \(\overline F\) be an \(\overline M\)-dimensional linear space of functions on \([0,1]^d\) and let \(F\) be an \(M\)-dimensional linear space of compactly supported functions in \(L_\infty(\mathbb{R}^d)\). Define, for \(j\geq 0\) an integer and \({\mathbf k}\in \mathbb{Z}^d\), \[ F_{j,{\mathbf k}}= \{g(2^j x-{\mathbf k}): g\in F\}. \] The paper presents a compression algorithm for approximating a function \(f\in L_1([0, 1]^d)\) which has on \([0,1]^d\) an expansion \[ f=\overline f+ \sum^\infty_{j= 0} \sum_{{\mathbf k}\in\Lambda(j)} f_{j,{\mathbf k}},\tag{\(*\)} \] where \(\Lambda(j)\subseteq \mathbb{Z}^d\) and \(2^{jd}\leq |\Lambda(j)|\leq \lambda 2^{jd}\) for all \(j\geq 0\), and in which \(\overline f\in\overline F\) and each \(f_{j,{\mathbf k}}\in F_{j,{\mathbf k}}\). The algorithm \({\mathbf A}({\mathcal L},{\mathbf J})\) depends upon a slowly varying increasing function \({\mathcal L}:(0, 1]\to (0,1]\) satisfying prescribed conditions and an integer \(J\geq 0\). It is defined as follows. Let \(K_j= [{\mathcal L}(2^{j-j}) 2^{d(J- j)}|\Lambda(j)|]\) for \(j\geq J\). For \(0\leq j< J\) define \(\Lambda'(j)= \Lambda(j)\) and for \(j\geq J\) let \(\Lambda'(j)\) be a subset of \(\Lambda(j)\) such that \(|\Lambda'(j)|= K_j\) and (the crux of the algorithm) \[ \|f_{j,{\mathbf k}'}\|_2\leq\|f_{j,{\mathbf k}}\|_2\text{ for all }{\mathbf k}\in \Lambda'(j),\;{\mathbf k}'\not\in \Lambda'(j). \] Take as an approximation to \(f\) the finite sum \[ \widetilde f_J=\overline f+ \sum^\infty_{j=0} \sum_{{\mathbf k}\in \Lambda'(j)} f_{j,{\mathbf k}}. \] The paper is concerned in particular with three types of expansions of the form \((*)\) and they are discussed, for simplicity, in the case \(d=1\): (1) \(f\in L_2([0, 1])\) and the expansion \((*)\) is derived from orthogonal projections, to the spaces of polynomials of degree \(\leq r-1\), of the restrictions of \(f\) to dyadic subintervals of \([0,1]\); (2) orthonormal wavelet expansions with an \((r-1)\)-regular mother wavelet \(\psi\), and (3) dyadic spline decompositions of degree \(r-1\) defined by quasi-interpolant projections or by \(L_2\)-orthogonal projections. If \(f\) belongs to a Besov space \(B^\alpha_{p,\infty}([0, 1])\) with \(p> 0\), \(\alpha> (1/p- 1/q)^+\) for some \(q\in [1,\infty]\), and \(r> \alpha\) then (Theorem 1) the algorithm \({\mathbf A}({\mathcal L},{\mathbf J})\) provides approximation \(\widetilde f_J\) to \(f\) for which \(\|f-\widetilde f_J\|_q\leq C|f|_{B^\alpha_p} 2^{-J\alpha}\), where \(C\) depends only upon \({\mathcal L}\), \(\alpha- (1/p- 1/q)^+\) and \(r\) or \(\psi\). It is emphasized that the algorithm itself depends only upon the existence of the expansion \((*)\) and not upon knowledge of any other property of the function \(f\). The central Theorem 3 is a more general result from which all the other main results are derived and which also applies to the multidimensional cases \(d> 1\). The algorithm also provides a new and elementary method (in Section 5) for computing the \(\varepsilon\)-entropy of Besov balls (compare the results for Sobolev balls of \textit{M. Sh. Birman} and \textit{M. Z. Solomjak} [Mat. Sb., 73, 295-317 (1967; Zbl 0173.16001)]. The method is cmopared (in Section 4) with earlier thresholding methods (see, in particular \textit{R. A. DeVore}, \textit{B. Jawerth} and \textit{V. Popov} [Am. J. Math. 114, No. 4, 737-785 (1992; Zbl 0764.41024)]). The paper contains throughout very readable and informative discussion of the significance of the results and their relation to earlier ones. The algorithm first appeared in a contribution by the same authors to a Festschrift for Lucien le Cam in 1997.