A multivariate fast discrete Walsh transform with an application to function interpolation

DOI10.1090/S0025-5718-09-02202-9MaRDI QIDQ3055160zbMATH OpenFDO

Authors Kwong Ip Liu, Josef Dick, Fred J. Hickernell

Publication date 7 November 2010

Published in Mathematics of Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Spline approximation (41A15) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10)

Abstract: For high dimensional problems, such as approximation and integration, one cannot afford to sample on a grid because of the curse of dimensionality. An attractive alternative is to sample on a low discrepancy set, such as an integration lattice or a digital net. This article introduces a multivariate fast discrete Walsh transform for data sampled on a digital net that requires only $O(NlogN)$ operations, where $N$ is the number of data points. This algorithm and its inverse are digital analogs of multivariate fast Fourier transforms. This fast discrete Walsh transform and its inverse may be used to approximate the Walsh coefficients of a function and then construct a spline interpolant of the function. This interpolant may then be used to estimate the function's effective dimension, an important concept in the theory of numerical multivariate integration. Numerical results for various functions are presented.

Recommendations

• The generalized discrete \(W\) transform and its application to interpolation
• Fast computation of the discrete Walsh and Hadamard transforms
• Computation of the Fast Walsh-Fourier Transform
• scientific article; zbMATH DE number 1839718
• scientific article; zbMATH DE number 7234326
• Fast discrete extrapolation via the fast Hartley transform
• Fast Fourier Transform for Discontinuous Functions
• Fast algorithms of multidimensional discrete nonseparable /spl Kscr/-wave transforms
• Approximation by \(T\)-transformation of double Walsh-Fourier series to multivariable functions
• Fast Fourier transforms of piecewise constant functions

Cites work

• A class of generalized Walsh functions
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Constructions of (t,m,s)-nets and (t,s)-sequences
• Discrépance de suites associées à un système de numération (en dimension s)
• Duality for digital nets and its applications
• Efficient Weighted Lattice Rules with Applications to Finance
• Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates
• scientific article; zbMATH DE number 4076564 (Why is no real title available?)
• scientific article; zbMATH DE number 45848 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 472857 (Why is no real title available?)
• scientific article; zbMATH DE number 2046351 (Why is no real title available?)
• scientific article; zbMATH DE number 914714 (Why is no real title available?)
• scientific article; zbMATH DE number 5049869 (Why is no real title available?)
• scientific article; zbMATH DE number 3310475 (Why is no real title available?)
• Low-discrepancy point sets
• Meshfree approximation methods with Matlab. With CD-ROM.
• Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces
• On the Numerical Integration of Walsh Series by Number-Theoretic Methods
• Randomized Halton sequences
• Sparse grids
• The effective dimension and quasi-Monte Carlo integration
• The jackknife estimate of variance
• Theory of Reproducing Kernels
• Why Are High-Dimensional Finance Problems Often of Low Effective Dimension?

Cited in

(2)

• On the approximation of smooth functions using generalized digital nets
• Spline methods using integration lattices and digital nets

Describes a project that uses

Uses Software

• Matlab

This page was built for publication: A multivariate fast discrete Walsh transform with an application to function interpolation

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