标题： 从$\ell_2$到$\ell_p$的快速降维 显示英文标题

标题： Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$

摘要： 约翰逊-林德勒斯特拉姆（JL）引理是降维中的一个基本结果，确保任何有限集合$X \subseteq \mathbb{R}^d$可以嵌入到一个较低维度的空间$\mathbb{R}^k$中，同时近似保留所有成对的欧几里得距离。 近年来，当在目标空间中通过$\ell_1$范数测量时，能够保持欧几里得距离的嵌入方法由于其在高维最近邻搜索等应用中的相关性而受到越来越多的关注。 迪尔克森、门德尔斯和斯托伦韦克最近的突破性工作建立了具有计算复杂度$O(d \log d)$的最优$\ell_2 \to \ell_1$嵌入。 在本工作中，我们推广了这一方向，并基于Ailon和Liberty的构造，提出了一种从$\ell_2$到$\ell_p$的简单线性嵌入，适用于任何$p \in [1,2]$。我们的方法在$k \leq d^{1/4}$时实现了减少的运行时间$O(d \log k)$，在目标维度较小时优于之前的运行时间结果。 此外，我们证明对于目标空间中的\emph{任何范数} $\|\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$情况下的最优界在对数因子范围内一致。 显示英文摘要

摘要： 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.