代数的組合せ最適化 part II 作用素スケーリングとCapacity 導入：行列スケーリングによるパーマネントの近似計算

Presentation on theme: "代数的組合せ最適化 part II 作用素スケーリングとCapacity 導入：行列スケーリングによるパーマネントの近似計算"— Presentation transcript:

1 代数的組合せ最適化 part II 作用素スケーリングとCapacity 導入：行列スケーリングによるパーマネントの近似計算
さらなる発展 Part IIでは， 𝐴= 𝑖=1 𝑘 𝐴 𝑖 𝑥 𝑖 , 𝐴 𝑖 :ℂ上𝑛×𝑛行列，の nc-正則性判定 を扱う． nc−rank 𝐴 = 𝑛かどうか

2 行列スケーリング 𝐵=( 𝑏 𝑖𝑗 ):𝑛×𝑛 非負行列，ゼロ列，ゼロ行なし 行スケーリング 𝐵←R 𝐵 ∙𝐵 列スケーリング
Sinkhorn 1964 𝐵=( 𝑏 𝑖𝑗 ):𝑛×𝑛 非負行列，ゼロ列，ゼロ行なし R 𝐵 ≔ 𝑗 𝑏 1𝑗 − 𝑗 𝑏 2𝑗 − ⋱ 𝑗 𝑏 𝑛𝑗 −1 行スケーリング 𝐵←R 𝐵 ∙𝐵 C 𝐵 ≔ 𝑖 𝑏 𝑖1 − 𝑖 𝑏 𝑖2 − ⋱ 𝑖 𝑏 𝑖𝑛 −1 列スケーリング 𝐵←𝐵∙C 𝐵 Question: 行スケーリングと列スケーリングを交互に 　　　　繰り返すことで，𝐵は２重確率行列に収束するか？

3 行列スケーリング 𝐵←R 𝐵 ∙𝐵, 𝐵←𝐵∙C 𝐵 ; repeat
Thm (Linial, Samorodnitsky, Wigderson 2000) 行列スケーリングで， 𝐵が２重確率行列に収束 ⇔ 𝐺 𝐵 に完全マッチングが存在 ここで, 𝐺 𝐵 ≔ 𝑛 , 𝑛 ;𝐸 , 𝑖𝑗 ∈𝐸⇔ 𝑏 𝑖𝑗 >0 注： ２重確率行列に「なる」わけではない，いくらでも近づくという意味 行列スケーリングで完全マッチングの存在が判定できる！？ （多項式時間で）出来る（Linial,Samorodnitsky, Wigderson 2000）

4 パーマネントの計算 #P完全 (Valiant 1979) FPRAS (Jerrum, Sinclair, Vigoda 2004)
ここでは， Linial, Samorodnitsky, Wigderson 2000の 行列スケーリングによる(決定的) 𝑒 𝑛 近似アルゴリズム の背景にある考え方を紹介する． それが，作用素スケーリングによる nc-正則性判定（Gurvits 2004, Garg et al. 2015）につながる．

5 パーマネント（permanent） 𝐵=( 𝑏 𝑖𝑗 ):𝑛×𝑛 非負行列，ゼロ列，ゼロ行なし
det 𝐵から符号を除いたもの Perm 𝐵≔ 𝜎 𝑖=1 𝑛 𝑏 𝑖𝜎(𝑖) パーマネント Obs. Perm 𝐵>0 ⇔ 𝐺 𝐵 に完全マッチングが存在 Obs. 𝐺= 𝑈,𝑉;𝐸 , 𝑈 = 𝑉 =𝑛 𝐵= 𝑏 𝑖𝑗 , 𝑏 𝑖𝑗 ≔ if 𝑖𝑗∈𝐸 0 otherwise  Perm 𝐵=| 𝐺の完全マッチング |

6 Capacity 𝐵=( 𝑏 𝑖𝑗 ):𝑛×𝑛 非負行列，ゼロ列，ゼロ行なし
古典的 Capacity Gurvits 2008 𝐵=( 𝑏 𝑖𝑗 ):𝑛×𝑛 非負行列，ゼロ列，ゼロ行なし 𝑝 𝐵 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑛 ≔ 𝑖=1 𝑛 𝐵𝑥 𝑖 = 𝑖=1 𝑛 𝑗=1 𝑛 𝑏 𝑖𝑗 𝑥 𝑗 Obs. 𝑝 𝐵 = (Perm 𝐵) 𝑥 1 𝑥 2 ⋯ 𝑥 𝑛 + (その他の項) Def (Capacity) Cap 𝐵 ≔ inf 𝑝 𝐵 ( 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑛 ) 𝑥 1 𝑥 2 ⋯ 𝑥 𝑛 | 𝑥 1 >0, 𝑥 2 >0,…, 𝑥 𝑛 >0 Obs. Cap 𝐵 ≥Perm 𝐵

7 Thm (一般化van der Waerden不等式; Gurvits 2008) Perm 𝐵≥ 𝑛! 𝑛 𝑛 Cap 𝐵
≈ 𝑒 −𝑛  Perm 𝐵≤Cap 𝐵 ≤ 𝑒 𝑛 Perm 𝐵 Cor: Cap 𝐵 は Perm 𝐵の 𝑒 𝑛 近似 Cap 𝐵 > 0⇔ Perm 𝐵>0⇔ 𝐺 𝐵 に完全マッチングあり 数え上げ問題（Perm 𝐵）が近似的に最適化問題（Cap 𝐵 ）になった！ Cap 𝐵 := inf 𝑖=1 𝑛 𝐵𝑥 𝑖 𝑥 1 𝑥 2 ⋯ 𝑥 𝑛 s.t. 𝑥 1 >0, 𝑥 2 >0,…, 𝑥 𝑛 >0.

8 行列スケーリングは Capの最小化アルゴリズムとみなせる
s.t. 𝑦 1 𝑦 2 ⋯ 𝑦 𝑛 = 𝑥 1 𝑥 2 ⋯ 𝑥 𝑛 =1, Def (対称Capacity) inf. 𝑦 𝑇 𝐵𝑥 𝑦 1 , 𝑦 2 ,… 𝑦 𝑛 , 𝑥 1 ,…, 𝑥 𝑛 >0. Ca p sym 𝐵 ≔ Lem: Ca p sym 𝐵 =𝑛 𝑛 Cap 𝐵 =𝑛 inf 𝑥 𝑛 𝑖 𝐵𝑥 𝑖 =𝑛 𝑛 Cap 𝐵 ∵Ca p sym 𝐵 = inf 𝑥 inf 𝑦 𝑦 𝑇 𝐵𝑥 𝑦に関する 　凸計画 𝑦 ∗ = 𝑛 𝑖 𝐵𝑥 𝑖 𝐵𝑥 1 −1 𝐵𝑥 2 −1 ⋮ 𝐵𝑥 𝑛 −1

9 Ca p sym 𝐵 = inf 𝑥,𝑦 𝑦 𝑇 𝐵𝑥 に対する交互最適化
𝑥,𝑦 =(𝟏,𝟏) 𝑦を固定して𝑥で最適化 𝑥を固定して𝑦で最適化  𝑥= −𝑛 det C(𝐵) C(𝐵) 𝟏 𝑥=𝟏となるように𝐵を規格化: 𝐵← −𝑛 det C(𝐵) 𝐵∙C(𝐵) repeat  𝑦= −𝑛 det R(𝐵) R 𝐵 𝟏 𝑦=𝟏となるように𝐵を規格化: 𝐵← −𝑛 det R(𝐵) R 𝐵 ∙𝐵 ～ 𝐵に対する行列スケーリング

10 行列スケーリングによる完全マッチングの存在判定
Linial,Samorodnitsky, Wigderson 2000 ds 𝐵 ≔ 𝐴 𝑇 𝟏−𝟏 𝐴𝟏−𝟏 2 --- 2重確率行列への近さ ds 𝐵 < 1 𝑛 ⇒ Cap 𝐵>0 完全マッチング存在 行（列）スケーリングするとCap 𝐵≤1 初回以降のスケーリングで，Cap 𝐵 非減少 ds 𝐵 >𝜀⇒ Cap 𝐵 は(1+Ω 𝜀 )倍される． 𝐵:整数，完マ存在⇒ Cap 𝐵≥ 𝑛 −𝑛 (exp. lower bound) ※ CapはPermに置き換えてもよい 完マッチング存在なら，poly(size 𝐵 ,𝑛)反復後にds 𝐵 < 1 𝑛 ∴ 1+Ω 𝜀 𝑁 Cap 𝐵≤1より

11 行列スケーリングから作用素スケーリングへ
Obs. 𝐵が非負行列 ⇔𝐵𝑧 ≥0 (∀𝑧≥0) Def. 正値作用素𝑇: ℂ 𝑛×𝑛 → ℂ 𝑛×𝑛 ⇔ 𝑇 𝑋 ≽0 (∀𝑋≽0) --- 非負行列の一般化 半正定値 Def. 完全正値作用素𝑇: ℂ 𝑛×𝑛 → ℂ 𝑛×𝑛 ⇔∃ 𝐴 1 , 𝐴 2 ,…, 𝐴 𝑘 : 𝑇 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † 複素共役 Gurvits 2004: 𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 ⟷ 𝑇 𝐴 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † 行列スケーリングとCapacityを完全正値作用素へ拡張

12 Edmonds問題（正則性判定）に対するGurvitz 2004のアプローチ
𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 ⟶ 𝑇 𝐴 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † 量子パーマネントQPermを定義 　→QPerm 𝑇 𝐴 =多項式 det 𝑖 𝐴 𝑖 𝑥 𝑖 の係数ベクトルのノルム 　→QPerm 𝑇 𝐴 >0⇔𝐴:正則 Capacity Cap 𝑇 𝐴 ≔ inf det 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † det 𝑋 𝑋≻0 作用素スケーリング（～ Cap 𝑇 𝐴 の最小化） ⟷ ? QPerm 𝑇 𝐴 >0 𝐴:正則 ↔ ⟶ ↚ Cap ( 𝑇 𝐴 )>0 ⟷ 𝐴:nc-正則 Garg et al. 2015

13 Rank nondecreasing 性 𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝑇 𝐴 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 †
Gurvits 2004 𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝑇 𝐴 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † Def 𝑇 𝐴 : rank nondecreasing ⇔rank 𝑇 𝐴 𝑋 ≥rank 𝑋 ∀𝑋≽0 Lem (本質的にGurvits 2004) 𝑇 𝐴 : rank nondecreasing ⇔𝐴: nc-正則

14 Lemの証明 ∗ ∗ ∗ 𝐴:nc-非正則 𝐴 𝑖 ~ ⇔ dim 𝐴 𝑖 𝑈< dim 𝑈 (∀𝑖) ⇔ 𝑠 𝑆 𝐴 𝑖 𝑈=
∃ 𝑈 𝐴 𝑖 𝑈 𝐴:nc-非正則 𝐴 𝑖 ~ ⇔ dim 𝐴 𝑖 𝑈< dim 𝑈 (∀𝑖) ⇔ 𝑟 𝑟+𝑠>𝑛 𝑠 < dim 𝑈 𝑆 𝐴 𝑖 𝑈= 正則 𝑆 𝑇 𝐴 𝑈 𝑈 † 𝑆 † = 𝑖 𝑆 𝐴 𝑖 𝑈 𝑈 † 𝐴 𝑖 † 𝑆 † = ∗ ⇒rank 𝑇 𝐴 𝑈 𝑈 † < dim 𝑈=rank 𝑈 𝑈 † ⇒ 𝑆 𝑇 𝐴 𝑋 𝑆 † = 𝑖 𝑆 𝐴 𝑖 𝑋 𝐴 𝑖 † 𝑆 † = 逆にrank 𝑇 𝐴 𝑋 <rank 𝑋 なら ∗ <rank 𝑋 (∀𝑖) 𝑆 𝐴 𝑖 𝑋 𝐴 𝑖 † 𝑆 † = ∗ ⇔ 半正定値性 𝑆 𝐴 𝑖 𝑈= ⇒

15 2重確率作用素 𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝑇 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † Def. 𝑇 ∗ 𝑋 ≔ 𝑖 𝐴 𝑖 † 𝑋 𝐴 𝑖
𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝑇 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † Def. 𝑇 ∗ 𝑋 ≔ 𝑖 𝐴 𝑖 † 𝑋 𝐴 𝑖 Def. 𝑇が２重確率 ⇔𝑇 𝐼 =𝐼, 𝑇 ∗ 𝐼 =𝐼 Lem (Gurvits 2004) 𝑇 𝐼 =𝐼, 𝑇 ∗ 𝐼 −𝐼 2 < 1 𝑛 ⟹ 𝑇: rank nondecreasing (⇔ nc-正則)

16 𝑋≽0, 𝑋= 𝑈 𝑉 𝜆 1 ⋱ 𝜆 𝑟 𝑂 𝑈 𝑉 † , 𝑈 𝑉 𝑈 𝑉 † =𝐼 Lemの証明
𝑋≽0, 𝑋= 𝑈 𝑉 𝜆 ⋱ 𝜆 𝑟 𝑂 𝑈 𝑉 † , 𝑈 𝑉 𝑈 𝑉 † =𝐼 Lemの証明 rank 𝑇 𝐴 𝑋 =rank 𝑖 𝜆 𝑖 𝐴 𝑖 𝑈 𝑈 † 𝐴 𝑖 † 半正定値 𝑖 𝑄 𝑖 𝑥=0⇔ 𝑖 𝑥 𝑇 𝑄 𝑖 𝑥=0 ⇔ ∀𝑖 𝑄 𝑖 𝑥=0 =rank 𝑖 𝐴 𝑖 𝑈 𝑈 † 𝐴 𝑖 † =rank 𝑇 𝐴 (𝑈 𝑈 † ) 𝑇 𝑈 𝑈 † ≼𝑇 𝑈 𝑈 † +𝑇 𝑉𝑉 † =𝑇 𝐼 =𝐼 ≥ tr 𝑇 𝐴 (𝑈 𝑈 † ) = 𝑖 tr 𝐴 𝑖 𝑈 𝑈 † 𝐴 𝑖 † = 𝑖 tr 𝐴 𝑖 † 𝐴 𝑖 𝑈 𝑈 † = tr 𝑇 𝐴 ∗ 𝐼 𝑈 𝑈 † 𝑇 ∗ 𝐼 =𝐼+Δ =𝑟+ Δ,𝑈 𝑈 † Cauchy-Schwarz >𝑟− 𝑟 𝑛 ≥𝑟− Δ 𝑈 𝑈 †

17 作用素スケーリング 𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝑇 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † , 𝑇 ∗ 𝑋 ≔ 𝑖 𝐴 𝑖 † 𝑋 𝐴 𝑖
𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝑇 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † , 𝑇 ∗ 𝑋 ≔ 𝑖 𝐴 𝑖 † 𝑋 𝐴 𝑖 行スケーリング R 𝑇 𝑋 ≔𝑇 𝐼 − 1 2 𝑇(𝑋)𝑇 𝐼 − 1 2 列スケーリング C 𝑇 𝑋 ≔𝑇 𝑇 ∗ 𝐼 −1/2 𝑋 𝑇 ∗ 𝐼 −1/2 Obs. R 𝑇 𝐼 =C 𝑇 ∗ 𝐼 =𝐼 ∵C 𝑇 ∗ 𝑋 = 𝑖 𝑇 𝐼 − 1 2 𝐴 𝑖 𝑋 𝐴 𝑖 † 𝑇 𝐼 − 1 2 作用素スケーリング ⟺ 𝐴 𝑖 ← 𝑇 ∗ 𝐼 −1/2 𝐴 𝑖 𝑇←R 𝑇 𝑇←C 𝑇 repeat ⟺ 𝐴 𝑖 ← 𝐴 𝑖 𝑇 ∗ 𝐼 −1/2

18 作用素スケーリングはCapを最小化している
Def (Capacity) Cap 𝑇 𝐴 ≔ inf det 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † det 𝑋 𝑋≻0 Def (対称capacity) Ca p sym 𝑇 𝐴 ≔ inf tr 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † 𝑌 det 𝑋= det 𝑌=1, 𝑋,𝑌≻0 Lem: Ca p sym 𝑇 𝐴 =𝑛 𝑛 Cap 𝑇 𝐴 Rem: 作用素スケーリング～Ca p sym に対する交互最適化

19 作用素スケーリングによるnc-正則性判定
Garg,Gurvits, Oliveira, Wigderson 2015 𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝑇 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † , 𝑇 ∗ 𝑋 ≔ 𝑖 𝐴 𝑖 † 𝑋 𝐴 𝑖 ds 𝑇 ≔ 𝑇 𝐼 −𝐼 𝑇 ∗ 𝐼 −𝐼 2 --- 2重確率作用素への近さ ds 𝑇 < 1 𝑛 ⇒ 𝐴:rank nondecreasing (nc-正則) 行（列）スケーリングするとCap(𝑇)≤1 初回以降のスケーリングで，Cap 𝑇 非減少 ds 𝑇 ≥𝜀⇒ Cap 𝑇 は(1+Ω 𝜀 )倍される． 𝐴 𝑖 :整数, 𝐴:nc-正則⇒ Cap 𝑇≥ (exp. lower bound) ?

20 Thm (Garg, Gurvits, Oliveira, Wigderson 2015)
𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝐴 𝑖 ∈ ℤ 𝑛×𝑛 , 𝐴:nc-正則 ⟹ Cap 𝑇 𝐴 ≥ 1 𝑛 2𝑛  作用素スケーリングでpoly(size(𝐴),𝑛)反復後にds 𝑇 < 1 𝑛

21 𝐴:nc-正則 ⇒ ∃𝑑,∃ 𝐷 𝑖 ∈ 𝕂 𝑑×𝑑 ,det( 𝑖 𝐷 𝑖 𝐴 𝑖 )≠0
Thmの証明 𝐴:nc-正則 ⇒ ∃𝑑,∃ 𝐷 𝑖 ∈ 𝕂 𝑑×𝑑 ,det( 𝑖 𝐷 𝑖 𝐴 𝑖 )≠0 ∀𝑋≽0, det 𝑋 =1, 𝐶 𝑖 ≔ 𝑇 𝐴 𝑋 − 𝐴 𝑖 𝑋 → 𝑖 𝐶 𝑖 𝐶 𝑖 † =𝐼 det 𝑖 𝐷 𝑖 𝐶 𝑖 = det 𝑖 𝐷 𝑖 𝐴 𝑖 det 𝑇 𝐴 𝑋 −𝑑 2 det 𝑋 𝑑 2 ≥ det 𝑇 𝐴 𝑋 −𝑑 2 Cap( 𝑇 𝐴 )≥ det 𝑇 𝐴 𝑋 ≥ det ( 𝑖 𝐷 𝑖 𝐶 𝑖 )( 𝑖 𝐷 𝑖 𝐶 𝑖 ) † −1 𝑑 ≥ 𝑛𝑑 tr( 𝑖 𝐷 𝑖 𝐶 𝑖 )( 𝑖 𝐷 𝑖 𝐶 𝑖 ) † 𝑛 固有値に関する 相加相乗平均 　≥ 𝑛𝑑 𝑖 𝐷 𝑖 2 𝑖 𝐶 𝑖 𝑛 = 𝑑 𝑖 𝐷 𝑖 𝑛 Cauchy-Schwarz

22 いま示したこと: 𝐷 𝑖 ∈ 𝕂 𝑑×𝑑 ,det( 𝑖 𝐷 𝑖 𝐴 𝑖 )≠0 ⇒ Cap( 𝑇 𝐴 )≥ 𝑑 𝑖 𝐷 𝑖 𝑛 実は， 𝑖 𝐷 𝑖 2 ≤ 𝑛 2 𝑑となる 𝐷 𝑖 ∈ ℤ 𝑑×𝑑 が選べる Alon’s Combinatorial Nullstellensatz (Alon 1999) 𝑝∈ℂ[ 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑁 ]: 次数ℎ, 各 𝑥 𝑖 の次数≤ ℎ 𝑖 →∃ 𝑎 1 , 𝑎 2 ,…, 𝑎 𝑁 ∈ ℤ + 𝑁 : 𝑖 𝑎 𝑖 ≤ℎ, 𝑎 𝑖 ≤ ℎ 𝑖 , 𝑝( 𝑎 1 , 𝑎 2 ,…, 𝑎 𝑁 )≠0

23 さらなる展開・拡がり Capacityの正体
　Ca p sym 𝑇 𝐴 = inf. tr 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † 𝑌 s.t. det 𝑋= det 𝑌=1, 𝑋,𝑌≻0 = inf. 𝑖 𝑈 𝐴 𝑖 𝑉 s.t. 𝑈,𝑉∈S L 𝑛 (ℂ) ～ 群S L 𝑛 (ℂ)×S L 𝑛 (ℂ)の軌道の閉包上の最小ノルム点問題 作用素スケーリングは，最小ノルム<𝜀 かどうかをpoly(size(𝐴),𝑛,1/𝜀)で判定 Geometric Complexity Theory (Mulmuley,Sohoni 2001 ～)からの問題意識 ～ ２つの軌道の閉包が交わるか判定できるか？ ～ poly(size(𝐴),𝑛,1/𝜀)をpoly(size(𝐴),𝑛, log 1/𝜀 )にできるか？

24 Cap ～ 非正曲率リーマン多様体上の測地的凸最適化
log Cap 𝑇 𝐴 ≔ inf. log det 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † − log det 𝑋 s.t. 𝑋≻0 目的関数は凸でない 多様体: 𝑃= 𝑋≻0 リーマン計量: 𝑆,𝑇∈𝑋の接空間(＝{エルミート行列}) 𝑆,𝑇 𝑋 ≔tr 𝑋 −1 𝑆 𝑋 −1 𝑇 † Fact: 𝑃は非正曲率リーマン多様体，測地線(最短路)一意 Fact: 目的関数は𝑃上，測地的凸 Allen-Zhu,Garg,Li,Oliveria,Wigderson 2017 𝑃上でBox constraint Newton法  poly(size(𝐴),𝑛, log 1/𝜀 )アルゴリズム

25 さらに拡がりをみせており，ついていけない． キーワード：Brascamp-Lieb不等式,
moment polytope, tensor scaling, quantum marginal, noncommutative optimization,.... FOCS2019にも論文がでている

26 part II まとめ 行列スケーリング，（古典的）Capacity 作用素スケーリング Capacity，対称Capacity