Frames and numerical approximation

Ben Adcock

Simon Fraser University


Functions of one or more variables are usually approximated using a basis; a complete but non-redundant set of functions that spans an appropriate function space. The topic of this talk is the numerical approximation of functions using the more general notion of frames; that is, complete systems that are possibly redundant. While frames are well-known tools in image and signal processing, coding theory and other areas of applied mathematics, their use in numerical analysis is far less widespread. Yet, 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 concern when using frames however is that computing a (quasi)-best approximation typically requires solving an ill-conditioned linear system. For this reason, frames haven often been avoided in function approximation, or their use is restricted to small-degree regimes in which they are well-conditioned. Nonetheless, I will show that the accurate frame approximations can be computed numerically up to an error of order √ ε  with a simple algorithm, or even of order ε with modifications to the algorithm. Here, ε is a threshold value that can be chosen close to machine precision. This analysis highlights the similarities between different settings and explains the convergence behavior in terms of properties of the frame at hand. To illustrate these results, I will consider the accurate and efficient numerical approximation of functions in complex geometries using certain Fourier frames.

This is joint work with Daan Huybrechs (KU Leuven)

Back to ACMS schedule