johnson-lindenstrauss

SpeakEZ.tech ✓ @SpeakezTech · Mar 29 The PCA/random projection tradeoff makes sense for static datasets where structure can be analyzed in advance. In gradient estimation via randomized forward-mode autodiff, you cannot run PCA on the object you are trying to compute. Random projection is not a fallback there. It is the only non-circular approach. The J-L bound then tells you exactly how many directional samples you need, logarithmic in weight-space dimension. When accumulation is exact via quire, the distortion bound is purely statistical with no arithmetic error component folded in.

Alex Clemmer 🔥🔥...✓ @haus... · Mar 28 The first time you hear about the JL lemma, it will seem too good to be true. And it is, kind of, I'll explain. The idea is: if you have points in large d-dimensional space, a RANDOM projection to much smaller k-dim subspace will be "nearly optimal" "in the general case." Or, more specifically: with high probability, the pairwise distances between points are preserved, given a couple other requirements around d and k. So why don't we just use random projections instead of carefully-constructed ones all the time? This is the most common misunderstanding of the JL lemma, and the one thing to really understand about it: in many (most?) datasets that are meaningful to humans, you actually CAN do better with something like maybe PCA. If your dataset is pathological, e.g., the points all lie on a plane even though it's technically in 3 dimensions, then clearly some planes you project onto will be better than others. The JL lemma does not apply to 2 and 3 dimensions, but you can imagine this would be true in large numbers of dimensions too. (See screenshot 1, i hope you like it because i made it myself lol.) If you know just those facts, you will be pretty well-prepared to answer most questions about its use. Most of the papers Delip mentions do presuppose that you know this. At least when I was a student, I found this to be non-obvious. [Embedded diagram: two 3D cube diagrams labeled "fig. 1: randomly projecting from R^3 to R^2" — left "random projection is nearly optimal", right "PCA is far better than random projection", each showing points projected onto a 2D plane inside a cube] > QUOTED: Delip Rao e/σ ✓ @deliprao · Mar 27 > The Google turboquant paper is [cut off]

Greg Burnham @GregHBurnham · Mar 26 Wild. Can you give an intuition for why? I can see it for N=2 ;) I guess that shows how the points can "waste" lots of dimensions, and the geometry is more determined by the points themselves than the ambient dimension. So I guess the question is just, why log(N)? [6 replies, 18 likes, 5.1K views] Paata Ivanisvili ✓ @PI010101 · Mar 26 log(N) comes from the union bound + the fact that square of Gaussian is subexponential. You can think of any linear map f as nxd matrix A, where n is the dimension of the target space, and d the dimension of the space where your N vectors live. A good starting point is to look among random matrices A having the property E ||Av||^2 =||v||^2 for all vectors v, and then, hopefully, the rest should follow from concentration inequalities, i.e., ||Av||^2 cannot be too far from its average E ||Av||^2=||v||^2. Union bound tells you that the probability this inequality fails for some two vectors among our set of N vectors is at most N^2 times P( ||Av||^2 is outside eps-neighbourhood of its average) < N^2 exp(-n C(eps)). And this is less than 1 if n is of order log(N). [1 reply, 69 likes, 4.4K views] Greg Burnham @GregHBurnham · Mar 26 Oh that's cool. So can you get something tighter precisely by the degree to which the square of the Gaussian is subexponential, if that makes sense? [1 reply, 6 likes, 810 views] Paata Ivanisvili ✓ @PI010101 · Mar 26 Good point. One can certainly experiment with different random variables, but since the log(N) is already sharp, there's not much room for [cut off]