循环矩阵与傅立叶矩阵

原题: 016_Fourier_compose

背景

设想有一圈首尾相连的传感器，沿环形轨道等间距排开。我们记录到一组长度为 $N$ 的离散信号

$$x=(x_0,x_1,\ldots,x_{N-1})^\mathrm{T},$$

现在对它做一个最朴素的平滑操作: 每个位置都拿自己的值和右边相邻位置的值取平均。由于系统是首尾相连的，所以最后一个点的右邻居会回到第一个点。

直观上，这样的操作会削弱跳动很快的“毛刺”，保留变化较慢的整体趋势。但如果我们把这个平均反复做很多次，最终到底会剩下什么? 为什么有些模式衰减得很快，有些模式却几乎不变?

本题的目标，就是把这个看似简单的平均过程写成一个线性变换，并借助傅立叶矩阵把它彻底分解开，从而理解离散信号处理中“低通滤波器”的数学本质。

相关知识点

定义循环移位变换 $S$ 为

$$(Sx)_n=x_{n+1 \, (\mathrm{mod}\ N)}, \qquad n=0,1,\ldots,N-1.$$

则“自己和右邻居取平均”的操作可以写成

$$T=\frac{1}{2}(I+S).$$

由于 $T$ 满足加法与数乘的线性性质，所以它是一个线性变换。真正关键的是，$S$ 具有非常强的环形平移对称性，因此最自然的研究方式，就是寻找它的特征向量。

令

$$\omega=e^{2\pi i/N},$$

则由各次单位根构成的向量会自然给出 $S$ 的特征向量，把这些特征向量按列排起来，就得到离散傅立叶矩阵 $F_N$。在傅立叶坐标下，循环移位矩阵和平均矩阵都会变成对角形式，于是

$$T^m$$

的行为也就变得一目了然: 高频模式被快速压低，低频模式相对保留，因此整个信号会越来越平滑。

题目

设 $N=4$，并记

$$\omega=e^{2\pi i/4}=i.$$

定义循环移位矩阵

$$S= \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}, \qquad T=\frac{1}{2}(I+S).$$

给定输入信号

$$x= \begin{pmatrix} 1 \\ 0 \\ -1 \\ 0 \end{pmatrix}.$$

请完成下列问题:

1. 说明为什么 $T$ 是线性变换。
2. 解释变换 $S$ 的含义，并说明为什么 $T=\frac{1}{2}(I+S)$ 可以表示“自己和右邻居取平均”。
3. 写出 $F_4$，并求出 $T$ 的傅立叶分解 $T=F_4 \Lambda F_4^\ast$。
4. 求信号 $x$ 的傅立叶系数 $\widehat{x}=F_4^\ast x$。
5. 利用傅立叶分解求 $Tx$。
6. 求 $T^m x$，并说明当 $m\to\infty$ 时它趋向什么。
7. 结合你的结果解释: 为什么“邻点平均”是一个低通滤波器?

下载题目文件

📥 下载《016_Fourier_compose.tmu》题目文件

提交要求：

1. 将答案写在《016_Fourier_compose.tmu》文件末尾
2. 重命名为：016_你的姓名_学校.tmu
3. 发送至：jiadong@liii.pro
4. 截止时间：本周日 23:59

奖品： 《数字信号处理引论：基于频谱和滤波器的分析方法》（首位答对者将获得特别奖品，所有答对者获得一个月 Liii STEM 会员）

参与方式： 见主页

← 返回每周一题活动主页