循环矩阵的正交分解推导
OFDM系统的CP(Cyclic Prefix)原理涉及循环矩阵。循环矩阵可以被分解为正交分解。这也提供了理解离散卷积定理的一种角度。
定义
循环矩阵(circulant matrix)
- 矩阵的列为前一列循环后移一位的方阵
DFT矩阵
\[Q\triangleq\frac1{\sqrt N} \begin{pmatrix} W^0&W^1&\dots&W^{N-1}\\ W^0&W^2&\dots&W^{2(N-1)}\\ &&\vdots\\ W^0&W^{N-1}&\dots&W^{(N-1)(N-1)} \end{pmatrix}\\ W=e^{-2\pi i/N},\ i=\sqrt{-1}\]IDFT矩阵定义为DFT矩阵的共轭转置。
待证明内容可表示为
\[\begin{align*} H_C&=\begin{pmatrix} \boldsymbol H_{C_0}&\boldsymbol H_{C_1}&\dots&\boldsymbol H_{C_{N-1}} \end{pmatrix}\\ &=Q^H\Lambda Q\\ \Lambda&= \begin{pmatrix} \lambda_1\\ &\lambda_2\\ &&\ddots\\ &&&\lambda_N \end{pmatrix} \end{align*}\]特征矩阵
- IDFT矩阵的列向量为任意循环矩阵的特征向量，且特征值为循环矩阵第一列的DFT
证明：
定义循环移位矩阵
\[P=\begin{pmatrix} 0&0&\dots&0&1\\ 1\\ &\ddots&&&\\ &&1&&\\ &&&1& \end{pmatrix}\]具有将输入向量向后圆移一位的性质。则
\[P^2=\begin{pmatrix} 0&\dots&0&1&0\\ &&&&1\\ 1\\ &\ddots\\ &&1 \end{pmatrix} ,\space P^{N-1}=\begin{pmatrix} 0&1&0&\dots&0\\ &&1\\ &&&\ddots&\\ &&&&1\\ 1 \end{pmatrix}\]- IDFT矩阵的列向量为循环移位矩阵的特征向量
证明：
P的特征值λ为
\[\begin{align*} |\lambda E-P|&=\lambda^N-1\\ &=\prod_{i=1,2,\dots,N}(\lambda-e^{2\pi i/N})\\ \lambda_i&=e^{2\pi i/N},i=1,2,\dots,N \end{align*}\]在复平面单位圆上均匀分布。
考虑到P的循环移位性质，可知P的特征向量具有循环移位等于乘以一复常数的性质：
\[\begin{align*} P\boldsymbol V_i&=\lambda_i\boldsymbol V_i\\ \begin{pmatrix}v_n\\ v_1\\ \vdots\\ v_{n-1}\end{pmatrix} &=e^{2\pi i/N}\begin{pmatrix}v_1\\ v_2\\ \vdots\\ v_{n}\end{pmatrix} \end{align*}\]可以推知，V应为单位圆上匀速旋转的点构成的复序列，旋转速度为对应的特征值的共轭。
则IDFT矩阵的列向量为P的特征向量。
则有
\[PQ^H=\begin{pmatrix}W^0\boldsymbol Q_0&W^1\boldsymbol Q_1&\dots&W^{N-1}\boldsymbol Q_{N-1}\end{pmatrix}\]对任意循环矩阵Hc，有
\[H_C=a_0I+a_1P+a_2P^2+\dots+a_{N-1}P^{N-1}\]循环矩阵第一列的DFT为
\[Q^H\boldsymbol H_{C0}=\begin{pmatrix} a_0+a_1+\dots+a_{N-1}\\ a_0+a_1W^1+\dots+a_{N-1}W^{N-1}\\ \vdots\\ a_0+a_1W^{N-1}+\dots+a_{N-1}W^{(N-1)(N-1)} \end{pmatrix} =\begin{pmatrix} A_0\\ A_1\\ \vdots\\ A_{N-1} \end{pmatrix}\]IDFT矩阵列向量作为$H_C$矩阵的特征向量时，特征值为
\[H_C\boldsymbol Q_{k}=(a_0+a_1W^k+a_2W^{2k}+\dots+a_{N-1}W^{(N-1)k})\boldsymbol V_k =A_k\boldsymbol Q_k\] \[\begin{align} H_CQ^H&=\begin{pmatrix}A_0\boldsymbol Q_0&A_1\boldsymbol Q_1&\dots&A_{N-1}\boldsymbol Q_{N-1}\end{pmatrix}\\ &=Q^H\begin{pmatrix}A_0\\&A_1\\&&\ddots\\&&&A_{N-1}\end{pmatrix}\\ H_C&=Q^H\begin{pmatrix}A_0\\&A_1\\&&\ddots\\&&&A_{N-1}\end{pmatrix}(Q^H)^{-1}\\ &=Q^H\begin{pmatrix}A_0\\&A_1\\&&\ddots\\&&&A_{N-1}\end{pmatrix}Q \end{align}\]当Q为正交矩阵时，式（4）成立。
显然离散傅立叶变换和逆变换互为逆过程，则DFT矩阵和IDFT矩阵是一对逆矩阵，故证明完毕。
分析
循环矩阵可视为托普利兹矩阵(Toeplitz matrix)（对角线元素相同的矩阵）的一种特例，两种矩阵分别对应循环卷积和线性卷积。
DFT矩阵和IDFT矩阵实际上由相同的列向量以不同顺序构成，故DFT矩阵也可将任意循环矩阵相似对角化。
本文给出了离散卷积定理的一种证明方式。离散卷积定理指两序列的循环卷积的离散傅立叶变换等于各自的变换序列对应值相乘。
离散卷积定理将循环卷积转化为频谱相乘，结合FFT算法，可将计算复杂度从O(N^2)降至O(Nlog_2N)，在信号和图像处理中均有重要意义。
从结论重新理解性质。IDFT矩阵的列向量是复指数函数，频谱为冲激函数，与任意函数相乘等于乘以一复常数，故其为循环矩阵的特征向量，特征值为该频点值。
附录
证明DFT矩阵为正交矩阵。
先给出正交矩阵一基本性质
正交性
- 正交矩阵的充要条件为矩阵的列向量两两正交且自内积为1（规范正交基）。
证明：
\[\begin{align*} I&=M^{-1}M=M^HM\\ \Leftrightarrow \boldsymbol Q_j\boldsymbol Q_k^\ast&= \begin{cases} 1,j=k\\ 0,j\neq k \end{cases} \end{align*}\]证法1
\[\begin{align*} \boldsymbol Q_k\boldsymbol Q_k^\ast&=1\\ \boldsymbol Q_k\boldsymbol Q_j^\ast&=W^{0}+W^{j-k}+W^{2(j-k)}+\dots+W^{(N-1)(j-k)}\\ W^{j-k}\boldsymbol Q_k\boldsymbol Q_j^\ast&=W^{j-k}+W^{2(j-k)}+\dots+W^{N(j-k)}\\ &=\boldsymbol Q_k\boldsymbol Q_j^\ast\\ \therefore\boldsymbol Q_k\boldsymbol Q_j^\ast&=0 \end{align*}\]证法2
可由正规矩阵/实对称矩阵的性质得出。
正规矩阵指与自身的共轭转置矩阵满足乘法交换律的矩阵。即
\[MM^H=M^HM\]正规矩阵存在N个相互正交的特征向量，证明略。
显然N阶循环矩阵为实对称矩阵 ，故为正规矩阵。
由结论2证明可知，N阶循环矩阵仅有N个特征向量，即为DFT矩阵的N个列向量。故DFT矩阵为正交矩阵。
参考资料
- Gilbert Strang. MATRIX METHODS IN DATA ANALYSIS, SIGNAL PROCESSING, AND MACHINE LEARNING(lecture 31, lecture 32)
- 郑宝东，王忠英(2013). 线性代数与空间解析几何