Finite Volume Spaces and Sparsification

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

previous revision was the wrong file: the new revision: changed (extended considerably) the treatment of finite volumes (see r

Scientific paper

We introduce and study finite $d$-volumes - the high dimensional generalization of finite metric spaces. Having developed a suitable combinatorial machinery, we define $\ell_1$-volumes and show that they contain Euclidean volumes and hypertree volumes. We show that they can approximate any $d$-volume with $O(n^d)$ multiplicative distortion. On the other hand, contrary to Bourgain's theorem for $d=1$, there exists a $2$-volume that on $n$ vertices that cannot be approximated by any $\ell_1$-volume with distortion smaller than $\tilde{\Omega}(n^{1/5})$. We further address the problem of $\ell_1$-dimension reduction in the context of $\ell_1$ volumes, and show that this phenomenon does occur, although not to the same striking degree as it does for Euclidean metrics and volumes. In particular, we show that any $\ell_1$ metric on $n$ points can be $(1+ \epsilon)$-approximated by a sum of $O(n/\epsilon^2)$ cut metrics, improving over the best previously known bound of $O(n \log n)$ due to Schechtman. In order to deal with dimension reduction, we extend the techniques and ideas introduced by Karger and Bencz{\'u}r, and Spielman et al.~in the context of graph Sparsification, and develop general methods with a wide range of applications.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Finite Volume Spaces and Sparsification does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finite Volume Spaces and Sparsification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite Volume Spaces and Sparsification will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-406194

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.