``Push-the-Error'' algorithm for nonlinear \(n\)-term approximation (Q853533)

Let \(\Omega\) be a compact domain in \({\mathbb R}^d\) and let \(V_m\), \(m=0,1,2,\ldots\), be subspaces of \(C(\Omega)\) such that \(V_0 \subset V_1 \subset \ldots\) and \(\overline {{\cup V_m}}=C(\Omega)\). It is assumed that for every \(m\) there is a finite set \(\Theta_m \subset \{0,1, \ldots \}\) so that \(V_m\) is spanned by a basis \(\{\phi_\theta \}_ {\theta \in \Theta_m}\) and a given \(f \in C(\Omega)\) can be represented in the form \[ f=\sum_{m=0}^\infty \sum_{ \theta \in \Theta_m} b_\theta \phi_\theta. \] The authors consider an algorithm that produces for any target accuracy an approximation to \(f\) of the form \(\sum d_\theta \phi_\theta\) with a small number of non-zero coefficients \(d_\theta\). Compared with the previous work in the field, the paper offers a more general setting for multiresolution analysis. The algorithm is especially designed to deal with the \(L_\infty\) approximation. The main conceptually new result is the quasi-subadditivity, with respect to \(f\), of the functional \(N(\varepsilon)\) counting the number of terms needed to achieve accuracy \(\epsilon\).