Frames and numerical approximation II: generalized sampling

Ben Adcock, Daan Huybrechs

Published 2018-02-06Version 1

In a previous paper [Adcock & Huybrechs, 2016] we described the numerical properties of function approximation using frames, i.e. complete systems that are generally redundant but provide infinite representations with coefficients of bounded norm. Frames offer enormous flexibility compared to bases. We showed that, in spite of extreme ill-conditioning, a regularized projection onto a finite truncated frame can provide accuracy up to order $\sqrt{\epsilon}$, where $\epsilon$ is an arbitrarily small threshold. Here, we generalize the setting in two ways. First, we assume information or samples from $f$ from a wide class of linear operators acting on $f$, rather than inner products with the frame elements. Second, we allow oversampling, leading to least-squares approximations. The first property enables the analysis of fully discrete approximations based, for instance, on function values only. We show that the second property, oversampling, crucially leads to much improved accuracy on the order of $\epsilon$ rather than $\sqrt{\epsilon}$. Overall, we show that numerical function approximation using truncated frames leads to highly accurate approximations in spite of having to solve an ill-conditioned system of equations. Once the approximations start to converge, i.e. once sufficiently many degrees of freedom are used, any function $f$ can be approximated to within order $\epsilon$ with coefficients of small norm.