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

View Researcher's Other Codes

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors Shaogang Wang, Vishal M. Patel, A. Petropulu
Journal/Conference Name I
Paper Category
Paper Abstract 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.
Date of publication 2019
Code Programming Language MATLAB

Copyright Researcher 2022