Vectors that are almost orthogonal on average: lower bounds on dimension?

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?

• I guess a more flexible reformulation is to let $v_1,\ldots,v_k$ be unit-length vectors in some vector space of large (infinite?) dimension, and ask for a lower bound on the dimension of their span given the almost-orthogonal condition. – Peter Humphries Feb 9 '17 at 22:05
• Isn't this equivalent? – H A Helfgott Feb 9 '17 at 22:12
• Yes of course.. – Peter Humphries Feb 9 '17 at 22:13

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.

References:

V.M. Sidelnikov, On mutual correlation of sequences, Soviet Math Dokl. 12:197-201, 1971.

V.M. Sidelnikov, Cross correlation of sequences, Problemy Kybernitiki, 24:15-42, 1971 (in Russian)

Welch, L.R. Lower Bounds on the Maximum Cross Correlation of Signals. IEEE Transactions on Information Theory. 20 (3): 397–399, 1974.

Kabatianskii, G. A.; Levenshtein, V. I. Bounds for packings on the sphere and in space. (Russian) Problemy Peredači Informacii 14 (1978), no. 1, 3–25. (A version of this might be available in English translation, in Problems of Information Transmission)

• Wait. Doesn't the inequality you cite as Welch's imply that $d\geq \epsilon^{-1}$, with no dependence on $k$? This seems a little too strong. – H A Helfgott Feb 9 '17 at 23:13
• @HAHelfgott, please see edit. – kodlu Feb 9 '17 at 23:31
• Thanks. That answers the question, then. But how far is it from being tight? Is the Johnson Lindenstrauss Lemma tight? – H A Helfgott Feb 9 '17 at 23:52
• As I pointed out earlier in a now deleted comment, we can (trivially) achieve the bound for a given $\epsilon$ without any real size restrictions on $k$ if $d\ge\epsilon^{-1}$ by just repeating an ONB of $\mathbb R^d$. (I guess it would be more honest to say that if $d$ is very close to $\epsilon^{-1}$, then $k$ should be a multiple of $d$ to be safe.) – Christian Remling Feb 10 '17 at 1:51
• May you give references to "Welch, Kabatianski, Levenshtein, Sidelnikov", please. – Sergei Feb 11 '17 at 5:37