Thread (3 posts)

The paper shows exactly how the quoted comment works through the construction of "incoherent matrices" - matrices where all columns have unit $\ell_2$ norm and pairwise inner products are at most $\eps$.

Here's the key construction from the paper:

Given an error-correcting code $\mathcal{C} = \{C_1, \ldots, C_n\}$ with:

• Alphabet size $q$
• Block length $t$
• Relative distance $1-\eps$ (meaning any two codewords differ in at least $(1-\eps)t$ positions)

You can build an $m \times n$ matrix $A$ with $m = qt$ rows as follows:

• Each column $A_i$ corresponds to codeword $C_i$
• Set $(A_i)_{j,k} = 1/\sqrt{t}$ if the $j$-th symbol of $C_i$ equals $k$, and $0$ otherwise

This gives you $n$ columns (vectors) where:

• Each column has exactly $t$ non-zero entries of value $1/\sqrt{t}$, so $\|A_i\|_2 = 1$
• For distinct columns $i \neq j$: $\langle A_i, A_j \rangle = \frac{t - \Delta(C_i, C_j)}{t} \leq \eps$

where $\Delta(C_i, C_j)$ is the Hamming distance between codewords.

For Reed-Solomon codes specifically, they take:

• $q = \Theta(\eps^{-1}\log n/(\log\log n + \log(1/\eps)))$
• Each codeword corresponds to evaluations of a degree-$d$ polynomial over $\mathbb{F}_q$
• This gives $n > q^d$ codewords (exponentially many in $d$)

The Reed-Solomon construction achieves $m = O(\eps^{-2}(\log n/(\log\log n + \log(1/\eps)))^2)$ rows, which beats random constructions when $\eps < 2^{-\Omega(\sqrt{\log n})}$.

So the "fun fact" is realized through error-correcting codes: good codes with large distance naturally give you many vectors with small pairwise inner products!