Non-uniform discrete Fourier transform

Remarks

Example: with $K = N$, $p_n = n/N$ and $f_k = k$, the sum is $\sum_n x_n e^{-2\pi i nk/N}$, the ordinary discrete Fourier transform; it is both of type I and of type II. Non-example: the sum $\sum_{n \in \Z} x_n e^{-2\pi i n f}$ over all integers is not a non-uniform DFT, because the definition requires finitely many sample points. The map $x \mapsto X$ is linear, with the $K \times N$ matrix $A_{kn} = e^{-2\pi i p_n f_k}$. Unlike the DFT matrix, $A$ is in general not a multiple of a unitary matrix, and it can be badly conditioned or singular, for example when two sample points coincide. The adjoint transform, with $e^{+2\pi i p_n f_k}$, is used in place of an inverse. Some authors use multidimensional points $p_n, f_k \in \R^d$ with the dot product $p_n \cdot f_k$ in the exponent.