# DFT of 2d data points?

If you have some regularly sampled data points (like, a digital sound wave recording), I understand how you take the DFT of that data, by multiplying the data points by sine and cosine waves of specific frequencies. (https://blog.demofox.org/2016/08/11/understanding-the-discrete-fourier-transform/)

I also get how you can do similar if you have regularly sampled 2 dimensional data (like pixels in an image). (https://blog.demofox.org/2016/07/28/fourier-transform-and-inverse-of-images/)

I'm curious though how you'd take the DFT of another type of 1d and 2d data.

If we have some $x=f(N)$ where $N$ is a sequence index, and $x$ is the 1d location of the sequence point, how would I take the DFT of that?

For instance, the image below has data that is purely random so is effectively white noise, and should have a DFT that looks like the DFT of white noise: This data however is "regular grid + jitter" so is small amounts of randomness added to evenly distributed samples. That ought to have a DFT that looks more like blue noise, where there are high frequency components but smaller magnitude lower frequency components. Taking this to 2d, we have a $(x,y) = f(N)$ where $x$ and $y$ is a 2d point location for a sequence index $N$. The image below is poisson disc sampling so again should have high frequency components, but low amounts of low frequency components: While I know what the resulting DFT should look like, I have no idea how to calculate it.

How would I calculate the DFT of these data points?

• I don't think I entirely understand what the goal is. (1) Do I understand correctly that only the spatial location of the points matter, but not their sequence index $N$ in terms of the data? In particular, rather than thinking what you are given as a sequence of data, I can equally well think of them as a set of (un-ordered) data points? (2) In your 2d case, suppose instead of a poisson disc sampling you actually just enumerate the grid points, so all the points sit on a square grid. What do you expect the answer to be? (3) I don't understand the connection between your first picture and... – Willie Wong Jun 9 '17 at 19:32
• ... white noise. Can you explain in more detail why you believe the picture is white noise and have the corresponding DFT? (Basically, when you say you want to compute the DFT of the data points, I don't think you actually mean that you want to compute the DFT of the data points, but rather you want to extract certain types of information about those data points, which frequently involve using the DFT. But I am not sure what is the info you want.) – Willie Wong Jun 9 '17 at 19:36
• 1) You are right that their sequence doesn't matter. I'll see how I can update my question. 3) I've chosen the sample points using a uniformly distributed random number generator, which is how you create white noise either in the audio case (time domain sound samples) or in the image case (using it to set a greyscale color for each pixel). I think it's still relevant to say white noise in this situation but if not let me know! – Alan Wolfe Jun 9 '17 at 19:43
• 2) I'm not really sure what I would expect to see there honestly. Maybe only DC (0 hz)? – Alan Wolfe Jun 9 '17 at 19:44
• Re (2) Really? You don't want to pick up information about the grid spacing? (3) What I am trying to wrap my head around is the fact that when you generate the white noise that way, you are getting a time series; and you cannot just rearrange the order of the points in a time series when doing analysis. (4) It may help me understand better what you want if you can tell me, perhaps in non-mathematical terms, what you want for the output. For example, the DFT allows you to decompose a signal into a superposition of signals of different frequencies, which you can recombine to get the original... – Willie Wong Jun 9 '17 at 19:58

## 1 Answer

As far as I can tell, the best way seems to be just taking the resulting image and computing the Fourier transform thereof. In the continuous case what would be done is:

1. Given the list of points $f(N)$, place a Dirac mass at the location, obtaining the function $$g(x) = \sum_{N} \delta_{f(N)}(x)$$
2. Take the Fourier transform of $g(x)$; the computation is pretty simple (I illustrate in the one dimensional case) \begin{align*} \hat{g}(k) &= \int e^{-ikx} \sum \delta_{f(N)}(x) ~\mathrm{d}x \\ & = \sum \int e^{-ikx} \delta_{f(N)}(x) ~\mathrm{d}x \\ & = \sum_N e^{-ik f(N)} \end{align*}

In the discrete case you will produce the array corresponding to the sampled points (with a value of 1 at the sample and 0 elsewhere) and take the DFT as you would for an image.

References:

• Cook, Stochastic sampling in computer graphics
• Note: Bridson shows in his paper a periodogram in Figure 1. The periodogram shown is averaged over many runs. At the low density he is sampling, and the low number of samples, the corresponding periodogram should look a bit more noisy for one given run.