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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.