The Fast Fourier Transform algorithm computes a Fourier decomposition under the assumption that its input points are equally spaced in the time domain, $t_k = kT$. What if they're not? Is there another algorithm I could use, or some way I could modify the FFT, to account for what is effectively a variable sampling rate?

If the solution depends on how the samples are distributed, there are two particular situations I'm most interested in:


Constant sampling rate with jitter: $t_k = kT + \delta t_k$ where $\delta t_k$ is a randomly distributed variable. Suppose it's safe to say $|\delta t_k| < T/2$.
Dropped samples from an otherwise constant sampling rate: $t_k = n_k T$ where $n_k \in\mathbb{Z}\ge k$


Motivation: first of all, this was one of the higher voted questions on the proposal for this site. But in addition, a while ago I got involved in a discussion about FFT usage (prompted by a question on Stack Overflow) in which some input data with unevenly sampled points came up. It turned out that the timestamps on the data were wrong, but it got me thinking about how one could tackle this problem.

There is a wide variety of techniques for non-uniform FFT, and the most efficient ones are all meant for exactly your case: quasi-uniform samples. The basic idea is to smear the unevenly sampled sources onto a slightly finer ("oversampled") uniform grid though local convolutions against Gaussians. A standard FFT can then be run on the oversampled uniform grid, and then the convolution against the Gaussians can be undone. Good implementations are something like $C^d$ times more expensive than a standard FFT in $d$ dimensions, where $C$ is something close to 4 or 5. 

I recommend reading Accelerating the Nonuniform Fast Fourier Transform by Greengard and Lee.

There also exist fast, i.e., $O(N^d \log N)$ or faster, techniques when the sources and/or evaluation points are sparse, and there are also generalizations to more general integral operators, e.g., Fourier Integral Operators. If you are interested in these techniques, I recommend Sparse Fourier transform via butterfly algorithm and A fast butterfly algorithm for the computation of Fourier Integral Operators. The price paid in these techniques versus standard FFT's is a much higher coefficient. Disclaimer: My advisor wrote/cowrote those two papers, and I have spent a decent amount of time parallelizing those techniques.

An important point is that all of the above techniques are approximations that can be made arbitrarily accurate at the expense of longer runtimes, whereas the standard FFT algorithm is exact.
