行列集中不等式による組合せ最適化アルゴリズムの設計

行列集中不等式は，ラプラシアンソルバーや，グラフの疎化，ネットワークフローアルゴリズムなどに幅広い応用がある．本研究課題では，行列集中不等式を通じて新たな組合せ最適化アルゴリズムの開発を目指す．本年は，(1)マトロイド基多面体上の丸めアルゴリズムの行列集中不等式の開発と，(2)作用素スケーリングの情報幾何の研究を行った．まず，マトロイド基多面体上の代表的な丸めアルゴリズムであるスワップ丸めについて，Chernoff型の行列集中不等式を示した．これは，独立確率変数に対するChernoff型行列集中不等式を，スワップ丸めで現れる従属確率変数へ拡張したものである．また，先行研究の最大固有値に対する片側バウンドを両側バウンドへ拡張した結果とみなすこともできる．今後は，得られた行列集中不等式を応用し，組合せ最適化の新しいアルゴリズムを開発することを目指していく．また，作用素スケーリングに関する情報幾何の研究も行った．作用素スケーリングは行列スケーリングの非可換版として導入された問題で，Edmonds問題やBrascamp-Lieb不等式への応用が近年見つかりつつある．元々，行列スケーリングは情報幾何との密接な繋がりがあり，例えば行列スケーリングの代表的なアルゴリズムであるSinkhorn反復は，Fisher計量に対する交互e射影に一致する．ところが，作用素スケーリングにおいて同様の情報幾何的な解釈ができるかは分かっていなかった．本研究では，作用素スケーリングの代表的アルゴリズムである作用素Sinkhorn反復が，量子情報幾何で知られているSLD計量に対する交互e射影に一致することを示した．本成果は行列集中不等式で使われてきた正定値行列の幾何を作用素スケーリングへ応用したものである．今後，得られた成果を取りまとめ国際学術誌に投稿する予定である．

行列集中不等式は，ラプラシアンソルバーや，グラフの疎化，ネットワークフローアルゴリズムなどに幅広い応用がある．本研究課題では，行列集中不等式を通じて新たな組合せ最適化アルゴリズムの開発を目指す．本年は，(1)マトロイド基多面体上の丸めアルゴリズムの行列集中不等式の開発と，(2)作用素スケーリングの情報幾何の研究を行った．まず，マトロイド基多面体上の代表的な丸めアルゴリズムであるスワップ丸めについて，Chernoff型の行列集中不等式を示した．これは，独立確率変数に対するChernoff型行列集中不等式を，スワップ丸めで現れる従属確率変数へ拡張したものである．また，先行研究の最大固有値に対する片側バウンドを両側バウンドへ拡張した結果とみなすこともできる．今後は，得られた行列集中不等式を応用し，組合せ最適化の新しいアルゴリズムを開発することを目指していく．また，作用素スケーリングに関する情報幾何の研究も行った．作用素スケーリングは行列スケーリングの非可換版として導入された問題で，Edmonds問題やBrascamp-Lieb不等式への応用が近年見つかりつつある．元々，行列スケーリングは情報幾何との密接な繋がりがあり，例えば行列スケーリングの代表的なアルゴリズムであるSinkhorn反復は，Fisher計量に対する交互e射影に一致する．ところが，作用素スケーリングにおいて同様の情報幾何的な解釈ができるかは分かっていなかった．本研究では，作用素スケーリングの代表的アルゴリズムである作用素Sinkhorn反復が，量子情報幾何で知られているSLD計量に対する交互e射影に一致することを示した．本成果は行列集中不等式で使われてきた正定値行列の幾何を作用素スケーリングへ応用したものである．今後，得られた成果を取りまとめ国際学術誌に投稿する予定である．