3

In a $d$ dimensional vector space defined over $\mathbb{C}$, how do I calculate the largest number $N(\epsilon, d)$ of vectors $\{V_i\}$ which satisfies the following properties. Here $\epsilon$ is smaller but finite compared to 1.

$$\langle V_i, V_i\rangle = 1$$

$$|\langle V_i, V_j\rangle| \leq \epsilon, i \neq j$$

Some examples are as follows.

  1. $N(0, d)$ = d

  2. $N\left(\frac{1}{2}, 2\right)$ = 3

  3. $N\left(\frac{1}{\sqrt{2}}, 2\right) = 6$

How do I obtain any general formula for $N(\epsilon, d)$. Even an approximate form for $N(\epsilon, d)$ in the large $d$ and small $\epsilon$ ($\epsilon \ll 1$) limit works fine for me.

  • 1
    crossposted https://math.stackexchange.com/questions/3296448/maximum-number-of-almost-orthogonal-vectors-in-a-complex-vector-space --- please don't do that, in order to avoid duplication of efforts. – Carlo Beenakker Jul 18 '19 at 08:09
  • this is the content of the Johnson–Lindenstrauss lemma : $N\simeq e^{d\epsilon^2/8}$ – Carlo Beenakker Jul 18 '19 at 08:13
  • Hi @CarloBeenakker, I crossposted this to increase the audience, and to avoid duplication of efforts I would edit the question on other platform if I find my answer somewhere. Regarding your comment, is there a version of JL lemma for high dimensional vector spaces defined over ℂ ? This is very close to the formula I was looking for, so thanks for pointing that out. –  Jul 18 '19 at 08:33
  • Related question and answers. https://mathoverflow.net/questions/24864/almost-orthogonal-vectors/184677#184677 – kodlu Jul 18 '19 at 10:40

1 Answers1

1

The variant of the Johnson-Lindenstrauss lemma that you can use is derived by L. Welch in Lower bounds on the maximum cross correlation of signals (1974). This paper is behind a paywall, I quote the result from arXiv:0909.0206

Consider $N=d^{k}$ unit vectors $V_i$ in $\mathbb{C}^d$ with $N>d$. Then the maximal inner product $\epsilon=\max_{i\neq j}|\langle V_i|V_j\rangle|$ satisfies the inequality $$\epsilon^{2k}\geq \frac{1}{N-1}\left(\frac{N}{{{d+k-1}\choose{k}}}-1\right).$$

Carlo Beenakker
  • 177,695