# FFT of “implicitly” uniform data

I am trying to take a Fourier transform of a density field estimated from mock galaxy survey catalogs.

Basically, you start with a list of galaxy positions, then you bin these positions over some grid spacing, getting an array with a weight for each grid position in the relevant volume of space.

Because I am trying to preserve the information about small spatial scales, I would like to avoid using large bins. Unfortunately, this makes a full array representation of the density field quite memory expensive, as there are huge numbers of empty bins which are for most purposes irrelevant.

I have thus far been binning without the array representation, instead keeping the data in a list of coordinates with their respective weights.

However, my understanding is that this is not sufficient to perform a standard FFT routine. I need evenly spaced data, which I do not have in this representation.

A natural option could then be something like pynufft (since I am using Python primarily) or nfft.

However, my situation seems somewhat different from the standard non-uniform FFT one; I am not dealing with "nonuniform sampling" per se, rather, my sampling is perfectly uniform but just too large to store with explicit zeroes.

Is there any implementation of FFT which would allow me to not create an explicit array of zeros, or at least leverage the fact that I implicitly know the "missing" bins in the sparse representation of my data are zero-valued?

• Would this really help you? The output of the FFT will still be a full uniform array of Fourier coefficients, so you'll need all that memory in the end anyway. – user3883 Jul 1 '18 at 5:45
• You make a good point. I hadn't yet thought of this. – Davis Jul 2 '18 at 18:49

Since your histogram is very sparse, your density field is approximately a sum of weighted delta functions: $$\rho(\vec r) = \sum_{j=1}^{N_{\mathrm{bins}}} w_j\, \delta(\vec r - \vec r_j)$$ where $r_j$ is the center of each bin, and $w_j$ is the weight. Its Fourier transform is then simply \begin{align} \hat\rho(\vec k) &= \int \exp(-i\vec k\cdot\vec r) \rho(\vec r)\,d^3r \\ &= \sum_{j=1}^{N_{\mathrm{bins}}} w_j \exp(-i\vec k\cdot\vec r_j) \end{align} Alternatively, you could skip the binning process, treating each galaxy as being in its own "bin" with weight equal to one. In principle, this gives you access to arbitrarily high-$k$ information (rather than being limited by the physical width of the bin), but it will be noisier than the binned density.