Adaptive wavelet methods using semiorthogonal spline wavelets: Sparse evaluation of nonlinear functions

Enormous progress has been made in the construction and analysis of adaptive wavelet methods in the recent years. Cohen, Dahmen, and DeVore showed that such methods converge for a wide class of operator equations, both linear and nonlinear. Moreover, they showed that the rate of convergence is asymptotically optimal and that the methods are asymptotically optimally efficient. So far, these methods are based upon biorthogonal wavelets with compactly supported primal and dual functions. Semiorthogonal spline wavelets offer some quantitative advantages, namely small supports and good conditioning of the bases. On the other hand, the corresponding dual functions are globally supported so that they are ruled out for existing wavelet methods for nonlinear variational problems. In this paper, we focus on a core ingredient of adaptive wavelet methods for nonlinear problems, namely the adaptive evaluation of nonlinear functions. We present an efficient adaptive method for approximately evaluating nonlinear functions of wavelet expansions using semiorthogonal spline wavelets. This is achieved by modifying and extending a method for compactly supported biorthogonal wavelets by Dahmen, Schneider, and Xu. In order to do so, we introduce a new adaptive quasi-interpolation scheme, a corresponding prediction and a new decomposition. We give a complete analysis including an investigation of the complexity.