疎データからスパースグラフを学習するためのフィードラー数最大化

要旨: 観測データが疎である状況から、疎かつ連結なグラフを学習することを目指します。ここで、観測数 K は、R^N にある信号 x に対する信号次元 N よりも大幅に小さくなり得ます。また、基となる分布は未知です。この極めて不適切（重度に不良設定）な問題設定において、疎グラフ学習の目的関数に対し、頑健な正則化項としてフィードラー数（連結性を定量化するグラフラプラシアン行列の第2固有値）を組み込みます。まず、目的関数を低下させるために、エッジを弱める／削除する操作を行うためのエッジを、グローバルに1本ずつ反復的に選択する貪欲アルゴリズムを開発します。この際、エッジ変更がフィードラー数に及ぼす悪影響を抑える上界を与える固有値摂動の定理を活用します。次に、チェゲルの不等式に基づく並列版を設計します。これは、入力グラフを、近似チェゲルカットを用いて再帰的に2つの部分グラフへ分割し、それによって最適なエッジを分散的に見つけるものです。シミュレーション実験の結果、フィードラー数の最大化は、疎グラフ推定を頑健化し、従来の疎グラフ学習アルゴリズムよりも優れた性能を示すことが分かりました。