Weirdly, in spaces of high dimension, almost all vectors are almost at right angles.
This part, I can imagine. With a fixed reference vector written as (1,0,0,…,0), a second random vector has many dimensions that it can distribute its length along (x1,x2,x2,…,xd) while for alignment to the reference (the scalar product) only the first entry x1 contributes.
It’s perfectly feasible for this space to represent zillions of concepts almost at right angles to each other.
This part I struggle with. Is there an intuitive argument for why this is possible?
If I assume smaller angles below 60° or so, a non-rigorous argument could be:
each vector blocks a 30°-circle around it on the d-hypersphere[1] (if the circles of two vectors touch, their relative angle is 60°).
an estimate for the blocked area could be that this is mostly a ‘flat’ (d-1)-sphere of radius 30°/(1rad)=π/6≈0.6 which has an area that scales with Avector∼(0.6)d−1
the full hypersphere has a surface area with a similar pre-factor but full radius A∼(1)d−1
thus we can expect to fit a number of vectors N that scales roughly like N∼A/Avector∼(10.6)d−1 which is an exponential growth in d.
For a proof, one would need to include whether it is possible to tile the surface efficiently with the Avector circles. This seems clearly true for tiny angles (we can stack spheres in approximately flat space just fine), but seems a lot less obvious for larger angles. For example, full orthogonality would mean 90° angles and my estimate would still give N∼(1π/4)d−1≈(1.27)d−1, an exponential estimate for the number of strictly orthogonal states although these are definitely not exponentially many.
and a copy of that circle on the opposite end of the sphere ↩︎
Update: I found a proof of the “exponential number of near-orthogonal vectors” in these lecture notes https://www.cs.princeton.edu/courses/archive/fall16/cos521/Lectures/lec9.pdf
From my understanding, the proof uses a quantification of just how likely near-orthogonality becomes in high-dimensional spaces and derives a probability for pairwise near-orthogonality of many states.
This does not quite help my intuitions, but I’ll just assume that the “it it possible to tile the surface efficiently with circles even if their size gets close to the 45° threshold” resolves to “yes, if the dimensionality is high enough”.
One interesting aspect of these considerations should be that with growing dimensionality the definition of near-orthogonality can be made tighter without loosing the exponential number of vectors. This should define a natural signal-to-noise ratio for information encoded in this fashion.
This part, I can imagine. With a fixed reference vector written as (1,0,0,…,0), a second random vector has many dimensions that it can distribute its length along (x1,x2,x2,…,xd) while for alignment to the reference (the scalar product) only the first entry x1 contributes.
This part I struggle with. Is there an intuitive argument for why this is possible?
If I assume smaller angles below 60° or so, a non-rigorous argument could be:
each vector blocks a 30°-circle around it on the d-hypersphere[1] (if the circles of two vectors touch, their relative angle is 60°).
an estimate for the blocked area could be that this is mostly a ‘flat’ (d-1)-sphere of radius 30°/(1rad)=π/6≈0.6 which has an area that scales with Avector∼(0.6)d−1
the full hypersphere has a surface area with a similar pre-factor but full radius A∼(1)d−1
thus we can expect to fit a number of vectors N that scales roughly like N∼A/Avector∼(10.6)d−1 which is an exponential growth in d.
For a proof, one would need to include whether it is possible to tile the surface efficiently with the Avector circles. This seems clearly true for tiny angles (we can stack spheres in approximately flat space just fine), but seems a lot less obvious for larger angles. For example, full orthogonality would mean 90° angles and my estimate would still give N∼(1π/4)d−1≈(1.27)d−1, an exponential estimate for the number of strictly orthogonal states although these are definitely not exponentially many.
and a copy of that circle on the opposite end of the sphere ↩︎
Update: I found a proof of the “exponential number of near-orthogonal vectors” in these lecture notes https://www.cs.princeton.edu/courses/archive/fall16/cos521/Lectures/lec9.pdf From my understanding, the proof uses a quantification of just how likely near-orthogonality becomes in high-dimensional spaces and derives a probability for pairwise near-orthogonality of many states.
This does not quite help my intuitions, but I’ll just assume that the “it it possible to tile the surface efficiently with circles even if their size gets close to the 45° threshold” resolves to “yes, if the dimensionality is high enough”.
One interesting aspect of these considerations should be that with growing dimensionality the definition of near-orthogonality can be made tighter without loosing the exponential number of vectors. This should define a natural signal-to-noise ratio for information encoded in this fashion.