Function Approximation on Arbitrary Domains Using Fourier Extension Frames

DOI10.1137/17M1134809zbMATH Open1404.33019arXiv1706.04848OpenAlexW2963837865MaRDI QIDQ4564012

Author name not available (Why is that?)

Publication date: 5 June 2018

Published in: (Search for Journal in Brave)

Abstract: Fourier extension is an approximation scheme in which a function on an arbitary bounded domain is approximated using a classical Fourier series on a bounding box. On the smaller domain the Fourier series exhibits redundancy, and it has the mathematical structure of a frame rather than a basis. It is not trivial to construct approximations in this frame using function evaluations in points that belong to the domain only, but one way to do so is through a discrete least squares approximation. The corresponding system is extremely ill-conditioned, due to the redundancy in the frame, yet its solution via a regularized SVD is known to be accurate to very high (and nearly spectral) precision. Still, this computation requires $mathcalO(N^3)$ operations. In this paper we describe an algorithm to compute such Fourier extension frame approximations in only $mathcalO(N^{2}lo{g}^{2}N)$ operations for general 2D domains. The cost improves to $mathcalO(Nlo{g}^{2}N)$ operations for simpler tensor-product domains. The algorithm exploits a phenomenon called the plunge region in the analysis of time-frequency localization operators, which manifests itself here as a sudden drop in the singular values of the least squares matrix. It is known that the size of the plunge region scales like $mathcalO(logN)$ in one dimensional problems. In this paper we show that for most 2D domains in the fully discrete case the plunge region scales like $mathcalO(NlogN)$, proving a discrete equivalent of a result that was conjectured by Widom for a related continuous problem. The complexity estimate depends on the Minkowski or box-counting dimension of the domain boundary, and as such it is larger than $mathcalO(NlogN)$ for domains with fractal shape.

Full work available at URL: https://arxiv.org/abs/1706.04848

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

Related Items (1)

Fourier embedded domain methods: Extending a function defined on an irregular region to a rectangle so that the extension is spatially periodic and \(C^{\infty}\)

This page was built for publication: Function Approximation on Arbitrary Domains Using Fourier Extension Frames

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4564012)