cs.DSNov 8, 2026

Fast Approximate ℓp\ell_p Chamfer Distance via Lopsided Embeddings and Structured JL

Authors: Ying Feng, David P. Woodruff

Organizations: MIT · Carnegie Mellon University and Google Research

Abstract

For two dd-dimensional point sets A,BA, B of size nn, the Chamfer distance from AA to BB is defined as CH(A,B)=∑a∈Amin⁡b∈Bdist(a,b)\text{CH}(A,B)=\sum_{a \in A} \min_{b \in B} \mathsf{dist}(a, b), where dist\mathsf{dist} is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the ℓp\ell_p norm for 1<p≤21 < p \le 2. For the general case 1<p<21 < p < 2, we utilize lopsided ℓp\ell_p to ℓ1\ell_1 embeddings with weak guarantees. We show that they are sufficient for preserving the Chamfer distance. In the high-dimensional regime, we use Fast Matrix Multiplication techniques to speed up the lopsided embeddings. These lead to O(nd⋅poly(log⁡log⁡n,log⁡(1/ε))/ε2)O(nd\cdot \mathrm{poly}(\log \log n, \log(1/\varepsilon))/\varepsilon^2) total time. For the specific Euclidean case (p=2p=2), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous ℓ1\ell_1-specific Chamfer algorithm in ℓ2\ell_2. These achieve a runtime matching the recent state-of-the-art ℓ1\ell_1 result of O(nd(log⁡log⁡n+log⁡(1/ε))/ε2)O(nd(\log \log n + \log (1/\varepsilon))/\varepsilon^2), improving upon the previous O(ndlog⁡n/ε2)O(nd \log n/\varepsilon^2) bound for ℓ2\ell_2. We also give additional results for the angular distance and upper and lower bounds in the streaming setting.

Figures & tables

Explore similar work

Feb 14, 2023

Linearized Wasserstein dimensionality reduction with approximation guarantees

We introduce LOT Wassmap, a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. The algorithm is motivated by the observation that many datasets are naturally interpreted as probability measures rather than points in Rn\mathbb{R}^n, and that finding low-dimensional descriptions of such datasets requires manifold learning algorithms in the Wasserstein space. Most available algorithms are based on computing the pairwise Wasserstein distance matrix, which can be computationally challenging for large datasets in high dimensions. Our algorithm leverages approximation schemes such as Sinkhorn distances and linearized optimal transport to speed-up computations, and in particular, avoids computing a pairwise distance matrix. We provide guarantees on the embedding quality under such approximations, including when explicit descriptions of the probability measures are not available and one must deal with finite samples instead. Experiments demonstrate that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
Jul 3, 2026

Dimension Reduction for Curves: Simplified and Generalized

We revisit random projections for reducing the dimension of high-dimensional polygonal curves. Drawing from the toolbox of randomized linear algebra, we give a considerably simplified proof of the known O(ε−2log⁡(nm))O(\varepsilon^{-2}\log(nm)) bound on the target dimension of a random projection that preserves the continuous Fréchet distance of polygonal curves up to a factor (1±ε)(1\pm\varepsilon). Our proof is based on the concept of sparse oblivious subspace embeddings. While previous techniques were limited to the case of the Fréchet distance, our techniques are fairly general and extend to all possible distance measures that involve the maximum, a sum or an integral over Euclidean distances between pairs of points on both input curves. We define a generalized dissimilarity measure for curves that includes several popular measures such as Fréchet, qq-DTW, Hausdorff, etc. as special cases and show that the same dimension reduction technique works for this generalized dissimilarity measure. Finally, we apply the same framework for dimension reduction to piecewise linear surfaces, after extending the distance measure suitably to such surfaces.
May 19, 2026

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size nn from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems (d∈{2,3})\left( d \in \{2,3\} \right), algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of nn and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to εε-additive error in expectation with respect to the sampling; we allow O(1)O(1) computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under αα-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate W22(P,Q)W_2^2(P,Q) within εε error in ε−max⁡(2,d+1+o(1)1+α)ε^{-\max(2,\frac{d+1+o(1)}{1+α})} time for 0<α<10 < α< 1 Hölder smooth distributions P,QP,Q on (0,1)d(0,1)^{d}; an optimal Θ(ε−2)Θ(ε^{-2}) for α>1/2α> 1/2 when d=2d=2 and nearly optimal as α→1α\to 1 when d=3d = 3.