# What is the frequency representation of nonuniform sampling?

Uniform sampling can be thought of as multiplication of a function $$x(t)$$ with a Dirac comb function: $$\text{III}_T(t) = \sum_{k=-\infty}^{\infty}\delta(t-kT)$$

Multiplication of $$x(t)$$ with $$\text{III}_T(t)$$ is equivalent to convolution with $$\text{III}_{1/T}(f)$$ in the Fourier domain, giving rise to copies of $$X(f)$$ spaced by $$\Delta f = 1/T$$ (the well known sampling theorem): $$\sum_{k=-\infty}^{\infty} X(f-\frac{1}{T}k)$$

Question: What is the frequency representation of a non-uniformly sampled $$x(t)$$? Or relatedly, what is the Fourier transform of a non-uniform Dirac comb, assuming we know the time of each impulse?

The easy answer is that it is a sum of complex exponentials, but is there a way to simplify this, or see that it converges to a frequency domain Dirac comb as the time domain spacing approaches that of a uniform Dirac comb?

Many thanks for any insights!

• You gotta scaling issue with $T$ that you might wanna worry about. It's quite common and almost every electrical engineering text puts this $T$ in the passband gain of the reconstruction LPF, where it does not belong. Jun 23 at 16:16
• Could you elaborate Robert? Or do you have a link I could look at? Thanks for pointing that out. Jun 24 at 0:55
• Sure. I wrote several answers here and have bitched for decades on comp.dsp about this issue, because nearly all EE DSP textbooks do it wrong. They're mathematically good because they put this scaler $T$ into the passband gain of the reconstruction low-pass filter. Jun 25 at 23:47
• The strict mathematical point is that you gotta multiply $x(t)$ with $T\cdot \mathrm{III}_T(t)$ to get $$\sum_{k=-\infty}^{\infty} X\big(f-\tfrac{k}{T} \big)$$ in the frequency domain. If you leave that leading $T$ off in the dirac comb function, then you get an additional factor of $\frac1T$ in the frequency domain and most textbooks deal with that with a $T$ in the passband gain of the reconstruction filter where it doesn't belong. Jun 25 at 23:52
• Now, if your non-uniform sampling was sorta uniform in it's non-uniformity, then this idea from Bob Adams shows that if you throw away one sample out of every $N$ samples, you can still get perfect reconstruction if your input $x(t)$ is bandlimited to a little lower than Nyquist: $$X(f) = 0 \qquad \forall \ \ |f| \ge \frac{N-1}{N} \frac{1}{2T}$$ Remember $\frac{1}{T} = f_\mathrm{s}$ is the sampling frequency, so half of it is Nyquist. Jun 26 at 0:01

Matlab has the nufft which uses:

For a vector $$X$$ of length $$n$$, sample points $$t$$, and frequencies $$f$$, the nonuniform discrete Fourier transform of $$X$$ is defined as

$$Y(k)= \sum_{j=1}^{n} X(j)e^{−2\pi i t(j) f(k)}$$

where $$k = 1, 2, \ldots, m$$. When $$t = 0, 1, \ldots, n-1$$ and $$f = (0, > 1, \ldots, n-1)/n$$ (defaults for nufft), the formula is equivalent to the uniform discrete Fourier transform used by the fft function.

For the simplest case of $$N$$ random samples of $$x(t)$$ taken over a duration of $$T$$ and satisfying the average Nyquist rate criterion, then the resulting Fourier transform of the non-uniform samples will be an $$N$$-fold aliased (as if $$N$$ times undersampled) and weighted sum of $$X(\Omega)$$.

This is an approximate statement which would be ideally true if the sampling instants periodically repeated by blocks of $$N$$, an ideal situation. If this is not so; i.e., random sampling instants never repeat or do not extend from minus to plus infinity, or if there's no analytic expression for the non-uniform sampling instants, then a closed form expression for the Fourier transform of the non-uniform samples may not exist. (I cannot say it won't, but I think it won't)

• If sampling instants are non-random and expressed as some $f(k) \neq kT$, wouldn't $\mathcal{F}$ also be some function of $k$? Jun 23 at 0:04
• @OverLordGoldDragon reading the answer you could see that if sampling instants have an analytic expression then there can be a closed form Fourier transform. Jun 23 at 0:24
• Thanks for the answer @Fat32. If the sampling is random, but we know where the samples were taken, can we say anything about how the aliasing occurs? Like where the wrapping point is for the ailaised copy of the spectrum for a given sample or something like that (if that even makes sense)? Also, what do you mean by "sampling instants periodically repeated by blocks of N"? Thanks again for your answer. Jun 23 at 4:00
• @Gillespie yes that's the most typical scenerio. Aliasing will be similar to that of undersampling by N, but with special weights. Repeating is to make finite length samples go to infinity for mathematical convenience. Jun 23 at 15:25
• @Gillespie No. They are centered at $k \Omega_s/N$ to right; that's why I miscoined the term N-fold alias :-) Jun 24 at 3:01

If the samples are finite (e.g. not a running process) then you'd have to take the greatest common divider and resample all the vector, resulting in a "toothless" train of impulses.

For example, suppose the vector is $$x=[1, 2, 1, 3]$$ and it's sampled at $$t=[0, 3, 5, 10]$$. The time derivative will be $$t'=[3, 2, 5]$$, showing the step sizes. This means that the maximum sample size that would satisfy equisampling would be $$T=1$$, in which case the resulting vector will look like this: $$y=[1, 0, 0, 2, 0, 1, 0, 0, 0, 0, 3]$$. This is as "analytic" as you can get.

If $$x$$ is a live signal then the only thing you can do is to use chunks of the signal and perform an FFT on them as above, but any subsequent difference will mean that the first FFT will not be the same as any of the following chunks.