Thursday,
January 24, 3:15 p.m. GWC 487
Mark Iwen
University of Michigan, Department of Mathematics
Faster Fourier Transforms via Compressed Sensing
Abstract
I will discuss a recently proposed Deterministic sublinear-time Sparse
Fourier Transform algorithm (hereafter called DSFT). DSFT can exactly
reconstruct the Fourier transform (FT) of an N-bandwidth signal f,
consisting of B << N non-zero frequencies, using O(B^2 log^4(N)) time and
O(B^2 log^3(N)) f-samples. DSFT works by taking advantage of natural
aliasing phenomena to hash a frequency-sparse signal's FT information
modulo O(B log (N)) pairwise coprime numbers via O(B log (N)) small
Discrete Fourier Transforms. Number theoretic arguments then guarantee
the original DFT frequencies/coefficients can be recovered via the
Chinese Remainder Theorem. DSFT's usage of primes makes its runtime and
signal sample requirements highly dependent on the sizes of sums and
products of small primes. Thus, we can use analytic number theoretic
techniques to generate (asymptotic) bounds for DSFT. Applications,
algorithmic improvements, and implementation issues will also be discussed.
For further information please contact:
mittelmann@asu.edu