Multidimensional Sparse Fourier Transform Based on the Fourier Projection-Slice Theorem

We propose Multidimensional Random Slice-based Sparse Fourier Transform (MARS-SFT), a sparse Fourier transform for multidimensional, frequency-domain sparse signals, inspired by the idea of the Fourier projection-slice theorem. MARS-SFT identifies frequencies by operating on one-dimensional slices of the discrete-time domain data, taken along specially designed lines; these lines are parametrized by slopes that are randomly generated from a set at runtime. The discrete Fourier transforms (DFTs) of data slices represent DFT projections onto the lines along which the slices were taken. On designing the line lengths and slopes so that they allow for orthogonal and uniform projections of the sparse frequencies, frequency collisions are avoided with high probability, and the multidimensional frequencies can be recovered from their projections with low sample and computational complexity. We show analytically that the large number of degrees of freedom of frequency projections allows for the recovery of less sparse signals. Although the theoretical results are obtained for uniformly distributed frequencies, empirical evidence suggests that MARS-SFT is also effective in recovering clustered frequencies. We also propose an extension of MARS-SFT to address noisy signals that contain off-grid frequencies and demonstrate its performance in digital beamforming automotive radar signal processing. In that context, the robust MARS-SFT is used to identify range, velocity, and angular parameters of targets with low sample and computational complexity.