How to efficiently convolve the function $h(t)=H(t)e^{-t}$ with a function $x(t)$ sampled non-uniformly, i.e. $\{x(t_0), x(t_1), ..., x(t_{N-1})\}$? $H(t)$ is the Heaviside step function, and the Fourier transform of $h(t)$ is $\tilde{h}(\omega)=(1-i\omega)^{-1}$.

What I have done

If $x(t)$ is sampled uniformly, I can apply the Fourier transform to $x(t)$ (with enough 0-paddings) to get $\tilde{x}(\omega)$, multiply it with $\tilde{h}(\omega)$, and apply inverse Fourier transform to get the convolution result. If $x(t)$ is sampled non-uniformly, the first thing that comes to my mind is to apply the non-uniform discrete Fourier transform (NUDFT). However, it is unclear to me which NUDFT I should use (type I, II, or III?), which points in the frequency domain I should choose, and how to invert them back?


1 Answer 1


After briefly reading the user manual of NUFFT you simply have to choose both variants I and II as forward and backward transformation. With this you can proceed in a similar way as having uniformal distributed data since the modal representation is still based on integer frequencies.

As alternative you may use Toeplitz matrices.


We can define the discrete Fourier transform via trigonometric Interpolation

\begin{align} f_{h}(x)&= \sum_{k=0}^{N-1} c_k e^{ik x} =\sum_{k=0}^{N-1} c_k \phi_{k}(x), \label{al:approx}\\ &=c_{0}\phi_{0}(x)\;+\; c_{1} \phi_{1}(x) \;+ \; \ldots \;+ \; c_{N-1} \phi_{N-1}(x), \end{align}

by minimizing the error at $N$ specific collocation points

\begin{align} \underbrace{\begin{pmatrix} \phi_{0}(x_{0}) & \phi_{1}(x_{0}) & \cdots & \phi_{N-1}(x_{0}) \\ \phi_{0}(x_{1}) & \phi_{1}(x_{1}) & \cdots & \phi_{N-1}(x_{1}) \\ \vdots & \vdots & \ddots & \vdots \\ \phi_{0}(x_{N-1}) & \phi_{1}(x_{N-1}) & \cdots & \phi_{N-1}(x_{N-1}) \end{pmatrix}}_{\mathbf{\underline{V}}} \underbrace{\begin{pmatrix} c_{0} \\ c_{1} \\ \vdots \\ c_{N-1} \\ \end{pmatrix}}_{\mathbf{c}} = \underbrace{\begin{pmatrix} f_{0} \\ f_{1} \\ \vdots \\ f_{N-1} \end{pmatrix}}_{\mathbf{f}}. \end{align}

Here $\mathbf{\underline{V}}$ is the Vandermonde matrix (see also DFT matrix), $\mathbf{c}$ are the modal and $\mathbf{f}$ the nodal values.

You may define the forward and backward DFT as

\begin{align} \mathcal{F}: \ \mathbf{c}&= \mathbf{\underline{V}}^{-1} \mathbf{f}, \\ \mathcal{F}^{-1}: \mathbf{f}&= \mathbf{\underline{V}} \> \mathbf{c}. \end{align}

Note that the inverse of a matrix is generally defined as

\begin{align} \mathbf{\underline{V}}^{-1} = \text{det}(\mathbf{\underline{V}})^{-1} \text{adj}(\mathbf{\underline{V}}). \end{align}

where $\text{det}(\mathbf{\underline{V}})^{-1}$ is a scaling factor and has to be taken into account.

  • $\begingroup$ NUFFT type II is the adjoint, but not the inverse of type I NUFFT. This page (homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/PIRODDI1/NUFT/…) also shows that type I then type II NUFFT does not reconstruct the original signal. If we take type I & II as the forward & backward transformation, then it will produce incorrect results for the convolution. $\endgroup$
    – Firman
    Nov 11, 2022 at 11:47
  • $\begingroup$ @Firman Sure, that's why I pointed to the manual since the scaling factor (determinant) is merely a convention and differs in some treatments. $\endgroup$
    – ConvexHull
    Nov 11, 2022 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.