14
$\begingroup$

Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:

$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$

Clearly, if $n=d$, the minimum is attained by taking $v_i=e_i$. Could it be that for $n>d$ in order to minimize the latter expression it is still best to take the vectors $v_i=e_{i\, \text{mod}\, d}$?

$\endgroup$
4
  • 7
    $\begingroup$ Probably the question is missing some assumptions - perhaps you mean vectors of unit length (otherwise you could simply put $v_i=0$). $\endgroup$ Jun 21, 2017 at 11:08
  • $\begingroup$ There is a related problem: finding an almost orthonormal system meaning that $|v_i|=1$ and $|\langle v_i,v_j\rangle|<\varepsilon$. For fixed small $\varepsilon>0$ the maximal number of elements in a almost orthonormal system grows exponentially from the dimension $d$. (It can be proved using the probabilistic method.) $\endgroup$ Jun 21, 2017 at 15:09
  • $\begingroup$ Martin Sleziak you are correct - vectors of unit length - I edited the question. $\endgroup$
    – TOM
    Jun 22, 2017 at 12:34
  • $\begingroup$ A problem in the same spirit and with the same conjectural optimal configuration: mathoverflow.net/questions/173712/… $\endgroup$ Jun 22, 2017 at 20:09

3 Answers 3

12
$\begingroup$

It is quite likely. At least, the proof for the case $d\mid n$ is easy. First of all, the restriction $i\ne j$ does not matter: adding $n$ ones changes nothing in the problem. Now notice that $|\langle v_i,v_j\rangle|\ge \langle v_i,v_j\rangle^2=\langle V_i,V_j\rangle$ where $V_i=v_i\otimes v_i$. Now, $\langle V_i,I\rangle=1$ for all $i$ ($I$ is the identity matrix, as usual), so $\langle\sum_i V_i,I\rangle=n$ and, by Cauchy-Schwarz, $\|\sum_i V_i\|^2\ge n^2/\|I\|^2=n^2/d$ (the norm here is the Frobenius norm, i.e., the square root of the sum of the squares of the matrix elements), which results in $\min_{v_i}\sum_{i,j}\langle v_i,v_j\rangle^2\ge n^2/d$. For the conjectured minimizer, both this estimate and the crude inequalities $|\langle v_i,v_j\rangle|\ge \langle v_i,v_j\rangle^2$ become identities, whence the conclusion.

I do not see off hand how to modify this argument for the case $d\not\mid n$ but it still makes the conjecture quite plausible. In the worst case scenario, you are off by at most $d/4$ from the true minimum with your system.

$\endgroup$
2
  • 2
    $\begingroup$ Alas, $\sum \langle v_i, v_j\rangle^2$ has different minimizer already for $n=3$, $d=2$. $\endgroup$ Jun 26, 2017 at 4:47
  • $\begingroup$ In general, minimizing in $\ell^1$ and $\ell^2$ is not the same thing, so it's surprising (to me) that this works so smoothly here. For example, for $d=2$, $n=3$ equally spaced vectors beat the orthogonal configuration for $p=2$. $\endgroup$ Jun 26, 2017 at 4:48
7
$\begingroup$

In addition to fedja's clever argument for the case $d|n$, let me prove this for $d=2$ (and $n$ of arbitrary parity).

We have $|\cos x|\geqslant 1-\frac2\pi x$ for $x\in [0,\pi/2]$ by concavity of cosine. So, it suffices to prove that the sum of angles between lines $\ell_1,\dots,\ell_n$ (which are parallel to vectors $v_1,\dots,v_n$) is maximal when $\lfloor n/2\rfloor$ lines coincide with certain line $a$ and $\lceil n/2\rceil$ other lines also coincide with $b\perp a$. Induct with bases $n=1,2$. Note that if, say, $\ell_n,\ell_{n-1}$ are orthogonal, we have $\angle(\ell_i,\ell_n)+\angle(\ell_i,\ell_{n-1})\geqslant \pi/2$, and summing up these inequalities with induction proposition for $\ell_1,\dots,\ell_{n-2}$ we get the result. If no two lines are orthogonal, we may move any of them to the direction which increases the sum of angles until either two lines become orthogonal or two of them coincide. In this second case move this pair of coinciding line, etc. Finally either all lines coincide, and the sum of angles is too small, or we get a pair of orthogonal lines on some step.

$\endgroup$
3
  • $\begingroup$ Actually, combined with the argument from my post, this idea allows one to prove the sharp bound for the case $n\ge N_0(d)$ (I'm too lazy to estimate $N_0(d)$ now but it is surely at most polynomial in $d$). Also it is easy to do the case $d<n\le 2d$ by simple induction. This makes the conjecture in question extremely plausible (though I'm somewhat short of the full proof yet). $\endgroup$
    – fedja
    Jun 27, 2017 at 16:42
  • $\begingroup$ @fedja You mean that for large $n$ even the sum of squares has the same minimizer? $\endgroup$ Jun 27, 2017 at 18:22
  • 1
    $\begingroup$ Of course, not! The sum of squares has the minimum $n^2/d$ more often than not (any time you can write $nI=\sum_i v_i\otimes v_i$ with unit length vectors $v_i$). What I mean is that the difference between the sum and the sum of squares can be at most $d/4$, so the Gram matrix may have only $O(d/\varepsilon)$ elements with absolute values between $\varepsilon$ and $1-\varepsilon$. From there it is easy to see that the minimizing configuration must consist of $d$ bunches of nearly coinciding vectors and different bunches are nearly orthogonal. After that the local analysis is not hard at all. $\endgroup$
    – fedja
    Jun 27, 2017 at 18:38
5
$\begingroup$

In fact, the minimizers of the sum $\sum \langle v_i, v_j \rangle^2$ are precisely tight frames, i.e. sets such that for some $C>0$and for each $x\in \mathbb R^d$, one has $\| x \|^2 = C \sum \langle x, v_j \rangle^2$. This was proved in Benedetto, Fickus "Finite Normalized Tight Frames", Adv. Comp. Math., 18 (2003), pp. 357-385.

Thus for $n$ not a multiple of $d$, the set $v_i = e_{i\mod d}$ is not a minimizer, since it is not a tight frame.

Although, I believe that for $\ell^1$ the answer may still be correct.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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