skip to content
 

Explicit Euclidean Sections, Codes over the Reals and Expanders

Presented by: 
A Wigderson [IAS Princeton]
Date: 
Tuesday 12th April 2011 - 13:45 to 14:45
Venue: 
INI Seminar Room 1
Abstract: 
Here is a basic problem, which comes under various names including "compressed sensing matrices", Euclidean sections of L1", "restricted isometries" and more. Find a subspace X or R^N such that every vector x in X has the same L1 and L2 norms (with proper normalization) up to constant factors. It is known that such subspaces of dimension N/2 exist (indeed "most" of them are), and the problem is to describe one explicitly. I will describe some progress towards this problem, based on extending the notion of expander codes from finite fields to the reals.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute The Leverhulme Trust London Mathematical Society Microsoft Research NM Rothschild and Sons