Ich habe einige Verteilungen ausprobiert und fast alle haben eine Varianz von . Zum Beispiel sowohl die Verteilung, in der jede Koordinate jedes unabhängig und einheitlich aus als auch die Verteilung, in der jedes ist ein unabhängiger gleichförmiger Vektor auf der dimensionalen Einheitskugel mit einer Varianz von .
Ist die minimale Varianz unter allen Verteilungen?
Antworten:
Ich werde eine äquivalente, aber einfacher aussehende Formulierung des Problems präsentieren und eine Untergrenze von ( n / k - 1) / ( n - 1) zeigen.
Ich zeige auch einen Zusammenhang mit einem offenen Problem in der Quanteninformation.[Bearbeiten in Revision 3: In früheren Revisionen habe ich behauptet, dass eine genaue Charakterisierung der Fälle, in denen die unten gezeigte Untergrenze erreicht wird, wahrscheinlich schwierig ist, da eine analoge Frage im komplexen Fall ein offenes Problem über SIC-POVMs in enthält Quanteninformation. Diese Verbindung zu SIC-POVMs war jedoch falsch. Einzelheiten finden Sie im Abschnitt „Falsche Verbindung zu SIC-POVMs in Quanteninformationen“ weiter unten.]Äquivalente Formulierung
Zunächst ist, wie bereits in Daniellos Antwort erwähnt, zu beachten, dass 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 ]. Im Rest der Antwort vergessen wir also die Varianz und minimieren stattdessen max i ≠ j E [( x i T x j ) 2 ].
Als nächstes können wir die Einschränkung ignorieren, dass E [ x i T x j ] = 0 ist , sobald wir uns entschlossen haben, max i ≠ j E [( x i T x j ) 2 ] zu minimieren . Dies liegt daran, dass wir zufällig sind Einheitsvektoren x 1 ,…, x n , dann können wir jeden von ihnen unabhängig mit der Wahrscheinlichkeit 1/2 negieren, um E [ x i T x j ] = 0 zu erfüllen, ohne den Wert der Zielfunktion max i ≠ j E [( x i T x j) 2 ].
Darüber hinaus wird die Zielfunktion von max i ≠ j E [( x i T x j ) 2 ] auf (1 / ( n ( n - 1))) ∑ i ≠ j E [( x i T x j ) 2 ] geändert. ändert den optimalen Wert nicht. Letzteres ist höchstens Ersteres, weil der Durchschnitt höchstens das Maximum ist. Wir können jedoch immer die Werte von E [( x i T x j ) 2 ] für verschiedene Auswahlmöglichkeiten von ( i , j ) ( i ≠ machenj ) gleich durch zufälliges Permutieren der n Vektoren x 1 ,…, x n .
Für jedes n und k ist der optimale Wert des fraglichen Problems gleich dem Minimum von (1 / ( n ( n - 1))) ∑ i ≠ j E [( x i T x j ) 2 ] wobei x 1 ,…, x n sind Zufallsvariablen, die Einheitsvektoren in ℝ k als Werte annehmen .
Aufgrund der Linearität der Erwartung ist diese Zielfunktion jedoch gleich dem erwarteten Wert E [(1 / ( n ( n - 1))) ∑ i ≠ j ( x i T x j ) 2 ]. Da das Minimum höchstens der Durchschnitt ist, müssen Wahrscheinlichkeitsverteilungen nicht mehr berücksichtigt werden. Das heißt, der optimale Wert des obigen Problems ist gleich dem optimalen Wert des Folgenden:
Untergrenze
Mit dieser äquivalenten Formulierung werden wir beweisen, dass der optimale Wert mindestens ( n / k - 1) / ( n - 1) ist.
Für 1 ≤ i ≤ n sei X i = x i x i T der Rang-1-Projektor, der dem Einheitsvektor x i entspricht . Dann gilt ( x i T x j ) 2 = Tr ( X i X j ).
Sei Y = ∑ i X i . Dann gilt: ∑ i ≠ j Tr ( X i X j ) = ∑ i , j Tr ( X i X j ) - n = Tr ( Y 2 ) - n .
Die Cauchy-Schwarz-Ungleichung impliziert, dass Tr ( Y 2 ) ≥ (Tr Y ) 2 / k = n 2 / k und daher ∑ i ≠ j Tr ( X i X j ) = Tr ( Y 2 ) - n ≥ n 2 ist / k - n . Durch Teilen durch n ( n - 1) erhalten wir, dass der Zielwert mindestens ( n / k - 1) / ( n - 1) ist.
Insbesondere wenn n = k + 1 ist, liegt die Antwort von Daniello innerhalb eines Faktors von 2 vom optimalen Wert.
Wann ist diese Untergrenze erreichbar?
Erreichen diese untere Grenze ( n / k - 1) / ( n - 1) ist äquivalent zu machen Y = ( n / k ) I . Ich kenne die genaue Charakterisierung nicht, wann sie erreichbar ist, aber es gibt folgende ausreichende Bedingungen:
Obwohl ich keine Details überprüft habe, scheint es, dass jedes sphärische 2-Design eine Lösung bietet, die diese Untergrenze erreicht.
Falsche Verbindung zu SIC-POVMs in Quanteninformationen
In früheren Überarbeitungen habe ich Folgendes angegeben:
Aber diese Beziehung war falsch. Ich werde erklären warum.
Bisher war es richtig.
Dieser Teil war falsch. Ein SIC-POVM ist eine Menge von k 2 Einheitsvektoren x 1 ,…, x n ∈ ∈ k, für die | x i * x j | 2 = 1 / ( k + 1) für alle i ≠ j . Beachten Sie, dass hier die Anforderung für alle Paare i ≠ j gelten muss , nicht nur für den Durchschnitt aller Paare i ≠ j . Im Abschnitt „Äquivalente Formulierung“ haben wir die Äquivalenz zwischen der Minimierung des Maximums und der Minimierung des Durchschnitts gezeigt. Dies war jedoch möglich, weil x 1,…, X n waren Zufallsvariablen, die dort Einheitsvektoren nahmen. Hier sind x 1 ,…, x n nur Einheitsvektoren, daher können wir nicht denselben Trick anwenden.
quelle
Die schnelle und schmutzige Antwort auf die Frage lautet "Nein, die Varianz kann kleiner sein": Sei die Standardbasis und betrachte den folgenden zufälligen Prozess: Wähle ein Paar verschiedener Ganzzahlen i, j aus und setze . Für die anderen Vektoren (für ) weisen Sie sie eins zu eins zu. Dann behalte für jedes entweder wie es ist oder drehe es (auf ) mit der Wahrscheinlichkeit .v1,v2,…,vk {1,2,…,k+1} xi=xj=v1 xt t∉{i,j} v2,…,vk t∈{1,…,k+1} xi −xi 12
Es ist leicht zu erkennen, dass - entweder sind und orthogonal oder sie zeigen mit der Wahrscheinlichkeit in dieselbe / entgegengesetzte Richtung .x a x b 1E[xa⋅xb]=0 xa xb 12
Andererseits haben wir . Wir haben das genau dann, wenn , was mit der Wahrscheinlichkeit geschieht . Andernfalls . Wir haben also für jedes , : ( x a ≤ x b ) 2 = 1 { a , b } = { i , j }Var[xa⋅xb]=E[(xa⋅xb)2] (xa⋅xb)2=1 {a,b}={i,j} 1(k+12) (xa⋅xb)2=0 a b
Meine Intuition ist, dass dies so schlecht (klein) ist, wie es nur geht, aber ich habe keinen Beweis. Interessanter ist, dass diese Konstruktion für n >> k zusammenzubrechen scheint und auch dann, wenn die unabhängig voneinander ausgewählt werden müssen (möglicherweise aus verschiedenen Verteilungen).xi
quelle