Abstract

Fourier series approximations can be constructed and manipulated efficiently, and in a numerically stable manner, with the Fast Fourier transform (FFT). However, high accuracy is achieved only for smooth and periodic functions due to the Gibbs phenomenon. This is a limiting factor already for functions defined on an interval, but is even more restrictive for functions defined on domains with general shapes in more than one dimension. For many domains, it is not even clear what periodicity is. We show that these restrictions originate at least partially in the desire to construct a basis for a finite-dimensional function space in which to approximate functions. This stringent condition ensures uniqueness of the representation of any function in that space, but that is not essential for high-accuracy approximations. We relax the notion of a basis to that of a frame, a set of functions that is possibly redundant. Frames based on Fourier series are easily defined for very general domains, and the FFT may still be used to manipulate the corresponding approximations. We illustrate the surprising flexibility and approximation power of Fourier-based frames with a variety of examples. The corresponding algorithms are inherently ill-conditioned due to the redundancy of the frame. Yet, all computations are numerically stable and a newly developed theory proves this point.