Fast Dimensionality Reduction From \(\ell_2\) To \(\ell_p\)

Abstract

The Johnson-Lindenstrauss (JL) lemma is a fundamental result in dimensionality reduction, ensuring that any finite set \(X \subseteq \mathbb\{R\}^d\) can be embedded into a lower-dimensional space \(\mathbb\{R\}^k\) while approximately preserving all pairwise Euclidean distances. In recent years, embeddings that preserve Euclidean distances when measured via the \(\ell_1\) norm in the target space have received increasing attention due to their relevance in applications such as nearest neighbor search in high dimensions. A recent breakthrough by Dirksen, Mendelson, and Stollenwerk established an optimal \(ℓ₂ \to \ell_1\) embedding with computational complexity \(O(d log d)\). In this work, we generalize this direction and propose a simple linear embedding from \(ℓ₂\) to \(\ell_p\) for any \(p \in [1,2]\) based on a construction of Ailon and Liberty. Our method achieves a reduced runtime of \(O(d log k)\) when \(k \leq d^\{1/4\}\), improving upon prior runtime results when the target di