Math Twitter: How many almost-orthogonal unit vectors can you fit into n dimensions? Is there a good bound to help get a sense for this?
Show this thread
cc @dabacon, @AndrewDohertyQu, what are good results on this? Tyler: for fixed epsilon, you can find exponentially many unit vectors such that the inner product between each is < epsilon. IIRC, it's pretty easy to prove by choosing vectors at random, & weeding out exceptions.
-
-
I believe there are explicit constructions based on error-correcting codes, too.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
Some explicit constructions & also bounds based on random choice in this paper: https://arxiv.org/pdf/quant-ph/0102001.pdf …
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
In high dim, no known construction beats 'sequentially choose arbitrary points until you run out of space'. There are 'concentration of measure' results which bound the area of spherical caps; these easily give lower bounds for the number of mutually almost-orthogonal vectors.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
There are well-summarized results for some n and epsilon here http://neilsloane.com/packings/
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
This is kinda what cdma is, right?
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.