Fast Approximate Chamfer Distance via Lopsided Embeddings and Structured JL
Organizations: MIT · Carnegie Mellon University and Google Research
Abstract
For two -dimensional point sets of size , the Chamfer distance from to is defined as , where is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the norm for . For the general case , we utilize lopsided to 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 total time. For the specific Euclidean case (), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous -specific Chamfer algorithm in . These achieve a runtime matching the recent state-of-the-art result of , improving upon the previous bound for . We also give additional results for the angular distance and upper and lower bounds in the streaming setting.
Figures & tables
| Seed | Average Spearman ( ) | Average Spearman ( ) | Average Spearman ( ) |
|---|---|---|---|
| 0 | 0.8783 | 0.8817 | 0.8802 |
| 1 | 0.8895 | 0.8916 | 0.8870 |
| 2 | 0.8898 | 0.8917 | 0.8889 |
| 3 | 0.8894 | 0.8903 | 0.8896 |
| 4 | 0.8761 | 0.8786 | 0.8749 |
| Algorithm / Reference | Supported Metric | Time Complexity | Space Complexity | Dynamic Streaming |
| Naive Exact | Any ( ) | |||
| BIJ+ (23) | ||||
| FI (25) | ||||
| Ours (Theorem 3.4) | General ( ) | ✓ | ||
| Ours (Theorems 4.5 & 5.2) | and MaxSim | ✓ | ||
| Our Lower Bound (Theorem 5.3) | Any ( ) | — | bits | — |
| BIJ+ (23) Mean Relative Error (%) | Ours Mean Relative Error (%) | |
|---|---|---|
| 1000 | 0.055 0.023 | 0.614 0.412 |
| 2000 | 0.066 0.062 | 0.559 0.058 |
| 5000 | 0.067 0.040 | 0.622 0.249 |
| 10000 | 0.027 0.025 | 0.397 0.264 |
Approximation Algorithms
Approximation algorithms find provably near-optimal solutions to computationally hard optimization problems when exact solutions are impractical.
See all 102 papers