张量t-product积基础 | 循环矩阵与向量乘积的离散傅立叶变换 · 循环矩阵的傅里叶对角化

循环矩阵与向量乘积的离散傅立叶变换

证明过程非常有意思写下来给大家看一下

证明：

F A B = ( F A ( : , 1 ) ) ⊙ ( F B ) FAB=(FA(:,1))\odot(FB) FAB=(FA(:,1))⊙(FB) 其中 A A A为循环矩阵，F为DFT矩阵， A ( : , 1 ) A(:,1) A(:,1)是 A A A的第一列， ⊙ \odot ⊙是Hadamard积，就是把位置相同的元素乘在一起，这论文中的符号和很多论文中的不一样就很烦，这里因为 ( F A ( : , 1 ) ) (FA(:,1)) (FA(:,1))和(FB)都是列向量，因此为了容易理解我们将其写为： F A B = d i a g ( F A ( : , 1 ) ) ( F B ) FAB=diag(FA(:,1))(FB) FAB=diag(FA(:,1))(FB) 就两个列向量每个元素一一相乘不相当于把第一个向量的每一个元素都放在一个对角阵的对角线，然后再乘列向量嘛。

符号说明

A是循环矩阵，为了方便后面书写我们将A的列记为 A 1 ， A 2 , … , A n A_1，A_2,\dots,A_n A1​，A2​,…,An​.

A = ( a 1 a n a n − 1 ⋯ a 2 a 2 a 1 a n ⋯ a 3 a 3 a 2 a 1 ⋯ a 4 ⋮ ⋮ ⋮ ⋱ ⋮ a n a n − 1 a n − 2 ⋯ a 1 ) = ( ∣ ∣ ∣ ⋯ ∣ A 1 A 2 A 3 ⋯ A n ∣ ∣ ∣ ⋯ ∣ ) A=\begin{pmatrix} a_1&a_n&a_{n-1}&\cdots&a_2\\ a_2&a_1&a_n&\cdots&a_3\\ a_3&a_2&a_1&\cdots&a_4\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ a_n&a_{n-1}&a_{n-2}&\cdots&a_1 \end{pmatrix}= \begin{pmatrix} \mid&\mid&\mid&\cdots&\mid\\ A_1&A_2&A_3&\cdots&A_n\\ \mid&\mid&\mid&\cdots&\mid \end{pmatrix} A=⎝⎜⎜⎜⎜⎜⎛​a1​a2​a3​⋮an​​an​a1​a2​⋮an−1​​an−1​an​a1​⋮an−2​​⋯⋯⋯⋱⋯​a2​a3​a4​⋮a1​​⎠⎟⎟⎟⎟⎟⎞​=⎝⎛​∣A1​∣​∣A2​∣​∣A3​∣​⋯⋯⋯​∣An​∣​⎠⎞​

F是DFT矩阵，具有如下形式，为了方便后面将F的行记为 F 1 ， F 2 , … , F n F_1，F_2,\dots,F_n F1​，F2​,…,Fn​. F = ( 1 1 1 1 ⋯ 1 1 ω ω 2 ω 3 ⋯ ω n − 1 1 ω 2 ω 4 ω 6 ⋯ ω 2 ( n − 1 ) 1 ω 3 ω 6 ω 9 ⋯ ω 3 ( n − 1 ) ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ 1 ω n − 1 ω 2 ( n − 1 ) ω 3 ( n − 1 ) ⋯ ω ( n − 1 ) ( n − 1 ) ) = ( — F 1 — — F 2 — — F 3 — — F 4 — ⋮ ⋮ ⋮ — F n — ) F=\begin{pmatrix} 1&1&1&1&\cdots&1\\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^{n-1}\\ 1&\omega^2&\omega^4&\omega^6&\cdots&\omega^{2(n-1)}\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^{3(n-1)}\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega^{n-1}&\omega^{2(n-1)}&\omega^{3(n-1)}&\cdots&\omega^{(n-1)(n-1)} \end{pmatrix}= \begin{pmatrix} —&F_1&—\\ —&F_2&—\\ —&F_3&—\\ —&F_4&—\\ \vdots&\vdots&\vdots\\ —&F_n&— \end{pmatrix} F=⎝⎜⎜⎜⎜⎜⎜⎜⎛​1111⋮1​1ωω2ω3⋮ωn−1​1ω2ω4ω6⋮ω2(n−1)​1ω3ω6ω9⋮ω3(n−1)​⋯⋯⋯⋯⋱⋯​1ωn−1ω2(n−1)ω3(n−1)⋮ω(n−1)(n−1)​⎠⎟⎟⎟⎟⎟⎟⎟⎞​=⎝⎜⎜⎜⎜⎜⎜⎜⎛​————⋮—​F1​F2​F3​F4​⋮Fn​​————⋮—​⎠⎟⎟⎟⎟⎟⎟⎟⎞​

其中 ω = e − 2 π i n \omega=e^{\frac{-2\pi i}{n}} ω=en−2πi​，实际上 1 , ω , ω 2 , … , ω n − 1 1,\omega,\omega^2,\dots,\omega^{n-1} 1,ω,ω2,…,ωn−1就是令 x n = 1 x^n=1 xn=1成立的n个解。

证明过程

首先看右边 F A 1 = ( — F 1 — — F 2 — — F 3 — — F 4 — ⋮ ⋮ ⋮ — F n — ) A 1 = ( F 1 A 1 F 2 A 1 F 3 A 1 F 4 A 1 ⋮ F n A 1 ) FA_1=\begin{pmatrix} —&F_1&—\\ —&F_2&—\\ —&F_3&—\\ —&F_4&—\\ \vdots&\vdots&\vdots\\ —&F_n&— \end{pmatrix}A_1= \begin{pmatrix} F_1A_1\\ F_2A_1\\ F_3A_1\\ F_4A_1\\ \vdots\\ F_nA_1 \end{pmatrix} FA1​=⎝⎜⎜⎜⎜⎜⎜⎜⎛​————⋮—​F1​F2​F3​F4​⋮Fn​​————⋮—​⎠⎟⎟⎟⎟⎟⎟⎟⎞​A1​=⎝⎜⎜⎜⎜⎜⎜⎜⎛​F1​A1​F2​A1​F3​A1​F4​A1​⋮Fn​A1​​⎠⎟⎟⎟⎟⎟⎟⎟⎞​ 那么原式可写为：

F A B = d i a g ( F 1 A 1 , F 2 A 1 , F 3 A 1 , … , F n A 1 ) ( F B ) FAB=diag(F_1A_1,F_2A_1,F_3A_1,\dots,F_nA_1)(FB) FAB=diag(F1​A1​,F2​A1​,F3​A1​,…,Fn​A1​)(FB)

再看式子左边先计算FA： F A = ( F 1 A 1 F 1 A 2 F 1 A 3 … F 1 A n F 2 A 1 F 2 A 2 F 2 A 3 … F 2 A n F 3 A 1 F 3 A 2 F 3 A 3 … F 3 A n ⋮ ⋮ ⋮ ⋱ ⋮ F n A 1 F n A 2 F n A 3 … F n A n ) FA=\begin{pmatrix} F_1A_1&F_1A_2&F_1A_3&\dots&F_1A_n\\ F_2A_1&F_2A_2&F_2A_3&\dots&F_2A_n\\ F_3A_1&F_3A_2&F_3A_3&\dots&F_3A_n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ F_nA_1&F_nA_2&F_nA_3&\dots&F_nA_n\\ \end{pmatrix} FA=⎝⎜⎜⎜⎜⎜⎛​F1​A1​F2​A1​F3​A1​⋮Fn​A1​​F1​A2​F2​A2​F3​A2​⋮Fn​A2​​F1​A3​F2​A3​F3​A3​⋮Fn​A3​​………⋱…​F1​An​F2​An​F3​An​⋮Fn​An​​⎠⎟⎟⎟⎟⎟⎞​

这时候我们回想起了 ω \omega ω的一些性质， ω n = 1 \omega^n=1 ωn=1，A矩阵的列向量是循环的，我们可以让F的行向量跟着一起循环，这个原理可能不太好描述，但总体来说我们要做的是下面这样的一件事情，可以类比推理一下： ( c 1 c 2 c 3 ) ( d 1 d 2 d 3 ) = ( c 3 c 1 c 2 ) ( d 3 d 1 d 2 ) \begin{pmatrix} c_1&c_2&c_3 \end{pmatrix}\begin{pmatrix} d_1\\ d_2\\ d_3 \end{pmatrix}= \begin{pmatrix} c_3&c_1&c_2 \end{pmatrix}\begin{pmatrix} d_3\\ d_1\\ d_2 \end{pmatrix} (c1​​c2​​c3​​)⎝⎛​d1​d2​d3​​⎠⎞​=(c3​​c1​​c2​​)⎝⎛​d3​d1​d2​​⎠⎞​ 我们就举FA第二行的例子： F 2 A 1 = ( 1 ω ω 2 ⋯ ω n − 1 ) ( a 1 a 2 a 3 ⋮ a n ) = ( ω n − 1 1 ω ⋯ ω n − 2 ) ( a n a 1 a 2 ⋮ a n − 1 ) = ( ω n − 1 1 ω ⋯ ω n − 2 ) A 2 = ω − 1 ( 1 ω ω 2 ⋯ ω n − 1 ) A 2 = ω − 1 F 2 A 2 \begin{array}{ll} F_2A_1=\begin{pmatrix} 1&\omega&\omega^2&\cdots&\omega^{n-1} \end{pmatrix}\begin{pmatrix} a_1\\ a_2\\ a_3\\ \vdots \\ a_n \end{pmatrix}\\= \begin{pmatrix} \omega^{n-1}&1&\omega&\cdots&\omega^{n-2} \end{pmatrix}\begin{pmatrix} a_n\\ a_1\\ a_2\\ \vdots \\ a_{n-1} \end{pmatrix} \\=\begin{pmatrix} \omega^{n-1}&1&\omega&\cdots&\omega^{n-2} \end{pmatrix}A_2 \\=\omega^{-1} \begin{pmatrix} 1&\omega&\omega^2&\cdots&\omega^{n-1} \end{pmatrix}A_2 \\=\omega^{-1}F_2A_2 \end{array} F2​A1​=(1​ω​ω2​⋯​ωn−1​)⎝⎜⎜⎜⎜⎜⎛​a1​a2​a3​⋮an​​⎠⎟⎟⎟⎟⎟⎞​=(ωn−1​1​ω​⋯​ωn−2​)⎝⎜⎜⎜⎜⎜⎛​an​a1​a2​⋮an−1​​⎠⎟⎟⎟⎟⎟⎞​=(ωn−1​1​ω​⋯​ωn−2​)A2​=ω−1(1​ω​ω2​⋯​ωn−1​)A2​=ω−1F2​A2​​

同理可得： F 1 A 1 = F 1 A 2 = F 1 A 3 = ⋯ = F 1 A n F 2 A 1 = ω − 1 F 2 A 2 = ω − 2 F 2 A 3 = ⋯ = ω − ( n − 1 ) F 2 A n F 3 A 1 = ω − 2 F 3 A 2 = ω − 4 F 3 A 3 = ⋯ = ω − 2 ( n − 1 ) F 3 A n … F n A 1 = ω − ( n − 1 ) F n A 2 = ω − 2 ( n − 1 ) F n A 3 = ⋯ = ω − ( n − 1 ) ( n − 1 ) F n A n \begin{array}{ll} F_1A_1=F_1A_2=F_1A_3=\dots=F_1A_n\\ F_2A_1=\omega^{-1}F_2A_2=\omega^{-2}F_2A_3=\dots=\omega^{-(n-1)}F_2A_n\\ F_3A_1=\omega^{-2}F_3A_2=\omega^{-4}F_3A_3=\dots=\omega^{-2(n-1)}F_3A_n\\ \dots\\ F_nA_1=\omega^{-(n-1)}F_nA_2=\omega^{-2(n-1)}F_nA_3=\dots=\omega^{-(n-1)(n-1)}F_nA_n\\ \end{array} F1​A1​=F1​A2​=F1​A3​=⋯=F1​An​F2​A1​=ω−1F2​A2​=ω−2F2​A3​=⋯=ω−(n−1)F2​An​F3​A1​=ω−2F3​A2​=ω−4F3​A3​=⋯=ω−2(n−1)F3​An​…Fn​A1​=ω−(n−1)Fn​A2​=ω−2(n−1)Fn​A3​=⋯=ω−(n−1)(n−1)Fn​An​​

这样我们可以将所有的 A 2 , A 3 , … , A n A_2,A_3,\dots,A_n A2​,A3​,…,An​全部用 A 1 A_1 A1​表示，就形成了等式右侧的情况，因此，完整证明过程如下：

F A B = ( F 1 A 1 F 1 A 2 F 1 A 3 … F 1 A n F 2 A 1 F 2 A 2 F 2 A 3 … F 2 A n F 3 A 1 F 3 A 2 F 3 A 3 … F 3 A n ⋮ ⋮ ⋮ ⋱ ⋮ F n A 1 F n A 2 F n A 3 … F n A n ) B = ( F 1 A 1 F 1 A 1 F 1 A 1 … F 1 A 1 F 2 A 1 ω F 2 A 1 ω 2 F 2 A 1 … ω n − 1 F 2 A 1 F 3 A 1 ω 2 F 3 A 1 ω 4 F 3 A 1 … ω 2 ( n − 1 ) F 3 A 1 ⋮ ⋮ ⋮ ⋱ ⋮ F n A 1 ω n − 1 F n A 1 ω 2 ( n − 1 ) F n A 1 … ω ( n − 1 ) ( n − 1 ) F n A 1 ) B = ( F 1 A 1 F 2 A 1 F 3 A 1 ⋱ F n A 1 ) ( 1 1 1 ⋯ 1 1 ω ω 2 ⋯ ω n − 1 1 ω 2 ω 4 ⋯ ω 2 ( n − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 ω n − 1 ω 2 ( n − 1 ) ⋯ ω ( n − 1 ) ( n − 1 ) ) B = ( F 1 A 1 F 2 A 1 F 3 A 1 ⋱ F n A 1 ) F B = d i a g ( F A 1 ) F B = ( F A ( : , 1 ) ) ⊙ ( F B ) \begin{array}{ll} FAB=\begin{pmatrix} F_1A_1&F_1A_2&F_1A_3&\dots&F_1A_n\\ F_2A_1&F_2A_2&F_2A_3&\dots&F_2A_n\\ F_3A_1&F_3A_2&F_3A_3&\dots&F_3A_n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ F_nA_1&F_nA_2&F_nA_3&\dots&F_nA_n\\ \end{pmatrix}B\\=\begin{pmatrix} F_1A_1&F_1A_1&F_1A_1&\dots&F_1A_1\\ F_2A_1&\omega F_2A_1&\omega^2 F_2A_1&\dots&\omega^{n-1} F_2A_1\\ F_3A_1&\omega^2F_3A_1&\omega^4F_3A_1&\dots&\omega^{2(n-1)}F_3A_1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ F_nA_1&\omega^{n-1}F_nA_1&\omega^{2(n-1)}F_nA_1&\dots&\omega^{(n-1)(n-1)}F_nA_1\\ \end{pmatrix}B\\= \begin{pmatrix} F_1A_1& & & & \\ &F_2A_1& & & \\ & &F_3A_1& & \\ & & &\ddots & \\ & & & &F_nA_1 \end{pmatrix}\begin{pmatrix} 1&1&1&\cdots&1\\ 1&\omega&\omega^2&\cdots&\omega^{n-1}\\ 1&\omega^2&\omega^4&\cdots&\omega^{2(n-1)}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega^{n-1}&\omega^{2(n-1)}&\cdots&\omega^{(n-1)(n-1)} \end{pmatrix}B \\=\begin{pmatrix} F_1A_1& & & & \\ &F_2A_1& & & \\ & &F_3A_1& & \\ & & &\ddots & \\ & & & &F_nA_1 \end{pmatrix}FB \\=diag(FA_1)FB \\=(FA(:,1))\odot(FB) \end{array} FAB=⎝⎜⎜⎜⎜⎜⎛​F1​A1​F2​A1​F3​A1​⋮Fn​A1​​F1​A2​F2​A2​F3​A2​⋮Fn​A2​​F1​A3​F2​A3​F3​A3​⋮Fn​A3​​………⋱…​F1​An​F2​An​F3​An​⋮Fn​An​​⎠⎟⎟⎟⎟⎟⎞​B=⎝⎜⎜⎜⎜⎜⎛​F1​A1​F2​A1​F3​A1​⋮Fn​A1​​F1​A1​ωF2​A1​ω2F3​A1​⋮ωn−1Fn​A1​​F1​A1​ω2F2​A1​ω4F3​A1​⋮ω2(n−1)Fn​A1​​………⋱…​F1​A1​ωn−1F2​A1​ω2(n−1)F3​A1​⋮ω(n−1)(n−1)Fn​A1​​⎠⎟⎟⎟⎟⎟⎞​B=⎝⎜⎜⎜⎜⎛​F1​A1​​F2​A1​​F3​A1​​⋱​Fn​A1​​⎠⎟⎟⎟⎟⎞​⎝⎜⎜⎜⎜⎜⎛​111⋮1​1ωω2⋮ωn−1​1ω2ω4⋮ω2(n−1)​⋯⋯⋯⋱⋯​1ωn−1ω2(n−1)⋮ω(n−1)(n−1)​⎠⎟⎟⎟⎟⎟⎞​B=⎝⎜⎜⎜⎜⎛​F1​A1​​F2​A1​​F3​A1​​⋱​Fn​A1​​⎠⎟⎟⎟⎟⎞​FB=diag(FA1​)FB=(FA(:,1))⊙(FB)​

圆满收工

循环矩阵的傅里叶对角化

利用上面证明的原理我们可以得到另一个非常有意思的结论：

离散傅立叶变换矩阵DFT的列向量是循环矩阵的特征向量。

这次我们将A行向量表示为 A 1 ， A 2 , … , A n A_1，A_2,\dots,A_n A1​，A2​,…,An​. F的列向量表示为 F 1 ， F 2 , … , F n F_1，F_2,\dots,F_n F1​，F2​,…,Fn​.

A = ( — A 1 — — A 2 — — A 3 — ⋮ ⋮ ⋮ — A n — ) A=\begin{pmatrix} —&A_1&—\\ —&A_2&—\\ —&A_3&—\\ \vdots&\vdots&\vdots\\ —&A_n&— \end{pmatrix} A=⎝⎜⎜⎜⎜⎜⎛​———⋮—​A1​A2​A3​⋮An​​———⋮—​⎠⎟⎟⎟⎟⎟⎞​

F = ( ∣ ∣ ∣ ⋯ ∣ F 1 F 2 F 3 ⋯ F n ∣ ∣ ∣ ⋯ ∣ ) F=\begin{pmatrix} \mid&\mid&\mid&\cdots&\mid\\ F_1&F_2&F_3&\cdots&F_n\\ \mid&\mid&\mid&\cdots&\mid \end{pmatrix} F=⎝⎛​∣F1​∣​∣F2​∣​∣F3​∣​⋯⋯⋯​∣Fn​∣​⎠⎞​

依旧举第二列为例子： A F 2 = ( A 1 F 2 A 2 F 2 A 3 F 2 ⋮ A n F 2 ) = ( A 1 F 2 ω A 1 F 2 ω 2 A 1 F 2 ⋮ ω n − 1 A 1 F 2 ) = A 1 F 2 ( 1 ω ω 2 ⋮ ω n − 1 ) = ( A 1 F 2 ) F 2 AF_2=\begin{pmatrix} A_1F_2\\ A_2F_2\\ A_3F_2\\ \vdots\\ A_nF_2 \end{pmatrix}=\begin{pmatrix} A_1F_2\\ \omega A_1F_2\\ \omega^2 A_1F_2\\ \vdots\\ \omega^{n-1} A_1F_2 \end{pmatrix} =A_1F_2\begin{pmatrix} 1\\ \omega\\ \omega^2\\ \vdots\\ \omega^{n-1} \end{pmatrix}= (A_1F_2)F_2 AF2​=⎝⎜⎜⎜⎜⎜⎛​A1​F2​A2​F2​A3​F2​⋮An​F2​​⎠⎟⎟⎟⎟⎟⎞​=⎝⎜⎜⎜⎜⎜⎛​A1​F2​ωA1​F2​ω2A1​F2​⋮ωn−1A1​F2​​⎠⎟⎟⎟⎟⎟⎞​=A1​F2​⎝⎜⎜⎜⎜⎜⎛​1ωω2⋮ωn−1​⎠⎟⎟⎟⎟⎟⎞​=(A1​F2​)F2​ 这就证明了 F 2 F_2 F2​是A的一个特征向量，其对应的特征值为: ( A 1 F 2 ) (A_1F_2) (A1​F2​).其他列向量的证明方式与之同理。

因此通过离散傅里叶矩阵，我们可以轻易将循环矩阵对角化( F H F^H FH代表共轭转置)： F H A F = d i a g ( A 1 F 1 , A 1 F 2 , … , A 1 F n ) F^HAF=diag(A_1F_1,A_1F_2,\dots,A_1F_n) FHAF=diag(A1​F1​,A1​F2​,…,A1​Fn​)

后言

所证明的公式源自：

Misha E. Kilmer, Karen Braman, Ning Hao and Randy C. Hoover, “Third Order Tensors as Operators on Matrices: A Theoretical and Computational Framework with Applications in Imaging,” SIAM J. on Matrix Analysis and Applications, 34(1), pages 148-172, 2013.

是该论文中描述的t-product积的性质之一，原文中的描述为：

Given a , b ∈ K n a,b\in\mathbb{K}_n a,b∈Kn​ , a ∗ b a*b a∗b can be computed as a ∗ b : = i f f t ( a ^ ⊙ b ^ , [ ] , 3 ) a*b: = ifft(\hat{a} \odot \hat{b},[],3) a∗b:=ifft(a^⊙b^,[],3)

where ⊙ \odot ⊙ of two tubal scalars means pointwise multiplication. ∗ * ∗ means t-product: A ∗ B = f o l d ( b c i r c ( A ) ⋅ u n f o l d ( B ) ) \mathcal{A} *\mathcal{B} =fold(bcirc(\mathcal{A})\cdot unfold(\mathcal{B})) A∗B=fold(bcirc(A)⋅unfold(B))