The fast Fourier Transform and fast Wavelet Transform for Patterns on the Torus

Abstract

We introduce a fast Fourier transform on regular d-dimensional lattices. We investigate properties of congruence class representants, i.e. their ordering, to classify directions and derive a Cooley-Tukey-Algorithm. Despite the fast Fourier techniques itself, there is also the advantage of this transform to be parallelized efficiently, yielding faster versions than the one-dimensional Fourier transform. These properties of the lattice can further be used to perform a fast multivariate wavelet decomposition, where the wavelets are given as trigonometric polynomials. Furthermore the preferred directions of the decomposition itself can be characterised.

23 pages, 10 figures, revised version

Cited by in corpus (6)

• Edge detection with trigonometric polynomial shearlets
• Multivariate periodic wavelets of de la Vallée Poussin type
• A Framework for FFT-based Homogenization on Anisotropic Lattices
• Multivariate Anisotropic Interpolation on the Torus
• FFT-based homogenization on periodic anisotropic translation invariant spaces
• Approximation of Periodic PDE Solutions with Anisotropic Translation Invariant Spaces