Timeline for Johnson-Lindenstrauss lemma preserves angles
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 3, 2020 at 17:13 | history | edited | Andreas Blass | CC BY-SA 4.0 |
added 1765 characters in body
|
| Apr 3, 2020 at 16:46 | comment | added | Andreas Blass | @keyboardAnt No, but usul's comments suggest a rough idea, which might underlie the actual proof, and which I'll edit into my answer.. | |
| Apr 3, 2020 at 14:05 | comment | added | keyboardAnt | @AndreasBlass, have you read the paper mentioned by @ usual in his comment to my original post? "Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications" by Magen, 2002. It seems like Magen took a different approach than you described, and got to a target dimension $\Theta(\frac{logn}{\epsilon^2})$. Best regards | |
| Apr 1, 2020 at 18:42 | comment | added | Andreas Blass | @usul I agree with part (2) of your comment. I also agree that, because arccos isn't Lipschitz, you can't directly apply the distance result to get the angle result. That's why I expected (and still expect) to need a higher power of $\epsilon$ in the denominator of the target dimension. I don't see how to get by with only $\epsilon^2$ unless we know something about the points not getting too close to collinear. (Once the angles are bounded away from $0$ and $\pi$, that bound will give a Lipschitz constant for arccos, and everything should be OK.) | |
| Apr 1, 2020 at 15:24 | comment | added | usul | (1) I don't see that this proof approach will give the theorem because arccos isn't Lipschitz -- as you say, the constant would depend on how far from collinear the points are. (2) Note the projectionis linear, so if the points are collinear then so are their projections. | |
| Apr 1, 2020 at 14:23 | comment | added | keyboardAnt | Regarding yours & @PaulSiegel suggestion to use the continuity of arccos: I'm only familiar with a single definition for a continues function, but now I see there are many other equivalent definitions. I would appreciate if anyone could please explain what exactly the "continuity argument" means, and why the result almost follows it directly. Best regards | |
| Apr 1, 2020 at 14:03 | comment | added | keyboardAnt | @ Andreas, thank you for pointing on my mistake; now I understand that I wrote it wrong. | |
| Apr 1, 2020 at 0:31 | history | answered | Andreas Blass | CC BY-SA 4.0 |