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 $\ell_2 \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 $\ell_2$ 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 \emph{any norm} $\|\cdot\|$ in the target space, any embedding of $(\mathbb{R}^d, \|\cdot\|_2)$ into $(\mathbb{R}^k, \|\cdot\|)$ with distortion $\varepsilon$ generally requires $k = \Omega\big(\varepsilon^{-2} \log(\varepsilon^2 n)/\log(1/\varepsilon)\big)$, matching the optimal bound for the $\ell_2$ case up to a logarithmic factor.

翻译：Johnson-Lindenstrauss (JL) 引理是降维领域的一项基本结果，它确保任何有限集合 $X \subseteq \mathbb{R}^d$ 均可嵌入到低维空间 $\mathbb{R}^k$ 中，同时近似保持所有成对欧氏距离。近年来，通过在目标空间中使用 $\ell_1$ 范数度量欧氏距离的嵌入方法，因其在高维最近邻搜索等应用中的相关性而受到越来越多的关注。Dirksen、Mendelson 和 Stollenwerk 最近的一项突破性工作建立了计算复杂度为 $O(d \log d)$ 的最优 $\ell_2 \to \ell_1$ 嵌入。在本研究中，我们推广了这一方向，基于 Ailon 和 Liberty 的构造，提出了一种从 $\ell_2$ 到任意 $p \in [1,2]$ 的 $\ell_p$ 的简单线性嵌入方法。当 $k \leq d^{1/4}$ 时，我们的方法实现了 $O(d \log k)$ 的运行时间，在目标维度较小时改进了先前的运行时间结果。此外，我们证明对于目标空间中的任意范数 $\|\cdot\|$，将 $(\mathbb{R}^d, \|\cdot\|_2)$ 嵌入到 $(\mathbb{R}^k, \|\cdot\|)$ 且失真度为 $\varepsilon$ 的嵌入通常需要 $k = \Omega\big(\varepsilon^{-2} \log(\varepsilon^2 n)/\log(1/\varepsilon)\big)$，该结果在对数因子范围内与 $\ell_2$ 情形的最优界相匹配。