Average-Case Dimensionality Reduction in $\ell_1$: Tree Ising Models

Given an arbitrary set of high dimensional points in $\ell_1$, there are known negative results that preclude the possibility of mapping them to a low dimensional $\ell_1$ space while preserving distances with small multiplicative distortion. This is in stark contrast with dimension reduction in Euclidean space ($\ell_2$) where such mappings are always possible. While the first non-trivial lower bounds for $\ell_1$ dimension reduction were established almost 20 years ago, there has been minimal progress in understanding what sets of points in $\ell_1$ are conducive to a low-dimensional mapping. In this work, we shift the focus from the worst-case setting and initiate the study of a characterization of $\ell_1$ metrics that are conducive to dimension reduction in $\ell_1$. Our characterization focuses on metrics that are defined by the disagreement of binary variables over a probability distribution -- any $\ell_1$ metric can be represented in this form. We show that, for configurations of $n$ points in $\ell_1$ obtained from tree Ising models, we can reduce dimension to $\mathrm{polylog}(n)$ with constant distortion. In doing so, we develop technical tools for embedding capped metrics (also known as truncated metrics) which have been studied because of their applications in computer vision, and are objects of independent interest in metric geometry.