Multidimensional Sparse Fourier Transform & Application to Digital Beamforming Automotive Radar

With the rapid developments in advanced driver-assistance systems and self-driving vehicles, the automotive radar plays an increasingly important role in providing multidimensional information on the dynamic environment to the control unit of the vehicle. Traditional automotive radars use digital beamforming to identify range, velocity, and angular parameters of pedestrians, vehicles, obstacles, referred to here as targets. In that context, in the return signal after demodulation, each target is represented as a D-dimensional complex sinusoid, whose frequency in each dimension is related to the target parameters. When the number of targets is much smaller than the number of samples, the return is sparse in the D- dimensional frequency domain.
Sparsity can be employed to reduce the complexity and computation time of the process that estimates D-dimensional frequencies.
In this talk, we present MARS-SFT, a novel 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; those lines are parametrized by slopes that are randomly generated from a set at runtime. The Discrete Fourier Transforms (DFT) of data slices represent multidimensional 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 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 evidences suggest 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, where MARS-SFT can be used to identify range, velocity and angular parameters of targets with low sample and computational complexity.