concentration inequalities

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]