<p>Does the Johnson-Lindenstrauss Lemma apply to any finite-dimensional Hilbert Space? In particular, I am interested in the space of random variables $X = (X_1,...,X_N)$ over $N$ uncertain states. If $\pi_i$ is the probability of state $i$, then this space has an inner product $\langle X, Y \rangle = E(XY) = \sum_{i=1}^n \pi_i X_i Y_i$ and a norm $\|X\|^2_{\pi} = \langle X, X \rangle = \sum_{i=1}^N \pi_i X_i^2$.  </p>

<p>The standard JL lemma says that, if $S$ is a set of $m$ points in $\mathbb{R}^n$ and $n &gt; C \frac{ln(m)}{\varepsilon^2}$ then there a (suitably scaled) random orthogonal projection $f:\mathbb{R}^N \to \mathbb{R}^n$ 
will satisfy</p>

<p>$$(1-\varepsilon)\|u-v\|^2_{N} \leq \|f(u) - f(v)\|_{n}^2 \leq (1+\varepsilon)\|u-v\|_{N}^2$$
where I have used $\|\cdot\|_{n},\|\cdot\|_{N}$ to denote the standard euclidean norms in $\mathbb{R}^n$ and $\mathbb{R}^N.$</p>

<p>Does there exist a version of the lemma with the weighted norm  $\|X\|^2_{\pi}$? What would the corresponding norm in the lower $n$-dimensional space look like?</p>

CC BY-SA 3.0
2015-04-11T22:49:42.150Z
It is not clear from your question if $\pi$ is fixed or not. If it is not fixed, then this is impossible, as your can expose every coordinate in the original input. If $\pi$ is fixed, then it can be interepeted as a linear scaling of space ($\sqrt(\pi_i)$ in each coordinate, naturally. Of course, you need that JL works for dot products, but that is well known.
Sariel Har-Peled
CC BY-SA 3.0
2015-04-12T01:24:29.597Z
Yes, JL does work with any dot product you define, because all Hilbert spaces of the same dimension are linearly isometric.
Sasho Nikolov
<machine-learning><high-dimensional-geometry>
Johnson Lindenstrauss for Random variables?
Asterix
# Johnson Lindenstrauss for Random variables?

(Asked by: username_0 on 2015-04-11)

Does the Johnson-Lindenstrauss Lemma apply to any finite-dimensional Hilbert Space? In particular, I am interested in the space of random variables $X = (X\_1,...,X\_N)$ over $N$ uncertain states. If $\pi\_i$ is the probability of state $i$, then this space has an inner product $\langle X, Y \rangle = E(XY) = \sum\_{i=1}^n \pi\_i X\_i Y\_i$ and a norm $\|X\|^2\_{\pi} = \langle X, X \rangle = \sum\_{i=1}^N \pi\_i X\_i^2$.

The standard JL lemma says that, if $S$ is a set of $m$ points in $\mathbb{R}^n$ and $n > C \frac{ln(m)}{\varepsilon^2}$ then there a (suitably scaled) random orthogonal projection $f:\mathbb{R}^N \to \mathbb{R}^n$
will satisfy

$$(1-\varepsilon)\|u-v\|^2\_{N} \leq \|f(u) - f(v)\|\_{n}^2 \leq (1+\varepsilon)\|u-v\|\_{N}^2$$
where I have used $\|\cdot\|\_{n},\|\cdot\|\_{N}$ to denote the standard euclidean norms in $\mathbb{R}^n$ and $\mathbb{R}^N.$

Does there exist a version of the lemma with the weighted norm $\|X\|^2\_{\pi}$? What would the corresponding norm in the lower $n$-dimensional space look like?

**Tags:** machine-learning, high-dimensional-geometry

> **Comments:**
> **username_1**: It is not clear from your question if $\pi$ is fixed or not. If it is not fixed, then this is impossible, as your can expose every coordinate in the original input. If $\pi$ is fixed, then it can be interepeted as a linear scaling of space ($\sqrt(\pi_i)$ in each coordinate, naturally. Of course, you need that JL works for dot products, but that is well known.  
> **username_2**: Yes, JL does work with any dot product you define, because all Hilbert spaces of the same dimension are linearly isometric.  

---

## 0 answers

