代数的組合せ最適化part II

(1)

代数的組合せ最適化 part II

作用素スケーリングと

Capacity

1.

導入：行列スケーリングによるパーマネントの近似計算

2.

作用素スケーリングと

Capacity

3.

さらなる発展

Part II

では，

の

nc-

正則性判定を扱う．

かどうか

(2)

行列スケーリング

非負行列，ゼロ列，ゼロ行なし

Sinkhorn 1964

行スケーリング

列スケーリング

Question:

行スケーリングと列スケーリングを交互に

繰り返すことで，は２重確率行列に収束するか？

(3)

行列スケーリング

repeat

Thm (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)

パーマネント

非負行列，ゼロ列，ゼロ行なし

Perm �≔

∑

�

∏

�=1

�

�_��₍_�)

から符号を除いたもの

Obs.



パーマネント（

permanent

）

Obs.

完全マッチングが存在

(6)

Capacity

古典的

非負行列，ゼロ列，ゼロ行なし

Obs. (

その他の項

)

Def (Capacity)

Obs.

Gurvits 2008

(7)

Thm (

一般化

van der Waerden

不等式

; Gurvits 2008)



≈�⁻^�

Cor:

は近似

完全マッチングあり

数え上げ問題（）が近似的に最適化問題（）になった！

(8)

行列スケーリングはの最小化アルゴリズムとみなせる

, Def (

対称

Capacity)

inf . �^� ��

�₁, �₂ , … �_�, �₁ , … , �_�>0.

Ca p^sym( �)≔

Lem:

∵Ca p^sym(� )=inf

� inf

� �^� ��

に関する凸計画

(9)

に対する交互最適化

を固定してで最適化

_

となるようにを規格化

:

 repeat

～に対する行列スケーリング

(10)

行列スケーリングによる完全マッチングの存在判定

ds(� )≔‖^�^��−�‖²⁺‖� �−�‖² ^{--- 2}

重確率行列への近さ

•

行（列）スケーリングすると

•

初回以降のスケーリング非減少

は倍される．

•

整数，

(exp. lower bound)

Linial,Samorodnitsky, Wigderson 2000

なら，

より

(11)

行列スケーリングから作用素スケーリングへ

Obs.

が非負行列

Def.

正値作用素

Def.

完全正値作用素

Gurvits 2004:

•

行列スケーリングと

Capacity

を完全正値作用素へ拡張

半正定値

複素共役

---

非負行列の一般化

(12)

Edmonds

問題（正則性判定）に対する

Gurvitz 2004

のアプローチ

•

量子パーマネントを定義係数ベクトルのノルム

:

正則

• Capacity

•

作用素スケーリング（～の最小化）

Cap(� _�)>0

⟷^?

QPerm � _�>0

:

正則

↚⟶ ^nc-

^正則

(13)

Rank nondecreasing

性

,

Def rank nondecreasing

Gurvits 2004

Lem (

本質的に

Gurvits²⁰⁰⁴)

rank nondecreasing : nc-

正則

(14)

Lem

の証明

:nc-

非正則 �

_�

0

�_��

� �

⇔ dim �_��<dim�(∀�)

∃

¿ dim �

� �_��=¿

正則

0

^��^�

⁽

^{� �}

†

)

_�^†=

∑

�

� �_�� �^† �_�^† �^†=¿

0 0 0

∗

⇒rank� _�(_{� �}^†)<dim�=rank � �^†

⇒

�� _�( �)�^†=

∑

�

� �_� � �_�^† �^†=¿

逆に

0 0 0

∗ ^¿ ^rank ^�

∀�) ^{� �} ^{� �}^†^�^†

∗ 0

半正定値性

� � �=¿

⇒

� + � > �

(15)

2

重確率作用素

,

Def.

が２重確率

Lem (Gurvits 2004)

: rank nondecreasing (nc-

正則

)

(16)

Lem

の証明

≥tr� _�(� �^†)

¿tr �^∗_�(� )� �^†

¿ � + ⟨ Δ, ��

^†

⟩

�^∗( �)=� +Δ

Cauchy-Schwarz

� (� �^†)_≼� (��^†)+� (��^†)=� (_�)₌_�

¿rank � _�(� �^†)

半正定値

(17)

,

行スケーリング列スケーリング

Obs.

作用素スケーリング

(18)

作用素スケーリングは

Cap

を最小化している

Def (Capacity)

Def (

対称

capacity)

Lem

Rem:

作用素スケーリング～に対する交互最適化

(19)

作用素スケーリングによる

nc-

正則性判定

ds(� ) ≔‖^� ⁽ ^� ⁾⁻ ^�‖²⁺‖� ^∗(� ) − �‖² --- 2

重確率作用素への近さ

• rank nondecreasing (nc-

正則

)

•

行（列）スケーリングすると

•

初回以降のスケーリング非減少

は倍される．

•

整数

, nc-

正則

(exp. lower bound)

Garg,Gurvits, Oliveira, Wigderson 2015

?

,

(20)

Thm (Garg, Gurvits, Oliveira, Wigderson 2015) , , nc-

正則



作用素スケーリングで

poly()

反復後に

(21)

Thm

の証明

nc-

正則

∀ � ≽ 0, det � =1,

≥det � _� ( _� )⁻^�/²

固有値に関する

相加相乗平均

(22)

いま示したこと

:

Alon’s Combinatorial Nullstellensatz (Alon 1999) :

次数

,

各

,

実は，が選べる

(23)

さらなる展開・拡がり

• Capacity

の正体

～群の軌道の閉包上の最小ノルム点問題

作用素スケーリングは，最小ノルム判定

• Geometric Complexity Theory (Mulmuley,Sohoni 2001

～

)

からの問題意識

～２つの軌道の閉包が交わるか判定できるか？

をできるか？

(24)

Cap

～非正曲率リーマン多様体上の測地的凸最適化

s.t. �≻0

^{目的関数は凸でない}

多様体

:

リーマン計量

:

接空間

(

＝

{

エルミート行列

})

Fact:

は非正曲率リーマン多様体，測地線

(

最短路

)

一意

Fact:

目的関数は上，測地的凸

Allen-Zhu,Garg,Li,Oliveria,Wigderson 2017

上で

Box constraint Newton

法



アルゴリズム

(25)

さらに拡がりをみせており，ついていけない．

キーワード：

Brascamp-Lieb

不等式

,

moment polytope, tensor scaling, quantum marginal, noncommutative optimization,....

FOCS2019

にも論文がでている

(26)

part II

まとめ

•

行列スケーリング，（古典的）

Capacity

•

作用素スケーリング

• Capacity

，対称

Capacity

代数的組合せ最適化part II