Universal bases and greedy algorithms for anisotropic function classes (Q1862756)

We suggest a three-step strategy to find a good basis (dictionary) for nonlinear \(m\)-term approximation. The first step consists of solving an optimization problem of finding a near best basis for a given function class \(F\), when we optimize over a collection \({\mathbf D}\) of bases (dictionaries). The second step is devoted to finding a universal basis (dictionary) \({\mathcal D}_u\in {\mathbf D}\) for a given pair \(({\mathcal F},{\mathbf D})\) of collections: \({\mathcal F}\) of function classes and \({\mathbf D}\) of bases (dictionaries). This means that \({\mathcal D}_u\) provides near optimal approximation for each class \(F\) from a collection \({\mathcal F}\). The third step deals with constructing a theoretical algorithm that realizes near best \(m\)-term approximation with regard to \({\mathcal D}_u\) for function classes from \({\mathcal F}\). In this paper we work this strategy out in the model case of anisotropic function classes and the set of orthogonal bases. The results are positive. We construct a natural tensor-product-wavelet-type basis and prove that it is universal. Moreover, we prove that a greedy algorithm realizes near best \(m\)-term approximation with regard to this basis for all anisotropic function classes.