MathLabs

解法: 交差族によるMarcus–Spielman–Srivastavaの証明(2013年)

ステップ 4/8: 混合特性多項式:注文設計された実根平均
ざっくり言うと

Marcus、Spielman、Srivastavaは、共分散行列 Ai=E[wiwi∗]A_i=\mathbb{E}[w_iw_i^*] に対して混合特性多項式 μ[A1,…,Am]\mu[A_1,\ldots,A_m] を定義する。その微分作用素によるレシピは、この多項式が独立なランク1ランダム行列の和 ∑iwiwi∗\sum_i w_iw_i^* の期待特性多項式と正確に一致するよう設計されており、実安定性によってその根がすべて実数であることが保証される。

μ[A1,…,Am](x):=∏i=1m(1−∂zi)det⁡(xI+∑iziAi)∣z=0,Ai=E[wiwi∗]\mu[A_1,\ldots,A_m](x) := \prod_{i=1}^m\Big(1-\partial_{z_i}\Big)\det\Big(xI+\sum_i z_i A_i\Big)\Big|_{z=0},\qquad A_i=\mathbb{E}[w_iw_i^*]
詳しい解説

半正定な共分散行列 A1,…,AmA_1,\ldots,A_m に対して、μ[A1,…,Am](x):=∏i=1m(1−∂zi)det⁡(xI+∑iziAi)∣z=0\mu[A_1,\ldots,A_m](x) := \prod_{i=1}^m(1-\partial_{z_i})\det\big(xI+\sum_i z_iA_i\big)\big|_{z=0} と定義する。出発点の行列式は実安定であり、微分作用素と実数への特殊化も実安定性を保つ。論文の定理4.1は、この多項式が共分散 AiA_i を持つ独立ランダムベクトルに対する E[det⁡(xI−∑iwiwi∗)]\mathbb{E}[\det(xI-\sum_i w_iw_i^*)] と一致することを示すため、これは実根を持ち、交差族の議論に適した平均である。

このステップの用語
半正定行列
すべての固有値が非負であるエルミート行列。単一のベクトル vv から作られる vv∗v v^* の形の行列は常に半正定である。
このステップで使う知識