3 ms·

Favorite lemmata: Johnson–Lindenstrauss lemma https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma https://en.wikipedia.org/wiki/Johnson%E2%80%93

by emil-lp 5mo ago

Favorite lemmata: Johnson–Lindenstrauss lemma https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_... Isolation lemma https://en.wikipedia.org/wiki/Isolation_lemma https://en.wikipedia.org/wiki/Isolation_lemma Schwartz–Zippel lemma https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma Lovász local lemma https://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma https://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma

dchftcs 5mo ago
The division of lemmas and theorems is really a bit artificial for these things. But yeah I think the spirit is that a theorem is an object that you aim to study, while a lemma is something you use to do that. Fermat's last theorem was a target, but the techniques including lemmas used and developed for it are the real prize for a working mathematician. Sculptures are kind of the point, but there's no question the tools used for sculpting are more useful and "worth" more in that sense.
trostaft 5mo ago
Ah the JL lemma. Probably one of my favorite too. I'm teaching a mathematics of data course next semester, and even though we don't assume probability as a prerequisite I'm going to find a way to talk about that idea.
- srean 5mo ago
  I am sure you know this, but inner-products are not preserved, the el_2 distance is (approximately). So it needs judicious care when used along with algorithm s that work with inner-products
  - dchftcs 5mo ago
    If you preserve the l2 distance you preserve the inner product, that's somewhat tautological in an L2 space. Just that the degree you can preserve inner products can be misleading, main problem is that orthogonal vectors may only become near-orthogonal which is sometimes a big deal, though perfect correlations are preserved because the JL transform is linear. Both can be seen looking at: https://en.wikipedia.org/wiki/Polarization_identity https://en.wikipedia.org/wiki/Polarization_identity
    - srean 5mo ago
      > If you preserve the l2 distance you preserve the inner product That's trivially untrue. You can move the origin around and that doesn't change the el_2 metric but will change the inner product. This would not happen for random rotations of course because they do not change the origin. However random Euclidean motions can change the origin.
      - dchftcs 5mo ago
        Right, indeed you need to first preserve the origin, but also that is trivially true for a linear map like JL.
        srean 5mo ago
        As far as I can recall JL holds for affine transformations too, in any case it's an existence result. Have to double check on the affine bit. The popular proof does uses random linear transforms and they indeed will not change the origin, but that's just one class of transforms with the JL property.

by emil-lp 5mo ago

dchftcs 5mo ago

The division of lemmas and theorems is really a bit artificial for these things. But yeah I think the spirit is that a theorem is an object that you aim to study, while a lemma is something you use to do that. Fermat's last theorem was a target, but the techniques including lemmas used and developed for it are the real prize for a working mathematician. Sculptures are kind of the point, but there's no question the tools used for sculpting are more useful and "worth" more in that sense.

trostaft 5mo ago

Ah the JL lemma. Probably one of my favorite too. I'm teaching a mathematics of data course next semester, and even though we don't assume probability as a prerequisite I'm going to find a way to talk about that idea.

srean 5mo ago
I am sure you know this, but inner-products are not preserved, the el_2 distance is (approximately). So it needs judicious care when used along with algorithm s that work with inner-products
- dchftcs 5mo ago
  If you preserve the l2 distance you preserve the inner product, that's somewhat tautological in an L2 space. Just that the degree you can preserve inner products can be misleading, main problem is that orthogonal vectors may only become near-orthogonal which is sometimes a big deal, though perfect correlations are preserved because the JL transform is linear. Both can be seen looking at: https://en.wikipedia.org/wiki/Polarization_identity https://en.wikipedia.org/wiki/Polarization_identity
  - srean 5mo ago
    > If you preserve the l2 distance you preserve the inner product That's trivially untrue. You can move the origin around and that doesn't change the el_2 metric but will change the inner product. This would not happen for random rotations of course because they do not change the origin. However random Euclidean motions can change the origin.
    - dchftcs 5mo ago
      Right, indeed you need to first preserve the origin, but also that is trivially true for a linear map like JL.
      - srean 5mo ago
        As far as I can recall JL holds for affine transformations too, in any case it's an existence result. Have to double check on the affine bit. The popular proof does uses random linear transforms and they indeed will not change the origin, but that's just one class of transforms with the JL property.