  We propose a multi-dimensional (M-D) 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 an M-D data cube), which are
parameterized by random slopes and offsets. The discrete Fourier transform
(DFT) along those lines represents projections of M-D DFT of the M-D data onto
those lines. The M-D sinusoids 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 practical
problems.
