Function approximation on arbitrary domains using Fourier extension frames
From MaRDI portal
Publication:4564012
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 operations. In this paper we describe an algorithm to compute such Fourier extension frame approximations in only operations for general 2D domains. The cost improves to 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 in one dimensional problems. In this paper we show that for most 2D domains in the fully discrete case the plunge region scales like , 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 for domains with fractal shape.
Recommendations
Cites work
- scientific article; zbMATH DE number 3758993 (Why is no real title available?)
- scientific article; zbMATH DE number 2042292 (Why is no real title available?)
- A Class of Nonharmonic Fourier Series
- A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds
- A fast algorithm for Fourier continuation
- A hybrid Fourier-Chebyshev method for partial differential equations
- A spectral FC solver for the compressible Navier-Stokes equations in general domains. I: Explicit time-stepping
- Accurate, high-order representation of complex three-dimensional surfaces via Fourier continuation analysis
- Digital and discrete geometry. Theory and algorithms
- Edge Illumination and Imaging of Extended Reflectors
- Eigenvalue distribution of time and frequency limiting
- Extrapolation algorithms for discrete signals with application in spectral estimation
- Fast algorithms for the computation of Fourier extensions of arbitrary length
- 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}\)
- 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
- Fractal geometry. Mathematical foundations and applications
- Frames and numerical approximation
- High-order unconditionally stable FC-AD solvers for general smooth domains. I: Basic elements
- High-order unconditionally stable FC-AD solvers for general smooth domains. II: Elliptic, parabolic and hyperbolic PDEs; theoretical considerations
- On Szegö's eigenvalue distribution theorem and non-Hermitian kernels
- On choosing a radial basis function and a shape parameter when solving a convective PDE on a sphere
- On the Fourier Extension of Nonperiodic Functions
- On the Periodic Discrete Prolate Spheroidal Sequences
- On the numerical stability of Fourier extensions
- On the resolution power of Fourier extensions for oscillatory functions
- 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 - IV: Extensions to Many Dimensions; Generalized Prolate Spheroidal Functions
- 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-V: The Discrete Case
- Prolate spheroidal wave functions of order zero. Mathematical tools for bandlimited approximation
- Quasi-classical asymptotics for pseudodifferential operators with discontinuous symbols: Widom's conjecture
- Randomized algorithms for the low-rank approximation of matrices
- Spatiospectral concentration in the Cartesian plane
- Wiener-Hopf operators in higher dimensions: the Widom conjecture for piece-wise smooth domains
Cited in
(23)- Level set methods for stochastic discontinuity detection in nonlinear problems
- A Super Order Regularization Scheme in Hilbert Scales under General Smoothing Conditions
- Frames and numerical approximation. II: Generalized sampling
- An oversampled collocation approach of the wave based method for Helmholtz problems
- Two-dimensional Fourier continuation and applications
- An Adaptive Partition of Unity Method for Multivariate Chebyshev Polynomial Approximations
- Oversampled collocation approximation method of functions via Jacobi frames
- Frame approximation with bounded coefficients
- Quadrature by two expansions for evaluating Helmholtz layer potentials
- 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 numerical stability of Fourier extensions
- Efficient least squares approximation and collocation methods using radial basis functions
- Computing with functions on domains with arbitrary shapes
- Two algorithms for periodic extension on uniform grids
- Parameter selection and numerical approximation properties of Fourier extensions from fixed data
- Pointwise and uniform convergence of Fourier extensions
- The AZ algorithm for least squares systems with a known incomplete generalized inverse
- Fast and stable approximation of analytic functions from equispaced samples via polynomial frames
- Frames and numerical approximation
- A Fourier Extension Based Numerical Integration Scheme for Fast and High-Order Approximation of Convolutions with Weakly Singular Kernels
- Multitaper estimation on arbitrary domains
- Efficient function approximation on general bounded domains using splines on a Cartesian grid
- On the computation of the SVD of Fourier submatrices
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)
