13
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Feb 9, 2017 at 22:05
  • 1
    $\begingroup$ Isn't this equivalent? $\endgroup$ Feb 9, 2017 at 22:12
  • $\begingroup$ Yes of course.. $\endgroup$ Feb 9, 2017 at 22:13

1 Answer 1

7
$\begingroup$

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)

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Feb 9, 2017 at 23:13
  • $\begingroup$ @HAHelfgott, please see edit. $\endgroup$
    – kodlu
    Feb 9, 2017 at 23:31
  • $\begingroup$ Thanks. That answers the question, then. But how far is it from being tight? Is the Johnson Lindenstrauss Lemma tight? $\endgroup$ Feb 9, 2017 at 23:52
  • 1
    $\begingroup$ 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.) $\endgroup$ Feb 10, 2017 at 1:51
  • $\begingroup$ May you give references to "Welch, Kabatianski, Levenshtein, Sidelnikov", please. $\endgroup$
    – Sergei
    Feb 11, 2017 at 5:37

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.