ノイマン級数

大学院の研究において、$(\mathbf{I} - a\mathbf{A})^{-1}$ を展開することができないか悩んでいて、ノイマン級数に知見を得たので、その内容をまとめる。

この記事では、ノイマン級数の定義、性質、および応用例について詳述する。特に、機械学習や推薦システムにおける利用例に焦点を当てる。数式とPythonのコードを用いて具体的な計算例を示す。

ソースコード

github

jupyter notebook形式のファイルはこちら

google colaboratory

google colaboratory で実行する場合はこちら

実行環境

OSはmacOSである。LinuxやUnixのコマンドとはオプションが異なることに注意。

!sw_vers

ProductName:		macOS
ProductVersion:		13.5.1
BuildVersion:		22G90

!python -V

Python 3.9.17

基本的なライブラリをインポートし watermark を利用してそのバージョンを確認する。ついでに乱数のseedの設定を行う。

import random
import numpy as np

seed = 123
random_state = 123

random.seed(seed)
np.random.seed(seed)


from watermark import watermark

print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))

Python implementation: CPython
Python version       : 3.9.17
IPython version      : 8.17.2

numpy: 1.25.2

Watermark: 2.4.3

$(\mathbf{I} - a\mathbf{A})^{-1}$ のノイマン級数について

ノイマン級数を用いて $(\mathbf{I} - a\mathbf{A})^{-1}$ を表す方法は、行列 $\mathbf{A}$ と定数 $a$ に対して有用な逆行列の計算方法である。この展開は特に、$\mathbf{A}$ のスペクトル半径が小さい場合に有効である。見てわかるとおり、ノイマン級数は等比数列の和の公式：

$$ \sum_{n=0}^{\infty} a^n = \frac{1}{1 - a} $$

の行列への拡張版である。

定義

定数 $a$ と行列 $\mathbf{A}$ に対して、ノイマン級数を用いた $(\mathbf{I} - a\mathbf{A})^{-1}$ の展開は次のように表される：

$$ (\mathbf{I} - a\mathbf{A})^{-1} = \sum_{n=0}^{\infty} (a\mathbf{A})^n $$

収束条件

この級数が収束するためには、次の条件が必要である：

$$ |a| \cdot \rho(\mathbf{A}) < 1 $$

ここで、$\rho(\mathbf{A})$ は行列 $\mathbf{A}$ のスペクトル半径、つまり $\mathbf{A}$ の固有値の絶対値の最大値を表す。

Pythonによる実装例

以下のPythonコードは、ノイマン級数を用いて $(\mathbf{I} - a\mathbf{A})^{-1}$ を近似計算する例である。 3次のノイマン級数を計算するために、行列 $\mathbf{A}$ と定数 $a$ を定義し、ノイマン級数の和を計算する。

記載する意味があるかは不明だが、一応記載しておく。

import numpy as np

from pprint import pprint

# 適当な初期行列 A
A = np.array([[0.3, 0.2], [0.1, 0.4]])

# 適当な定数
a = 0.8

# スペクトル半径の計算
eigenvalues = np.linalg.eig(A)[0]
spectral_radius = max(abs(eigenvalues))

print(f"spectral_radius : {spectral_radius}")

# 収束条件
if abs(a) * spectral_radius < 1:

    I = np.eye(A.shape[0])

    # 逆行列の近似を計算
    n_iter = 3
    A_inv_approx = np.zeros_like(A)

    for n in range(n_iter):
        A_inv_approx += np.linalg.matrix_power(a * A, n)

    # 最終的な逆行列の近似
    A_inv_approx = np.dot(A_inv_approx, I)

    print("=" * 20)
    print("近似逆行列 : ")
    pprint(A_inv_approx.round(2))
else:
    print("収束条件 |a| * ρ(A) < 1 を満たしていない")


# 行列 A の逆行列を計算
A_inv = np.linalg.inv(I - a * A)

print("=" * 20)
print("逆行列 : ")
pprint(A_inv.round(2))

spectral_radius : 0.5
====================
近似逆行列 : 
array([[1.31, 0.25],
       [0.12, 1.44]])
====================
逆行列 : 
array([[1.35, 0.32],
       [0.16, 1.51]])

結論

ノイマン級数は、特定の条件下で効率的に逆行列を求める方法である。$(\mathbf{I} - a\mathbf{A})^{-1}$ のノイマン級数展開は、行列 $\mathbf{A}$ のスペクトル半径が小さい場合に有効であり、機械学習や線形代数の問題において広く応用されるらしい（知らなかったが…）。

参考文献

Wikipedia: Neumann Series

[線形代数] ノイマン級数