On the Compressibility of Operators in Wavelet Coordinates

In [Found. Comput. Math., 2 (2002), pp. 203--245], Cohen, Dahmen, and DeVore proposed an adaptive wavelet algorithm for solving operator equations. Assuming that the operator defines a boundedly invertible mapping between a Hilbert space and its dual, and that a Riesz basis of wavelet type for this Hilbert space is available, the operator equation can be transformed into an equivalent well-posed infinite matrix-vector system. This system is solved by an iterative method, where each application of the infinite stiffness matrix is replaced by an adaptive approximation. For a certain range of s>0, determined by the compressibility of the stiffness matrix, i.e., by how well it can be approximated by sparse matrices, it was proven that if the errors of best linear combinations from the wavelet bases with N terms are $\mathcal{O}(N^{-s})$, then approximations yielded by the adaptive method with N terms also have errors of $\mathcal{O}(N^{-s})$, where their computation takes only $\mathcal{O}(N)$ operations. With the available estimates for both differential and singular integral operators, the compressibility of the stiffness matrix appears to limit the rate of convergence of the adaptive method, in the sense that for solutions that have a sufficiently high (Besov) regularity, these best N-term approximations converge with a better rate than can be shown for the approximations produced by the adaptive method. In this paper, considering piecewise smooth wavelets as spline or finite element wavelets, and using modified sparse matrix approximations, we derive improved results concerning compressibility. From these results it will follow that for the full range of s for which, under appropriate smoothness conditions, convergence of the best N-term approximations of $\mathcal{O}(N^{-s})$ can be shown, the adaptive method converges with that rate.