Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"

技術要約：「凸集合上の多項式最適化における偏極階層、および非負行列ランクへの応用」

問題設定
本論文は、Plávala, Ligthart, および Gross [1] によって提案された、凸集合上の多項式最適化のための偏極階層（polarization hierarchy）における実現可能性および収束性の主張を再検討するものである。この階層は、$a \in K_A$ および $b \in K_B$（ここで $K_A, K_B$ はコンパクト凸集合）に対し、$f(a, b) = 0$ という制約の下で $\min p(a, b)$ を解く問題を対象としている。ここで $f, p$ は各引数に対してアフィンである。この手法は、これらの集合のコピーの最大テンソル積上での凸緩和を用い、制約を課すために線形な「偏極写像」$\Pi: V \otimes V \to W$ を利用する。

先行研究 [1] は、(H2) と表記される特定の代数的条件に依拠していた。これは、$\Pi(v \otimes v + w \otimes w) = 0$ ならば $v = w = 0$ であることを意味する。この仮定の下で、[1] は、偏極制約を満たす「バイコンパティブルな列（bicompatible sequence）」の存在が元の問題の実現可能性と等価であること（定理3）、および階層の最適値が真の最小値に収束すること（定理5）を主張した。

手法および解析
著者である Julius A. Zeiss は、条件 (H2) がこれらの主張を保証するには不十分であることを証明する。解析の核心は、バイコンパティブルな列の表現測度 $\mu(a, b)$ に対する二次のモーメント演算子 $M = \int f(a, b) \otimes f(a, b) \, d\mu(a, b)$ のスペクトル分解にある。$M$ は半正定値（PSD）であるが、(H2) の下であっても、もし $M$ のランクが2を超える場合、$\Pi(M) = 0$ は必ずしも $M = 0$ を意味しない。なぜなら、3つ以上の項の間で相殺が発生し得るからである。

これに対処するため、本論文は以下の手順を踏む：

1. 反例の構築： 例 3.1 および 3.2 では、対称なトレースレス行列への特定の射影写像 $\Pi_3$ を用いている。これらの例は、(H2) の下では、実現不可能（infeasible）な問題が偏極制約を満たすバイコンパティブルな列を持つことがあり、また、実現可能な問題において階層が真の最適値に収束しないことがあることを示している。
2. 修正された条件の確立： 本論文は、より強い代数的条件 (H$_k$) を導入する。これは、$\Pi(\sum_{j=1}^k v_j \otimes v_j) = 0$ ならばすべての $v_j = 0$ であることを要求するものである。修正された仮定は (H$_D$) であり、ここで $D = \dim V$ である。これは、$\Pi$ の核（kernel）が非ゼロの半正定値演算子を含まないことと等価であることが示されている（命題 4.1）。
3. コンパクト性議論の提供： [1] における収束の証明は、2コピーの周辺分布の極限に依存していたが、これは完全なバイコンパティブルな列の存在を保証するには不十分であった。本論文は、厳密なコンパクト性議論（定理 5.4）を提供し、共通の部分列に沿ってすべての固定次数の周辺分布の極限を抽出することで、有効なバイコンパティブルな列を構成する。

主要な貢献および結果

• (H2) の反駁： 本論文は、(H2) が実現可能性の特性化および階層の収束の両方に対して不十分であることを証明する。反例は、階層が実現不可能な問題に対して実現可能であり続け、かつ真の最適値よりも厳密に悪い値に収束し得ることを示している。
• 修正された実現可能性定理（定理 5.1）： $\Pi$ がより強い条件 (H$_D$)（すなわち $\ker \Pi \cap S_+(V) = \{0\}$）を満たす場合、偏極制約を満たすバイコンパティブルな列の存在は、元の問題が実現可能であるための必要十分条件であることが確立される。
• 修正された収束定理（定理 5.4）： 条件 (H$_D$) の下で、元の問題が実現可能であれば、階層の最適値 $p_n^\Pi$ は真の最適値 $p^*$ に単調に収束することが示される。この証明は、有限レベルの解を有効なバイコンパティブルな列へと拡張するために必要な、新たに提供されたコンパクト性議論に依拠している。
• ランク境界： 命題 4.3 は、$D$ が、すべての写像に対して (H$_k$) が修正された条件を導く最小の整数 $k$ であることを示している。しかし、命題 4.4 は、対称テンソルへの $\Pi$ の制限のランクに依存する、よりタイトな境界 $\kappa$ を提供している。具体的には、このランクが最大4であれば (H2) で十分である。
• 元々の応用の妥当性： 備考 5.2 および 5.7 は、[1] で提案された3つの特定の偏極写像（恒等写像やヒルベルト・シュミット内積に関連する写像を含む）が、すでに強化された条件 (H$_D$) を満たしていることを明確にしている。したがって、一般的な (H2) の仮定は不十分であるものの、それらの特定の選択肢に関する [1] の収束結果および数値的な知見（非負行列ランクに関するものなど）は依然として有効である。
• 有限の証明（Finite Certificates）： セクション 6 では、反例の線形計画法による検証、および例 5.3 におけるバイコンパブルな拡張性の失敗に関する有限の証明を提供し、拡張可能な周辺分布の集合への距離を定量化している。

意義
本論文は、偏極階層の理論的基礎に対する厳密な修正として機能する。[1] における一般的な代数的仮定 (H2) は弱すぎた一方で、元の応用で使用された特定の写像は十分に強力であったことを明らかにしている。$\Pi$ の核が非ゼロの PSD 演算子を含まないという条件の必要性を確立することで、本論文は、この階層を多項式最適化や非負行列ランクのような問題に使用することの数学的正当性を保証している。また、有限レベルの極限を無限のバイコンパブルな列へと拡張するために必要な、欠落していたコンパクト性議論を提供することで、収束証明の空白を埋めている。