The Power of Recursive Embeddings for ℓ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 $\ell_{p}$ spaces, $p \lt 2$, yielding state-of-theart results for Lipschitz decomposition, for Nearest Neighbor Search, and for embedding into $\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. Index Terms-Metric Embedding, Lipschitz Decomposition, Nearest Neighbor Search, $\ell_{p}$ norm