|
Let $v_1,\dotsc,v_k \in \mathbb{R}^d$ be unit-length vectors such that $$\sum_{1\leq i,j\leq k} |\langle v_i,v_j\rangle|^2 \leq \epsilon k^2.$$ What sort of lower bound can we give on $d$ in terms of $k$ and $\epsilon$? Must it be the case that $d\gg \min(\log k,\epsilon^{-1})$, say, or anything of the sort? Is that tight? |
|||||||||||||||||
|
|
The Johnson Lindenstrauss Lemma states that there are $k$ vectors achieving $\epsilon$ provided $d\geq C \epsilon^{-2} \log k.$ If you actually want to bound the maximum absolute value of the inner product for distinct vectors, instead of the average as you stated which is of course stronger, then tighter bounds apply. Relevant results for this case are due to Welch, Kabatianski, Levenshtein, Sidelnikov. Welch's applies to arbitrary vectors, real or complex. The others apply to vectors constructed from complex roots of unity of some finite order. Welch's bound states Let $e\geq 1$ be an integer and let $a_1,\ldots,a_k$ be distinct vectors in $\mathbb{C}^d.$ Then the following inequalities hold $$ \sum_{i=1}^k \sum_{j=1}^k \left| \langle a_i, a_j \rangle \right|^{2e} \geq \frac{\left(\sum_{i=1}^k \lVert a_i \rVert^{2e}\right)^2}{\binom{d+e-1}{e}}, $$ If the set of vectors you are interested in is of size roughly $d^u,$ the tightest lower bound is obtained by choosing $e=\lfloor u\rfloor.$ Edit: Since you required $\langle a_i,a_i\rangle=1,1\leq i\leq k,$ if I subtract the diagonal inner products, I obtain $$ \sum_{1\leq i\neq j\leq k} \left| \langle a_i, a_j \rangle \right|^{2} \geq \frac{k^2-kd}{d}, $$ recovering the dependence on $k.$ Edit 2: The Johnson Lindenstrauss Lemma is tight up to a constant factor. The Welch bound is tight for some cases, when so-called Welch Bound with Equality sets of vectors exist, which correspond to all unequal innner products being the same in absolute value. |
|||||||||||||||||
|
