# Computing convolution on non-uniform sample

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?

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.

Edit:

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.

• 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. Nov 11, 2022 at 11:47
• @Firman Sure, that's why I pointed to the manual since the scaling factor (determinant) is merely a convention and differs in some treatments. Nov 11, 2022 at 13:40