固有値分解

対称行列に対する対角化。 スペクトル分解とも呼ぶ。

$$A=Q\mathrm{\Lambda }{Q}^{\top },Q^{\top }Q=I$$

$Q$ が直交行列である点が一般の対角化と違う。 $P^{-1}$ を計算せず $Q^{\top }$ で済むため、数値的にも扱いやすい。

外積の和として#

$$A=\sum _{i=1}^n{\lambda }_i{q}_i{q}_i^{\top }$$

固有値を重みとした、固有ベクトル方向の射影の重ね合わせ。 大きい固有値に対応する方向が、その行列の主要な作用を担う。

小さい ${\lambda }_i$ の項を捨てれば低ランク近似になる。 主成分分析はこれを共分散行列に適用したもの。

行列関数#

対角化できれば、行列に関数を適用できる。

$$f(A)=Qf(\mathrm{\Lambda })Q^{\top }$$

$f$ を対角成分に適用するだけ。これで 行列の平方根、 逆平方根、行列指数関数 $e^A$ が定義できる。

量子計算の時間発展 $e^{-iHt}$ もこの形で、 $H$ がエルミートなので 固有値分解が保証されている。

計算コスト#

$𝒪(n^3)$。CMA-ES が 毎世代ではなく $𝒪(n^2)$ 世代に 1 回だけ分解するのは、 このコストを償却するため。

参考文献#

• Lloyd N. Trefethen, David Bau III. Numerical Linear Algebra. SIAM, 1997. https://doi.org/10.1137/1.9780898719574
• Gene H. Golub, Charles F. Van Loan. Matrix Computations, 4th ed. Johns Hopkins University Press, 2013. https://www.press.jhu.edu/books/title/10678/matrix-computations