UDFT: Unitary Discrete Fourier Transform (and related)

This module implements unitary (orthonormal) discrete Fourier transforms and related functions for convolution. It is built on top of the Array API standard via array-api-compat, making it compatible with NumPy, PyTorch, and other compliant array libraries.

It is useful for convolution [1]: they respect the Parseval equality \(\|x\|_2^2 = \|X\|_2^2\), e.g., the value of the null frequency \(X_0\) is equal to

\[X_0 = \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x_n, \text{ and } x_0 = \frac{1}{\sqrt{N}} \sum_{n'=0}^{N-1} X_{n'}.\]

and if \(H\) is a circulant convolution with \(h\) as a real impulse response, then \(H = F^* \Lambda F\) where \(F^*\) is the unitary IDFT computed by irdftn(), \(F\) the unitary DFT computed by rdftn(), and \(\Lambda\) the frequency response computed with ir2fr() from \(h\).

[1] B. R. Hunt "A matrix theory proof of the discrete convolution theorem",
IEEE Trans. on Audio and Electroacoustics, vol. au-19, no. 4, pp. 285-288,
dec. 1971

If you are having issues, please let me know:

francois.orieux AT universite-paris-saclay.fr

Installation

UDFT is a single file (udft.py) requiring Python >= 3.12. Install with pip:

pip install udft

For multithreaded FFT on NumPy arrays, install the optional SciPy dependency:

pip install udft[scipy]

The project follows Semantic Versioning.

License

The code is in the public domain.

Contents

• Discrete Fourier Transform
  • dftn
  • idftn
  • dft
  • idft
  • dft2
  • idft2
• Real Discrete Fourier Transform
  • rdftn
  • irdftn
  • rdft
  • rdft2
• Convolution related
  • ir2fr
  • fr2ir
  • diff_ir
  • laplacian
• Other
  • hnorm
  • crandn