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

Slides:



Advertisements
Similar presentations
ゲームプログラミング講習 第2章 関数の使い方
Advertisements

サービス管理責任者等研修テキスト 分野別講義    「アセスメントと        支援提供の基本姿勢」 <児童発達支援管理責任者> 平成27年10月1日.
ヒトの思考プロセスの解明を目的とするワーキングメモリの研究
第27講 オームの法則 電気抵抗の役割について知る オームの法則を使えるようにする 抵抗の温度変化を理解する 教科書P.223~226
コラッツ予想の変形について 東邦大学 理学部 情報科 白柳研究室 山中 陽子.
コンパイラ 第3回 字句解析 ― 決定性有限オートマトンの導出 ―
第5章 家計に関する統計 ー 経済統計 ー.
公共財 公共経済論 II no.3 麻生良文.
VTX alignment D2 浅野秀光 2011年12月15日  放射線研ミーティング.
冷却フランシウム原子を用いた 電子の永久電気双極子能率探索のための ルビジウム磁力計の研究
生命情報学 (8) スケールフリーネットワーク
前半戦 「史上最強」風 札上げクイズ.

認知症を理解し 環境の重要性について考える
フッ化ナトリウムによる洗口 2010・9・13 宮崎市郡東諸県郡薬剤師会 学校薬剤師  日高 華代子.
食品の安全性に関わる社会システム:総括 健康弱者 ハイリスク集団 HACCP (食肉処理場・食品工場) 農場でのQAP 一般的衛生管理
規制改革とは? ○規制改革の目的は、経済の活性化と雇用の創出によって、   活力ある経済社会の実現を図ることにあります。
地域保健対策検討会 に関する私見(保健所のあり方)
公共政策大学院 鈴木一人 第8回 専門化する政治 公共政策大学院 鈴木一人
医薬品ネット販売規制について 2012年5月31日 ケンコーコム株式会社.
平成26年8月27日(水) 大阪府 健康医療部 薬務課 医療機器グループ
平成26年度 呼吸器学会からの提案結果 (オレンジ色の部分が承認された提案) 新規提案 既収載の変更 免疫組織化学染色、免疫細胞化学染色
エナジードリンクの危険性 2015年6月23日 経営学部市場戦略学科MR3195稲沢珠依.
自動吸引は 在宅を変えるか 大分協和病院 院長         山本 真.
毎月レポート ビジネスの情報 (2016年7月号).
医療の歴史と将来 医療と医薬品産業 個人的経験 3. 「これからの医療を考える」 (1)医薬品の研究開発 -タクロリムスの歴史-
社会福祉調査論 第4講 2.社会調査の概要 11月2日.
2015年12月28日-2016年3月28日 掲載分.
2010度 民事訴訟法講義 補論 関西大学法学部教授 栗田 隆.
腫瘍学概論 埼玉医科大学国際医療センター 包括的がんセンター 緩和医療科/緩和ケアチーム 奈良林 至
“企業リスクへの考え方に変化を求められています。 トータルなリスクマネジメント・サービスをプロデュースします。“
情報漏えい 経済情報学科 E  西村 諭 E  釣 洋平.
金融班(ミクロ).
第11回 2009年12月16日 今日の資料=A4・4枚+解答用紙 期末試験:2月3日(水)N2教室
【ABL用語集】(あいうえお順) No 用語 解説 12 公正市場価格 13 債権 14 指名債権 15 事業収益資産 16 集合動産 17
基礎理論(3) 情報の非対称性と逆選択 公共政策論II No.3 麻生良文.
浜中 健児 昭和42年3月27日生まれ 東京都在住 株式会社ピー・アール・エフ 代表取締役 (学歴) 高 校:千葉県立東葛飾高校 卒業
COPYRIGHT(C) 2011 KYUSHU UNIVERSITY. ALL RIGHTS RESERVED
Blosxom による CMS 構築と SEO テクニック
記入例 JAWS DAYS 2015 – JOB BOARD 会社名 採用職種 営業職/技術職/その他( ) 仕事内容 待遇 募集数
ネットビジネスの 企業と特性 MR1127 まさ.
Future Technology活用による業務改革
ネットビジネス論(杉浦) 第8回 ネットビジネスと情報技術.
g741001 長谷川 嵩 g740796 迫村 光秋 g741000 西田 健太郎 g741147 小井出 真聡
自然独占 公共経済論 II no.5 麻生良文.
Autonomic Resource Provisioning for Cloud-Based Software
Webショップにおける webデザイン 12/6 08A1022 甲斐 広大.
物理的な位置情報を活用した仮想クラウドの構築
ハイブリッドクラウドを実現させるポイントと SCSKのOSSへの取組み
寺尾 敦 青山学院大学社会情報学部 第12回 情報デザイン(4) 情報の構造化と表現 寺尾 敦 青山学院大学社会情報学部
【1−1.開発計画 – 設計・開発計画】 システム開発計画にはシステム開発を効率的、効果的に実行する根拠(人員と経験、開発手順、開発・導入するシステム・アプリケーション・サービス等)を記述すること。 システム開発の開始から終了までの全体スケジュールを記載すること。 アプリケーション機能配置、ソフトウェア、インフラ構成、ネットワーク構成について概要を示すこと。
6 日本のコーポレート・ガバナンス 2008年度「企業論」 川端 望.
急成長する中国ソフトウェア産業 中国ソフトウェアと情報サービス産業の規模 総売上高は5年間で約5.3倍の成長
米国ユタ州LDS病院胸部心臓外科フェローの経験
公益社団法人日本青年会議所 関東地区埼玉ブロック協議会 JCの情熱(おもい)育成委員会 2011年度第1回全体委員会
次世代大学教育研究会のこれまでの活動 2005年度次世代大学教育研究大会 明治大学駿河台校舎リバティタワー9階1096教室
子どもの本の情報 大阪府内の協力書店の情報 こちらをクリック 大阪府内の公立図書館・図書室の情報
第2回産業調査 小島浩道.
〈起点〉を示す格助詞「を」と「から」の選択について
広東省民弁本科高校日語専業骨幹教師研修会 ①日本語の格助詞の使い分け ②動詞の自他受身の選択について   -日本語教育と中日カルチャーショックの観点から- 名古屋大学 杉村 泰.
■5Ahバッテリー使用報告 事例紹介/東【その1】 ■iphon4S(晴れの昼間/AM8-PM3) ◆約1時間で68%⇒100%
『ワタシが!!』『地域の仲間で!!』 市民が始める自然エネルギー!!
ポイントカードの未来形を形にした「MUJI Passport」
SAP NetWeaver を支える Microsoft テクノロジーの全貌 (Appendix)
ガイダンス(内業) 測量学実習 第1回.
Python超入門 久保 幹雄 東京海洋大学.
熱力学の基礎 丸山 茂夫 東京大学大学院 工学系研究科 機械工学専攻
京都民医連中央病院 CHDF学習推進委員会
資料2-④ ④下水道.
Accessによる SQLの操作 ~実際にテーブルを操作してみよう!~.
Presentation transcript:

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

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

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

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

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

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 𝐵

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.

行列スケーリングは 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

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

行列スケーリングによる完全マッチングの存在判定 Linial,Samorodnitsky, Wigderson 2000 ds 𝐵 ≔ 𝐴 𝑇 𝟏−𝟏 2 + 𝐴𝟏−𝟏 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より

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

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

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

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

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

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

作用素スケーリング 𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝑇 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † , 𝑇 ∗ 𝑋 ≔ 𝑖 𝐴 𝑖 † 𝑋 𝐴 𝑖 𝐴= 𝑖 𝐴 𝑖 𝑥 𝑖 , 𝑇 𝑋 = 𝑖 𝐴 𝑖 𝑋 𝐴 𝑖 † , 𝑇 ∗ 𝑋 ≔ 𝑖 𝐴 𝑖 † 𝑋 𝐴 𝑖 行スケーリング 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

作用素スケーリングは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 に対する交互最適化

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

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

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

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

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

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/𝜀 )アルゴリズム

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

part II まとめ 行列スケーリング,(古典的)Capacity 作用素スケーリング Capacity,対称Capacity