Speaker: Venkatesan Guruswami
Title: Compressed Sensing, Euclidean sections, and JL lemma
Abstract:
I will discuss the compressed sensing problem, which has received a lot of
attention in diverse communities in the last 4-5 years. (The repository at
Rice University http://www.dsp.ece.rice.edu/cs/ gives an idea of the volume of
recent work this problem has attracted.) In this talk, I will focus on
connections of this problem to two classical themes in high-dimensional
geometry: (i) Euclidean sections (or low-distortion embeddings of \ell_2 into
\ell_1), and (ii) the Johnson-Lindenstrauss lemma and restricted isometry. I
might also discuss some recent work on constructing explicit/derandomized
Euclidean sections and compressed sensing matrices using expander graphs.