Harvard Theory of Computation Seminar
Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1
Piotr Indyk, MIT
Place and Time: Monday, October 30, Maxwell Dworkin 319
Refreshments at 2:30pm, talk at 2:45pm
ABSTRACT
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. 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.