Fps-Sft: A Multi-Dimensional Sparse Fourier Transform Based on the Fourier Projection-Slice Theorem

We propose a multidimensional sparse Fourier transform inspired by the idea of the Fourier projection-slice theorem, called FPS-SFT. FPS-SFT extracts samples along lines (1-dimensional slices from a multidimensional data cube), which are parameterized by random slopes and offsets. The discrete Fourier transform (DFT) along those lines represents projections of multidimensional DFT of the data onto those lines. The multidimensional frequencies that are contained in the signal can be reconstructed from the DFT along lines with a low sample and computational complexity provided that the signal is sparse in the frequency domain and the lines are appropriately designed. The performance of FPS-SFT is demonstrated both theoretically and numerically. A sparse image reconstruction application is illustrated, which shows the capability of the FPS-SFT in solving less sparse scenarios containing non-uniformly distributed frequencies.