Robust Quantization and Uncertainty Principles

Time Frequency Brown Bag Seminar, Princeton, March 23, 2006

The uncertainty principle in Harmonic Analysis has been
interpreted and enriched in a way to yield algorithms for signal
reconstruction (sparse recovery problem). We will see that
uncertainty principles can also be used in a natural way to
construct robust vector quantizers. Such a quantizer takes a
unit vector in Euclidean space and makes its components integers
of constant magnitude. Even when an epsilon percentage of
coefficients is quantized incorrectly, the quantization error
will be of order of epsilon. This is an algorithmic version of
Kashin's theorem in asymptotic convex geometry. Open problems
will be discussed.

[Joint work with Yura Lyubarskii]