10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – daniello Oct 15 '14 at 20:48
  • $\begingroup$ @daniello, do you mean a lower bound of 1/ck for n>ck where c is some constant? How to prove this? $\endgroup$ – peng Oct 16 '14 at 0:20
  • $\begingroup$ 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$? $\endgroup$ – daniello Oct 16 '14 at 12:19
  • $\begingroup$ @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. $\endgroup$ – peng Oct 16 '14 at 13:39
8
$\begingroup$

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 daniello’s answer, note that Var(xiTxj) = E[(xiTxj)2] − E[xiTxj]2 = E[(xiTxj)2]. So in the rest of the answer, we forget about variance and instead minimize maxijE[(xiTxj)2].

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

Moreover, changing the objective function from maxijE[(xiTxj)2] to (1/(n(n−1)))∑ijE[(xiTxj)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[(xiTxj)2] for different choices of (i, j) (ij) equal by permuting the n vectors x1, …, xn 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)))∑ijE[(xiTxj)2] where x1, …, xn 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)))∑ij(xiTxj)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 x1, …, xn ∈ ℝk to minimize (1/(n(n−1)))∑ij(xiTxj)2.

Lower bound

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

For 1≤in, let Xi=xixiT be the rank-1 projector corresponding to the unit vector xi. Then, it holds that (xiTxj)2 = Tr(XiXj).

Let Y = ∑iXi. Then, it holds that ∑ijTr(XiXj) = ∑i,jTr(XiXj) − n = Tr(Y2) − n.

The Cauchy–Schwarz inequality implies that Tr(Y2) ≥ (Tr Y)2/k = n2/k, and therefore ∑ijTr(XiXj) = Tr(Y2) − nn2/kn. 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, daniello’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 daniello’s answer to the optimal 1/k2.
  • 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 v1, …, vn.
  • More generally than the last bullet point, if it is attainable with some choice of k and both n=n1 and n=n2, then it is also attainable for the same k and n=n1+n2. In particular, it is attainable if n=ak+b where a and b are integers satisfying ab≥0.

Although I have not checked details, it seems that any spherical 2-design 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 x1, …, xn ∈ ℂk to minimize (1/(n(n−1)))∑ij|xi*xj|2.

The lower bound above equally holds in this complex version. Consider the case where n=k2 in the complex version. Then the lower bound is equal to 1/(k+1).

So far, it was correct.

A set of k2 unit vectors x1, …, xk2 ∈ ℂk attaining the lower bound is called a SIC-POVM in dimension k,

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

$\endgroup$
5
$\begingroup$

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

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