Каков минимум по всем распределениям единичных векторов дисперсии точечного произведения векторов?

Я пытаюсь найти распределение по $n$ случайным векторам, скажем, $x_1,\ldots, x_n$ , на $k$ мерной единичной сфере (где $n > k$ ), которое минимизирует $\max_{i\neq j} \mathrm{Var}(x_i^T x_j)$ при условии ограничения $\mathbb{E}[x_i^Tx_j]=0$ .

Я попробовал некоторые дистрибутивы, и почти все они имеют дисперсию $1/k$ . Например, как распределение, в котором каждая координата каждого $x_i$ независимо и равномерно выбирается из $\left\{-1/\sqrt{k}, 1/\sqrt{k}\right\}$и распределение, в котором каждый$x_i$является независимым равномерным вектором на$k$мерной единичной сфере, имеют дисперсию$1/k$.

Является ли $1/k$ минимальной дисперсией среди всех распределений?

Я представлю эквивалентную, но более простую на вид формулировку проблемы и покажу нижнюю границу ( n / k - 1) / ( n − 1). Я также показываю связь с открытой проблемой в квантовой информации. [Изменить в редакции 3: В более ранних редакциях я утверждал, что точная характеристика случаев, в которых достигается нижняя граница, показанная ниже, вероятно, будет трудной, поскольку аналогичный вопрос в сложном случае включает открытую проблему о SIC-POVM в квантовая информация. Однако эта связь с SIC-POVM была неправильной. Подробности см. В разделе «Неправильное подключение к SIC-POVM в квантовой информации» ниже.]

Эквивалентная формулировка

Во-первых, как уже указывалось в ответе Даниелло, обратите внимание, что Var ( x _i ^T x _j ) = E [( x _i ^T x _j ) ² ] - E [ x _i ^T x _j ] ² = E [( x _i ^T х _J ) ² ]. Таким образом, в оставшейся части ответа мы забываем о дисперсии и вместо этого минимизируем max _{i ≠ j} E [( x _i ^T x _j ) ² ].

Далее, как только мы решим, что наша цель - минимизировать max _{i ≠ j} E [( x _i ^T x _j ) ² ], мы можем игнорировать ограничение, что E [ x _i ^T x _j ] = 0. Это потому, что если мы имеем случайный единичные векторы x ₁ ,…, x _n , тогда мы можем отрицать каждый из них независимо с вероятностью 1/2 для удовлетворения E [ x _i ^T x _j ] = 0 без изменения значения целевой функции max _{i ≠ j} E [( x _i ^T x _j) ² ].

Кроме того, изменение целевой функции с max _{i ≠ j} E [( x _i ^T x _j ) ² ] на (1 / ( n ( n − 1))) ∑ _{i ≠ j} E [( x _i ^T x _j ) ² ] не меняет оптимальное значение. Последнее самое большее первое, потому что среднее значение самое большее максимальное. Однако мы всегда можем сделать значения E [( x _i ^T x _j ) ² ] для различных вариантов ( i , j ) ( i ≠j ) равен, переставляя n векторов x ₁ ,…, x _n случайным образом.

Таким образом, для любых n и k оптимальное значение рассматриваемой задачи равно минимуму (1 / ( n ( n − 1))) ∑ _{i ≠ j} E [( x _i ^T x _j ) ² ], где x ₁ ,…, x _n - случайные величины, которые принимают единичные векторы в ℝ ^{k в} качестве значений.

Однако по линейности ожидания эта целевая функция равна ожидаемому значению E [(1 / ( n ( n − 1))) ∑ _{i ≠ j} ( x _i ^T x _j ) ² ]. Поскольку минимум является максимумом среднего значения, нет необходимости больше рассматривать распределение вероятностей. То есть оптимальное значение вышеуказанной задачи равно оптимальному значению следующего:

Выберите единичные векторы x ₁ ,…, x _n ∈ ℝ ^k, чтобы минимизировать (1 / ( n ( n − 1))) ∑ _{i ≠ j} ( x _i ^T x _j ) ² .

Нижняя граница

Используя эту эквивалентную формулировку, мы докажем, что оптимальное значение не менее ( n / k - 1) / ( n − 1).

Для 1≤ i ≤ n пусть X _i = x _i x _i ^T будет проектором ранга 1, соответствующим единичному вектору x _i . Тогда имеет место, что ( x _i ^T x _j ) ² = Tr ( X _i X _j ).

Пусть Y = ∑ _i X _i . Тогда оно гласит, что ∑ _{i ≠ j} Tr ( X _i X _j ) = ∑ _{i , j} Tr ( X _i X _j ) - n = Tr ( Y ² ) - n .

Из неравенства Коши – Шварца следует, что Tr ( Y ² ) ≥ (Tr Y ) ² / k = n ² / k и, следовательно, ∑ _{i ≠ j} Tr ( X _i X _j ) = Tr ( Y ² ) - n ≥ n ² / к - н . Делив на n ( n − 1), мы получаем, что целевое значение не меньше ( n / k - 1) / ( n − 1).

В частности, когда n = k + 1, ответ Даниелло находится в пределах 2 от оптимального значения.

Когда эта нижняя граница достижима?

Достигнув этот нижнюю грань ( п / K - 1) / ( п -1) эквивалентно делая Y = ( п / к ) Я . Я не знаю точную характеристику, когда она достижима, но существуют следующие достаточные условия:

• Когда n = k +1, это достижимо, рассматривая k +1 единичных векторов, которые формируют регулярный k- симплекс с центром в начале координат, улучшаясь от 2 / ( k ( k +1)) в ответе Даниелло к оптимальному 1 / k ² .
• Когда n кратно k , это очевидно достижимо путем фиксации ортонормированного базиса ℝ ^k и присвоения каждого из базисных векторов n / k из v ₁ ,…, v _n .
• В более общем смысле, чем последняя точка, если она достижима при некотором выборе k и при n = n ₁ и n = n ₂ , то она также достижима для тех же k и n = n ₁ + n ₂ . В частности, это достижимо, если n = a k + b, где a и b целые числа, удовлетворяющие a ≥ b ≥0.

Хотя я не проверял детали, кажется, что любой сферический 2-дизайн дает решение, достигающее этой нижней границы.

Неверное подключение к SIC-POVM в квантовой информации

В предыдущих редакциях я заявлял:

Я подозреваю, что полностью ответить на этот вопрос сложно. Причина в том, что если вместо этого мы рассмотрим комплексное векторное пространство ℂ ^k , то этот вопрос будет связан с открытой проблемой в квантовой информации.

Но это отношение было неверным. Я объясню почему.

Точнее рассмотрим следующую проблему:

Выберите единичные векторы x ₁ ,…, x _n ∈ ℂ ^k, чтобы минимизировать (1 / ( n ( n − 1))) ∑ _{i ≠ j} | x _i ^* x _j | ² .

Нижняя граница выше в равной степени справедлива в этой сложной версии. Рассмотрим случай, когда n = k ² в комплексной версии. Тогда нижняя граница равна 1 / ( k +1).

Пока это было правильно.

Набор из k ² единичных векторов x ₁ ,…, x _{k ²} ∈ ∈ ^k, достигающих нижней границы, называется SIC-POVM в размерности k ,

Эта часть была неверной. SIC-POVM - это набор из k ² единичных векторов x ₁ ,…, x _n ∈ ℂ ^k, для которых | x _i ^* x _j | ² = 1 / ( k +1) для всех i ≠ j . Обратите внимание, что здесь требование должно выполняться для всех пар i ≠ j , а не только для среднего значения по всем парам i ≠ j . В разделе «Эквивалентная формулировка» мы показали эквивалентность между минимизацией максимума и минимизацией среднего, но это было возможно, потому что x ₁,…, X _n были случайными величинами, берущими там единичные векторы. Здесь x ₁ ,…, x _n - просто единичные векторы, поэтому мы не можем использовать один и тот же прием.

$v_1, v_2, \ldots, v_k$$\{1,2,\ldots,k+1\}$$x_i = x_j = v_1$$x_t$$t \notin \{i,j\}$$v_2, \ldots, v_k$$t \in \{1,\ldots,k+1\}$$x_i$$-x_i$$\frac{1}{2}$

$E[x_a \cdot x_b] = 0$$x_a$$x_b$$\frac{1}{2}$

$Var[x_a \cdot x_b] = E[(x_a \cdot x_b)^2]$$(x_a \cdot x_b)^2 = 1$$\{a,b\} = \{i,j\}$$\frac{1}{k+1 \choose 2}$$(x_a \cdot x_b)^2 = 0$$a$$b$

$x_i$