Efficient Estimation of a Sparse Delay-Doppler Channel

Multiple wireless sensing tasks, e.g., radar detection for driver safety, involve estimating the "channel" or relationship between signal transmitted and received. In this paper, we focus specifically on the delay-doppler channel. This channel model has recently become relevant on the heels of the mmWave breakthrough, because the signals used experience a significant doppler effect. Additionally, high resolution delay-doppler estimation is often desirable, and one standard approach to achieving this is to use signals of large bandwidth, which is feasible in the mmWave realm. This approach, however, results in a tension with the desire for efficiency because, in particular, large bandwidth immediately implies that the signals in play live in a space of very high dimension N (e.g., similar to 10(6) in some applications), as per the Shannon-Nyquist sampling theorem. To address this, in this paper we propose a novel randomized algorithm for channel estimation in the k-sparse setting (e.g., k objects in radar detection), with sampling and space complexity on the order of k(log N)(2), and arithmetic complexity on the order of k(log N)(3) + k(2) , for N sufficiently large. To the best of our knowledge, the algorithm is the first of this nature. It seems to be extremely efficient, yet it is just a simple combination of three ingredients, two of which are well-known and widely used, namely digital chirp signals and discrete Gaussian filter functions, and the third being recent developments in Sparse Fast Fourier Transform algorithms.