Berapakah minimum dari semua distribusi vektor satuan dari varian produk titik vektor?

10

Saya mencoba menemukan distribusi di atas vektor acak, katakanlah , pada -satuan dimensi ruang (di mana ) yang meminimalkan \ max_ {i \ neq j} \ mathrm {Var} (x_i ^ T x_j) tunduk pada kendala \ mathbb {E} [x_i ^ Tx_j] = 0 .nx1,,xnkn>kE [ x T i x j ] = 0maxijVar(xiTxj)E[xiTxj]=0

Saya mencoba beberapa distribusi dan hampir semuanya memiliki varian 1/k . Misalnya, distribusi di mana setiap koordinat setiap xi dipilih secara independen dan seragam dari {1/k,1/k} dan distribusi di mana masing-masing xi adalah vektor seragam independen pada k -dimensional unit sphere memiliki varian 1/k .

Apakah 1/k varian minimum di antara semua distribusi?

peng
sumber
Seberapa ketat ikatan yang Anda minati? Artinya, apakah batas bawah 1 / 100k yang hanya berfungsi untuk n> 100k akan menarik atau tidak?
daniello
@aniello, maksud Anda batas bawah 1 / ck untuk n> ck di mana c adalah konstanta? Bagaimana cara membuktikannya?
peng
Sesuatu yang saya tidak mengerti dalam pertanyaan: pada awalnya Anda mengatakan distribusi atas vektor satuan , tetapi tidak semua distribusi yang Anda katakan Anda mencoba menghasilkan vektor satuan ... Apakah maksud Anda untuk semua , ? E [ | x i | ] = 1xiE[|xi|]=1
daniello
@deniello, saya bermaksud membuat semua vektor menjadi "unit" .. Maaf, saya lupa melakukan normalisasi pada vektor "Gaussian", setelah normalisasi, itu akan sama dengan vektor seragam. Terima kasih telah menunjukkan kesalahan ini.
peng

Jawaban:

8

Saya akan menyajikan rumusan masalah yang setara tetapi terlihat lebih sederhana, dan menunjukkan batas bawah ( n / k - 1) / ( n −1). Saya juga menunjukkan koneksi ke masalah terbuka dalam informasi kuantum. [Sunting dalam revisi 3: Dalam revisi sebelumnya, saya mengklaim bahwa karakterisasi yang tepat dari kasus-kasus di mana batas bawah yang ditunjukkan di bawah ini cenderung sulit karena pertanyaan analog dalam kasus kompleks mencakup masalah terbuka tentang SIC-POVMs di informasi kuantum. Namun, koneksi ke SIC-POVM ini salah. Untuk detailnya, lihat bagian “Koneksi yang salah ke SIC-POVMs dalam informasi kuantum” di bawah ini.]

Formulasi yang setara

Pertama, seperti yang telah ditunjukkan dalam jawaban daniello, perhatikan bahwa 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 ]. Jadi dalam sisa jawabannya, kita lupa tentang varians dan bukannya meminimalkan max ij E [( x i T x j ) 2 ].

Selanjutnya, begitu kita memutuskan tujuan kita adalah untuk meminimalkan maks ij E [( x i T x j ) 2 ], kita dapat mengabaikan batasan bahwa E [ x i T x j ] = 0. Ini karena jika kita memiliki random vektor satuan x 1 , ..., x n , maka kita dapat meniadakan masing-masing secara independen dengan probabilitas 1/2 untuk memenuhi E [ x i T x j ] = 0 tanpa mengubah nilai fungsi tujuan max ij E [( x i T x j) 2 ].

Selain itu, mengubah fungsi tujuan dari maks ij E [( x i T x j ) 2 ] ke (1 / ( n ( n −1))))) ij E [( x i T x j ) 2 ] tidak mengubah nilai optimal. Yang terakhir paling banyak yang pertama karena rata-rata paling banyak maksimum. Namun, kita selalu dapat membuat nilai E [( x i T x j ) 2 ] untuk berbagai pilihan ( i , j ) ( ij ) sama dengan mengubah n vektor x 1 , ..., x n secara acak.

Jadi untuk setiap n dan k , nilai optimal dari masalah yang dimaksud adalah sama dengan minimum (1 / ( n ( n −1)))) i ij E [( x i T x j ) 2 ] di mana x 1 ,…, x n adalah variabel acak yang menggunakan vektor satuan dalam ℝ k sebagai nilai.

Namun, dengan linearitas harapan, fungsi objektif ini sama dengan nilai yang diharapkan E [(1 / ( n ( n n1 ))))) ij ( x i T x j ) 2 ]. Karena minimum adalah paling banyak rata-rata, tidak perlu lagi mempertimbangkan distribusi probabilitas. Artinya, nilai optimal masalah di atas sama dengan nilai optimal berikut ini:

Pilih vektor satuan x 1 ,…, x n ∈ ℝ k untuk meminimalkan (1 / ( n ( n −1)))) ∑ ij ( x i T x j ) 2 .

Batas bawah

Dengan menggunakan formulasi yang setara ini, kami akan membuktikan bahwa nilai optimal setidaknya ( n / k - 1) / ( n −1).

Untuk 1≤ in , misalkan X i = x i x i T menjadi proyektor peringkat-1 yang sesuai dengan vektor satuan x i . Kemudian, ia berpendapat bahwa ( x i T x j ) 2 = Tr ( X i X j ).

Biarkan Y = i X i . Kemudian, ia menyatakan bahwa i ij Tr ( X i X j ) = i i , j Tr ( X i X j ) - n = Tr ( Y 2 ) - n .

Ketidaksamaan Cauchy-Schwarz menyiratkan bahwa Tr ( Y 2 ) ≥ (Tr Y ) 2 / k = n 2 / k , dan karenanya ij Tr ( X i X j ) = Tr ( Y 2 ) - nn 2 / k - n . Dengan membaginya dengan n ( n −1), kita memperoleh bahwa nilai obyektif setidaknya ( n / k - 1) / ( n )1).

Khususnya, ketika n = k +1, jawaban daniello berada dalam faktor 2 dari nilai optimal.

Kapan batas bawah ini dapat dicapai?

Mencapai ini terikat lebih rendah ( n / k - 1) / ( n -1) adalah setara dengan membuat Y = ( n / k ) saya . Saya tidak tahu karakterisasi pasti ketika itu dapat dicapai, tetapi mengikuti kondisi yang cukup ada:

  • Ketika n = k +1, itu dapat dicapai dengan mempertimbangkan k +1 unit vektor yang membentuk k -simplex biasa yang berpusat pada titik asal, meningkat dari 2 / ( k ( k +1)) dalam jawaban daniello ke optimal 1 / k 2 .
  • Ketika n adalah kelipatan k , itu jelas dapat dicapai dengan memperbaiki basis ortonormal dari ℝ k dan menetapkan masing-masing vektor basis ke n / k dari v 1 ,…, v n .
  • Lebih umum daripada titik peluru terakhir, jika dapat dicapai dengan beberapa pilihan k dan keduanya n = n 1 dan n = n 2 , maka juga dapat dicapai untuk k yang sama dan n = n 1 + n 2 . Secara khusus, itu dicapai jika n = a k + b di mana a dan b adalah bilangan bulat memuaskan ab ≥0.

Meskipun saya belum memeriksa detail, tampaknya setiap desain 2 bola memberikan solusi untuk mencapai batas bawah ini.

Koneksi yang salah ke SIC-POVMs dalam informasi kuantum

Dalam revisi sebelumnya, saya menyatakan:

Saya menduga bahwa menjawab ini sepenuhnya adalah pertanyaan yang sulit. Alasannya adalah bahwa jika kita sebaliknya mempertimbangkan ruang vektor kompleks ℂ k , pertanyaan ini terkait dengan masalah terbuka dalam informasi kuantum.

Tetapi hubungan ini tidak benar. Saya akan menjelaskan alasannya.

Lebih tepatnya, pertimbangkan masalah berikut:

Pilih vektor satuan x 1 ,…, x n ∈ ℂ k untuk meminimalkan (1 / ( n ( n −1)))) ¢ ij | x i * x j | 2 .

Batas bawah di atas sama-sama berlaku dalam versi kompleks ini. Pertimbangkan kasus di mana n = k 2 dalam versi kompleks. Maka batas bawah sama dengan 1 / ( k +1).

Sejauh ini benar.

Satu set k 2 unit vektor x 1 ,…, x k 2 ∈ ℂ k yang mencapai batas bawah disebut SIC-POVM dalam dimensi k ,

Bagian ini salah. SIC-POVM adalah seperangkat k 2 vektor unit x 1 ,…, x n ∈ ℂ k yang | x i * x j | 2 = 1 / ( k +1) untuk semua ij . Perhatikan bahwa di sini persyaratan harus berlaku untuk semua pasangan ij , bukan hanya rata-rata untuk semua pasangan ij . Di bagian "Rumusan ekivalen", kami menunjukkan kesetaraan antara meminimalkan maksimum dan meminimalkan rata-rata, tetapi ini dimungkinkan karena x 1,…, X n adalah variabel acak yang mengambil vektor satuan di sana. Di sini x 1 , ..., x n hanyalah vektor satuan, jadi kita tidak dapat menggunakan trik yang sama.

Tsuyoshi Ito
sumber
5

Jawaban cepat dan kotor untuk pertanyaan adalah "tidak, bisa lebih kecil": Biarkan menjadi basis standar, dan pertimbangkan proses acak berikut: pilih sepasang bilangan bulat yang berbeda i, j dari , dan set . Untuk vektor lainnya (untuk ) tetapkan untuk dengan cara satu-ke-satu. Kemudian, untuk setiap , jaga apa adanya atau balikkan (ke ) dengan probabilitas .v1,v2,,vk{1,2,,k+1}xi=xj=v1xtt{i,j}v2,,vkt{1,,k+1}xixi12

Mudah untuk melihat bahwa - baik dan adalah ortogonal atau mereka menunjuk ke arah yang sama / berlawanan dengan probabilitas masing-masing.x a x b 1E[xaxb]=0xaxb12

Di sisi lain kita memiliki . Kami memilikinya jika dan hanya jika yang terjadi dengan probabilitas . Kalau tidak . Jadi kita memiliki itu untuk setiap , : ( x ax b ) 2 = 1 { a , b } = { i , j }Var[xaxb]=E[(xaxb)2](xaxb)2=1{a,b}={i,j} (xaxb)2=0ab1(k+12)(xaxb)2=0ab

Var[xaxb]=E[(xaxb)2]=1(k+12)

Intuisi saya adalah bahwa ini seburuk (kecil) karena mendapat tetapi saya tidak punya bukti. Lebih menarik adalah bahwa konstruksi ini tampaknya rusak untuk n >> k, dan juga ketika harus dipilih secara independen (mungkin dari distribusi yang berbeda).xi

daniello
sumber