Return to Question

Edit (April 1, 2020):###

• I formalized the original question (from the reference below) wrong. Please see @AndreasBlass correction.
• Also, all the suggestions proposed so far doesn't seems to be related to 2 hints that I found online (but didn't understand how to use), and I'm curious if anyone could explain more about them:

Hint 1:

For every angle, construct a equilateral triangle that its edges are being preserved by the projection (add the vertices of those triangles [conceptually] to the point set being embedded). Argue, that this implies that the angle is being preserved.

Hint 2:

If two triangles lie in the same plane (a 2-dimensional affine space) in $\mathbb R^n$, then under a linear mapping their areas have the same multiplicative error. For every triangle, add an extra point to form a right-angled isosceles triangle in the same plane.

###My original post:### As described in https://sarielhp.org/teach/08/a/lec/22_jl.pdf, Exercise 22.6.5 ("Johnson–Lindenstrauss lemma works for angles").

Let $x,y,z\in \mathbb R^n$. Let $0<\epsilon<1$. Denote $\theta\mathrel{:=}\angle xyz$. Let $k=\Theta(\frac{\log⁡ n}{\epsilon^2})$. I'm struggling to show that $\exists$ linear map $f:\mathbb R^n\to\mathbb R^k$ s.t. with high probability $(1-\epsilon)\theta\le\theta'\le(1+\epsilon)\theta$, where $\theta'=\angle x' y' z'$ (and $x'\mathrel{:=}f(x)$,$y'\mathrel{:=}f(y)$,$z'\mathrel{:=}f(z)$).

Would appreciate your help.

PS: I tried to express $\theta$ using the law of cosine, but got stuck:

Denote $a\mathrel{:=}\|x-y\|$, $b\mathrel{:=}\|x-z\|$, $c\mathrel{:=}\|y-z\|$, and $a'\mathrel{:=}\|x'-y' \|$, $b'\mathrel{:=}\|x'-z'\|$, $c'\mathrel{:=}\|y'-z'\|$. By the law of cosines, $\theta=\arccos⁡(\frac{a^2+b^2-c^2}{2ab})$ and $\theta'=\arccos⁡(\frac{a^2+b'^2-c'^2}{2a'b'})$.

Edit (April 1, 2020):

• I formalized the original question (from the reference below) wrong. Please see @AndreasBlass correction.
• Also, all the suggestions proposed so far doesn't seems to be related to 2 hints that I found online (but didn't understand how to use), and I'm curious if anyone could explain more about them:

Hint 1:

For every angle, construct a equilateral triangle that its edges are being preserved by the projection (add the vertices of those triangles [conceptually] to the point set being embedded). Argue, that this implies that the angle is being preserved.

Hint 2:

If two triangles lie in the same plane (a 2-dimensional affine space) in $\mathbb R^n$, then under a linear mapping their areas have the same multiplicative error. For every triangle, add an extra point to form a right-angled isosceles triangle in the same plane.

My original post:

As described in https://sarielhp.org/teach/08/a/lec/22_jl.pdf, Exercise 22.6.5 ("Johnson–Lindenstrauss lemma works for angles").

Let $x,y,z\in \mathbb R^n$. Let $0<\epsilon<1$. Denote $\theta\mathrel{:=}\angle xyz$. Let $k=\Theta(\frac{\log⁡ n}{\epsilon^2})$. I'm struggling to show that $\exists$ linear map $f:\mathbb R^n\to\mathbb R^k$ s.t. with high probability $(1-\epsilon)\theta\le\theta'\le(1+\epsilon)\theta$, where $\theta'=\angle x' y' z'$ (and $x'\mathrel{:=}f(x)$,$y'\mathrel{:=}f(y)$,$z'\mathrel{:=}f(z)$).

Would appreciate your help.

PS: I tried to express $\theta$ using the law of cosine, but got stuck:

Denote $a\mathrel{:=}\|x-y\|$, $b\mathrel{:=}\|x-z\|$, $c\mathrel{:=}\|y-z\|$, and $a'\mathrel{:=}\|x'-y' \|$, $b'\mathrel{:=}\|x'-z'\|$, $c'\mathrel{:=}\|y'-z'\|$. By the law of cosines, $\theta=\arccos⁡(\frac{a^2+b^2-c^2}{2ab})$ and $\theta'=\arccos⁡(\frac{a^2+b'^2-c'^2}{2a'b'})$.

Edit (April 1, 2020):###

I formalized the original question (from the reference below) wrong. Please see @AndreasBlass correction.

###My original post:### As described in https://sarielhp.org/teach/08/a/lec/22_jl.pdf, Exercise 22.6.5 ("Johnson–Lindenstrauss lemma works for angles").

Let $x,y,z\in \mathbb R^n$. Let $0<\epsilon<1$. Denote $\theta\mathrel{:=}\angle xyz$. Let $k=\Theta(\frac{\log⁡ n}{\epsilon^2})$. I'm struggling to show that $\exists$ linear map $f:\mathbb R^n\to\mathbb R^k$ s.t. with high probability $(1-\epsilon)\theta\le\theta'\le(1+\epsilon)\theta$, where $\theta'=\angle x' y' z'$ (and $x'\mathrel{:=}f(x)$,$y'\mathrel{:=}f(y)$,$z'\mathrel{:=}f(z)$).

Would appreciate your help.

PS: I tried to express $\theta$ using the law of cosine, but got stuck:

Denote $a\mathrel{:=}\|x-y\|$, $b\mathrel{:=}\|x-z\|$, $c\mathrel{:=}\|y-z\|$, and $a'\mathrel{:=}\|x'-y' \|$, $b'\mathrel{:=}\|x'-z'\|$, $c'\mathrel{:=}\|y'-z'\|$. By the law of cosines, $\theta=\arccos⁡(\frac{a^2+b^2-c^2}{2ab})$ and $\theta'=\arccos⁡(\frac{a^2+b'^2-c'^2}{2a'b'})$.

Edit (April 1, 2020):###

• I formalized the original question (from the reference below) wrong. Please see @AndreasBlass correction.
• Also, all the suggestions proposed so far doesn't seems to be related to 2 hints that I found online (but didn't understand how to use), and I'm curious if anyone could explain more about them:

Hint 1:

For every angle, construct a equilateral triangle that its edges are being preserved by the projection (add the vertices of those triangles [conceptually] to the point set being embedded). Argue, that this implies that the angle is being preserved.

Hint 2:

If two triangles lie in the same plane (a 2-dimensional affine space) in $\mathbb R^n$, then under a linear mapping their areas have the same multiplicative error. For every triangle, add an extra point to form a right-angled isosceles triangle in the same plane.

###My original post:### As described in https://sarielhp.org/teach/08/a/lec/22_jl.pdf, Exercise 22.6.5 ("Johnson–Lindenstrauss lemma works for angles").

Let $x,y,z\in \mathbb R^n$. Let $0<\epsilon<1$. Denote $\theta\mathrel{:=}\angle xyz$. Let $k=\Theta(\frac{\log⁡ n}{\epsilon^2})$. I'm struggling to show that $\exists$ linear map $f:\mathbb R^n\to\mathbb R^k$ s.t. with high probability $(1-\epsilon)\theta\le\theta'\le(1+\epsilon)\theta$, where $\theta'=\angle x' y' z'$ (and $x'\mathrel{:=}f(x)$,$y'\mathrel{:=}f(y)$,$z'\mathrel{:=}f(z)$).

Would appreciate your help.

PS: I tried to express $\theta$ using the law of cosine, but got stuck:

Denote $a\mathrel{:=}\|x-y\|$, $b\mathrel{:=}\|x-z\|$, $c\mathrel{:=}\|y-z\|$, and $a'\mathrel{:=}\|x'-y' \|$, $b'\mathrel{:=}\|x'-z'\|$, $c'\mathrel{:=}\|y'-z'\|$. By the law of cosines, $\theta=\arccos⁡(\frac{a^2+b^2-c^2}{2ab})$ and $\theta'=\arccos⁡(\frac{a^2+b'^2-c'^2}{2a'b'})$.

As described in https://sarielhp.org/teach/08/a/lec/22_jl.pdf, Exercise 22.6.5 ("Johnson–Lindenstrauss lemma works for angles").

Let $x,y,z\in \mathbb R^n$. Let $0<\epsilon<1$. Denote $\theta\mathrel{:=}\angle xyz$. Let $k=\Theta(\frac{\log⁡ n}{\epsilon^2})$. I'm struggling to show that $\exists$ linear map $f:\mathbb R^n\to\mathbb R^k$ s.t. with high probability $(1-\epsilon)\theta\le\theta'\le(1+\epsilon)\theta$, where $\theta'=\angle x' y' z'$ (and $x'\mathrel{:=}f(x)$,$y'\mathrel{:=}f(y)$,$z'\mathrel{:=}f(z)$).

Would appreciate your help.

PS: I tried to express $\theta$ using the law of cosine, but got stuck:

Denote $a\mathrel{:=}\|x-y\|$, $b\mathrel{:=}\|x-z\|$, $c\mathrel{:=}\|y-z\|$, and $a'\mathrel{:=}\|x'-y' \|$, $b'\mathrel{:=}\|x'-z'\|$, $c'\mathrel{:=}\|y'-z'\|$. By the law of cosines, $\theta=\arccos⁡(\frac{a^2+b^2-c^2}{2ab})$ and $\theta'=\arccos⁡(\frac{a^2+b'^2-c'^2}{2a'b'})$.

Edit (April 1, 2020):###

I formalized the original question (from the reference below) wrong. Please see @AndreasBlass correction.

###My original post:### As described in https://sarielhp.org/teach/08/a/lec/22_jl.pdf, Exercise 22.6.5 ("Johnson–Lindenstrauss lemma works for angles").

Let $x,y,z\in \mathbb R^n$. Let $0<\epsilon<1$. Denote $\theta\mathrel{:=}\angle xyz$. Let $k=\Theta(\frac{\log⁡ n}{\epsilon^2})$. I'm struggling to show that $\exists$ linear map $f:\mathbb R^n\to\mathbb R^k$ s.t. with high probability $(1-\epsilon)\theta\le\theta'\le(1+\epsilon)\theta$, where $\theta'=\angle x' y' z'$ (and $x'\mathrel{:=}f(x)$,$y'\mathrel{:=}f(y)$,$z'\mathrel{:=}f(z)$).

Would appreciate your help.

PS: I tried to express $\theta$ using the law of cosine, but got stuck:

Denote $a\mathrel{:=}\|x-y\|$, $b\mathrel{:=}\|x-z\|$, $c\mathrel{:=}\|y-z\|$, and $a'\mathrel{:=}\|x'-y' \|$, $b'\mathrel{:=}\|x'-z'\|$, $c'\mathrel{:=}\|y'-z'\|$. By the law of cosines, $\theta=\arccos⁡(\frac{a^2+b^2-c^2}{2ab})$ and $\theta'=\arccos⁡(\frac{a^2+b'^2-c'^2}{2a'b'})$.