2023/12/05 by Moses Charikar, Charikar, Moses, Spencer Compton +3
Computer Science · Mathematics · #Algorithms and Data Compression #Characterization (materials science) #Combinatorics #Computer science #Data Structures and Algorithms (cs.DS) #Dimension (graph theory) #Dimensionality reduction #Discrete mathematics #Distortion (music) #Embedding #Euclidean geometry #Euclidean space #FOS: Computer and information sciences #Geometry #Ising model #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematics #Metric (unit) #Metric space #Multiplicative function #Physics #Reduction (mathematics) #Statistical physics #Topological and Geometric Data Analysis #Tree (set theory)
paper · pdf · doi:10.48550/arxiv.2312.02435
openalex publication_date 2023/12/05 · openalex created_date 2023/12/07 · openalex updated_date 2026/07/28
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. In this work, we study a new characterization of ℓ1 metrics that are conducive to dimension reduction in ℓ1. Our characterization focuses on metrics that are defined by the disagreement of binary variables over a probability distribution -- any ℓ1 metric can be represented in this form. We show that, for configurations of n points in ℓ1 obtained from tree Ising models, we can reduce dimension to polylog(n) with constant distortion. In doing so, we develop technical tools for embedding truncated metrics which have been studied because of their applications in computer vision, and are objects of independent interest in metric geometry. Among other tools, we show how any ℓ1 metric can be truncated with O(1) distortion and O(log(n)) blowup in dimension.