CQTで和音を解析するその３（コレスキー分解）

前回実装した、NNLSのLawson–Hanson アルゴリズムで、能動集合（passive set）に制限した最小二乗問題を解くときにコレスキー分解を行っている。

辞書行列Eが、各半音ごとに独立した倍音スペクトル分布を列として持つため、ほぼフルランク（すべて線形独立）であることを前提にしている。

コレスキー分解とは？

コレスキー分解とは、対称正定値行列 $A$ を次のように分解する方法である。

$\displaystyle A = L L^{T}$

ここで：

$L$ は下三角行列（対角要素は正）
$L^{T}$ は $L$ の転置

つまり、複雑な行列を「三角形の形」に分解できる、というのがコレスキー分解のポイントである。

直感的なイメージ

行列の連立方程式を解くとき、そのままでは計算が重かったり不安定だったりする。
しかし三角行列は「順番に代入していくだけ」で解ける。

コレスキー分解が使える条件

行列 $A$ が次の条件を満たす必要がある。

1. 対称行列 ( $A = A^{T}$ )
2. 正定値行列（全ての固有値が正）

これらを満たさないと、途中で平方根の計算が破綻する。

具体例で理解する

例として、次の行列を考える：

$\displaystyle A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}$

この行列は対称かつ正定値である。
コレスキー分解すると、

$\displaystyle L = \begin{bmatrix} 2 & 0 \\ 1 & \sqrt{2} \end{bmatrix}$

となり、

$\displaystyle A = L L^T = \begin{bmatrix} 2 & 0 \\ 1 & \sqrt{2} \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 0 & \sqrt{2} \end{bmatrix} = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}$

が確認できる。

コレスキー分解のメリット

連立一次方程式の高速解法

最小二乗法やガウス過程回帰などでは、

$\displaystyle A x = b$

のような連立方程式を解く必要がある。

コレスキー分解を使うと、

1. $L y = b$ を前進代入で解く
2. $L^T x = y$ を後退代入で解く

という2段階の簡単な計算で解が得らる。

数値的安定性

LU分解や逆行列計算に比べて、コレスキー分解は計算が安定しており、誤差が蓄積しにくい。
そのため、機械学習や統計分野では「SPD行列を扱うときはまずコレスキー分解」と言われるほど定番である。

まとめ

コレスキー分解は SPD行列を下三角行列に分解する方法。
連立一次方程式や最小二乗法を効率的・安定的に解くのに有効。
機械学習や数値解析で頻出するテクニック。

TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。