Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918177840037888 |
|---|---|
| author | Chiclana, Rafael Iwen, Mark |
| author_facet | Chiclana, Rafael Iwen, Mark |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25541 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$ Chiclana, Rafael Iwen, Mark Probability Data Structures and Algorithms 68W20 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. |
| title | Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$ |
| topic | Probability Data Structures and Algorithms 68W20 |
| url | https://arxiv.org/abs/2510.25541 |