{"ID":2848606,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.25541","arxiv_id":"2510.25541","title":"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 $\\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 = Ω\\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.","short_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 Eucli...","url_abs":"https://arxiv.org/abs/2510.25541","url_pdf":"https://arxiv.org/pdf/2510.25541v1","authors":"[\"Rafael Chiclana\",\"Mark Iwen\"]","published":"2025-10-29T14:04:31Z","proceeding":"math.PR","tasks":"[\"math.PR\",\"cs.DS\"]","methods":"[]","has_code":false}