dimensionality reduction

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]

Gunn @gunnchun · Nov 13 Nicely written! I was gonna ask if you'd do the same for UMap but you already got that covered haha [1K views] Auriel MorningStar @Ebayednoob · 23h Mor - Model Object Reduction, is the group of techniques I started using along with lots of projected geometric expansion styles. I will say using a standardized universal 64 bit tensor hash to represent projected data, and having that projected data 'perspective' be a low-dimensional manifold really allows optimal compression, as long as you follow proper physics and geometry rules. So a quick example, 72 spheres pack optimally into a hexagonal polygon. If you were to wrap a 6 point node stream around a toroid, and divide it into 72 sections, you will get a projected 4-sphere that can convert completely to a square. This square can be a matrix that stores the 2D low dimensional array data. It's all about properly back-tracking the steps with the encoders / decoders. [1K views] joe @JOcadhla · Nov 13 Intuitive and soothing [868 views] Max David Gu... @MaxDavidGup... · Nov 13 super cool and much needed for a relatively un-discussed technique ! do you find people use isomap often enough in interpretability work ? [552 views] soulblocks @solcoindegen · 16h Neat [361 views]