2
$\begingroup$

Consider the Johnson-Lindenstrauss lemma in the case where we can assume the $n$ input points $x_i$ in $\mathbb{R}^d$ are actually located on the sphere $$S^{d-1}(r):=\{u=(u_1,\ldots,u_{d}): u_1^2+\cdots+u_d^2=r\},$$ for some $r>0.$

How does this impact the conclusion of the theorem? In particular, can the upper and lower bounds $$ (1-\varepsilon)\sqrt{k/d}~\left| x_i-x_j\right|^2\leq \left| f(x_i)-f(x_j)\right|^2 \leq (1+\varepsilon)\sqrt{k/d}~\left| x_i-x_j\right|^2, $$ which hold with probability at least $1-\frac{1}{n^{c-2}},$ with $f$ an orthogonal projection on a random $k-$dimensional subspace, where $k=c \log n/\varepsilon^2,$ possibly be strengthened in this case?

$\endgroup$
1
1
$\begingroup$

Given that the worst-case configurations require dimension projection proportional to the one obtained by linear embeddings

http://people.seas.harvard.edu/~minilek/publications/papers/jl_tight.pdf

it's not possible to gain by restricting the points to the sphere. Furthermore, I believe in the proof of this paper the input points (except for the origin) are all unit vectors.

$\endgroup$
1
$\begingroup$

By the (supposedly unpublished) result of Noga Alon cited in the paper of Dasgupta and Gupta, the answer is NO:

Dasgupta, Sanjoy; Gupta, Anupam, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Struct. Algorithms 22, No.1, 60-65 (2003). ZBL1018.51010.

$\endgroup$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.