- Info

#
Near-optimal (Euclidean) metric compression

### Wednesday, January 25th, 2017 16:10

### Schreiber 309

### Near-optimal (Euclidean) metric compression

### Tal Wagner, MIT

### Abstract:

n the Metric Sketching (a.k.a. Distance
Oracle) problem, we are given a finite metric space, and our goal is to
store all the pairwise distances, up to a small relative error, with as
little space as possible. For
Euclidean metrics, a famous dimensionality reduction theorem of Johnson
and Lindenstrauss yields a sketch of size O(log(n)) numbers per point,
or O(log^2(n)) bits per point. We show this can improved to O(log(n))
bits per point, which is tight. We also provide tight bounds for
sketching arbitrary metrics with relative error approaching 1.

I
will present our sketching scheme, and then discuss some extensions,
applications and empirical results that we obtained since the
publication of this work.

Joint work with Piotr Indyk.