<p>Are there any dimensionality reduction techniques known for the general <span class="math-container">$\ell_{p}$</span>-normed spaces for <span class="math-container">$p \geq 1$</span>?</p>
<p>In the Euclidean space, there is a classical result: <a href="https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma" rel="nofollow noreferrer">Johnson-Lindenstrass lemma</a> that can map any <span class="math-container">$n$</span> points to <span class="math-container">$O(\log n)$</span> dimensional space while preserving the pairwise distances up to a factor of  <span class="math-container">$(1+\epsilon)$</span> factor. From the lower bound perspective, the <span class="math-container">$\log n$</span> bound on the dimension is also tight (see <a href="https://arxiv.org/pdf/1609.02094.pdf" rel="nofollow noreferrer">this</a>).</p>
<p>Are there similar upper or lower bound results known for the general <span class="math-container">$\ell_{p}$</span>-normed spaces? Thanks.</p>

CC BY-SA 4.0
2021-09-26T23:32:58.597Z
You can look at the paper for some discussion on this topic. https://drops.dagstuhl.de/opus/volltexte/2016/5908/pdf/LIPIcs-SoCG-2016-16.pdf
Chandra Chekuri
CC BY-SA 4.0
2021-01-25T20:07:11.720Z
Essentially no dimensionality reduction is possible in $\ell_1$: https://ieeexplore.ieee.org/document/6108191
Aryeh
<high-dimensional-geometry><metric-spaces>
Dimentionality Reduction for Lp-Normed Spaces
Inuyasha Yagami
# Dimentionality Reduction for Lp-Normed Spaces

(Asked by: username_0 on 2021-01-25)

Are there any dimensionality reduction techniques known for the general $\ell\_{p}$-normed spaces for $p \geq 1$?

In the Euclidean space, there is a classical result: [Johnson-Lindenstrass lemma](https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma) that can map any $n$ points to $O(\log n)$ dimensional space while preserving the pairwise distances up to a factor of $(1+\epsilon)$ factor. From the lower bound perspective, the $\log n$ bound on the dimension is also tight (see [this](https://arxiv.org/pdf/1609.02094.pdf)).

Are there similar upper or lower bound results known for the general $\ell\_{p}$-normed spaces? Thanks.

**Tags:** high-dimensional-geometry, metric-spaces

> **Comments:**
> **username_2**: Essentially no dimensionality reduction is possible in $\ell_1$: https://ieeexplore.ieee.org/document/6108191  
> **username_1**: You can look at the paper for some discussion on this topic. https://drops.dagstuhl.de/opus/volltexte/2016/5908/pdf/LIPIcs-SoCG-2016-16.pdf  

---

## 0 answers

