17:00
Representation Theoretic Patterns in Digital Signal Processing I: Computing the Matched Filter in Linear Time
Abstract
R(t) = exp{2πiωt/p}⋅S(t+τ) + W(t),
where W(t) in H is a white noise, and τ,ω in ℤ/p, encode the distance from, and velocity of, the object.
Problem (digital radar problem) Extract τ,ω from R and S.
I first introduce the classical matched filter (MF) algorithm that suggests the 'traditional' way (using fast Fourier transform) to solve the digital radar problem in order of p^2⋅log(p) operations. I will then explain how to use techniques from group representation theory to design (construct) waveforms S(t) which enable us to introduce a fast matched filter (FMF) algorithm, that we call the "flag algorithm", which solves the digital radar problem in a much faster way of order of p⋅log(p) operations. I will demonstrate additional applications to mobile communication, and global positioning system (GPS).
This is a joint work with A. Fish (Math, Madison), R. Hadani (Math, Austin), A. Sayeed (Electrical Engineering, Madison), and O. Schwartz (Electrical Engineering and Computer Science, Berkeley).