ダブル・コミュテータ固有値問題による多項式時間の最適グループ選択

概要: 整数多様性（algebraic diversity）フレームワークは、2次統計推定のために、複数の観測にわたる時間平均化を、単一の観測への代数群作用へ置き換える。 このフレームワークにおける中心的な未解決問題は extit{群の選択} である。すなわち、未知の共分散構造をもつ M 次元の観測が与えられたとき、共分散を最もよく一致させる有限群を、そのスペクトル分解から求める。 対称群 S_M の全ての部分群を素朴に列挙するには、M に対して指数時間が必要である。 我々は、この組合せ問題が、共分散行列の二重交換子（double commutator）から導かれる一般化固有値問題に帰着することを証明し、その結果として、計算量 O(d^2M^2 + d^3) の多項式時間アルゴリズムを得る。ここで d は生成子基底の次元である。 二重交換子行列の最小固有ベクトルは、反復的な最適化を行うことなく、最適な群の生成子を閉形式で直接構成する。 帰着は厳密である。すなわち、二重交換子の最小固有値が 0 であることは、最適な生成子が基底の張る空間に含まれることと同値であり、またそれが含まれない場合には、その大きさが証明可能な最適性ギャップを与える。 この問題は、計算複雑性の標準的なカタログ（Garey and Johnson, 1979）には見当たらず、群論、行列解析、統計的推定を結びつける新しいクラスを表す。 我々は、独立成分分析（JADE）、構造化された行列の近接問題、同時対角化との関連を確立し、さらに、二重交換子による定式化が、同時に多項式時間、閉形式、かつ証明可能であるという性質を満たす唯一のアプローチであることを示す。