Sub-Linear Channel Estimation and the Heisenberg group

Multiple wireless sensing tasks, e.g. radar detection for driver safety, involve estimating the "channel" or relationship between signal transmitted and received.In this talk I will tell you about the standard math model for the radar channel. In the case where the channel is sparse, I will demonstrate a channel estimation algorithm that is sub-linear in sampling and arithmetic complexity (and convince you of the need for such). The main ingredients in the algorithm will be the use of an intrinsic algebraic structure known asthe Heisenberg group and recent developments in the theory of the sparseFast Fourier Transform (sFFT, due to Indyk et al.)The talk will assume minimal background knowledge.