Expander codes, Explicit Euclidean sections, and compressed sensing

Speaker: Prof. Venkatesan Guruswami , University of Washington & Carnegie Mellon University


Classical results from the 1970's state that a random subspace of R^N of dimension N/2 has “distortion” O(1) w.h.p where the distortion is measured by sqrt{N} times the largest ratio of the L_2 to L_1 norms of a vector in the subspace. (So O(1) distortion means each vector in the subspace has its mass spread nearly evenly over a constant fraction of the coordinates.) This result is a particular example of the use of the probabilistic method, a technique which is ubiquitous in asymptotic convex geometry. Similar randomized geometric constructions arise in areas like dimensionality reduction and compressed sensing. Explicit constructions of such objects , however, seem very hard to come by. We will describe constructions inspired by expander codes that can be used to produce subspaces with distortion nearly as good as a random subspace either explicitly or with sublinear randomness. Specifically, we construct an explicit subspace of R^N with dimension N(1-o(1)) and distortion (slightly worse than) poly(log N). The construction combines various ingredients such as Ramanujan graphs, sum-product theorems in finite fields, and Kerdock codes. We are also able to construct subspaces of R^N of dimension N/2 with O(1) distortion using N^d random bits for any constant d > 0 (and hence deterministically in sub-exponential time). The talk will also briefly discuss connections to sparse signal recovery (aka compressed sensing). [Based on joint works with James Lee, Alexander Razborov, and Avi Wigderson]