【线性代数07】马尔科夫矩阵和傅里叶矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了【线性代数07】马尔科夫矩阵和傅里叶矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本篇可以看作对行列式和特征值应用的举例。但我会谈些我感兴趣的部分，即离散信源信道模型和循环矩阵的对角化。

马尔科夫矩阵

这个矩阵从概率论中概率的定义生发，因此各元素实际上就是非负的概率值。马尔科夫矩阵（Markov matrix）又称概率矩阵（probability matrix）、转移概率矩阵（transition probability matrix）,在英语数学文献中的惯例是用概率的行向量和概率的右随机矩阵，于是参照维基百科上给出定义：

随机矩阵描述了一个有限状态空间 $S$ 上的马尔科夫链 $X_t$ ，如果在一个时间步长内从 $i$ 到 $j$ 移动的概率为 $Pr(j|i)=P_{i,j}$ ，随机矩阵 $P$ 的第 $i$ 行、第 $j$ 列元素由 $P_{i,j}$ 给出：
$P=\left[{\begin{matrix}P_{1,1}&P_{1,2}&\dots &P_{1,j}&\dots &P_{1,S}\\P_{2,1}&P_{2,2}&\dots &P_{2,j}&\dots &P_{2,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{i,1}&P_{i,2}&\dots &P_{i,j}&\dots &P_{i,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{S,1}&P_{S,2}&\dots &P_{S,j}&\dots &P_{S,S}\\\end{matrix}}\right].}{\displaystyle$

性质

一个显而易见的结论是矩阵 $P$ 有特征值 $1$ ~~（对应的是右随机矩阵，其中每一行求和为1，若每一列求和为1，取转置验证即可，理同）~~ ，即
$Px=1\cdot x$
基于概率的完备性和可列可加性，可以验证，或言之，由于转移的这个过程是必然发生的，因此各概率的和为1。

从一个概率空间转移到另一个概率空间，概率的完备性、非负性、可列可加性仍旧成立。因此如果 $A 、 B$ 为两个 $n\times n$ 的转移矩阵，则其乘积（概率转移）、幂（自身演化）、算术平均仍旧是转移矩阵，即
$AB、\ \ A^n、 \ \ \frac{A+B}{2}$

让我们来思考下 $A^n$ 当 $\rightarrow \infty$ 时的场景，可证 $A$ 的最大特征值就是1，其余特征值的绝对值均小于1，因此 $A^n$ 其实将趋于由 $\lambda=1$ 所表征的那个稳态。

离散信源信道模型

学过《信息论》的朋友应该对类似形式的转移矩阵并不陌生，因此我们用一个离散的信源信道模型作为举例。准确地说，信源可描述为一个概率矩阵。所谓信源分布，即各发送信号各自占据一定的发射可能性。 如用行向量 $P_X$ 来描述一个三元等可能性的信源分布，即
$P_X=\begin{bmatrix} 1/3 & 1/3 & 1/3 \end{bmatrix}$
假设我们面临这样一个信道转移模型
【线性代数07】马尔科夫矩阵和傅里叶矩阵
则相应的信道转移矩阵为
$P_{ij}=\begin{bmatrix} 0.8 & 0.2 \\ 0.5 & 0.5 \\ 0.2 & 0.8 \end{bmatrix} \ \ 行i(X的概率空间)→列j(Y的概率空间)$
于是有信宿的概率分布为
$P_Y=P_XP_{ij}=\begin{bmatrix} 1/3 & 1/3 & 1/3 \end{bmatrix}\begin{bmatrix} 0.8 & 0.2 \\ 0.5 & 0.5 \\ 0.2 & 0.8 \end{bmatrix} =\begin{bmatrix} 0.5 & 0.5 \end{bmatrix}$
但其实我们往往是面临这个问题，求信道的容量 $C$ 为？
$C=\max [H(Y)-H(Y|X)]$
而已知
$\le H(0.5,0.5)=1比特， \ \ \ H(Y|X) \ge H(0.2,0.8)=0.7219比特$
而当两式均取等时，对应的信源分布为
$P_X=\begin{bmatrix} 1/2 & 0 & 1/2 \end{bmatrix}$
于是信道容量也就等于
$C = H (0.5, 0.5) - H (0.2, 0.8) = 0.2781 比特$
这给人的直观感觉是，选取信道的转移概率越偏离0.5越好，等可能性差错的传输是无效的。

傅里叶矩阵

选一组基底

傅里叶变换是信号处理中的经典操作，对照小波变换，其差异即在于所取基函数的不同。那么怎样选取基函数会让人觉得舒服呢？答案之一是选取一组标准正交基。如此，当我们将这些基向量排列在一起组成变换矩阵时，矩阵就会是一个正规矩阵，而其逆就是其共轭转置。

老爷子说了这样一句话，“I need infinitely many, because my space is infinite dimensional.”，也就是说，无穷维的空间要用无穷维的基去描述。那么对于n维空间，其实我们就用n个标准正交基，即
$v=x_1q_1+x_2q_2+\cdots+x_iq_i+\cdots+x_nq_n$
其中 $x_i$ 表示对应基底 $q_i$ 上的延展系数。如何求得这个系数呢？这就要体现出标准正交性的巧妙了，令两边同乘共轭转置向量即可
$q_i^Hv=x_1q_i^Hq_1+x_2q_i^Hq_2+\cdots+x_iq_i^Hq_i+\cdots+x_nq_i^Hq_n=x_i$
此时由于彼此正交将得到0，由于自身标准化将得到1，从而方便求得系数 $x_i$ 。

值得说明的是，正交性是十分有用的。在信号分析中，熟悉的傅里叶级数即采用了正交的三角函数作为基底，即 $\sin(nx)$ 和 $\cos(nx)$ ，可以验证它们在单周期内的积分为0，也即正交，这种正交的思想也是OFDM子载波选取的原则。

傅里叶矩阵

参照维基百科，给出傅里叶矩阵的定义。

N点的离散傅立叶变换可以用一个 $n\times m$ 的矩阵乘法来表示，即 $X = F x$ ，其中 $x$ 是原始的输入信号， $X$ 是经过离散傅立叶变换得到的输出信号。 一个 $n\times n$ 的变换矩阵 $F$ 可以定义成 $F=(\omega ^{{ij}})_{{i,j=0,\ldots ,N-1}}/{\sqrt {N}}$ ，即
$F={\frac {1}{\sqrt {N}}}{\begin{bmatrix}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 &&\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\\\end{bmatrix}}$

其中 $w$ 定义为 $1$ 的 $n$ 次方根的主值 ，即
$w=e^{\frac{-2\pi i}{N}}$
注意到对于某列 $j$ 来说，其列向量为：
$q_j=\begin{bmatrix} w^{\alpha \times (j-1)} \end{bmatrix}^T/\sqrt{N} \ \ \ \ \ \alpha=0,1,2,\cdots,N-1$
此时我们再取另一列 $q_{j+k}$ ，令两者作内积，就有
$q_{j+k}^Hq_{j}=\frac{1}{N} \sum_{\alpha = 0}^{N-1} w^{\alpha \times (j-1)}w^{-\alpha \times (j+k-1)}= \sum_{\alpha = 0}^{N-1}w^{-\alpha k}$
当 $k = 0$ 时，即在求自身模值的平方，可知此时内积的结果为1，验证了标准性。
而当 $\ne 0$ 时，可知 $w^{-k}$ 是一个 $N$ 次的单位根，而 $\alpha$ 这个系数起到了在单位圆上旋转的作用 。不如举 $- k = 1$ 为例，则此时可以想到当 $\alpha$ 从 $0$ 遍取完 $N - 1$ 时，这 $N$ 个结果将重新组成单位圆上 $1$ 的 $N$ 个 $N$ 次单位根。于是问题变成了，为什么这 $N$ 个单位根的和为 $0$ ？在百度百科上给出了这三种解释：

一个基本方法是等比级数的求和，即 $\sum_{\alpha = 0}^{\infty} w^{\alpha} = \frac{1-w^N}{1-w}=0$
第二个证法是它们在复平面上构成正多边形的顶点，而由对称性可知多边形的重心在原点。最后一个证法利用关于方程根与系数的韦达定理，由分圆方程 $x_{n-1}$ 项但系数为零得出。

无论采用哪种解释，结论是一致的，即 $\ne 0$ 时，内积的结果为0，从而验证了正交性。那么，傅里叶矩阵是一个正规矩阵，一个优良的性质就产生了，即
$F^{-1}=F^H$

FFT开销 N l o g 2 N / 2 Nlog_2N/2 Nlog2N/2 的说明

先从理论角度说明。在数字信号处理中，我们知道有两种典型思路来完成FFT，一种是时间抽选DIT，另一种是频率抽选DIF，经过一次分序后，两种方法都将减少一半的运算量。
对于DIT而言，对 $x (n)$ 序列的奇偶进行分序，结果输出 $X (k)$ 为前一半后一半。
【线性代数07】马尔科夫矩阵和傅里叶矩阵

对于DIF而言，是对 $x (n)$ 序列的前一半后一半进行分序，结果输出 $X (k)$ 分奇和偶。

【线性代数07】马尔科夫矩阵和傅里叶矩阵

又知DFT运算的定义为
$X(k)=\sum_{n=0}^{N-1} x(n)w_{N}^{nk}, k = 0,1,\cdots,N-1$

在运算中，乘法的运算开销是最大的。对于 $N$ 点的DFT而言，其矩阵乘法开销为N，一共有N点，开销估计为 $N^2$ ，而FFT使得最终转换成了 $log_2N$ 级的蝶形运算，每级采用蝶形运算后所用的乘法开销均为 $N /2$ （即每两个可共用一次系数，节约一半计算量），从而总开销为 $Nlog_2N/2$ 。

现在我们从矩阵变换的视角理解上述过程，来看展示一个64点的FFT转为32点FFT的过程：
$F_{64}=\begin{bmatrix} I &D_{32} \\ I &-D_{32} \end{bmatrix}\begin{bmatrix} F_{32} &0 \\ 0 & F_{32} \end{bmatrix} \begin{bmatrix} \colorbox{yellow}1& 0 &0 &0 &\cdots & 0 & 0\\ 0 & 0 & \colorbox{yellow}1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & \colorbox{yellow}1 & 0 \\ 0 & \colorbox{aqua}1 & 0 & 0 &\cdots & 0 & 0 \\ 0 & 0 & 0 & \colorbox{aqua}1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & \colorbox{aqua}1 \end{bmatrix} \ \ \ \colorbox{yellow}{odd \ rows} \ \ \ \colorbox{aqua}{even \ rows}$
其中 $D_{32}$ 为用于修正的对角矩阵，元素为熟悉的修正因子 $w$ ，我们可以发现其正是蝶形运算中的修正系数 ，即
$D_{32} = \begin{bmatrix} w^0 & 0 & 0 & 0& \cdots \\ 0 & w^1 & 0 & 0 &\cdots \\ 0 & 0 & w^2 & 0& \cdots \\ \vdots & \vdots &\vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & w^{31} \end{bmatrix}$
最右端的矩阵为交换矩阵 $P_{64}$ ，实现奇偶分序的作用 。观察这个过程，我们发现增加的乘法开销主要在 $D_{32}$ ，故该级分解后运算量转换为两个 $F_{32}$ 的乘法计算量和一个 $D_{32}$ 的乘法运算量。依次类推， $F_{32}$ 也可以继续向下分解为 $F_{16} \cdots$ 于是最后得到的基本元素块将是 $F_2$ ，展现如下
$\begin{bmatrix} I &D_{32} \\ I &-D_{32} \end{bmatrix} \begin{bmatrix} \begin{matrix} I & D_{16} \\ I & D_{16} \end{matrix} & \text{\Large 0} \\ \text{\Large 0} & \begin{matrix} I & D_{16} \\ I & -D_{16} \end{matrix} \end{bmatrix} \cdots \begin{bmatrix} \begin{matrix} I & D_{1} & \\ I & D_{1} & \\ & & \ddots \end{matrix} &\text{\Large 0} \\ \text{\Large 0} & \begin{matrix} I & D_{1} \\ I & -D_{1} \end{matrix} \end{bmatrix} \begin{bmatrix} \begin{matrix} F_2& \\& \ddots \end{matrix} & \text{\Large 0} \\ \text{\Large 0} & \begin{matrix} F_{2} \end{matrix} \end{bmatrix} \begin{bmatrix} \begin{matrix} P_2& \\& \ddots \end{matrix} & \text{\Large 0} \\ \text{\Large 0} & \begin{matrix} P_{2} \end{matrix} \end{bmatrix} \cdots \begin{bmatrix}P_{32} & 0 \\ 0 & P_{32} \end{bmatrix} \begin{bmatrix}P_{64} \end{bmatrix}$
由此可见，修正矩阵共有 $log_2N$ 级，每级有 $N /2$ 次乘法运算。因而最终运算开销为 $Nlog_2N/2$ 。来直观感受下运算量的缩减，以 $N = 1024$ 为例，有
$\frac{N^2}{Nlog_2N/2}=\frac{1024^2}{1024*5} \approx 205$
由此可见，FFT为傅里叶变换处理的高性能提供了可能。

循环矩阵对角化的说明

这个说明的背景是OFDM中的循环前缀，参照维基百科，先来看定义

形式为 $A={\begin{bmatrix}c_{0}&c_{n-1}&c_{n-2}&\dots &c_{1}\\c_{1}&c_{0}&c_{n-1}& \cdots &c_{2}\\c_{2}&c_{1}&c_{0}&\cdots &c_3 \\\vdots &\vdots& \vdots&\ddots &\vdots \\c_{n-1}&c_{n-2}&c_{n-3}&\dots &c_{0}\end{bmatrix}}$ 的矩阵就是循环矩阵。

我们关注这条性质：循环矩阵的特征向量矩阵是同样维数的离散傅立叶变换矩阵，因此循环矩阵的特征值可以很容易地通过快速傅立叶变换计算出来，或言为循环矩阵可被傅里叶矩阵对角化，即：
$AF=F\Lambda \Rightarrow \Lambda=F^HA F或 A = F\Lambda F^{H}$
让我们来浅浅地证明一下，预备条件主要有3个：一是DFT的定义，二是其时域循环移位性质，三是对称性。即
$条件1：X(k)=\sum_{n=0}^{N-1} x(n)w_{N}^{nk}, k = 0,1,\cdots,N-1 \\ 条件2：x((n+m))_N R_N(n) \Leftrightarrow w_N^{-km}X(k) \\ 条件3:x(N-n) \Leftrightarrow X(N-k)$
取第二行为例，可以看到
$c_1w^{0 \times 1} +c_0w^{1\times 1}+c_{N-1}w^{2 \times 1}+\cdots+c_2w^{N-1\times1}=\sum_{n=0}^{N-1}c((N-n+1))_NR_{N}(n)w^{n \times 1}=w^{-1 \times 1} \ \sum_{n=0}^{N-1}c((N-n))_NR_{N}(n)w^{n \times 1}=C(N-1)w^{-1 \times 1} \ \ 此时k=1$
依此类推，我们可以知道 $i$ 就是移位的 $m$ ， $i$ 也是DFT结果中的 $k$ ， $j$ 相当于序列号 $n$ 。
$\sum_{j=0}^{N-1}c((N-j+i))_N R_{N}(n) w^{j \times i}=C((N-i))_NR_{N}(n) w^{-i^2} \ \ \ \ i(k,m),j(n)=0,1,2,\cdots,N-1$
将上述形式写成矩阵，即有
$\begin{bmatrix}c((N-j+i))_N R_{N}(n) \end{bmatrix} \begin{bmatrix}w^{i \times j} \end{bmatrix} = \begin{bmatrix}C((N-i))_NR_{N}(n) \end{bmatrix} \begin{bmatrix}w^{- i^2} \end{bmatrix}$
两边再同除 $\sqrt{N}$ 归一化，就可写成傅里叶矩阵的形式
$AF=\begin{bmatrix}C(0) & 0 & 0 & \cdots & 0 \\ 0 & C(N-1) &0 & \cdots & 0 \\ 0 & 0 & C(N-2) & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 &0 &C(1) \end{bmatrix} F^{H}=\Lambda F^H=HF^H$
由这个证明过程，我们还能看出第 $i$ 行输入信号序列 $c((N-j+i))_NR_{N}(n)$ ，对应输出的特征值为 $C((N-i))_NR_{N}(n)$ 。这样进行的目的在于可以将求信道响应相应的卷积运算转换为FFT运算，而FFT具有高性能的运算效率，或言之，此时的特征值对应了信道响应。由此可见，数字信号处理技术的进步为通信技术的进步打下基石，而这一切都需要数学。

注意，如果循环矩阵写成下列形式
$A={\begin{bmatrix}c_{0}&c_{1}&c_{2}&\dots &c_{n-1}\\c_{n-1}&c_{0}&c_{1}& \cdots &c_{n-2}\\c_{n-2}&c_{n-1}&c_{0}&\cdots &c_{n-3} \\\vdots &\vdots& \vdots&\ddots &\vdots \\c_{1}&c_{2}&c_{3}&\dots &c_{0}\end{bmatrix}}$
则求出的特征值即为 $C (i)$ ，这也是《Toeplitz and Circulant Matrices: A review》这本书中给出的举例矩阵。书中对循环矩阵的对角化给出了一般性的证明（第三章），所不同的是，我在此结合了DFT的性质更简便地谈了谈。文章来源地址https://www.toymoban.com/news/detail-443244.html