Tue, 17 Jan 2012

Representation Theoretic Patterns in Digital Signal Processing I: Computing the Matched Filter in Linear Time

Professor S Gurevich
In the digital radar problem we design a function (waveform) S(t) in the Hilbert space H=C(Z/p) of complex valued functions on Z/p={0,...,p-1}, the integers modulo a prime number p>>0. We transmit the function S(t) using the radar to the object that we want to detect. The wave S(t) hits the object, and is reflected back via the echo wave R(t) in H, which has the form

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

Wed, 23 Jul 2008

14:30 - 15:30

Isomorphism Types of Maximal Cofinitary Groups

Bart Kastermans
Cofinitary groups are subgroups of the symmetric group on the natural numbers

(elements are bijections from the natural numbers to the natural numbers, and

the operation is composition) in which all elements other than the identity

have at most finitely many fixed points. We will give a motivation for the

question of which isomorphism types are possible for maximal cofinitary

groups. And explain some of the results we achieved so far.

Wed, 19 May 2004

Galois groups of p-class towers

Prof Nigel Boston
Galois groups of p-class towers of number fields have long been a mystery,

but recent calculations have led to glimpses of a rich theory behind them,

involving Galois actions on trees, families of groups whose derived series

have finite index, families of deficiency zero p-groups approximated by

p-adic analytic groups, and so on.

Subscribe to Wisconsin