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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Apr 11 '15 at 22:49
  • 2
    $\begingroup$ Yes, JL does work with any dot product you define, because all Hilbert spaces of the same dimension are linearly isometric. $\endgroup$ – Sasho Nikolov Apr 12 '15 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.