Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1
Speaker: Piotr Indyk , MIT CSAIL
Date: February 15 2007
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Madhu Sudan, MIT CSAIL
Contact: Joanne Hanley, 617 253 6054, joanne@csail.mit.edu
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/piotr-abs.html
The area of geometric functional analysis is concerned with studying properties of geometric (normed) spaces. A typical question in the area is: given two geometric spaces X, Y, is there an embedding F of X into Y so that F distorts the distances between any pair of points by only a constant factor ? One of the classic results of this type is a constant-distortion embedding of an n-dimensional space equipped with L2 norm, into an O(n)-dimensional space equipped with L1 norm (also known as Dvoretzky's theorem for L_1). Embeddings have many interesting applications, in computer science and beyond.
A ubiquitous tool for constructing such embeddings is the probabilistic method: the mapping is chosen at random, and one shows that it "works" with high probability. Unfortunately, this approach does not yield a concrete (or explicit) construction of an embedding. A folklore open problem has been to obtain explicit constructions with parameters that (almost) match the non-constructive bounds. However, the progress on this front has been somewhat limited. For example, the best known explicit construction of an embedding of an n-dimensional L2 space into an m-dimensional L1 space guaranteed only m=O(n^2).
In this talk I will show an explicit construction of an embedding of an n-dimensional L2 space into L1 space of dimension n^{1+o(1)}. The construction utilizes two tools: discrete uncertainty principles (introduced by Donoho and Stark in the area of digital signal processing) and randomness extractors. If time allows, I will also show some related constructions, with application to digital signal processing and compressed sensing.
See other events that are part of Algorithms and Complexity Series 2006/2007
See other events happening in February 2007
