Fast Function Interpolation for Bandlimited Periodic Signals

Theory

Let \(\phi: \mathbb{R} \to \mathbb{C}\) be a \(T\)-periodic function of bandwidth \(N_{FS} = 2 N + 1\). Then \(\phi\) is fully characterized by its \(N_{FS}\) Fourier Series coefficients \(\{ \phi_{n}^{FS}, n = -N, \ldots, N \}\) such that

(1)\[\phi(t) = \sum_{n = -N}^{N} \phi_{n}^{FS} \exp \left( j \frac{2 \pi}{T} n t \right).\]

Using (1), we can obtain \(M\) values of \(\phi\) at arbitrary positions \(\{t_{k}, k = 0, \ldots, M-1 \}\) with \(\mathcal{O}(N_{FS} M)\) operations.

In the case of \(M\) regularly-spaced samples however, an efficient algorithm based on the Chirp Z-Transform can be used.

Complex-valued Functions

Theorem

Let \(\phi: \mathbb{R} \to \mathbb{C}\) be a \(T\)-periodic function of bandwidth \(N_{FS} = 2 N + 1\). Let \(\{ \phi_{n}^{FS}, n = -N, \ldots, N \}\) be its Fourier Series coefficients and \(a \lt b \in \mathbb{R}\) be the end-points of an interval on which we want to evaluate \(M\) equi-spaced samples of \(\phi\).

Then the following holds:

\[\Phi = A^{N} \text{CZT}_{N_{FS}}^{M} \{ \Phi^{FS} \} \circ W^{-N E},\]

where \(\text{CZT}\) of parameters \(A, W\) is as defined in The Chirp Z-Transform and

\[ \begin{align}\begin{aligned}\Phi & = \left[ \phi(t[0]), \ldots, \phi(t[M - 1]) \right] \in \mathbb{C}^{M},\\\Phi^{FS} & = \left[ \phi_{-N}^{FS}, \ldots, \phi_{N}^{FS} \right] \in \mathbb{C}^{N_{FS}},\\E & = \left[ 0, \ldots, M - 1 \right] \in \mathbb{N}^{M},\\t[k] & = \left( a + \frac{b - a}{M - 1} k \right) 1_{[0, \ldots, M-1]}[k],\\A & = \exp \left( -j \frac{2 \pi}{T} a \right),\\W & = \exp \left( j \frac{2 \pi}{T} \frac{b - a}{M - 1}\right).\end{aligned}\end{align} \]

Proof

Replacing \(t[k]\) in (1), we get

\[ \begin{align}\begin{aligned}\phi(t[k]) & = \sum_{n = -N}^{N} \phi_{n}^{FS} A^{-n} W^{n k}\\& = A^{N} W^{-N k} \sum_{n = 0}^{2 N} \phi_{n - N}^{FS} A^{-n} W^{n k}\\& = A^{N} W^{-N k} \text{CZT}_{N_{FS}}^{M} \{ \Phi^{FS} \}[k],\end{aligned}\end{align} \]

with \(A, W, \Phi^{FS}\) as defined above.

Rearranging the equation into vector form proves the theorem.

Real-valued Functions

Theorem

Let \(\phi: \mathbb{R} \to \mathbb{R}\) be a \(T\)-periodic function of bandwidth \(N_{FS} = 2 N + 1\). Let \(\{ \phi_{n}^{FS}, n = -N, \ldots, N \}\) be its Fourier Series coefficients and \(a \lt b \in \mathbb{R}\) be the end-points of an interval on which we want to evaluate \(M\) equi-spaced samples of \(\phi\).

Then the following holds:

\[\Phi = \phi_{0}^{FS} + 2 \Re \left[ A^{-1} \text{CZT}_{N}^{M} \{ \Phi_{+}^{FS} \} \circ W^{E} \right],\]

where \(\text{CZT}\) of parameters \(A, W\) is as defined in The Chirp Z-Transform and

\[ \begin{align}\begin{aligned}\Phi & = \left[ \phi(t[0]), \ldots, \phi(t[M - 1]) \right] \in \mathbb{C}^{M},\\\Phi_{+}^{FS} & = \left[ \phi_{1}^{FS}, \ldots, \phi_{N}^{FS} \right] \in \mathbb{C}^{N},\\E & = \left[ 0, \ldots, M - 1 \right] \in \mathbb{N}^{M},\\t[k] & = \left( a + \frac{b - a}{M - 1} k \right) 1_{[0, \ldots, M-1]}[k],\\A & = \exp \left( -j \frac{2 \pi}{T} a \right),\\W & = \exp \left( j \frac{2 \pi}{T} \frac{b - a}{M - 1}\right).\end{aligned}\end{align} \]

Proof

Leverage the conjugate symmetry of the \(\phi_{k}^{FS}\) in the previous proof.

Multi-dimensional Functions

For a multi-dimensional signal \(\phi: \mathbb{R}^D \to \mathbb{C}\) that is \([T_1, T_2, \ldots, T_D]\)-periodic and \([N_{FS, 1}, N_{FS, 2}, \ldots, N_{FS, D}]\)-bandlimited, we can also obtain arbitrary values of \(\phi\) on a uniform grid in a similarly efficient manner. To do so, we need to perform a multi-dimensional \(\text{CZT}\) and then modulate along each dimension as done in the complex-valued theorem above.

Implementation Notes

fs_interp() can be used to obtain samples of a function using the algorithms above.

fs_interpn() can be used to obtain samples of a \(D\)-dimensional function.