Skip to main content
MathOverflow

Return to Answer

added 1765 characters in body
Source Link
Andreas Blass
Andreas Blass
  • 73.2k
  • 8
  • 191
  • 290

I'll discuss separately the question you asked and the exercise in the notes you linked to.

The question you asked is trivial as long as $k\geq3$. Just let $f$ be a projection onto the $3$-dimensional subspace spanned by $x,y,z$. You don't even need $\epsilon$, since $x,y,z$, and the angle are preserved exactly. (In fact, even if $k=2$, you can preserve the angle exactly by projecting orthogonally to the subspace spanned by $x-y$ and $z-y$.)

Of course, this isn't what the exercise (or the Johnson-Lindenstrauss lemma) is about. You wanted to approximately preserve one angle. The analog for angles of Johnson-Lindenstrauss wants to approximately preserve all angles between points from some given $q$-element set. To do this, one needs the target space to have dimension of order $(\log q)/(\epsilon^2)$; note the log of the number $q$ of points, not of the dimension of the space in which they lie.

Once the statement of the problem has been corrected to obtain for angles what Johnson-Lindenstrauss gives for distances, I want to use Paul Siegel's comment, that this follows from continuity of arccos. The only catch is that, at the ends $\pm1$ of its domain, arccos, though continuous, isn't differentiable. In other words, when $x,y,z$ are collinear, one can't trivially estimate the error in $\theta$ in terms of the errors in the distances between $x,y,z$. But one can estimate it with a bit of work. I'm too tired to attempt that work now, but it looks to me as if we might need $\epsilon^4$ rather than $\epsilon^2$ in the estimate for the dimension of the target space. (If we're guaranteed that no three of the $q$ points are collinear, then $\epsilon^2$ should suffice but the implicit constant in "of order $(\log q)/(\epsilon^2)$" will depend on how far from collinear the points are.)

Technicality: Worse than collinearity would be coincidence. If $y$ coincides with $x$ or $z$, then the angle at $y$ is undefined and the question disappears.

EDIT: Comments by usul under the question suggest that the collinearity problem can be attacked using the following rough idea, which might underlie the proof he describes, and which I hope is easier to understand (though harder to believe). Fix a small angle $b$, say $\pi/100$. Now given $n$ points and wanting to project to $O(\epsilon^{-2}\ln n)$ dimensions while approximately preserving the angles they determine, we know from Johnson-Lindenstrauss that we can preserve the distances between them, and we know from the earlier part of this answer that that will approximately preserve the angles if they're in the range $[b,\pi-b]$. For each of the remaining "bad" angles, say $\angle xyz$, adjoin to the configuration a new point $w$ chosen so that all the new angles thereby introduced are in the "good" range $[b,\pi-b]$. (See below if no such $w$ exists.) Now the approximate preservation of lengths and preservation of these "good" angles should imply approximate preservation of $\angle xyz$. This process, applied to all the bad angles in the original configuration adds at most $n^3$ new points, so the increase in the number of points is only polynomial, the increase in $\ln n$ is at most a constant factor, and $O(\epsilon^{-2}\ln n)$ remains correct (with a bigger implicit constant in $O$).

Unfortunately, there might not be an appropriate $w$. Suppose $x$ and $y$ are close together and $z$ is far away. To keep $\angle xwy$ in the good range, $w$ needs to be fairly near $x$ and $y$, but then $\angle xzw$ won't be good. That's part of the reason why this is only a rough idea; another part is the "should imply" in the previous paragraph.

Presumably all this roughness is smoothed out in the actual proof that usul referred to.

I'll discuss separately the question you asked and the exercise in the notes you linked to.

The question you asked is trivial as long as $k\geq3$. Just let $f$ be a projection onto the $3$-dimensional subspace spanned by $x,y,z$. You don't even need $\epsilon$, since $x,y,z$, and the angle are preserved exactly. (In fact, even if $k=2$, you can preserve the angle exactly by projecting orthogonally to the subspace spanned by $x-y$ and $z-y$.)

Of course, this isn't what the exercise (or the Johnson-Lindenstrauss lemma) is about. You wanted to approximately preserve one angle. The analog for angles of Johnson-Lindenstrauss wants to approximately preserve all angles between points from some given $q$-element set. To do this, one needs the target space to have dimension of order $(\log q)/(\epsilon^2)$; note the log of the number $q$ of points, not of the dimension of the space in which they lie.

Once the statement of the problem has been corrected to obtain for angles what Johnson-Lindenstrauss gives for distances, I want to use Paul Siegel's comment, that this follows from continuity of arccos. The only catch is that, at the ends $\pm1$ of its domain, arccos, though continuous, isn't differentiable. In other words, when $x,y,z$ are collinear, one can't trivially estimate the error in $\theta$ in terms of the errors in the distances between $x,y,z$. But one can estimate it with a bit of work. I'm too tired to attempt that work now, but it looks to me as if we might need $\epsilon^4$ rather than $\epsilon^2$ in the estimate for the dimension of the target space. (If we're guaranteed that no three of the $q$ points are collinear, then $\epsilon^2$ should suffice but the implicit constant in "of order $(\log q)/(\epsilon^2)$" will depend on how far from collinear the points are.)

Technicality: Worse than collinearity would be coincidence. If $y$ coincides with $x$ or $z$, then the angle at $y$ is undefined and the question disappears.

I'll discuss separately the question you asked and the exercise in the notes you linked to.

The question you asked is trivial as long as $k\geq3$. Just let $f$ be a projection onto the $3$-dimensional subspace spanned by $x,y,z$. You don't even need $\epsilon$, since $x,y,z$, and the angle are preserved exactly. (In fact, even if $k=2$, you can preserve the angle exactly by projecting orthogonally to the subspace spanned by $x-y$ and $z-y$.)

Of course, this isn't what the exercise (or the Johnson-Lindenstrauss lemma) is about. You wanted to approximately preserve one angle. The analog for angles of Johnson-Lindenstrauss wants to approximately preserve all angles between points from some given $q$-element set. To do this, one needs the target space to have dimension of order $(\log q)/(\epsilon^2)$; note the log of the number $q$ of points, not of the dimension of the space in which they lie.

Once the statement of the problem has been corrected to obtain for angles what Johnson-Lindenstrauss gives for distances, I want to use Paul Siegel's comment, that this follows from continuity of arccos. The only catch is that, at the ends $\pm1$ of its domain, arccos, though continuous, isn't differentiable. In other words, when $x,y,z$ are collinear, one can't trivially estimate the error in $\theta$ in terms of the errors in the distances between $x,y,z$. But one can estimate it with a bit of work. I'm too tired to attempt that work now, but it looks to me as if we might need $\epsilon^4$ rather than $\epsilon^2$ in the estimate for the dimension of the target space. (If we're guaranteed that no three of the $q$ points are collinear, then $\epsilon^2$ should suffice but the implicit constant in "of order $(\log q)/(\epsilon^2)$" will depend on how far from collinear the points are.)

Technicality: Worse than collinearity would be coincidence. If $y$ coincides with $x$ or $z$, then the angle at $y$ is undefined and the question disappears.

EDIT: Comments by usul under the question suggest that the collinearity problem can be attacked using the following rough idea, which might underlie the proof he describes, and which I hope is easier to understand (though harder to believe). Fix a small angle $b$, say $\pi/100$. Now given $n$ points and wanting to project to $O(\epsilon^{-2}\ln n)$ dimensions while approximately preserving the angles they determine, we know from Johnson-Lindenstrauss that we can preserve the distances between them, and we know from the earlier part of this answer that that will approximately preserve the angles if they're in the range $[b,\pi-b]$. For each of the remaining "bad" angles, say $\angle xyz$, adjoin to the configuration a new point $w$ chosen so that all the new angles thereby introduced are in the "good" range $[b,\pi-b]$. (See below if no such $w$ exists.) Now the approximate preservation of lengths and preservation of these "good" angles should imply approximate preservation of $\angle xyz$. This process, applied to all the bad angles in the original configuration adds at most $n^3$ new points, so the increase in the number of points is only polynomial, the increase in $\ln n$ is at most a constant factor, and $O(\epsilon^{-2}\ln n)$ remains correct (with a bigger implicit constant in $O$).

Unfortunately, there might not be an appropriate $w$. Suppose $x$ and $y$ are close together and $z$ is far away. To keep $\angle xwy$ in the good range, $w$ needs to be fairly near $x$ and $y$, but then $\angle xzw$ won't be good. That's part of the reason why this is only a rough idea; another part is the "should imply" in the previous paragraph.

Presumably all this roughness is smoothed out in the actual proof that usul referred to.

Source Link
Andreas Blass
Andreas Blass
  • 73.2k
  • 8
  • 191
  • 290

I'll discuss separately the question you asked and the exercise in the notes you linked to.

The question you asked is trivial as long as $k\geq3$. Just let $f$ be a projection onto the $3$-dimensional subspace spanned by $x,y,z$. You don't even need $\epsilon$, since $x,y,z$, and the angle are preserved exactly. (In fact, even if $k=2$, you can preserve the angle exactly by projecting orthogonally to the subspace spanned by $x-y$ and $z-y$.)

Of course, this isn't what the exercise (or the Johnson-Lindenstrauss lemma) is about. You wanted to approximately preserve one angle. The analog for angles of Johnson-Lindenstrauss wants to approximately preserve all angles between points from some given $q$-element set. To do this, one needs the target space to have dimension of order $(\log q)/(\epsilon^2)$; note the log of the number $q$ of points, not of the dimension of the space in which they lie.

Once the statement of the problem has been corrected to obtain for angles what Johnson-Lindenstrauss gives for distances, I want to use Paul Siegel's comment, that this follows from continuity of arccos. The only catch is that, at the ends $\pm1$ of its domain, arccos, though continuous, isn't differentiable. In other words, when $x,y,z$ are collinear, one can't trivially estimate the error in $\theta$ in terms of the errors in the distances between $x,y,z$. But one can estimate it with a bit of work. I'm too tired to attempt that work now, but it looks to me as if we might need $\epsilon^4$ rather than $\epsilon^2$ in the estimate for the dimension of the target space. (If we're guaranteed that no three of the $q$ points are collinear, then $\epsilon^2$ should suffice but the implicit constant in "of order $(\log q)/(\epsilon^2)$" will depend on how far from collinear the points are.)

Technicality: Worse than collinearity would be coincidence. If $y$ coincides with $x$ or $z$, then the angle at $y$ is undefined and the question disappears.