Toeplitz Matrix
Posted on Fri 09 March 2018 in Linear Algebra
簡介
Toeplitz matrix 又被稱為常對角矩陣，是一個對角線都是常數的矩陣。
對任一\(n \times n\)的矩陣\(\mathbf{A}\)，可以表示成：
$$\mathbf{A}=\begin{bmatrix}
a_0 & a_{-1} & a_{-2} & \cdots & a_{-(n-1)} \\
a_1 & a_0 & a_{-1} & \ddots & \vdots \\
a_2 & a_1 & \ddots & \ddots & \vdots \\
\vdots & \ddots & \ddots & a_0 & a_{-1} \\
a_{n-1} & \cdots & a_2 & a_1 & a_0
\end{bmatrix},$$
其通式可以寫成：
$$\mathbf{A}=A_{i,j}=A_{i+1,j+1}=a_{i-j}.$$
範例
Scipy 中有實作創造 Toeplitz matrix：
from scipy.linalg import toeplitz
c = [1,2,3] # c 為指定矩陣的第一行
toeplitz(c)
array([[1, 2, 3],
[2, 1, 2],
[3, 2, 1]])
r = [1,4,5,6] # r 為指定矩陣的第一列
toeplitz(c, r)
array([[1, 4, 5, 6],
[2, 1, 4, 5],
[3, 2, 1, 4]])
Convolution
convolution 運算中的輸入，可以轉換成 toeplitz matrix，使運算可以寫成矩陣乘法。\(h\)與\(x\)的 convolution 可以表示成：
$$y=h\ast x=\begin{bmatrix}
h_1 & 0 & \cdots & 0 & 0 \\
h_2 & h_1 & \ddots & \vdots & \vdots \\
h_3 & h_2 & \ddots & \vdots & \vdots \\
\vdots & h_3 & \ddots & h_1 & \vdots \\
h_m & \vdots & \ddots & h_2 & h_1 \\
0 & h_m & \ddots & h_3 & h_2 \\
0 & 0 & h_m & \vdots & h_3 \\
\vdots & \vdots & \vdots & h_m & \vdots \\
0 & 0 & \cdots & 0 & h_m
\end{bmatrix} \begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
\vdots \\
x_n
\end{bmatrix}$$