# Almost Orthogonal Vectors You can fit $n$ orthogonal vectors in an $n$-dimensional vector space. However, what if you slightly loosen the constraint and require that the vectors are "almost orthogonal". How many almost orthogonal vectors can you fit into an $n$-dimensional vector space? Consider a high-dimensional space, say 100 dimensions. We randomly generate 200 vectors where each component of each vector is either +1 or -1. We'll look at their inner products to measure how "close" these vectors come to being orthogonal. #### Step 1: Vector Generation Generate two random vectors $u$ and $v$ in $\mathbb{R}^{100}$, each with components randomly assigned to +1 or -1. #### Step 2: Calculating the Inner Product The inner product of $u$ and $v$ is: $\langle u,v \rangle = \sum_{i=1}^{100} u_iv_i$ Each term $u_iv_i$​ is either +1 (if $u_i = v_i$) or -1 (if $u_i \neq v_i$). If $u$ and $v$ were perfectly orthogonal, this sum would be 0. #### Step 3: Expectation of Randomness Given that $u_i$​ and $v_i$​ are independent and randomly assigned, the expected value of each product $u_i v_i$​ is 0 because there's an equal probability of getting +1 or -1. However, due to random variation, the actual sum is unlikely to be exactly zero but rather some small number relative to the vector length. #### Step 4: Observing "Almost Orthogonality" With 100 terms, by the Central Limit Theorem, the distribution of $\langle u,v \rangle$ tends to a normal distribution centered around 0 with some variance. Thus, as the dimension $n$ grows, the likelihood that the inner product $\langle u,v \rangle$ is close to zero increases, indicating that in high dimensions, randomly chosen vectors are "almost orthogonal" with high probability. ### Intuitive Conclusion In high-dimensional spaces, even if vectors are not strictly orthogonal, their inner products can be small relative to their lengths, which allows for the vectors to behave as if they are almost orthogonal. This phenomenon is crucial in applications like compressed sensing, where it supports the efficient encoding and recovery of information. The concept leverages the "curse of dimensionality" in a beneficial way, where the high dimensionality that complicates many machine learning and statistical tasks helps in creating large sets of useful, nearly orthogonal vectors. --- Date: 20240506 Links to: Tags: References: * [Sean Carroll: General Relativity, Quantum Mechanics, Black Holes & Aliens | Lex Fridman Podcast #428 - YouTube](https://www.youtube.com/watch?v=tdv7r2JSokI&t=2926s)