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).