<p>I will present an equivalent but simpler-looking formulation of the problem, and show a lower bound of (<i>n</i>/<i>k</i> − 1) / (<i>n</i>−1).  <del>I also show a connection to an open problem in quantum information.</del>  <em>[Edit in revision 3: In earlier revisions, I claimed that an exact characterization of the cases in which the lower bound shown below is attained is likely to be difficult because an analogous question in the complex case includes an open problem about SIC-POVMs in quantum information.  However, this connection to SIC-POVMs was incorrect.  For details, see the section “Incorrect connection to SIC-POVMs in quantum information” below.]</em></p>

<h2>Equivalent formulation</h2>

<p>First, as was already pointed out in daniello’s answer, note that Var(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>) = E[(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>] − E[<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>]<sup>2</sup> = E[(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>].  So in the rest of the answer, we forget about variance and instead minimize max<sub><i>i</i>≠<i>j</i></sub>E[(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>].</p>

<p>Next, once we decide our goal is to minimize max<sub><i>i</i>≠<i>j</i></sub>E[(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>], we can ignore the constraint that E[<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>] = 0.  This is because if we have random unit vectors <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub>, then we can negate each of them independently with probability 1/2 to satisfy E[<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>] = 0 without changing the value of the objective function max<sub><i>i</i>≠<i>j</i></sub>E[(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>].</p>

<p>Moreover, changing the objective function from max<sub><i>i</i>≠<i>j</i></sub>E[(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>] to (1/(<i>n</i>(<i>n</i>−1)))∑<sub><i>i</i>≠<i>j</i></sub>E[(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>] does not change the optimum value.  The latter is at most the former because the average is at most the maximum.  However, we can always make the values of E[(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>] for different choices of (<i>i</i>, <i>j</i>) (<i>i</i>≠<i>j</i>) equal by permuting the <i>n</i> vectors <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> randomly.</p>

<p>So for any <i>n</i> and <i>k</i>, the optimum value of the problem in question is equal to the minimum of (1/(<i>n</i>(<i>n</i>−1)))∑<sub><i>i</i>≠<i>j</i></sub>E[(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>] where <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> are random variables which take unit vectors in ℝ<sup><i>k</i></sup> as values.</p>

<p>However, by linearity of expectation, this objective function is equal to the expected value E[(1/(<i>n</i>(<i>n</i>−1)))∑<sub><i>i</i>≠<i>j</i></sub>(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>].  Because the minimum is at most the average, there is no need to consider probability distributions anymore.  That is, the optimum value of the problem above is equal to the optimum value of the following:</p>

<blockquote>
  <p>Choose unit vectors <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> ∈ ℝ<sup><i>k</i></sup> to minimize (1/(<i>n</i>(<i>n</i>−1)))∑<sub><i>i</i>≠<i>j</i></sub>(<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup>.</p>
</blockquote>

<h2>Lower bound</h2>

<p>Using this equivalent formulation, we will prove that the optimal value is at least (<i>n</i>/<i>k</i> − 1) / (<i>n</i>−1).</p>

<p>For 1≤<i>i</i>≤<i>n</i>, let <i>X</i><sub><i>i</i></sub>=<i>x</i><sub><i>i</i></sub><i>x</i><sub><i>i</i></sub><sup>T</sup> be the rank-1 projector corresponding to the unit vector <i>x</i><sub><i>i</i></sub>.  Then, it holds that (<i>x</i><sub><i>i</i></sub><sup>T</sup><i>x</i><sub><i>j</i></sub>)<sup>2</sup> = Tr(<i>X</i><sub><i>i</i></sub><i>X</i><sub><i>j</i></sub>).</p>

<p>Let <i>Y</i> = ∑<sub><i>i</i></sub><i>X</i><sub><i>i</i></sub>.  Then, it holds that ∑<sub><i>i</i>≠<i>j</i></sub>Tr(<i>X</i><sub><i>i</i></sub><i>X</i><sub><i>j</i></sub>) = ∑<sub><i>i</i>,<i>j</i></sub>Tr(<i>X</i><sub><i>i</i></sub><i>X</i><sub><i>j</i></sub>) − <i>n</i> = Tr(<i>Y</i><sup>2</sup>) − <i>n</i>.</p>

<p>The Cauchy–Schwarz inequality implies that Tr(<i>Y</i><sup>2</sup>) ≥ (Tr <i>Y</i>)<sup>2</sup>/<i>k</i> = <i>n</i><sup>2</sup>/<i>k</i>, and therefore ∑<sub><i>i</i>≠<i>j</i></sub>Tr(<i>X</i><sub><i>i</i></sub><i>X</i><sub><i>j</i></sub>) = Tr(<i>Y</i><sup>2</sup>) − <i>n</i> ≥ <i>n</i><sup>2</sup>/<i>k</i> − <i>n</i>.  By dividing by <i>n</i>(<i>n</i>−1), we obtain that the objective value is at least (<i>n</i>/<i>k</i> − 1) / (<i>n</i>−1).</p>

<p>In particular, when <i>n</i>=<i>k</i>+1, daniello’s answer is within a factor of 2 from the optimal value.</p>

<h2>When is this lower bound attainable?</h2>

<p>Attaining this lower bound (<i>n</i>/<i>k</i> − 1) / (<i>n</i>−1) is equivalent to making <i>Y</i>=(<i>n</i>/<i>k</i>)<i>I</i>.  I do not know the exact characterization when it is attainable, but following sufficient conditions exist:</p>

<ul>
<li>When <i>n</i>=<i>k</i>+1, it is attainable by considering <i>k</i>+1 unit vectors which form a regular <i>k</i>-simplex centered at the origin, improving from 2/(<i>k</i>(<i>k</i>+1)) in daniello’s answer to the optimal 1/<i>k</i><sup>2</sup>.</li>
<li>When <i>n</i> is a multiple of <i>k</i>, it is clearly attainable by fixing an orthonormal basis of ℝ<sup><i>k</i></sup> and assigning each of the basis vectors to <i>n</i>/<i>k</i> of <i>v</i><sub>1</sub>, …, <i>v</i><sub><i>n</i></sub>.</li>
<li>More generally than the last bullet point, if it is attainable with some choice of <i>k</i> and both <i>n</i>=<i>n</i><sub>1</sub> and <i>n</i>=<i>n</i><sub>2</sub>, then it is also attainable for the same <i>k</i> and <i>n</i>=<i>n</i><sub>1</sub>+<i>n</i><sub>2</sub>.  In particular, it is attainable if <i>n</i>=<i>a</i><i>k</i>+<i>b</i> where <i>a</i> and <i>b</i> are integers satisfying <i>a</i>≥<i>b</i>≥0.</li>
</ul>

<p>Although I have not checked details, it seems that any <a href="http://mathworld.wolfram.com/SphericalDesign.html" rel="nofollow">spherical 2-design</a> gives a solution attaining this lower bound.</p>

<h2>Incorrect connection to SIC-POVMs in quantum information</h2>

<p>In earlier revisions, I stated:</p>

<blockquote>
  <p>I suspect that answering this completely is a difficult question.  The reason is that if we instead consider the complex vector space ℂ<sup><i>k</i></sup>, this question is related to an open problem in quantum information.</p>
</blockquote>

<p>But this relation was incorrect.  I will explain why.</p>

<blockquote>
  <p>More precisely, consider the following problem:</p>
  
  <blockquote>
    <p>Choose unit vectors <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> ∈ ℂ<sup><i>k</i></sup> to minimize (1/(<i>n</i>(<i>n</i>−1)))∑<sub><i>i</i>≠<i>j</i></sub>|<i>x</i><sub><i>i</i></sub><sup>*</sup><i>x</i><sub><i>j</i></sub>|<sup>2</sup>.</p>
  </blockquote>
  
  <p>The lower bound above equally holds in this complex version.   Consider the case where <i>n</i>=<i>k</i><sup>2</sup> in the complex version.  Then the lower bound is equal to 1/(<i>k</i>+1).</p>
</blockquote>

<p>So far, it was correct.</p>

<blockquote>
  <p>A set of <i>k</i><sup>2</sup> unit vectors <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>k</i><sup>2</sup></sub> ∈ ℂ<sup><i>k</i></sup> attaining the lower bound is called a <a href="http://en.wikipedia.org/wiki/SIC-POVM" rel="nofollow">SIC-POVM</a> in dimension <i>k</i>,</p>
</blockquote>

<p>This part was incorrect.  A SIC-POVM is a set of <i>k</i><sup>2</sup> unit vectors <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> ∈ ℂ<sup><i>k</i></sup> for which |<i>x</i><sub><i>i</i></sub><sup>*</sup><i>x</i><sub><i>j</i></sub>|<sup>2</sup> = 1/(<i>k</i>+1) for all <i>i</i>≠<i>j</i>.  Note that here the requirement must hold for all pairs <i>i</i>≠<i>j</i>, not just the average over all pairs <i>i</i>≠<i>j</i>.  In the “Equivalent formulation” section, we showed the equivalence between minimizing the maximum and minimizing the average, but this was possible because <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> were random variables taking unit vectors there.  Here <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> are just unit vectors, so we cannot use the same trick.</p>

CC BY-SA 3.0
2014-10-19T02:22:25.733Z
2014-10-19T22:33:16.453Z
2014-10-19T22:33:16.453Z
Tsuyoshi Ito
<p>The quick and dirty answer to the question is "no, the variance can be smaller":
Let $v_1, v_2, \ldots, v_k$ be the standard basis, and consider the following random process: pick a pair of distinct integers i,j from $\{1,2,\ldots,k+1\}$, and set $x_i = x_j = v_1$. For the other vectors $x_t$ (for $t \notin \{i,j\}$) assign them to $v_2, \ldots, v_k$ in a one-to-one manner. Then, for each $t \in \{1,\ldots,k+1\}$, either keep $x_i$ as it is or flip it (to $-x_i$) with probability $\frac{1}{2}$. </p>

<p>It is easy to see that $E[x_a \cdot x_b] = 0$ - either $x_a$ and $x_b$ are orthogonal or they point in the same/opposite direction with probability $\frac{1}{2}$ each. </p>

<p>On the other hand we have $Var[x_a \cdot x_b] = E[(x_a \cdot x_b)^2]$. We have that $(x_a \cdot x_b)^2 = 1$ if and only if $\{a,b\} = \{i,j\}$ which happens with probability $\frac{1}{k+1 \choose 2}$. Otherwise $(x_a \cdot x_b)^2 = 0$. Thus we have that for every $a$,$b$:
$$Var[x_a \cdot x_b] = E[(x_a \cdot x_b)^2] = \frac{1}{k+1 \choose 2}$$</p>

<p>My intuition is that this is as bad (small) as it gets but I do not have a proof. More interesting is that this construction seems to break down for n >> k, and also when the $x_i$'s have to be chosen independently (possibly from different distributions).</p>

CC BY-SA 3.0
2014-10-16T21:18:24.910Z
2014-10-16T21:18:24.910Z
daniello
<p>I am trying to find a distribution over $n$ random vectors, say $x_1,\ldots, x_n$, on the $k$-dimensional unit sphere (where $n &gt; k$) that minimizes $\max_{i\neq j} \mathrm{Var}(x_i^T x_j)$ subject to the constraint $\mathbb{E}[x_i^Tx_j]=0$.</p>

<p>I tried some distributions and almost all them have variance $1/k$. For example, both the distribution in which each coordinate of each $x_i$ is independently and uniformly chosen from $\left\{-1/\sqrt{k}, 1/\sqrt{k}\right\}$ and the distribution in which each $x_i$ is an independent uniform vector on the $k$-dimensional unit sphere have variance $1/k$.</p>

<p>Is $1/k$ the minimum variance among all distributions?</p>

CC BY-SA 3.0
2014-10-15T20:48:14.457Z
How tight of a bound are you interested in? That is, would a lower bound of 1/100k that only works for n > 100k be interesting or not?
daniello
CC BY-SA 3.0
2014-10-16T00:20:09.893Z
@daniello, do you mean a lower bound of 1/ck for n>ck where c is some constant? How to prove this?
peng
CC BY-SA 3.0
2014-10-16T12:19:30.960Z
Something i don't understand in the question: in the beginning you say distribution over *unit* vectors, but not all of the distributions you say you tried generate unit vectors... Do you mean that for all $x_i$, $E[|x_i|] = 1$?
daniello
CC BY-SA 3.0
2014-10-16T13:39:13.783Z
@deniello, I intended to make all vectors to be "unit".. Sorry, I forgot to do normalization on "Gaussian" vector, after normalization, it will be the same as uniform vector. Thank you for pointing out this mistake.
peng
<reference-request><randomized-algorithms>
What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?
peng
# What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?

(Asked by: username_0 on 2014-10-14)

I am trying to find a distribution over $n$ random vectors, say $x\_1,\ldots, x\_n$, on the $k$-dimensional unit sphere (where $n > k$) that minimizes $\max\_{i\neq j} \mathrm{Var}(x\_i^T x\_j)$ subject to the constraint $\mathbb{E}[x\_i^Tx\_j]=0$.

I tried some distributions and almost all them have variance $1/k$. For example, both the distribution in which each coordinate of each $x\_i$ is independently and uniformly chosen from $\left\{-1/\sqrt{k}, 1/\sqrt{k}\right\}$ and the distribution in which each $x\_i$ is an independent uniform vector on the $k$-dimensional unit sphere have variance $1/k$.

Is $1/k$ the minimum variance among all distributions?

**Tags:** reference-request, randomized-algorithms

> **Comments:**
> **username_1**: How tight of a bound are you interested in? That is, would a lower bound of 1/100k that only works for n > 100k be interesting or not?  
> **username_0**: @username_1, do you mean a lower bound of 1/ck for n>ck where c is some constant? How to prove this?  
> **username_1**: Something i don't understand in the question: in the beginning you say distribution over *unit* vectors, but not all of the distributions you say you tried generate unit vectors... Do you mean that for all $x_i$, $E[|x_i|] = 1$?  
> **username_0**: @deniello, I intended to make all vectors to be "unit".. Sorry, I forgot to do normalization on "Gaussian" vector, after normalization, it will be the same as uniform vector. Thank you for pointing out this mistake.  

---

## 2 answers

### Answer by username_2 on 2014-10-19. Score: 8

I will present an equivalent but simpler-looking formulation of the problem, and show a lower bound of (*n*/*k* − 1) / (*n*−1). ~~I also show a connection to an open problem in quantum information.~~ *[Edit in revision 3: In earlier revisions, I claimed that an exact characterization of the cases in which the lower bound shown below is attained is likely to be difficult because an analogous question in the complex case includes an open problem about SIC-POVMs in quantum information. However, this connection to SIC-POVMs was incorrect. For details, see the section “Incorrect connection to SIC-POVMs in quantum information” below.]*

## Equivalent formulation

First, as was already pointed out in username_1’s answer, note that Var(*x**i*T*x**j*) = E[(*x**i*T*x**j*)2] − E[*x**i*T*x**j*]2 = E[(*x**i*T*x**j*)2]. So in the rest of the answer, we forget about variance and instead minimize max*i*≠*j*E[(*x**i*T*x**j*)2].

Next, once we decide our goal is to minimize max*i*≠*j*E[(*x**i*T*x**j*)2], we can ignore the constraint that E[*x**i*T*x**j*] = 0. This is because if we have random unit vectors *x*1, …, *x**n*, then we can negate each of them independently with probability 1/2 to satisfy E[*x**i*T*x**j*] = 0 without changing the value of the objective function max*i*≠*j*E[(*x**i*T*x**j*)2].

Moreover, changing the objective function from max*i*≠*j*E[(*x**i*T*x**j*)2] to (1/(*n*(*n*−1)))∑*i*≠*j*E[(*x**i*T*x**j*)2] does not change the optimum value. The latter is at most the former because the average is at most the maximum. However, we can always make the values of E[(*x**i*T*x**j*)2] for different choices of (*i*, *j*) (*i*≠*j*) equal by permuting the *n* vectors *x*1, …, *x**n* randomly.

So for any *n* and *k*, the optimum value of the problem in question is equal to the minimum of (1/(*n*(*n*−1)))∑*i*≠*j*E[(*x**i*T*x**j*)2] where *x*1, …, *x**n* are random variables which take unit vectors in ℝ*k* as values.

However, by linearity of expectation, this objective function is equal to the expected value E[(1/(*n*(*n*−1)))∑*i*≠*j*(*x**i*T*x**j*)2]. Because the minimum is at most the average, there is no need to consider probability distributions anymore. That is, the optimum value of the problem above is equal to the optimum value of the following:

> Choose unit vectors *x*1, …, *x**n* ∈ ℝ*k* to minimize (1/(*n*(*n*−1)))∑*i*≠*j*(*x**i*T*x**j*)2.

## Lower bound

Using this equivalent formulation, we will prove that the optimal value is at least (*n*/*k* − 1) / (*n*−1).

For 1≤*i*≤*n*, let *X**i*=*x**i**x**i*T be the rank-1 projector corresponding to the unit vector *x**i*. Then, it holds that (*x**i*T*x**j*)2 = Tr(*X**i**X**j*).

Let *Y* = ∑*i**X**i*. Then, it holds that ∑*i*≠*j*Tr(*X**i**X**j*) = ∑*i*,*j*Tr(*X**i**X**j*) − *n* = Tr(*Y*2) − *n*.

The Cauchy–Schwarz inequality implies that Tr(*Y*2) ≥ (Tr *Y*)2/*k* = *n*2/*k*, and therefore ∑*i*≠*j*Tr(*X**i**X**j*) = Tr(*Y*2) − *n* ≥ *n*2/*k* − *n*. By dividing by *n*(*n*−1), we obtain that the objective value is at least (*n*/*k* − 1) / (*n*−1).

In particular, when *n*=*k*+1, username_1’s answer is within a factor of 2 from the optimal value.

## When is this lower bound attainable?

Attaining this lower bound (*n*/*k* − 1) / (*n*−1) is equivalent to making *Y*=(*n*/*k*)*I*. I do not know the exact characterization when it is attainable, but following sufficient conditions exist:

* When *n*=*k*+1, it is attainable by considering *k*+1 unit vectors which form a regular *k*-simplex centered at the origin, improving from 2/(*k*(*k*+1)) in username_1’s answer to the optimal 1/*k*2.
* When *n* is a multiple of *k*, it is clearly attainable by fixing an orthonormal basis of ℝ*k* and assigning each of the basis vectors to *n*/*k* of *v*1, …, *v**n*.
* More generally than the last bullet point, if it is attainable with some choice of *k* and both *n*=*n*1 and *n*=*n*2, then it is also attainable for the same *k* and *n*=*n*1+*n*2. In particular, it is attainable if *n*=*a**k*+*b* where *a* and *b* are integers satisfying *a*≥*b*≥0.

Although I have not checked details, it seems that any [spherical 2-design](http://mathworld.wolfram.com/SphericalDesign.html) gives a solution attaining this lower bound.

## Incorrect connection to SIC-POVMs in quantum information

In earlier revisions, I stated:

> I suspect that answering this completely is a difficult question. The reason is that if we instead consider the complex vector space ℂ*k*, this question is related to an open problem in quantum information.

But this relation was incorrect. I will explain why.

> More precisely, consider the following problem:
>
> > Choose unit vectors *x*1, …, *x**n* ∈ ℂ*k* to minimize (1/(*n*(*n*−1)))∑*i*≠*j*|*x**i*\**x**j*|2.
>
> The lower bound above equally holds in this complex version. Consider the case where *n*=*k*2 in the complex version. Then the lower bound is equal to 1/(*k*+1).

So far, it was correct.

> A set of *k*2 unit vectors *x*1, …, *x**k*2 ∈ ℂ*k* attaining the lower bound is called a [SIC-POVM](http://en.wikipedia.org/wiki/SIC-POVM) in dimension *k*,

This part was incorrect. A SIC-POVM is a set of *k*2 unit vectors *x*1, …, *x**n* ∈ ℂ*k* for which |*x**i*\**x**j*|2 = 1/(*k*+1) for all *i*≠*j*. Note that here the requirement must hold for all pairs *i*≠*j*, not just the average over all pairs *i*≠*j*. In the “Equivalent formulation” section, we showed the equivalence between minimizing the maximum and minimizing the average, but this was possible because *x*1, …, *x**n* were random variables taking unit vectors there. Here *x*1, …, *x**n* are just unit vectors, so we cannot use the same trick.


---

### Answer by username_1 on 2014-10-16. Score: 5

The quick and dirty answer to the question is "no, the variance can be smaller":
Let $v\_1, v\_2, \ldots, v\_k$ be the standard basis, and consider the following random process: pick a pair of distinct integers i,j from $\{1,2,\ldots,k+1\}$, and set $x\_i = x\_j = v\_1$. For the other vectors $x\_t$ (for $t \notin \{i,j\}$) assign them to $v\_2, \ldots, v\_k$ in a one-to-one manner. Then, for each $t \in \{1,\ldots,k+1\}$, either keep $x\_i$ as it is or flip it (to $-x\_i$) with probability $\frac{1}{2}$.

It is easy to see that $E[x\_a \cdot x\_b] = 0$ - either $x\_a$ and $x\_b$ are orthogonal or they point in the same/opposite direction with probability $\frac{1}{2}$ each.

On the other hand we have $Var[x\_a \cdot x\_b] = E[(x\_a \cdot x\_b)^2]$. We have that $(x\_a \cdot x\_b)^2 = 1$ if and only if $\{a,b\} = \{i,j\}$ which happens with probability $\frac{1}{k+1 \choose 2}$. Otherwise $(x\_a \cdot x\_b)^2 = 0$. Thus we have that for every $a$,$b$:
$$Var[x\_a \cdot x\_b] = E[(x\_a \cdot x\_b)^2] = \frac{1}{k+1 \choose 2}$$

My intuition is that this is as bad (small) as it gets but I do not have a proof. More interesting is that this construction seems to break down for n >> k, and also when the $x\_i$'s have to be chosen independently (possibly from different distributions).


---

