EE261 Lecture 28

课程主页：https://see.stanford.edu/Course/EE261

这次回顾第二十八讲，这一讲介绍了高维傅里叶变换的性质以及高维傅里叶序列。

性质

线性性

$$\mathcal{F}(\alpha f+\beta g)(\xi)=\alpha \mathcal{F} f(\xi)+\beta \mathcal{F} g(\xi)$$

平移性

• 如果$f(\mathrm{x}) \rightleftharpoons F(\xi)$，那么$f(\mathbf{x} \pm \mathbf{b}) \rightleftharpoons e^{ \pm 2 \pi i \mathbf{b} \cdot \xi} F({\xi})$

以二维情形证明该结论：

$$\begin{aligned} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-2 \pi i\left(x_{1} \xi_{1}+x_{2} \xi_{2}\right)} f\left(x_{1}+b_{1}, x_{2}+b_{2}\right) d x_{1} d x_{2} =& \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-2 \pi i\left(\left(u-b_{1}\right) \xi_{1}+\left(v-b_{2}\right) \xi_{2}\right)} f(u, v) d u d v \\ =& \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{2 \pi i b_{1} \xi_{1}} e^{2 \pi i b_{2} \xi_{2}} e^{-2 \pi i\left(u \xi_{2}+v \xi_{2}\right)} f(u, v) d u d v \\ =&e^{2 \pi i\left(b_{1} \xi_{1}+b_{2} \xi_{2}\right)} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-2 \pi i\left(u \xi_{2}+v \xi_{2}\right)} f(u, v) d u d v \\ =&e^{2 \pi i\left(b_{1} \xi_{1}+b_{2} \xi_{2}\right)} \mathcal{F} f\left(\xi_{1}, \xi_{2}\right) \end{aligned}$$

伸缩

假设$A$为可逆矩阵，那么

$$\mathcal{F}(f(A \mathbf{x}))=\frac{1}{|\operatorname{det} A|} \mathcal{F} f\left(A^{-\top} \boldsymbol{\xi}\right)$$

证明：

$$\begin{aligned} \int_{\mathbf{R}^{n}} e^{-2 \pi i \xi \cdot \mathbf{x}} f(A \mathbf{x}) d \mathbf{x} &=\int_{\mathbf{R}^{n}} e^{-2 \pi i \xi \cdot A^{-1}(A \mathbf{x})} f(A \mathbf{x}) \frac{1}{|\operatorname{det} A|}|\operatorname{det} A| d \mathbf{x} \\ &=\frac{1}{|\operatorname{det} A|} \int_{\mathbf{R}^{n}} e^{-2 \pi i \xi \cdot A^{-1}(A \mathbf{x})} f(A \mathbf{x})|\operatorname{det} A| d \mathbf{x} & u=A\mathbf x\\ &=\frac{1}{|\operatorname{det} A|} \int_{\mathbf{R}^{n}} e^{-2 \pi i \xi \cdot A^{-1} \mathbf{u}} f(\mathbf{u}) d \mathbf{u} \end{aligned}$$

对于内积，我们有如下性质

$$\begin{aligned} \xi \cdot B \mathbf{u} &=\xi^\top B u\\ &= (B^{\top} {\xi})^{\top} u\\ &=B^{\top} {\xi} \cdot \mathbf{u} \end{aligned}$$

所以

$${\xi} \cdot A^{-1} \mathbf{u}=A^{-\top} {\xi} \cdot \mathbf{u}$$

代入原式可得

$$\frac{1}{|\operatorname{det} A|} \int_{\mathbf{R}^{n}} e^{-2 \pi i \xi \cdot A^{-1} \mathbf{u}} f(\mathbf{u}) d \mathbf{u}=\frac{1}{|\operatorname{det} A|} \int_{\mathbf{R}^{n}} e^{-2 \pi i A^{-\top} \xi \cdot \mathbf{u}} f(\mathbf{u}) d \mathbf{u}$$

综上，

$$\mathcal{F}(f(A \mathbf{x}))=\frac{1}{|\operatorname{det} A|} \mathcal{F}(f)\left(A^{-\top} \xi\right)$$

伸缩和平移

这部分计算

$$\mathcal{F}(f(A \mathbf{x}+\mathbf{b}))$$

我们有如下结论：

$$\mathcal{F}(f(A \mathrm{x}+\mathrm{b}))=\exp \left(2 \pi i \mathrm{b} \cdot A^{-\top} \xi\right) \frac{1}{|\operatorname{det} A|} \mathcal{F} f\left(A^{-\top} \xi\right)$$

证明：

令

$$g(\mathbf{x})=f(A \mathbf{x})$$

那么

$$f(A \mathbf{x}+\mathbf{b})=f\left(A\left(\mathbf{x}+A^{-1} \mathbf{b}\right)\right)=g\left(\mathbf{x}+A^{-1} \mathbf{b}\right)$$

取傅里叶变换得到

$$\mathcal{F}\left(g\left(\mathrm{x}+A^{-1} \mathrm{b}\right)\right)=\exp \left(2 \pi i A^{-1} \mathrm{b} \cdot \xi\right)(\mathcal{F} g)(\xi)=\exp \left(2 \pi i \mathrm{b} \cdot A^{-\top} \xi\right)(\mathcal{F} g)(\xi)$$

另一方面，利用伸缩定理可得

$$\mathcal{F} g(\xi)=\mathcal{F}(f(A \mathbf{x}))=\frac{1}{|\operatorname{det} A|} \mathcal{F} f\left(A^{-\top} \boldsymbol{\xi}\right)$$

卷积

$n$维卷积的形式和一维情形一致：

$$(f * g)(\mathrm{x})=\int_{\mathbf{R}^{n}} f(\mathrm{x}-\mathrm{y}) g(\mathrm{y}) d \mathrm{y}$$

和一维情形类似，我们有

$$\begin{aligned} \mathcal{F}(f * g)({\xi})&=\mathcal{F} f({\xi}) \mathcal{F} g({\xi})\\ \mathcal{F}(f g)(\xi)&=(\mathcal{F} f * \mathcal{F} g)(\xi) \end{aligned}$$

$\delta$函数及其性质

$n$维情形的$\delta$函数同样可以用分布理论解释，这里首先给出定义。

定义$n$维$\delta$函数为

$$\delta\left(x_{1}, x_{2}, \dots, x_{n}\right)=\delta_{1}\left(x_{1}\right) \delta_{2}\left(x_{2}\right) \cdots \delta_{n}\left(x_{n}\right)$$

定义

$$\delta(\mathrm{x}-\mathrm{b})=\delta\left(x_{1}-b_{1}, x_{2}-b_{2},, \ldots, x_{n}-b_{n}\right)$$

和一维情形类似，我们有如下性质

$$\begin{aligned} \int_{\mathbf{R}^{n}} \varphi(\mathbf{x}) \delta(\mathbf{x}) d \mathbf{x}&=\varphi(0)\\ f(\mathbf{x}) \delta(\mathbf{x})&=f({0}) \delta(\mathbf{x})\\ (f * \delta)(\mathrm{x})&=f(\mathrm{x})\\ f(\mathrm{x}) \delta(\mathrm{x}-\mathrm{b})&=f(\mathrm{b}) \delta(\mathrm{x}-\mathrm{b}) \end{aligned}$$

$\delta$函数的傅里叶变换

$$\delta(\mathrm{x}-\mathrm{b}) \rightleftharpoons e^{-2 \pi i \mathrm{b}.\xi}$$

伸缩性

$$\delta\left(a_{1} x_{1}, \ldots, a_{n} x_{n}\right)=\frac{1}{\left|a_{1} \cdots a_{n}\right|} \delta\left(x_{1}, \ldots, x_{n}\right)$$

对2维情形证明该结论，注意我们有

$$\delta(a x)=\frac{1}{|a|} \delta(x)$$

所以

$$\begin{aligned} \delta\left(a_{1} x_{1}, a_{2} x_{2}\right) &=\delta_{1}\left(a_{1} x_{1}\right) \delta_{2}\left(a_{2} x_{2}\right) \\ &=\frac{1}{\left|a_{1}\right|} \delta_{1}\left(x_{1}\right) \frac{1}{\left|a_{2}\right|} \delta_{2}\left(x_{2}\right) \\ &=\frac{1}{\left|a_{1}\right|\left|a_{2}\right|} \delta_{1}\left(x_{1}\right) \delta_{2}\left(x_{2}\right)=\frac{1}{\left|a_{1} a_{2}\right|} \delta\left(x_{1}, x_{2}\right) \end{aligned}$$

如果$A$可逆，那么

$$\delta(A \mathbf{x})=\frac{1}{|\operatorname{det} A|} \delta(\mathbf{x})$$

证明：

利用分布以及变量代换证明上述结论。

$$\begin{aligned} \int_{\mathbf{R}^{n}} \delta(A \mathbf{x}) \varphi(\mathbf{x}) d \mathbf{x} &=\int_{\mathbf{R}^{n}} \delta(A \mathbf{x}) \varphi\left(A^{-1} A \mathbf{x}\right) \frac{1}{|\operatorname{det} A|}|\operatorname{det} A| d \mathbf{x}\\ &=\frac{1}{|\operatorname{det} A|} \int_{\mathbf{R}^{n}} \delta(\mathbf{u}) \varphi\left(A^{-1} \mathbf{u}\right) d \mathbf{u} & \mathbf{u}=A \mathbf{x}\\ &=\frac{1}{|\operatorname{det} A|} \varphi\left(A^{-1} \mathbf{0}\right)\\ &=\frac{1}{|\operatorname{det} A|} \varphi(0) \end{aligned}$$

高维傅里叶序列

首先定义高维周期函数，这里假设周期为$1$，设

$$\begin{aligned} \mathbf{x}&=\left(x_{1}, x_{2}, \dots, x_{d}\right) \\ \mathbf{n}&=\left(n_{1}, n_{2}, \dots, n_{d}\right)\in \mathbf Z^d\\ f(\mathrm{x})&=f\left(x_{1}, x_{2}, \ldots, x_{d}\right) \end{aligned}$$

那么$f$为周期函数，如果对所有的$\mathbf{n}$，我们有

$$f(\mathrm{x}+\mathrm{n})=f(\mathrm{x})$$

傅里叶序列

定义$d$维的傅里叶序列为

$$\sum_{\mathbf{n \in \mathbf Z^d}} c_{\mathrm{n}} e^{2 \pi i \mathbf{n} \cdot \mathbf{x}}$$

类似一维情形，可以将周期函数展开为傅里叶序列，其中系数为

$$\hat{f}(\mathbf{n})=\int_{[0,1]^{d}} e^{-2 \pi i \mathbf{n} \cdot \mathbf{x}} f(\mathbf{x}) d \mathbf{x}$$

应用

考虑等概率随机游走问题，假设维度$d$。随机游走是指每次只对某个坐标变动$\pm 1$，每一步是相互独立的，不失一般性，这里假设出发点为原点。以$3$维为例，每一步可走的step为

$$( \pm 1,0,0), \quad(0, \pm 1,0), \quad(0,0, \pm 1)$$

假设一共走了$n$步，那么

$$\text {walk}_{n}=\operatorname{step}_{1}+\operatorname{step}_{2}+\cdots+\operatorname{step}_{n}$$

即

$$\mathbf{w}_{n}=\mathbf{s}_{1}+\mathbf{s}_{2}+\cdots+\mathbf{s}_{n}$$

关于随机游走有如下定理：

定理

在$1$维和$2$维情形， 我们有

$$\operatorname{Prob}\left(\text { walk }_{n}=0 \text { infinitely often }\right)=1$$

对于$\ge 3$维，我们有

$$\operatorname{Prob}\left(\lim _{n \rightarrow \infty}\left|\operatorname{walk}_{n}\right|=\infty\right)=1$$

证明：

定义

$$\Phi_{n}=e^{2 \pi i \mathbf{w}_{n} \cdot \mathbf{x}}$$

那么

$$\mathbf E[\Phi_n] =\sum_{l} \operatorname{Prob}\left(\mathbf{w}_{n}=l\right) e^{2 \pi i l\cdot x}$$

注意到

$$\begin{aligned} \Phi_{n} &=e^{2 \pi i \mathbf{w}_{n} \cdot \mathbf{x}}\\ &=e^{2 \pi i\left(\mathbf{s}_{1}+\mathbf{s}_{2}+\cdots+\mathbf{s}_{n}\right) \cdot \mathbf{x}}\\ &=e^{2 \pi i \mathbf{s}_{1} \cdot \mathbf{x}} e^{2 \pi i \mathbf{s}_{2} \cdot \mathbf{x}} \ldots e^{2 \pi i \mathbf{s}_{n} \cdot \mathbf{x}} \end{aligned}$$

而由独立性可得

$$\begin{aligned} \operatorname{Prob}\left(\mathbf{s}_{1}=s_{1}, \mathbf{s}_{2}=s_{2}, \ldots, \mathbf{s}_{n}=s_{n}\right)=& \operatorname{Prob}\left(\mathbf{s}_{1}=s_{1}\right) \operatorname{Prob}\left(\mathbf{s}_{2}=s_{2}\right) \cdots \operatorname{Prob}\left(\mathbf{s}_{n}=s_{n}\right) \\ =& \frac{1}{(2 d)^{n}} \end{aligned}$$

所以

$$\begin{aligned} \mathbf E[\Phi_n] &=\sum_{l} \operatorname{Prob}\left(\mathbf{w}_{n}=l\right) e^{2 \pi i l\cdot \mathbf x}\\ &=\sum_{s_{1}} \sum_{s_{2}} \cdots \sum_{s_{n}} \operatorname{Prob}\left(\mathbf{s}_{1}=s_{1}, \mathbf{s}_{2}=s_{2}, \ldots, \mathbf{s}_{n}=s_{n}\right) e^{2 \pi i s_{1} \cdot \mathbf{x}} e^{2 \pi i s_{2} \cdot \mathbf{x}} \cdots e^{2 \pi i s_{n} \cdot \mathbf{x}} \\ &=\sum_{s_{1}} \sum_{s_{2}} \cdots \sum_{s_{n}} \frac{1}{(2 d)^{n}} e^{2 \pi i s_{1} \cdot \mathbf{x}} e^{2 \pi i s_{2} \cdot \mathbf{x}} \cdots e^{2 \pi i s_{n} \cdot \mathbf{x}}\\ &=\left(\frac{1}{2 d} \sum_{s_{1}} e^{2 \pi i s_{1} \cdot \mathbf{x}}\right)^{n} \end{aligned}$$

由对称性，我们可得

$$\begin{aligned} \frac 1 2 \sum_{s_1} e^{2 \pi i s_{1} \cdot x} &= \frac 1 2 \left (\sum_{j=1}^d e^{2 \pi i x_j} +e^{-2 \pi i x_j} \right)\\ &=\sum_{j=1}^d \cos 2\pi x_j \end{aligned}$$

定义

$$\phi_{d}(\mathrm{x})=\frac{1}{d}\left(\cos 2 \pi x_{1}+\cos 2 \pi x_{2}+\cdots+\cos 2 \pi x_{d}\right)$$

显然

$$|\phi_d (x)| \le 1$$

那么

$$\mathbf E[\Phi_n] =\sum_{l} \operatorname{Prob}\left(\mathbf{w}_{n}=l\right) e^{2 \pi i l\cdot \mathbf x}=\phi_{d}(\mathrm{x})^n$$

接着，令

$$f(x) =\sum_{l} \operatorname{Prob}\left(\mathbf{w}_{n}=l\right) e^{2 \pi i l\cdot \mathbf x}$$

由傅里叶系数的定义可得

$$\operatorname{Prob}\left(\mathbf{w}_{n}=l\right)=\hat{f}(l)$$

即

$$\operatorname{Prob}\left(\mathbf{w}_{n}=l\right)=\hat{f}(l)=\widehat{\left(\phi_{d}\right)^{n}}(l)=\int_{[0,1]^{d}} e^{-2 \pi il \cdot \mathbf{x}} \phi_{d}(\mathbf{x})^{n} d \mathbf{x}$$

特别的，考虑$l =0$的特殊情形，并计算

$$\sum_{n=0}^{\infty} \operatorname{Prob}\left(\mathrm{w}_{n}=0\right)$$

事实上，上述和表示返回原点的次数的期望，理由如下：

定义随机变量$V_n$，其为$1$，如果在第$n$步返回原点，否则为$0$，那么

$$\mathbf E[V_n]= \operatorname{Prob}\left(\mathrm{w}_{n}=0\right)$$

现在令

$$V=\sum_{n=0}^{\infty} V_{n}$$

那么其期望即为返回原点的次数的期望，并且

$$\mathbf E[V] = \sum_{n=0}^{\infty} \operatorname{Prob}\left(\mathrm{w}_{n}=0\right)$$

现在对右式化简，我们有

$$\begin{aligned} \sum_{n=0}^{\infty} \operatorname{Prob}\left(\mathbf{w}_{n}=0\right) &=\sum_{n=0}^{\infty} \int_{[0,1]^{d}} \phi_{d}(\mathbf{x})^{n} d \mathbf{x} \\ &=\int_{[0,1]^{d}}\left(\sum_{n=0}^{\infty} \phi_{d}(\mathbf x)^{n}\right) d \mathbf{x}\\ &=\int_{[0,1]^{d}} \frac{1}{1-\phi_{d}(\mathbf{x})} d \mathbf{x} \end{aligned}$$

因为

$$\frac{1}{d}\left(\cos 2 \pi x_{1}+\cos 2 \pi x_{2}+\cdots+\cos 2 \pi x_{d}\right)$$

所以

$$1-\phi_{d}(\mathrm{x}) \sim c|\mathrm{x}|^{2}$$

因此

$$\frac{1}{1-\phi_{d}(\mathrm{x})} \sim \frac{1}{c|\mathrm{x}|^{2}}$$

利用微积分的知识可得上述积分在$d=1, 2$时发撒，在$d\ge 3$时收敛。

为了解决$d\le 2$的情形，还需要如下引理：

引理

• $p_n$为访问原点至少$n$次的概率
• $q_n$为访问原点$n$次的概率
• 那么$p_n = p_1^n ,q_n =p_1^n(1-p_1)$

证明：

$$\begin{aligned} p_{n+1}&=\text { Prob (visit origin at least } n+1 \text { times) }\\ &=\text { Prob (visit origin at least } n+1 \text { times given visit at least } n \text { times } ) \cdot \operatorname{Prob}(\text { visit at least } n \text { times })\\ &=\operatorname{Prob}(\text { visit at least } 1 \text { time }) \cdot p_{n} \\ &=p_{1} \cdot p_{n} \end{aligned}$$

由$p_0 =1$递推可得

$$p_{n}=p_{1}^{n}$$

由定义，我们有

$$q_n=p_{n}-p_{n+1}=p_{1}^{n}\left(1-p_{1}\right)$$

现在假设$p_1 < 1$，那么

$$\begin{aligned} \sum_{n=0}^{\infty} n q_{n} &=\sum_{n=0}^{\infty} n p_{1}^{n}\left(1-p_{1}\right)\\ &=\left(1-p_{1}\right) \sum_{n=0}^{\infty} n p_{1}^{n}\\ &=\left(1-p_{1}\right) \frac{p_{1}}{\left(1-p_{1}\right)^{2}} \\ &=\frac{p_{1}}{1-p_{1}}<\infty \end{aligned}$$

但是，由之前结论可得上述期望发散（$d\le 2 $），因此我们有$p_1= 1$，即返回原点的概率为$1$，所以$p_n= 1$，结论成立。