Uneven sampling

2022 May 31

A common trick when you're sampling and want to filter out noise of a particular frequency f is to space your samples regularly over a period of time of length 1/f. Then, by averaging your samples together, you'll get a good estimate of the DC component of the signal, and the component of frequency f is cancelled out completely, so it can't interfere in your measurement. This technique is common in electronics with the value of f set to 60Hz, the frequency of grid AC. This works because:

$\sum_{k=0}^{n-1} \nu\left(\frac{k}{nf} \right) = 0$

Where the noise function is defined as:

$\nu(t) = Ae^{2\pi i tf}$

Here, A is a random variable, which is why this is considered noise, and it determines the amplitude and phase of the noise.

But sometimes this technique may not be an option. What if, rather than being able to choose nice evenly spaced samples at a particular frequency, you're forced to put your samples at particular predetermined points in time, which may not even be evenly spaced. What if you're only allowed to sample at:

$t_1,t_2,t_3,\dots t_n$

In that case, it's still possible to get a pretty good result and to cancel out noise of frequency f. You'll just have to change how you're averaging, and in particular, to use a weighted average. Choose a set of weights w such that:

$\sum_{k=1}^n w_k = 1$

Then, for an input signal z(t), our weighted average will be:

$\bar z = \sum_{k=1}^n w_k z(t_k)$

What we then have is an optimization problem. We need to choose the weights to give a good result. Ideally, the weighted average will have the smallest possible variance, since that will mean that it's clustered as tightly around the true average as possible. We'll assume that each individual measurement has a standard deviation of σ and that the errors in each measurement are independent.

$\text{Var}(\bar z) = \text{Var}\left(\sum_{k=1}^n w_k z(t_k)\right) = \sum_{k=1}^n \text{Var}\left(w_k z(t_k)\right)$

$= \sum_{k=1}^n w_k^2 \text{Var}\left( z(t_k)\right) = \sum_{k=1}^n w_k^2 \sigma^2 = \sigma^2\sum_{k=1}^n w_k^2$

So this is the objective function we're trying to minimize:

$\min_{w_k} \sum_{k=1}^n w_k^2$

Subject to the constraint:

$\sum_{k=1}^n w_k = 1$

This has the following result:

$w_k=\frac{1}{n}$

This is ignoring the fact that we want to cut out noise of frequency f. But this is simple to fix: we just add another constraint:

$\sum_{k=1}^{n} w_k e^{2\pi i t_k f} = 0$

After adding this constraint, the weights may no longer all be exactly the same, but they will result in a weighted average that is insensitive to noise of frequency f. If we also want to filter out harmonics (eg. 120Hz, 180Hz), or just other frequencies, we add on another constraint for each frequency.

This technique has the advantage that it's mathematiclly straightforward to solve for the weights using least-squares.