TY - GEN

T1 - Hölder homeomorphisms and approximate nearest neighbors

AU - Andoni, Alexandr

AU - Naor, Assaf

AU - Nikolov, Aleksandar

AU - Razenshteyn, Ilya

AU - Waingarten, Erik

N1 - Funding Information:
We thank Sébastien Bubeck, Yin Tat Lee and Yuval Peres for useful discussions. The first-named author was supported in part by the Simons Foundation (#491119), NSF grants CCF-1617955, CCF-1740833, and Google Research Award. The second-named author was supported in part by the NSF grant CCF-1412958, the Packard Foundation and the Simons Foundation. The third author was supported by an NSERC Discovery grant (application number RGPIN-2016-06333),
Funding Information:
and part of this work was done while he was visiting the Simons Institute for the Theory of Computing semester on Bridging Continuous and Discrete Optimization, partially supported through NSF grant #CCF-1740425. The fifth-named author was supported in part by the NSF grants CCF-1563155, CCF-1420349, CCF-1149257, CCF-1423100), and the NSF Graduate Research Fellowship (DGE-16-44869).

PY - 2018/11/30

Y1 - 2018/11/30

N2 - We study bi-Hölder homeomorphisms between the unit spheres of finite-dimensional normed spaces and use them to obtain better data structures for high-dimensional Approximate Near Neighbor search (ANN) in general normed spaces. Our main structural result is a finite-dimensional quantitative version of the following theorem of Daher (1993) and Kalton (unpublished). Every d-dimensional normed space X admits a small perturbation Y such that there is a bi-Hölder homeomorphism with good parameters between the unit spheres of Y and Z, where Z is a space that is close to ℓ d 2 . Furthermore, the bulk of this article is devoted to obtaining an algorithm to compute the above homeomorphism in time polynomial in d. Along the way, we show how to compute efficiently the norm of a given vector in a space obtained by the complex interpolation between two normed spaces. We demonstrate that, despite being much weaker than bi-Lipschitz embeddings, such homeomorphisms can be efficiently utilized for the ANN problem. Specifically, we give two new data structures for ANN over a general d-dimensional normed space, which for the first time achieve approximation d o(1) , thus improving upon the previous general bound O(√d) that is directly implied by John's theorem.

AB - We study bi-Hölder homeomorphisms between the unit spheres of finite-dimensional normed spaces and use them to obtain better data structures for high-dimensional Approximate Near Neighbor search (ANN) in general normed spaces. Our main structural result is a finite-dimensional quantitative version of the following theorem of Daher (1993) and Kalton (unpublished). Every d-dimensional normed space X admits a small perturbation Y such that there is a bi-Hölder homeomorphism with good parameters between the unit spheres of Y and Z, where Z is a space that is close to ℓ d 2 . Furthermore, the bulk of this article is devoted to obtaining an algorithm to compute the above homeomorphism in time polynomial in d. Along the way, we show how to compute efficiently the norm of a given vector in a space obtained by the complex interpolation between two normed spaces. We demonstrate that, despite being much weaker than bi-Lipschitz embeddings, such homeomorphisms can be efficiently utilized for the ANN problem. Specifically, we give two new data structures for ANN over a general d-dimensional normed space, which for the first time achieve approximation d o(1) , thus improving upon the previous general bound O(√d) that is directly implied by John's theorem.

KW - Complex interpolation

KW - John's theorem

KW - Near neighbor search

UR - http://www.scopus.com/inward/record.url?scp=85058223632&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85058223632&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2018.00024

DO - 10.1109/FOCS.2018.00024

M3 - Conference contribution

AN - SCOPUS:85058223632

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 159

EP - 169

BT - Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018

A2 - Thorup, Mikkel

PB - IEEE Computer Society

T2 - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018

Y2 - 7 October 2018 through 9 October 2018

ER -