Combinatorics Seminar
When: Sunday, March 7, 10am
Where: Schreiber 309
Speaker: Adi Shraibman, Tel Aviv University
Title:
Some encounters with Poincare's inequality
Abstract:
We describe three different results. The first concerns
approximating the
average distance between points in some metric space. Our main
focus
is on
points in a Euclidean space. The second result is about conditional
dimension
reduction. Dimension reduction is a crucial part of many geometric
algorithms,
but it's limits are well known and sometimes it does not suffice.
One
can improve
the performance by relaxing the requirements, e.g. by asking to
preserve only
the distance between a subset of the pairs of points.
The last work is about the problem of approximating a noisy (or
partially observed)
target matrix Y with another matrix X. This natural problem
arises often in practice, e.g. when analyzing tabulated data such
as
gene expressions, word counts in a corpus of documents, or user
preferences
over a range of items.
The connecting thread between these works is an inequality of
Poincare. We will
present Poincare's inequality and describe the role it plays in the
above three results.