Fast Dimensionality Reduction From (\ell_2) To (\ell_p) | Awesome Similarity Search Papers

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

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 dimension is small. Additionally, we show that for any norm (|\cdot|) in the target space, any embedding of ((\mathbb{R}^d, |\cdot|_2)) into ((\mathbb{R}^k, |\cdot|)) with distortion (\epsilon) generally requires (k = Ω\big(\epsilon^{-2} log(\epsilon^2 n)/log(1/\epsilon)\big)), matching the optimal bound for the (ℓ₂) case up to a logarithmic factor.

Explore more on:
Uncategorized
Similar Work
Loading…