Yair Bartal
ABSTRACT
We prove that an ultrametric on n points can be embedded in ldp with distortion at most 1 + ε, and d = O(ε-2 log n). This bound matches the best known bound for the special case of an equilateral space.
- Dimension reduction for ultrametrics
Recommendations
Near Linear Lower Bound for Dimension Reduction in L1
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer ScienceGiven a set of $n$ points in $\ell_{1}$, how many dimensions are needed to represent all pair wise distances within a specific distortion? This dimension-distortion tradeoff question is well understood for the $\ell_{2}$ norm, where $O((\log n)/\epsilon^...
A Nonlinear Approach to Dimension Reduction
The $$\ell _2$$ℓ2 flattening lemma of Johnson and Lindenstrauss (in: Proceedings of the conference in modern analysis and probability, 1984) is a powerful tool for dimension reduction. It has been conjectured that the target dimension bounds can be ...
On the impossibility of dimension reduction in l1
The Johnson--Lindenstrauss lemma shows that any n points in Euclidean space (i.e., ℝn with distances measured under the ℓ2 norm) may be mapped down to O((log n)/ϵ2) dimensions such that no pairwise distance is distorted by more than a (1 + ϵ) factor. ...
Comments