Talk: On Multiplicative Approximations and Some Geometric Applications
Speaker: Ilan Newman , University of Haifa
Date: August 14 2012
Time: 2:00PM to 3:00PM
Location: 32-G449 (kiva)
Host: Ronitt Rubinfeld, MIT
Contact: Joanne Hanley, 3-6054, joanne@csail.mit.edu
Relevant URL: Abstract: Let $F$ be a set system over an underlying finite set $X$,
and let $\mu$ be a measure on $X$, inducing to a measure on $F$:
$\mu(S)=\sum_{x\in S} \mu(x)$. A measure $\mu^*$ on $X$ is a {\em
multiplicative ${\lambda}$-approximation} of $\mu$ if for every $S\in
F$ $\mu(S) \leq \mu^*(S) \leq (1+\epsilon) \mu(S)$.
The central question raised in this work is about the existence of
meaningful structural properties of $F$ implying that for any $\mu$ on
$X$ there exists an ${{1+\epsilon}$-approximation $\mu^*$ that is
supported on a small subset of $X$.
It turns out that the parameter that governs the support size of a
multiplicative approximation is the {\em triangular rank} of $F$. It
is defined as the maximal length of a sequence of sets $S_1, \ldots
,S_t$ in $F$ such that $S_i \not\subseteq \cup_{ji=2,...,t$. We show that for any $\mu$ on $X$ and $0<\epsilon<1$,
there is measure $\mu^*$ that ${{1+\epsilon}$-approximates $\mu$ and
has support of size $O(\trk(F) \cdot \vcdim(F)/ \epsilon^2)$, where
$\vcdim(F)$ and $trk(F)$ are the VC-dimension and triangular rank of
$F$ respectively (and the later upper-bounds the former).
We also present some alternative constructions which in some cases
improve upon this bound. Conversely, we show that for any $\epsilon <
1$ there exists a $\mu$ on $X$ that cannot be
${{1+\epsilon}$-approximated by any $\mu^*$ with support smaller than
$\trk(F)$.
As an application we show a new dimension-reduction result for
$\ell_1$ metrics: Any $\ell_1$-metric on $n$ points can be
(efficiently) embedded with ${{1+\epsilon}$-distortion into
$\R^{O(n/\epsilon^2)}$ equipped with the $\ell_1$ norm. This improves
over the best previously known bound of $O(n \log n /\poly(\epsilon))$
on dimension, due to Schechtman.
This is a joint work with Yuri Rabinovich.
See other events that are part of
See other events happening in August 2012
