Fourier Transform

基本的定义

严格来说, 傅里叶变换是Schwartz space 上的一一映射, 对于\(L^1\), 即可积函数我们都可以找到其对应的傅里叶变换.

注: 不同版本的傅里叶变换的定义存在系数上的差异.

性质

注: 虽然以上性质除11外都是用了标量, 但是实际上对于一般的傅里叶变换也是成立的.

1. pass

2. 卷积:

   \[\begin{array}{ll} (f \star g)^{\hat{}}(u) &= \int f \star g (t) e^{-j2\pi u t} \mathrm{d}t \&= \int \int f(t-\tau) g (\tau) \mathrm{d}\tau e^{-j2\pi u t} \mathrm{d}t \&= \int \int f(t-\tau) g (\tau) e^{-j2\pi u t} \mathrm{d}t \mathrm{d}\tau \quad \rightarrow \mathrm{Fubini}\&= \int \int f(t-\tau) e^{-j2\pi u (t-\tau)} \mathrm{d}t \: g(\tau)e^{-j2\pi u\tau} \mathrm{d}\tau \quad \&= F(u) \cdot G(u). \end{array} \]

   \(\Leftarrow\)是类似的证明.

3. correlation:

   \[\begin{array}{ll} (f \bullet g)^{\hat{}}(u) &= \int f*g(t) e^{-j2\pi ut} \mathrm{d}t \&= \int \int f^*(\tau) g(\tau + t) \mathrm{d}\tau e^{-j2\pi ut} \mathrm{d}t \&= \int f^*(\tau) \int g(\tau + t) e^{-j2\pi ut} \mathrm{d}t \mathrm{d}\tau \&= G(u)\int f^*(\tau) e^{j2\pi u\tau} \mathrm{d}\tau \&= G(u)[\int f(\tau) e^{-j2\pi u\tau} \mathrm{d}\tau]^* \&= F^*(u)G(u) \end{array} \]

4. 乘积的证明和上面是一样的, 无非是作用于\(\check{}\)上.

5. pass

6. 平移:

   \[(f(t+t_0))^{\hat{}} = \int f(t+t_0) e^{-j2\pi ut} \mathrm{d}t =e^{j2\pi u t_0}\int f(t+t_0) e^{-j2\pi u(t+t_0)} \mathrm{d}t = e^{j2\pi t_0u} F(u). \]

7. 逆:

   \[(f(-t))^{\hat{}} = \int f(-t) e^{-j2\pi u t} \mathrm{d}t = \int f(t) e^{j2\pi u t} \mathrm{d}t = F(-u). \]

8. \(\hat{F}(t) = \int F(u) e^{j2\pi t u} \mathrm{d}u = (F(-u))^{\check{}}(t) = f(-t)\).

9. scaling:

   \[(f(at))^{\hat{}}(u) = \int_{-\infty}^{+\infty} f(at) e^{-j2\pi ut} \mathrm{d}t = \frac{1}{|a|}\int_{-\infty}^{+\infty} f(z) e^{-j2\pi \frac{u}{a}z} dz = \frac{1}{|a|} F(\frac{u}{a}). \]

10. 导函数:

    \[\begin{array}{ll} f‘(t) &= \frac{\mathrm{d}}{\mathrm{d}t} \int_{-\infty}^{+\infty} F(u) e^{j2\pi t u} \mathrm{d}u \&= \int_{-\infty}^{+\infty} F(u) \frac{\mathrm{d}}{\mathrm{d}t} e^{j2\pi t u} \mathrm{d}u \&= \int_{-\infty}^{+\infty} F(u) (j2\pi u) e^{j2\pi t u} \mathrm{d}u \&= (j2\pi u F(u))^{\check{}}. \end{array} \]

11. 同上

12. 这个性质说明了, 对原图像加以旋转, 等价地在频域上加以同样的旋转.

    \[\begin{array}{ll} G(\mathbf{u}) &=\int f(R\mathbf{t}) e^{-j2 \pi \mathbf{u}^T \mathbf{t}} \mathrm{d}\mathbf{t} \ &=\int f(\mathbf{x}) e^{-j2 \pi (R\mathbf{u})^T \mathbf{x}} |R^{-1}|\mathrm{d}\mathbf{x} \ &=\int f(\mathbf{x}) e^{-j2 \pi (R\mathbf{u})^T \mathbf{x}} \mathrm{d}\mathbf{x} \ &=F(R\mathbf{u}) \end{array} \]

对称性

主要指的:

1. 奇函数

   \[f(x) = -f(-x). \]

2. 偶函数

   \[f(x) = f(-x). \]

3. 共轭对称

   \[f^*(x) = f(-x). \]

考查\(f(t)=r(t) + j i(t)\)与\(F(u) = R(u) + j I(u)\)之间的关系:

1. real ->(\(\Leftarrow\)采用反证法即可)

   \[\begin{array}{ll} F^*(u) &=[\int f(t) e^{-j2\pi ut} \mathrm{d}t]^* \&=\int f^*(t) e^{j2\pi ut} \mathrm{d}t \&=\int f(t) e^{-j2\pi (-u)t} \mathrm{d}t \rightarrow f*(t) = r^*(t) = r(t)\&=F(-u). \end{array} \]

2. 由1易证.

3. imaginary ->

   \[\begin{array}{ll} F^*(-u) &=[\int f(t) e^{j2\pi ut} \mathrm{d}t]^* \&=\int f^*(t) e^{-j2\pi ut} \mathrm{d}t \&=\int -f(t) e^{-j2\pi ut} \mathrm{d}t \rightarrow f^*(t) = -ji(t)=-f(t) \&=-F(u). \end{array} \]

4. 由3易证.

5. 由性质6以及上述的对称性3可知\((f(-t))^{\hat{}}= F(-u) = F^*(u)\).

6. 由性质6可知\((f(-t))^{\hat{}} = F(-u)\).

7. \[\int f^*(t) e^{-j2\pi ut} \mathrm{d}t = [\int f(t) e^{j2\pi ut} \mathrm{d}t]^* = F^*(-u). \]

8. \[F(u) = (f(t))^{\hat{}} = (f(-t))^{\hat{}} = F(-u) = F^*(u). \]

9. \[F(u) = (f(t))^{\hat{}} = -(f(-t))^{\hat{}} = -F(-u) = -F^*(u). \]

10. \[F(u) = (f(t))^{\hat{}} = (f(-t))^{\hat{}} = F(-u) = -F^*(u). \]

11. \[F(u) = (f(t))^{\hat{}} = -(f(-t))^{\hat{}} = -F(-u) = F^*(u). \]

12. \[F(u) = (f(t))^{\hat{}} = (f(-t))^{\hat{}} = F(-u). \]

13. \[F(u) = (f(t))^{\hat{}} = -(f(-t))^{\hat{}} = -F(-u). \]

卷积

这里特别说明离散卷积的一个重要性质:
注意到

则

定义

则有

FFT

考虑离散傅里叶变换:

每次计算包含\(N\)个乘法, 故傅里叶变换的计算量是\(N^2\)级别的.

下面假设\(N = P * Q, P, Q \in \mathbb{N}^+\), 则

注意到:

此时, \(m, n\)与唯一的\((u,v), (s, t)\)匹配, 则傅里叶变换可以表示为:

令

显然总共需要\(QN\)次乘法, 而

总共有\(PN\)次乘法, 故总共有\((P+Q) N\)次乘法运算.
由于每个\(F^t\)都是一个独立的傅里叶变换过程, 故倘若\(Q\)能够进一步分解, 计算量可以进一步降低.
甚至, 若假设\(N = P^J\), 则可以证明最后的计算量可以分解为

特别的, 常常\(N=2^J\), 则计算量是\(N\log_2 N\)量级的.

注: 卷积运算\([f\star g]_n, n=0,\cdots, N-1\), 计算量也是\(N^2\)级别的, 但是通过FFT, 应当是\((PN\log_P + 1)N\)?乘法次数, 也是可以降低计算量的.

逆傅里叶变换实际上就是

虽然下面的代码我并没有采取这种策略.

from typing import Iterable, Union
import numpy as np



def factorization(N: int):
    for P in range(2, N + 1):
        if N % P is 0:
            return P

def dft(arr: Iterable, m: int):
    N = len(arr)
    basis = np.arange(N) * m * 2 * np.pi * 1j * -1
    basis = np.exp(basis / N)
    return arr @ basis

def idft(arr: Iterable, m: int):
    N = len(arr)
    basis = np.arange(N) * m * 2 * np.pi * 1j
    basis = np.exp(basis / N) / N
    return arr @ basis

def basis_dft(N: int):
    basis = np.outer(np.arange(N), np.arange(N))
    basis = basis * 2 * np.pi * 1j * -1
    return np.exp(basis / N)

def basis_idft(N: int):
    basis = np.outer(np.arange(N), np.arange(N))
    basis = basis * 2 * np.pi * 1j
    return np.exp(basis / N) / N

def fft(arr: Iterable) -> np.ndarray:
    N = len(arr)
    P = factorization(N)
    if P is N:
        return arr @ basis_dft(N)
    Q = N // P
    Fvt = np.array([fft(arr[t::P]) for t in range(P)]).T # Q x P
    dummy = np.outer(np.arange(Q), np.arange(P))
    dummy = np.exp((dummy * 2 * np.pi * 1j * -1) / N)
    Fvt_ext = Fvt * dummy
    return (Fvt_ext @ basis_dft(P)).T.flatten()

def ifft(arr: Iterable) -> np.ndarray:
    N = len(arr)
    P = factorization(N)
    if P is N:
        return arr @ basis_idft(N)
    Q = N // P
    Fvt = np.array([ifft(arr[t::P]) for t in range(P)]).T # Q x P
    dummy = np.outer(np.arange(Q), np.arange(P))
    dummy = np.exp((dummy * 2 * np.pi * 1j) / N)
    Fvt_ext = Fvt * dummy
    return (Fvt_ext @ basis_idft(P)).T.flatten()

Fourier Transform