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

利用矩阵浓度不等式的组合优化算法设计

• 批准号: 19K20212
• 负责人: 相馬 輔
• 金额: $ 2.66万
• 依托单位: The Institute of Statistical Mathematics (2023)The University of Tokyo (2019)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-12-19 至 2026-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K20212/
• 关键词: 組合せ最適化; 集中不等式

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

Column concentration inequality, class classification, class transformation, class classification, class, class classification, class classification, class, class, This research topic is to explore new ways to optimize the development of row and column concentration inequalities. This year,(1) the development of rank concentration inequalities on polyhedra,(2) the study of information geometry of action elements. The Chernoff type of rank concentration inequality is shown in the following table. The Chernoff Type Concentration Inequality for Independent Accuracy The maximum inherent value of the film is studied first. In the future, we will find that the inequality of concentration of columns and columns is used in combination optimization. A study on the role of information geometry. The action element For example, the row and column of the representative of the row and column of the close contact between the row and column of the information geometry, the Sinkhorn repeated, the Fisher measurement of the interaction between the projection consistent. The solution of the same information geometry is the solution of the problem. In this study, we show that the interaction between the SLD and the quantum information geometry is consistent. The results of this paper are as follows: (1) The inequality of concentration of columns and rows is the geometric function of positive definite columns and rows. In the future, the achievements will be selected and submitted to the International Academic Journal.

项目成果

作用素スケーリングに対する情報幾何

用于算子缩放的信息几何

• 发表时间: 2020
• 作者: Ogawa Tomohiro;Takahashi Kazuki;Nagarkar Sanjog S.;Ohara Koji;Hong You-lee;Nishiyama Yusuke;Horike Satoshi;松田孟留，相馬輔
• 通讯作者: 松田孟留，相馬輔

Spectral Sparsification of Hypergraphs

• DOI: 10.1137/1.9781611975482.159
• 发表时间: 2018-07
• 期刊: ArXiv
• 作者: Tasuku Soma;Yuichi Yoshida

No-regret algorithms for online k-submodular maximization

在线 k 子模最大化的无悔算法

• 发表时间: 2019
• 作者: Ogawa Tomohiro;Takahashi Kazuki;Nagarkar Sanjog S.;Ohara Koji;Hong You-lee;Nishiyama Yusuke;Horike Satoshi;松田孟留，相馬輔;Tasuku Soma
• 通讯作者: Tasuku Soma

劣モジュラ関数最大化入門

子模函数最大化简介

• 发表时间: 2019
• 作者: Ogawa Tomohiro;Takahashi Kazuki;Nagarkar Sanjog S.;Ohara Koji;Hong You-lee;Nishiyama Yusuke;Horike Satoshi;松田孟留，相馬輔;Tasuku Soma;相馬輔
• 通讯作者: 相馬輔