Conference abstracts

Session A1 - Approximation Theory

July 11, 17:00 ~ 17:35 - Room B3

Sparse approximation with respect to the Faber-Schauder system

Tino Ullrich

University of Bonn/University of Osnabrueck, Germany   -   tino.ullrich@hcm.uni-bonn.de

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_\infty$ 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{F} \hookrightarrow X$ is measured by the usual best m-term widths denoted by $\sigma_m(\mathbf{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_\infty$

\[\sigma_m(\mathbf{B}^r_{p,\theta},\mathcal{F})_\infty \asymp m^{-r}\,. \]

Note, that this asymptotical rate of convergence does not depend on the dimension $d$ (only the constants behind). In addition, the error is measured in $L_\infty$ and to our best knowledge this is the first sharp result involving $L_\infty$ 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$.

Joint work with Glenn Byrenheid (University of Bonn).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.