# Spatial spectrum of EEG data: non-uniform DFT?

I want to compute the spatial spectrum of EEG data collected using a non-uniformly sampled grid of sensors (as in the figure below). One way to do this would be to interpolate the data on a uniformly spaced rectangular grid. However, I would like to try a non-uniform DFT approach.

QUESTION 1: Do you think an nonuniform DFT makes sense for such an electrode grid?

QUESTION 2: The reason I would like to used the nonuniform DFT is that I would like to extract the most parsimonious frequency representation. I will try to explain it better. With the uniform DFT, one can compute ~N/2 Fourier coefficient (N = number of points) at evenly spaced frequency intervals. One can estimate the DFT at further frequency point, theses, however, will only be an interpolated version of the set of N/2 coefficients. For the non-uniform case it is unclear to me, how many non-interpolated coefficients one can extract and what these coefficients are. Any idea?

QUESTION 3: I was checking the NFFT implementation, however I am confused by the fact that the grid points must be constrained to the [-1/2 1/2] grid. Is it enough if I scale down my grid to this range?

QUESTION 4: The electrodes are actually placed on the scalp surface. The grid below is a 2-D representation of the 3D scalp surface. Is there a way to compute a nonuniform DFT directly on the 3D grid?

• What exactly do you mean by: "spatial spectrum of EEG"? Did you have a look on phsyiological signal processing tools like: EEGLAB, SPM, Fieldtrip etc. see how they handle this kind of processing? – Irreducible Apr 9 '18 at 5:55
• Can I please ask how do you envisage doing this "spatial spectrum", from the point of view of the signals acquired? The reason I am asking is because: 1) There are already techniques for that (which you may be aware of, of course, but might be inadequate for what you are attempting), 2) There might be additional steps you need to take. – A_A Apr 9 '18 at 8:00
• Tools like EEGlab do not compute spatial spectra (they only compute sprectra of the time signal), it is not something that is too commonly done in EEG . Computing a spatial EEG spectrum is trivial if the samples are on a uniform regular rectangular grid. In that case an FFT2 suffices. An interpolation of the EEG signal on such grid is obviously possible. However, I want to keep the number of variables to the bare minimum. That is why would like to attempt a nonuniform FT. Even better would be a FT computed directly on the 3D surface (methods for FT on spherical shells are readily available). – Cesare Apr 9 '18 at 11:52

QUESTION 1: Do you think an nonuniform DFT makes sense for such an electrode grid?

The answer to that specific question is yes.

QUESTION 2: The reason I would like to used the nonuniform DFT is that I would like to extract the most parsimonious frequency representation. ...

With this, I suppose that you are after the most parsimonious frequency representation in the spatial domain. In other words, the answer to the question, "How many waves and at what frequencies and amplitudes compose the "surfface" of the electric field potential that is detected by the electrodes at the scalp". If that is accurate (?), it will be a useful reference later on.

... For the non-uniform case it is unclear to me, how many non-interpolated coefficients one can extract and what these coefficients are. Any idea?

In the case of a type 2 NUDFT, it is still $\frac{N}{2}$ discrete frequencies.

In the non-iterative cases, there is an implicit interpolation step anyway in order to be able to then use the Fast Fourier Transform, whether this is done via oversampling or "gridding". As is mentioned in "Using NFFT 3 – a software library for various nonequispaced fast Fourier transforms" (page 15):

"The chief idea of the NFFT algorithm is to use standard FFTs in combination with an approximation scheme that is based on a window function $\phi$. This function needs to be mutually well localized in time/spatial and frequency domain."

QUESTION 3: I was checking the NFFT implementation, however I am confused by the fact that the grid points must be constrained to the [-1/2 1/2] grid. Is it enough if I scale down my grid to this range?

I cannot find that specific reference but this probably refers to normalised frequency. If you notice (1) from here, the only thing that changes between the uniform and non-uniform Discrete Fourier Transform (DFT) is the substitution of the time variable with a sequence. In other words, the discrete sinusoids of the DFT (the $k$s) still "run" at the frequencies they would run anyway but you take extra care to correlate the acquired signal samples at the right phase. That is, take their relative timestamps into account, rather than simply putting them one next to the other as if they were acquired at equi distant sample intervals.

QUESTION 4: The electrodes are actually placed on the scalp surface. The grid below is a 2-D representation of the 3D scalp surface. Is there a way to compute a nonuniform DFT directly on the 3D grid?

Yes, with the non-uniform spherical version of the FFT. The brain is not a sphere though.

Now, let me suggest a different approach to achieve what you are trying to do.

The reason I asked you "...how do you envisage this "spatial spectrum"..." is because given a $N \times M$ matrix $X$ of acquired data over $N$ samples and $M$ electrodes, there are $N$ different "spatial spectra" that you can obtain. This is because, time and space are two different variables and obtaining the spatial spectrum means that you obtain the two dimensional Fourier Transform over all stations ("theses") at the same time instance. So, you freeze time and you obtain the spatial spectrum of *the electric potential measured across the scalp".

The next natural thought here is to say "that's not a big deal I will integrate over time and possibly over frequency as well and therefore will be extracting the spatial spectrum of the strongest wave activity across the scalp". Which leads us to things like filtering at a brain wave rhythm and then evaluating the distribution of those waves across the scalp and then, by that integration step, we essentially "freeze" activity over a unit of time and that allows us to obtain a spatial spectrum.

Eventually, you would be getting closer and closer to something that a technique like LORETA gives you for free.

LORETA estimates a small number of sources that are responsible for the electric activity across the scalp and projects that activity back to the scalp to form a potential map. So, essentially, if you were to use LORETA to estimate the distribution of the field you also get a nicely interpolated potential from the small number of sources that the low number of electrodes can estimate and you can then do a two dimensional FFT on that "reconstruction".

For more information you might want to have a closer look at this.

Hope this helps.

• Thanks a lot for your answer and the information. I will go through it carefully. To answer your final question: I am not attempting source reconstruction. My goal is to apply the 2D FT to each frame separately on the raw EEG signal. Two things are particularly important to me: 1) the transformation should NOT be data driven (-> choice of Fourier Transform + looking at the spatial EEG spectral distribution is interesting per se for the problem I want to tackle) 2) I want the computed spectral values to be as little correlated as possible (-> avoid interpolation in either domains). – Cesare Apr 10 '18 at 10:20
• @Cesare Thanks for letting me know. If you found this helpful you can upvote and / or accept it via the controls on the left of the answer. I am not saying that you want to do reconstruction. I am suggesting that route as an intermediate step towards what you are trying to achieve. Correlation in (2) depends on the physics of the problem and in EEG close-by electrodes are likely to be correlated. All the best – A_A Apr 10 '18 at 11:21
• The point that is still unclear to me is the following. Let's stick to the 1D case. For a uniformly sampled white noise sequence we compute the N/2 DFT frequency coefficients, which are also be largely uncorrelated. We could compute the DFT directly also at other frequencies, however this would only be a sync interpolation of the N/2 values. Now, if the samples are non-uniform, what are the N/2 coefficients that are maximally uncorrelated in the frequency domain? I can't imagine these being the same as for the uniform DFT. – Cesare Apr 10 '18 at 11:35
• @Cesare, "largely uncorrelated" applies to the time-domain samples. The frequency domain samples (for white noise) will all have similar amplitudes and completely unpredictable phase. In the non-uniform case, you don't have a sinc pulse but that $\phi$ function. – A_A Apr 10 '18 at 11:57
• For a DFT, the spectral values are asymptotically independent (check Percival and Walden or directly the results from David Brillingen). Essentially the power spectrum computed with the DFT is very very noisy. What happens in the non uniform case? The asymptotic independence probably still holds for the power of N/2 coefficients, but which ones? – Cesare Apr 10 '18 at 12:14