TIME: 1:30-2:20 pm,  October 2, 2007

PLACE: MGH 295

SPEAKER: James Lee
        University of Washington

TITLE:  Expander codes, compressed sensing, and pseudorandom matrices


ABSTRACT:
Classical results in high-dimensional geometry state that on a random
subspace of R^n of proportional dimension, the L_1 and L_2 norms are
equivalent up to universal factors.  Indeed, this is a particular
example of the use of the probabilistic method, a technique which is
now ubiquitous in asymptotic convex geometry.

Similar randomized geometric constructions arise in areas like
high-dimensional nearest-neighbor search and compressed sensing, but
it seems that such objects are very hard to come by explicitly.

I will show how constructions inspired by expander codes can be used
to explicitly produce subspaces that are nearly as good as random for
some of the problems discussed above.  I will also show how distortion
is directly related to sparse signal recovery (i.e. compressed sensing).
Guest appearances by:   Ramanujan graphs, sum-product theorems in finite fields,
and mutually unbiased bases.

[This is based on joint work with Venkat Guruswami and Sasha Razborov]