Almost Linear Complexity Methods for Delay-Doppler Channel Estimation

A fundamental task in wireless communication is channel estimation: Compute the channel parameters of a medium between a transmitter and a receiver. In this talk we will treat the case of delay-Doppler channels — thus a signal, while transmitted, undergoes time-frequency shifts. We will introduce the incidence and cross methods for channel estimation. The arithmetic complexity of the incidence and cross methods is (Nlog{N}+r^3), and O(Nlog{N}+r^2), respectively, for channels of sparsity r. The most efficient previously known algorithm for delay-Doppler channel estimation has arithmetic complexity O(rNlog{N}) operations. This is a joint work with Prof. Gurevich (Math, UW-Madison).