Function approximation on arbitrary domains using Fourier extension frames

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

Authors: Roel Matthysen, Daan Huybrechs 

Publication date: 5 June 2018

Published in: SIAM Journal on Numerical Analysis (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

Recommendations

• Fast algorithms for the computation of Fourier extensions of arbitrary length
• Computing with functions on domains with arbitrary shapes
• On the numerical stability of Fourier extensions
• Rapid function approximation by modified Fourier series
• Two-dimensional Fourier continuation and applications

zbMATH Keywords

Fourier seriesarbitrary domainFourier extensionplunge region

Mathematics Subject Classification ID

Trigonometric approximation (42A10) Numerical methods for discrete and fast Fourier transforms (65T50) Lamé, Mathieu, and spheroidal wave functions (33E10)

Cites Work

• Fractal geometry. Mathematical foundations and applications
• A Class of Nonharmonic Fourier Series
• Eigenvalue distribution of time and frequency limiting
• On Szegö's eigenvalue distribution theorem and non-Hermitian kernels
• Prolate spheroidal wave functions of order zero. Mathematical tools for bandlimited approximation
• Prolate Spheroidal Wave Functions, Fourier Analysis, and Uncertainty-V: The Discrete Case
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty - I
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty - II
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty-III: The Dimension of the Space of Essentially Time- and Band-Limited Signals
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty - IV: Extensions to Many Dimensions; Generalized Prolate Spheroidal Functions
• Spatiospectral concentration in the Cartesian plane
• Randomized algorithms for the low-rank approximation of matrices
• On the Fourier Extension of Nonperiodic Functions
• A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds
• High-order unconditionally stable FC-AD solvers for general smooth domains. I: Basic elements
• Accurate, high-order representation of complex three-dimensional surfaces via Fourier continuation analysis
• A spectral FC solver for the compressible Navier-Stokes equations in general domains. I: Explicit time-stepping
• High-order unconditionally stable FC-AD solvers for general smooth domains. II: Elliptic, parabolic and hyperbolic PDEs; theoretical considerations
• On choosing a radial basis function and a shape parameter when solving a convective PDE on a sphere
• Quasi-classical asymptotics for pseudodifferential operators with discontinuous symbols: Widom's conjecture
• 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}\)
• On the resolution power of Fourier extensions for oscillatory functions
• A fast algorithm for Fourier continuation
• On the numerical stability of Fourier extensions
• Title not available (Why is that?)
• Fourier embedded domain methods: Periodic and \(C^{\infty}\) extension of a function defined on an irregular region to a rectangle via convolution with Gaussian kernels
• A hybrid Fourier-Chebyshev method for partial differential equations
• Edge Illumination and Imaging of Extended Reflectors
• On the Periodic Discrete Prolate Spheroidal Sequences
• Extrapolation algorithms for discrete signals with application in spectral estimation
• Digital and discrete geometry. Theory and algorithms
• Fast algorithms for the computation of Fourier extensions of arbitrary length
• Frames and numerical approximation
• Wiener-Hopf operators in higher dimensions: the Widom conjecture for piece-wise smooth domains
• Title not available (Why is that?)

Cited In (23)

• Frames and numerical approximation. II: Generalized sampling
• On the numerical stability of Fourier extensions
• Efficient least squares approximation and collocation methods using radial basis functions
• Two algorithms for periodic extension on uniform grids
• Level set methods for stochastic discontinuity detection in nonlinear problems
• 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}\)
• Multitaper estimation on arbitrary domains
• An Adaptive Partition of Unity Method for Multivariate Chebyshev Polynomial Approximations
• The AZ algorithm for least squares systems with a known incomplete generalized inverse
• Parameter selection and numerical approximation properties of Fourier extensions from fixed data
• Pointwise and uniform convergence of Fourier extensions
• Frame approximation with bounded coefficients
• A Fourier Extension Based Numerical Integration Scheme for Fast and High-Order Approximation of Convolutions with Weakly Singular Kernels
• An oversampled collocation approach of the wave based method for Helmholtz problems
• On the computation of the SVD of Fourier submatrices
• A Super Order Regularization Scheme in Hilbert Scales under General Smoothing Conditions
• Oversampled collocation approximation method of functions via Jacobi frames
• Two-dimensional Fourier continuation and applications
• Fast and stable approximation of analytic functions from equispaced samples via polynomial frames
• Efficient function approximation on general bounded domains using splines on a Cartesian grid
• Quadrature by two expansions for evaluating Helmholtz layer potentials
• Computing with functions on domains with arbitrary shapes
• Frames and numerical approximation

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)