Tuesday, April 11, 2000
1:15 PM (refreshments 1:00)
Grier Room, Room 34-401B
EECS Special Seminar
Abstract
We will place the problem of data compression in a broad theoretical context, and we will discuss what is known about how well data can be compressed in practice, using limited resources.
In the first part of the talk we will consider the following question: What is the most efficient way to cover high-dimensional space using spheres of a fixed radius? We will present a precise and very general answer, and show that it contains various results in information theory, statistics and probability as corollaries. These include new converses to some important measure-concentration inequalities, Stein's lemma (in hypothesis testing), and Shannon's classical rate-distortion theorem.
In the second part we will discuss data compression (primarily lossy compression) in more detail. We will present recent results on the limits of how well and how efficiently data can be compressed in practice. The emphasis here will be in refining -- in fact, mostly avoiding -- asymptotics. These results offer significant insights into the design principles of efficient, practical compression algorithms, and they provide intuition about the fundamental limits of achievable compression performance. Connections with statistical model selection and portfolio theory will be briefly pointed out.
|
Modified: Apr 7, 2000|
Current events|
Your comments
and inquiries are welcome.