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

CardsList
  1. Linearized Wasserstein dimensionality reduction with approximation guarantees

    Feb 14, 2023Alexander Cloninger, Keaton Hamm, Varun Khurana +1Dimensionality ReductionManifold Learning

  2. Dimension Reduction for Curves: Simplified and Generalized

    Jul 3, 2026Matthijs Ebbens, Jie Lu, Alexander MunteanuDimensionality Reduction

  3. Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

    May 19, 2026Peter Matthew Jacobs, Jeff M. PhillipsRandomized SketchingApproximation Algorithms