The Power of Recursive Embeddings for ${\mathrm{\ell }}_p$ Metrics

Metric embedding is a powerful tool used extensively in mathematics and computer science. We devise a new method of using metric embeddings recursively, which turns out to be particularly effective in ${\mathrm{\ell }}_p$ spaces, $p>2$, yielding state-of-the-art results for Lipschitz decomposition, for Nearest Neighbor Search, and for embedding into ${\mathrm{\ell }}_2$. In a nutshell, our method composes metric embeddings by viewing them as reductions between problems, and thereby obtains a new reduction that is substantially more effective than the known reduction that employs a single embedding. We in fact apply this method recursively, oftentimes using double recursion, which further amplifies the gap from a single embedding.