テプリッツ行列

テプリッツ行列とは

テプリッツ行列（Toeplitz matrix）とは、左から右へ、各下降対角線上に要素が一定であるような行列のことです。別名、対角一定行列とも呼ばれます。数学者オットー・テプリッツによって研究されたことにその名前が由来します。

具体的には、以下のような形式の行列がテプリッツ行列です。


[ a b c d e ]
[ f a b c d ]
[ g f a b c ]
[ h g f a b ]
[ j h g f a ]


この例では、対角線上の要素がすべて`a`であり、その一つ右下の対角線上の要素がすべて`b`、さらにその右下の対角線上の要素がすべて`c`…といった具合に、各対角線上で要素が一定になっていることがわかります。

数学的定義

一般的に、n×nの行列Aがテプリッツ行列であるとは、以下の形式で表せることを意味します。


A = [ a₀ a₋₁ a₋₂ ... a₋n+₁ ]
[ a₁ a₀ a₋₁ ... ⋮ ]
[ a₂ a₁ ⋱ ⋱ ⋮ ]
[ ⋮ ⋱ ⋱ ⋱ a₋₁ a₋₂ ]
[ ⋮ ... ⋱ a₁ a₀ a₋₁ ]
[ aₙ₋₁ ... ... a₂ a₁ a₀ ]


ここで、行列Aのi行j列目の要素をAᵢⱼとすると、テプリッツ行列は以下の条件を満たします。


Aᵢⱼ = Aᵢ₋₁ⱼ₋₁


つまり、各要素はその左上にある要素と等しいということです。

テプリッツ行列の特性

テプリッツ行列は、その構造からいくつかの興味深い特性を持っています。

線形方程式系：
テプリッツ行列を係数とする線形方程式系 Ax=b は、通常の線形方程式系よりも少ない自由度（2n-1）を持つため、効率的に解くことが期待できます。
階数：
テプリッツ行列Aに対して、特定の演算（AUₙ - UₘA）を行うと、その結果の行列の階数が2となるという性質があります。ここで、Uₖはダウンシフト演算子です。
計算量：
2つのテプリッツ行列の加算はO(n)の計算量で可能です。
テプリッツ行列とベクトルの乗算は、O(n log n)で計算できます。
2つのテプリッツ行列の乗算は、O(n²)で計算可能です。
線形方程式系の解法：
テプリッツ行列を係数とする線形方程式系 Ax=b は、レビンソン-ダービンアルゴリズムを用いると、O(n²)の計算量で解くことができます。このアルゴリズムは、数値的に安定であることが知られています。

フーリエ級数との関係

テプリッツ行列は、フーリエ級数とも密接な関係があります。有限次元空間に圧縮された三角関数多項式による乗算演算子は、テプリッツ行列で表現できます。これは、信号処理や画像処理などの分野で重要な意味を持ちます。

その他の関連行列

巡回行列：
テプリッツ行列のうち、要素が aᵢ=aᵢ₊ₙ を満たすものは巡回行列と呼ばれます。
persymmetric行列：
テプリッツ行列はpersymmetricです。また、対称テプリッツ行列は中心対称かつ両対称です。

応用例

テプリッツ行列は、以下のような分野で応用されています。

畳み込み演算：
畳み込み演算は、テプリッツ行列を用いた行列積として表現できます。例えば、信号hとxの畳み込みは、以下のように表すことができます。

y = h x

これは、テプリッツ行列に変換されたhとベクトルxの積として表現できます。


y = [ h₁ 0 ... 0 0 ] [ x₁ ]
[ h₂ h₁ ... ⋮ ⋮ ] [ x₂ ]
[ h₃ h₂ ... 0 0 ] [ x₃ ]
[ ⋮ h₃ ... h₁ 0 ] [ ⋮ ]
[ hm₋₁ ⋮ ... h₂ h₁ ] [ xₙ ]
[ hm hm₋₁ ⋮ ⋮ h₂ ]
[ 0 hm ... hm₋₂ ⋮ ]
[ 0 0 ... hm₋₁ hm₋₂ ]
[ ⋮ ⋮ ⋮ hm hm₋₁ ]
[ 0 0 0 ... hm ]


この手法は、自己相関、相互相関、移動平均などの計算にも応用可能です。

まとめ

テプリッツ行列は、その構造の特殊性から、効率的な計算や解析が可能な行列です。信号処理、画像処理、線形代数など、幅広い分野で重要な役割を果たしています。本記事では、テプリッツ行列の基本的な定義から特性、応用例までを詳しく解説しました。

参考情報

Toeplitz and Circulant Matrices: A Review, by R. M. Gray

もう一度検索