I am trying to estimate the discrete Fourier transform of a discrete surface, $x:\{1,\dots,N\}\times \{1,\dots,N\} \to\mathbf{R}$, given a sparse set of samples on the grid.
If we had all the samples, we could just compute the DFT directly.
Since we don't have all the samples, one approach is to use the nonuniform discrete Fourier transform (NDFT), but the resulting estimate does not preserve the values of the samples we have, and in experiments I've run, the IFFT of the resulting estimate doesn't look that good given the samples we have:
I think it looks bad because, if I have implemented it properly, the NDFT equals the DFT of a surface that is 0 where we don't have samples.
What is a better way to do this?
Would it work to do a least squares regression for each frequency onto the samples we have?
Here is an idea that guarantees consistency with our sample points, written here for a 1D signal $\mathbf{x}=(x_0,\dots,x_{N-1})$, if we know all the $x_t$ for $t\in S \subseteq \{0,\dots,N-1\}$. I haven't tried it yet...
Choose the approximation $\hat{\mathbf{x}}= [\begin{smallmatrix}\mathbf{x}_S \\ \hat{\mathbf{x}}_{S^C} \end{smallmatrix}]$ from this set: $$\arg\min_{\hat{\mathbf{x}}_{S^C}}\ \left\| \begin{bmatrix} \mathbf{x}_S \\ \hat{\mathbf{x}}_{S^C}\end{bmatrix} -\mathsf{IDFT}\cdot \mathsf{DFT}\cdot \begin{bmatrix}\mathbf{x}_S\\ \hat{\mathbf{x}}_{S^C}\end{bmatrix}\right\|^2$$
This set is the collection of signals that appear most consistent with our sample in a least-squares sense.
Since the IDFT and DFT are linear transforms, the above can be expanded into just a linear least-squares problem, which has a closed form solution.
This will be about as fast as a matrix inversion and a few matrix multiplies, plus minus a few of these operations if you know the sampling pattern a priori.