Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

Piotr Indyk (MIT CSAIL)

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.

Host: Madhu Sudan

(The Algorithms and Complexity Seminar series talks are usually held Thursdays from 4-5:15pm in 32-G575.)