Chamfer distance breaks out of Euclidean: lopsided embeddings bring any ℓp approximation to near-linear time
Synopsis
Chamfer distance measures dissimilarity between two point sets, and efficient approximation had largely been limited to the Euclidean norm, leaving general ℓp norms open. This work reduces ℓp Chamfer distance to a low-dimensional ℓp instance using lopsided embeddings with weak guarantees, applies fast matrix multiplication to speed up the embedding in high dimensions, and obtains a near-linear-time approximation; for the Euclidean case it uses a Toeplitz-based fast Johnson-Lindenstrauss transform and matches the best known runtime.
Interpretation
Chamfer distance under general ℓp norms now has a near-linear-time approximation algorithm, no longer confined to the Euclidean case. Earlier efficient approximations for Chamfer distance were built mainly on the Euclidean norm, and extending the same efficiency to general ℓp norms remained an open problem. The algorithm reduces an ℓp instance to a low-dimensional ℓp instance, with total runtime growing near-linearly in input size and an approximation-ratio guarantee.
The method first compresses the point sets into low dimension with a random projection carrying weak guarantees, then runs an existing Chamfer solver in that low-dimensional space. The lopsided embedding used guarantees only non-contraction and bounded expected error, unlike a standard Johnson-Lindenstrauss transform that concentrates in both directions. Chamfer distance is a sum of nearest-neighbor distances, so non-contraction of pairwise distances suffices to preserve the original distance after embedding, and in high dimensions the embedding matrix is applied with fast matrix multiplication.
The Euclidean case instead uses a fast Johnson-Lindenstrauss transform built from Toeplitz matrices to reduce dimension, then re-analyzes the existing quadtree estimation framework in the reduced space. The earlier Euclidean Chamfer algorithm ran in the original dimension, and the quadtree estimator's approximation factor after dimension reduction needed a fresh argument. Only constant distortion is needed because the transform is used solely in the quadtree stage, where constant distortion is absorbed by the already-crude approximation factor, and the final runtime matches the best known result.
Perspective
The results concern directed Chamfer distance under the ℓp norm for point sets of size n, with theoretical guarantees on approximation ratio and total runtime; experiments use synthetic high-dimensional point sets and 300-dimensional GloVe word embeddings on a single NVIDIA T4 GPU.
For general ℓp, a factor gap remains between the upper bound and the naive lower bound, which the authors list as an open problem; the empirical evaluation is limited to synthetic data plus GloVe and a single-GPU setup, and the authors propose evaluating on a broader range of point-cloud and retrieval datasets.
