3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ crossposted math.stackexchange.com/questions/3296448/… --- please don't do that, in order to avoid duplication of efforts. $\endgroup$ Commented Jul 18, 2019 at 8:09
  • $\begingroup$ this is the content of the Johnson–Lindenstrauss lemma : $N\simeq e^{d\epsilon^2/8}$ $\endgroup$ Commented Jul 18, 2019 at 8:13
  • $\begingroup$ 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. $\endgroup$
    – user78150
    Commented Jul 18, 2019 at 8:33
  • $\begingroup$ Related question and answers. mathoverflow.net/questions/24864/almost-orthogonal-vectors/… $\endgroup$
    – kodlu
    Commented Jul 18, 2019 at 10:40

1 Answer 1

1
$\begingroup$

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).$$

$\endgroup$
2
  • $\begingroup$ Thanks, let me take a look. $\endgroup$
    – user78150
    Commented Jul 18, 2019 at 10:15
  • $\begingroup$ see also the answer given at physicsoverflow.org/42367 $\endgroup$ Commented Jul 19, 2019 at 10:47

You must log in to answer this question.