Fourier transform

Fourier transform將時間序列資料轉換為頻率分析，以下討論其數學推導過程。

內積空間(Inner product space)

  • 內積空間為向量空間VV與內積算子⟨⋅,⋅⟩:V×V→C\langle \cdot, \cdot \rangle: V \times V \rightarrow \mathbb{C}的組合。

  • 內積算子必須滿足以下的運算：

    • Positivity: ⟨v,v⟩>0, ∀v∈V \langle v, v \rangle > 0,\ \forall v \in V .
    • Conjugate symmetry: ⟨v,w⟩=⟨w,v⟩‾, ∀v,w∈V\langle v,w \rangle = \overline{\langle w, v \rangle}, \ \forall v,w \in V.
    • Homogeneity: ⟨cv,w⟩=c⟨v,w⟩, ∀v,w∈V, c∈C \langle cv, w \rangle = c \langle v, w \rangle, \ \forall v,w \in V, \ c \in \mathbb{C}.
    • Additivity: ⟨v+u,w⟩=⟨v,w⟩+⟨u,w⟩, ∀u,v,w∈V \langle v + u, w \rangle = \langle v, w \rangle + \langle u, w \rangle, \ \forall u,v,w \in V.

  • 向量vv的長度可用∥v∥2=⟨v,v⟩\Vert v \Vert^2 =\langle v, v \rangle表示。

  • 在向量空間Cn\mathbb{C}^n中，標準內積算子的定義如下：

    • x=(x1,x2,⋯,xn),y=(y1,y2,⋯,yn)∈Cn\mathbf{x} = (x_1, x_2, \cdots, x_n), \quad \mathbf{y} = (y_1, y_2, \cdots, y_n) \in \mathbb{C}^n.
    • ⟨x,y⟩=x⊤y‾=y⊤x‾=x1y1‾+x2y2‾+⋯+xnyn‾\langle \mathbf{x}, \mathbf{y} \rangle = \mathbf{x}^{\top} \overline{\mathbf{y}} = \mathbf{y}^{\top}\overline{\mathbf{x}} = x_1 \overline{y_1} + x_2 \overline{y_2} + \cdots + x_n \overline{y_n}.

  • 在複數值連續函數向量空間C[a,b]C[a,b]中，內積算子的定義如下：

    • Functions f, g∈C[a,b]f,\ g \in C[a,b], ⟨f,g⟩=∫abf(x)g(x)‾dx\langle f, g \rangle = \int_a^b f(x) \overline{g(x)} dx .

Cauchy-Schwarz 不等式

  • ∣⟨u,v⟩∣≤∥u∥∥v∥ |\langle u, v \rangle| \leq \Vert u \Vert \Vert v \Vert .

  • 由上式可得到向量u, vu,\ v的夾角θ\theta如下：

    • ∣⟨u,v⟩∣∥u∥∥v∥≤1⇔−1≤⟨u,v⟩∥u∥∥v∥≤1⇔∃θ∈R∋⟨u,v⟩=∥u∥∥v∥cosθ\begin{array}{cl} & \frac{| \langle u, v \rangle |}{\Vert u \Vert \Vert v \Vert} \leq 1 \\ \Leftrightarrow & -1 \leq \frac{\langle u, v \rangle }{ \Vert u \Vert \Vert v \Vert } \leq 1 \\ \Leftrightarrow & \exists \theta \in \mathbb{R} \ni \langle u, v \rangle = \Vert u \Vert \Vert v \Vert \cos{\theta} \end{array}

  • 兩向量u, vu, \ v的夾角為θ\theta，因此向量vv投影(project)到向量uu的向量為vprojv_{proj}如下：

    • vproj=∥v∥cosθu∥u∥=∥v∥⟨u,v⟩∥u∥∥v∥u∥u∥=⟨u,v⟩∥u∥2u.\begin{array}{rcl} v_{proj} & = & \Vert v \Vert \cos{\theta} \frac{u}{\Vert u \Vert} \\ & = & \Vert v \Vert \frac{\langle u, v \rangle}{\Vert u \Vert \Vert v \Vert} \frac{u}{\Vert u \Vert} \\ & = & \frac{\langle u, v \rangle}{\Vert u \Vert^2} u. \end{array}

    • 第一個等式中u∥u∥\frac{u}{\Vert u \Vert}為單位向量，即此向量長度為１。

    • 當兩個向量夾角θ=π/2\theta = \pi /2時，兩向量內積必為0 (⟨u,v⟩=∥u∥∥v∥cosπ/2=0\langle u,v \rangle = \Vert u \Vert \Vert v \Vert \cos{ \pi / 2} = 0),此時稱兩向量正交(orthogonal)，如果兩向量均為單位向量 (即∥u∥=∥v∥=1 \Vert u \Vert = \Vert v \Vert = 1 ，則稱兩向量單範正交(orthonormal)。

基底(basis)

  • 向量空間VV中，基底(basis)為VV中兩兩線性獨立的最小生成集合。

  • 基底並非唯一的集合，但是基底中元素的個數是唯一的，稱基底中元素個數為此向量空間的(歐式)維度(dimension)。

    • E.g. Basis of R2={(0,1),(1,0)}\mathbb{R}^2 = \{(0,1), (1,0) \} 或 {(1,1),(1,−1)}\{ (1,1), (1, -1) \}。
    • (a,b)∈R2(a,b) \in \mathbb{R}^2, (a,b)=a⋅(1,0)+b⋅(0,1)=(a+b)/2⋅(1,1)+(a−b)/2⋅(1,−1)(a,b) = a \cdot (1,0) + b \cdot (0,1) = (a+b)/2 \cdot (1,1) + (a-b)/2 \cdot (1,-1).
    • 其中的係數為使用該基底計算時，該點對此基底向量投影的長度。

L2-space

  • L2([a,b]L^2([a,b]向量空間為在閉區間[a,b][a,b]間，函數的平方可積分的所有連續函數。

    • a,b,t∈R, a≤t≤b, L2([a,b])={f:[a,b]→C∣∫ab∣f(t)∣2dt<∞} a,b, t \in \mathbb{R}, \ a \leq t \leq b, \ L^2([a,b]) = \left\lbrace f:[a,b] \rightarrow \mathbb{C} | \int_a^b | f(t)|^2 dt < \infty \right\rbrace .
    • ∫ab∣f(t)∣2dt<∞\int_a^b | f(t) |^2 dt < \infty 表示在函數在此區間內，訊號能量加總為有限值。
    • L2([a,b])L^2([a,b])向量空間的維度為無限，取a=0,b=1a=0, b=1為例，則{1,t,t2,t3,⋯}\{1, t, t^2, t^3, \cdots \}在L2([0,1])L^2([0,1])空間中均為線性獨立的向量。
    • 內積算子定義為∀f, g∈L2([a,b]), ⟨f,g⟩=∫abf(x)g(x)‾dx \forall f,\ g \in L^2([a,b]), \ \langle f, g \rangle = \int_a^b f(x) \overline{g(x)} dx.

  • 在實際應用中，所取到的訊號都是離散資料點x=⋯,x−1,x0,x1,⋯\mathbf{x} = \cdots, x_{-1}, x_0, x_{1}, \cdots ，其中每一個訊號值xjx_j是在時間[tj,tj+1][t_j, t_{j+1}]中取樣的結果。因此定義向量空間l2={X∣∑i=−∞∞∣xi∣2<∞,xi∈C}l^2= \left\lbrace X | \sum_{i= -\infty}^{\infty} |x_i|^2 < \infty, x_i \in \mathbb{C} \right\rbrace為所有平方加總為有限值的數列XX的空間。

    • l2([a,b])l^2([a,b])空間內積算子定義為⟨X,Y⟩=∑i=−∞∞xiyi‾\langle X, Y \rangle = \sum_{i=-\infty}^{\infty} x_i \overline{y_i}。

Fourier series

  • Fourier的發現實際上是在說任何一個信號都可以用兩種方式來表達，一種就是時間序列的表示表，參數是時間或者空間的座標，因變數是信號在該處的強度；另一種則是把一個信號展開成不同頻率的簡單三角函數（簡諧振動）的疊加，相當於把序列看作是定義在所有頻率所組成的空間（稱為頻域空間）上的另一個函數，參數是不同的頻率，因變數是該頻率所對應的簡諧振動的幅度。

  • 假設周期函數f(t)f(t)可用以下三角級數逼近, ak, bk∈R, ∀ka_k,\ b_k \in \mathbb{R},\ \forall k：

    • f(t)=a0+∑k=1∞(akcos(kt)+bksin(kt)), t∈[−π,π]f(t) = a_0 + \sum_{k=1}^{\infty} \left( a_k \cos(kt) + b_k \sin(kt) \right), \ t \in [-\pi, \pi].
    • 因假設f(t)f(t)為可積分函數，兩側同時積分得：
    • ∫−ππf(t)dt=a0∫−ππ1dt+∑k=1∞(ak∫−ππcos(kt)dt+bk∫−ππsin(kt)dt)\int_{-\pi}^{\pi} f(t) dt = a_0 \int_{-\pi}^{\pi}1 dt + \sum_{k=1}^{\infty} \left(a_k \int_{-\pi}^{\pi} \cos(kt) dt + b_k \int_{-\pi}^{\pi} \sin(kt) dt \right) .
    • ∵∫−ππcos(kt)dt=∫−ππsin(kt)dt=0, k=0,1,2,3,⋯ \because \int_{-\pi}^{\pi} \cos(kt) dt = \int_{-\pi}^{\pi} \sin(kt) dt = 0, \ k =0,1,2,3,\cdots.
    • 可得a0=12π∫−ππf(t)dta_0 = \frac{1}{2\pi} \int_{-\pi}^{\pi} f(t) dt. (即函數ff的平均值，可視為函數中沒有震盪的部份)。

    • 因為正弦函數在不同頻率時彼此正交，同理餘弦函數也有此性質，且正弦與館弦函數在所有頻率正交，因此不同頻率的正弦餘弦函數可視為函數f(t)f(t)之基底。

      • 1π∫−ππcos(nt)cos(mt)={1,if n=m≥1,2,if n=k=0,0otherwise. \frac{1}{\pi} \int_{-\pi}^{\pi} \cos(nt) \cos(mt) = \begin{cases} 1, & \quad \text{if } n = m \geq 1, \\ 2, & \quad \text{if } n = k = 0, \\ 0 & \quad \text{otherwise}. \end{cases}

      • 1π∫−ππsin(nt)sin(mt)={1,if n=k≥1,0otherwise. \frac{1}{\pi} \int_{-\pi}^{\pi} \sin(nt) \sin(mt) = \begin{cases} 1, & \quad \text{if } n = k \geq 1, \\ 0 & \quad \text{otherwise}. \end{cases}

      • 1π∫−ππcos(nt)sin(mt)=0, ∀n,m \frac{1}{\pi} \int_{-\pi}^{\pi} \cos(nt)\sin(mt) = 0, \ \forall n, m.

    • 因此係數ak=1π∫−ππf(t)cos(kt)dta_k = \frac{1}{\pi} \int_{-\pi}^{\pi} f(t) \cos(kt) dt, bk=∫−ππf(t)sin(kt)dtb_k = \int_{-\pi}^{\pi} f(t) \sin(kt) dt.
    • 可知係數ak, bka_k,\ b_k之值為函數f(t)f(t)與不同頻率之正弦函教與餘弦函數之內積。

  • 若函數的周期為[−h,h][-h, h]，可做區間變換: −π≤t≤π⇔−h≤πht≤h-\pi \leq t \leq \pi \Leftrightarrow -h \leq \frac{\pi}{h} t \leq h.

  • 因此只要f(t)f(t)為周期函數，均可使用三角函數逼近： f(t)=a0+∑k=1∞[akcos(kπth)+bksin(kπth)]=∑k=1∞[akcos(ωkt)+bksin(ωkt)],a0=12h∫−hhf(t)dt,ak=1h∫−hhf(t)cos(ωkt)dt,bk=1h∫−hhf(t)sin(ωkt)dt. \begin{array}{rcl} f(t) & = & a_0 + \sum_{k=1}^{\infty} \left[ a_k \cos(\frac{k \pi t}{h}) + b_k \sin(\frac{k \pi t}{h}) \right] \\ & = & \sum_{k=1}^{\infty} \left[ a_k \cos(\omega_k t) + b_k \sin(\omega_k t) \right],\, a_0 = \frac{1}{2h} \int_{-h}^h f(t)dt, \\ & & \\ a_k & = & \frac{1}{h} \int_{-h}^h f(t) \cos(\omega_k t) dt, \\ b_k & = & \frac{1}{h} \int_{-h}^h f(t) \sin(\omega_k t) dt. \end{array}

    • 其中ωk=kπh\omega_k = \frac{k \pi}{h}為kk倍的角速度(rad/sec).

複數表示法

  • Euler's formula: ∀x∈R, eix=cos(x)+isin(x)\forall x \in \mathbb{R},\ e^{ix} = \cos(x) + i \sin(x).

  • 因此可得eiωkt=cos(ωkt)+isin(ωkt)e^{i \omega_k t} = \cos(\omega_k t) + i \sin(\omega_k t).

    • cos(ωkt)=eiωkt+e−iωKt2 \cos(\omega_k t) = \frac{e^{i \omega_k t} + e^{- i \omega_K t}}{2}.
    • sin(ωkt)=eiωkt−e−iωKt2 \sin(\omega_k t) = \frac{e^{i \omega_k t} - e^{- i \omega_K t}}{2}.

  • Fourier series改寫如下： f(t)=a0+∑k=1∞[akcos(ωkt)+bksin(omegakt)]=a0+∑k=1∞[akeiωkt+e−iωKt2+bkeiωkt−e−iωKt2i]=a0+∑k=1∞[ak−ibk2eiωkt+ak+ibk2e−iωkt]. \begin{array}{rcl} f(t) & = & a_0 + \sum_{k=1}^{\infty} \left[ a_k \cos(\omega_k t) + b_k \sin(omega_k t) \right] \\ & = & a_0 + \sum_{k=1}^{\infty} \left[ a_k \frac{e^{i \omega_k t} + e^{- i \omega_K t}}{2} + b_k \frac{e^{i \omega_k t} - e^{- i \omega_K t}}{2i} \right] \\ & = & a_0 + \sum_{k=1}^{\infty} \left[ \frac{a_k - i b_k}{2} e^{i \omega_k t} + \frac{a_k + i b_k}{2} e^{-i \omega_k t} \right]. \end{array}

    • Let c0=a0, ck=ak−ibk2, c−k=ck‾=ak+ibk2c_0 = a_0, \ c_k = \frac{a_k - i b_k}{2}, \ c_{-k} = \overline{c_k} = \frac{a_k + i b_k}{2}.
    • ck=ak−ibk2=12h{∫−hhf(t)cos(ωkt)dt−i∫−hhf(t)sin(ωkt)dt}=12h∫−hhf(t)e−iωktdt. \begin{array}{rcl} c_k & = & \frac{a_k - i b_k}{2} \\ & = & \frac{1}{2h} \left\lbrace \int_{-h}^{h} f(t) \cos(\omega_k t) dt - i \int_{-h}^h f(t) \sin(\omega_k t) dt \right\rbrace \\ & = & \frac{1}{2h} \int_{-h}^h f(t) e^{-i \omega_k t}dt. \end{array}

  • 所以Fourier series的複數形式為f(t)=∑k=−∞∞ckeiωkt,ck=12h∫−hhf(t)e−iωktdtf(t) = \sum_{k=-\infty}^{\infty}c_k e^{i \omega_k t}, \, c_k = \frac{1}{2h}\int_{-h}^h f(t) e^{-i \omega_k t} dt.

Fourier transform

  • 令 Δω=ωk−ωk−1=kπh−(k−1)πh\Delta \omega = \omega_k - \omega_{k-1} = k \frac{\pi}{h} - (k-1) \frac{\pi}{h}

  • (Fourier transform) F(ω)=∫−∞∞f(t)e−iωtdt F(\omega) = \int_{-\infty}^{\infty} f(t) e^{-i \omega t} dt .

  • (Inverse Fourier transform) f(t)=12π∫−∞∞F(ω)eiωtdt f(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} F(\omega) e^{i \omega t} dt .

Discrete Fourier transform (DFT)

  • 在實際應用時，我們只能夠從訊號當中取樣得到離散的訊號值，無法得到訊號的真實函數，因此必須使用 DFT 來將訊號轉換為頻率域。

  • 假設我們用間隔Δ\Delta 時間來取樣函數f(t)f(t)的資料。令量到的第kk筆資料為xkx_k，共取得NN筆資料或是資料只在有限的時間內T=N⋅ΔT = N \cdot \Delta有值，則：

    • xk=g(Δ⋅k), k=0,1,⋯,N−1 x_k = g(\Delta \cdot k),\ k=0,1,\cdots, N-1 .

  • 假設NN為偶數，因為只有NN筆資料，所以最多能夠得到NN個不同頻率的結果，令第kk個頻率為fkf_k，則：

    • fk=kT=kN⋅Δ,k=0,1,⋯,N−1 f_k = \frac{k}{T} = \frac{k}{N \cdot \Delta}, k=0,1,\cdots , N-1 .

Parseval’s theorem

  • 此定理說明了函數在時間域與頻率域的總能量應相同，符合能量不滅的原則。

    • ∫−∞∞∣f(t)∣2dt=∫−∞∞∣F(ω)∣2dω \int_{-\infty}^{\infty} | f(t)|^2 dt = \int_{-\infty}^{\infty} |F(\omega)|^2 d\omega .

    • Proof:

    • ∫∣f(t)∣2dt=∫f(t)f(t)‾dt=∫f(t)∫F(ω)e−iωtdω‾dt=∫∫f(t)F(ω)‾eiωtdωdt=∫∫F(ω)‾f(t)eiωtdtdω=∫F(ω)‾(∫f(t)eiωtdt)dω=∫F(ω)‾F(ω)dω=∫∣F(ω)∣2dω.\begin{array}{rcl} \int | f(t) |^2 dt & = & \int f(t) \overline{f(t)} dt \\ & = & \int f(t) \overline{\int F(\omega) e^{-i \omega t} d\omega} dt \\ & = & \int \int f(t) \overline{F(\omega)} e^{i \omega t} d \omega dt \\ & = & \int \int \overline{F(\omega)} f(t) e^{i \omega t} dt d \omega \\ & = & \int \overline{F(\omega)} \left( \int f(t) e^{i \omega t} dt \right) d\omega \\ & = & \int \overline{F(\omega)} F(\omega) d\omega \\ & = & \int | F(\omega)|^2 d \omega. \end{array}

Uncertainty principle

  • 此原理由Werner Heisenberg所提出，其說明了任何訊號不可能同時準確的觀察到時間與頻率的分佈。簡單的說，如果人們觀察一個很短暫(時間域)的訊號(如音樂)，則很難以準確判定此訊號是屬於那些頻率，只能大概猜測其頻率範圍。反之，如果能夠長時間觀察到訊號，則能夠較準確判定訊號的頻率域。

  • 由於Fourier transform是將觀察到的一段時間訊號，轉換到頻率訊號，理論上是無法直接觀察到某一個瞬時時間點的頻率強度分佈。如果我們將原始的訊號切成非常小段時間訊號再做FT轉換，也就是所謂的Short-time Fourier transform (STFT)，直覺上是可以得到瞬時時間點的頻率分佈，但是Uncertainty principle說明了如果轉換時的時間訊號不夠長時，所得到的頻率分佈將會很模糊，因此後人提出了Wavelet transform和Hilbert-Huang transform來得到時頻分佈的關係。

results matching ""

    No results matching ""