Embedding Probability Distributions into Low Dimensional ℓ 1 : Tree Ising Models via Truncated Metrics
Moses Charikar, Spencer Compton, Chirag Pabbaraju · Society for Industrial and Applied Mathematics eBooks · 2025
Given an arbitrary set of high dimensional points in ℓ1, there are known negative results that preclude the possibility of always mapping them to a low dimensional ℓ1 space while preserving distances with small multiplicative distortion. This is in stark contrast with dimension reduction in Euclidean space (ℓ2) where such mappings are always possible. While the first non-trivial lower bounds for ℓ1 dimension reduction were established almost 20 years ago, there has been limited progress in understanding what sets of points in ℓ1 are conducive to a low-dimensional mapping.