Frames and numerical approximation

Ben Adcock, Daan Huybrechs

Published 2016-12-14Version 1

Functions of one or more variables are usually approximated with a basis; a complete, linearly independent set of functions that spans an appropriate function space. The topic of this paper is the numerical approximation of functions using the more general notion of frames; complete systems that are generally redundant but provide stable infinite representations. While frames are well-known in image and signal processing, coding theory and other areas of mathematics, their use in numerical analysis is far less widespread. Yet, as we show via example, frames are more flexible than bases, and can be constructed easily in a range of problems where finding orthonormal bases with desirable properties is difficult or impossible. A major difficulty in computing best approximations is that frames necessarily lead to ill-conditioned linear systems of equations. However, we show that frame approximations can in fact be computed numerically up to an error of order $\sqrt{\epsilon}$ with a simple algorithm, where $\epsilon$ is a threshold parameter that can be chosen close to machine precision. Moreover, this accuracy can be improved to order $\epsilon$ with modifications to the algorithm. Crucially, the order of convergence down to this limit is determined by the existence of representations of the function being approximated that are accurate and have small-norm coefficients. We demonstrate the existence of such representations in all our examples. Overall, our analysis suggests that frames are a natural generalization of bases in which to develop numerical approximation. In particular, even in the presence of severe ill-conditioning, the frame condition imposes sufficient mathematical structure on the redundant set in order to give rise to good approximations in finite precision calculations.