Constructive sparse approximation with respect to the Faber–Schauder system

This is joint work with Tino Ullrich (University of Bonn).
We consider approximations of multivariate functions using m terms from its tensorized Faber–Schauder expansion. The univariate Faber–Schauder system on $[0, 1]$ is given by dyadic dilates and translates (in the wavelet sense) of the $L_1$ normalized simple hat function with support in $[0, 1]$. We obtain a hierarchical basis which will be tensorized over all levels (hyperbolic) to get the dictionary $\mathcal F$. The worst-case error with respect to a class of functions $\mathbf{\mathrm{F}} \hookrightarrow X$ is measured by the usual best $m$-term widths denoted by $\sigma_m(\mathbf{\mathrm{F}}, \mathcal{F})_X$, where the error is measured in $X$. We constructively prove the following sharp asymptotical bound for the class of Besov spaces with small mixed smoothness (i.e. $1/p < r < min\{1/\theta - 1, 2\}$) in $L_q (p < q \le \infty)$
$$\sigma_m(S^r_{p,\theta}B,\mathcal{F})_q \asymp m^{-r}$$
Note that this asymptotical rate of convergence does not depend on the dimension $d$ (only the constants behind). In addition, this result holds for $q = 1$ and to our best knowledge this is the first sharp result involving $L_1$ as a target space. We emphasize two more things. First, the selection procedure for the coefficients is a level-wise constructive greedy strategy which only touches a finite prescribed number of coefficients. And second, due to the use of the Faber–Schauder system, the coefficients are finite linear combinations of discrete Function values. Hence, this method can be considered as a nonlinear adaptive sampling algorithm leading to a pure polynomial rate of convergence for any $d$.