Fast Approximate ${\ell }_p$ Chamfer Distance via Lopsided Embeddings and Structured JL

For two $d$-dimensional point sets $A,B$ of size $n$, the Chamfer distance from $A$ to $B$ is defined as $\text{CH}(A,B)={\sum }_{a\in A}{\min }_{b\in B}\mathsf{dist}(a,b)$, where $\mathsf{dist}$ is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the ${\ell }_p$ norm for $1<p\le 2$. For the general case $1<p<2$, we utilize lopsided ${\ell }_p$ to ${\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 $\mathcal{O}(nd\cdot \mathrm{poly}(\log \log n,\log (1/\epsilon ))/{\epsilon }^2)$ total time. For the specific Euclidean case ($p=2$), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous ${\ell }_1$-specific Chamfer algorithm in ${\ell }_2$. These achieve a runtime matching the recent state-of-the-art ${\ell }_1$ result of $\mathcal{O}(nd(\log \log n+\log (1/\epsilon ))/{\epsilon }^2)$, improving upon the previous $\mathcal{O}(nd\log n/{\epsilon }^2)$ bound for ${\ell }_2$. We also give additional results for the angular distance and upper and lower bounds in the streaming setting.