Fast Fourier Transform & Wavelet Transform 이해하기

먼저 다음 2개로 나누어진 렉처 영상을 조금 보고 개념을 잡았다.

part1 -  https://courses.edx.org/courses/RiceX/ELEC301x_/2015Q3/

part2 - https://courses.edx.org/courses/RiceX/ELEC301.2x/2015Q3/

Discrete Time Signals and Systems, Part 1: Time Domain

• signal is a function that maps an independent variable to a dependent variable

• convert an infinite length signal into a finite length signal

->windowing(걍 적당한 구간만 자르기)

• convert an finite length signal into an infinite length signal

-> zero padding(나머지 부분을 다 0으로 세팅해서 무한길이로 바꾸기) or periodization(반복시키기)

• every signal can be decomposed into the sum of even and odd part
• delta function과 unit function을 이용하여 원래 함수에 곱함으로서 함수를 원하는대로 변형시킬수 있음 
• harmonic sinusoid $e^{i( \omega n + \pi )}$ has a period only if $w=\frac{2 \pi k}{N}$
• signal을 벡터로 봤을때, L2 norm = energy in signal, L$\inf$ norm = peak value in signal
• system : signal을 signal로 바꿔주는 함수
• moving average $y[n]=\frac{1}{2}(x[n]+x[n-1])$=>finite impulse response filters(FIR)
• Recursive average $y[n]=x[n]+\alpha y[n-1]$=>infinite impulse response filters(IIR)
• These two above systems are linear system
• time invariant system : 시간 shift가 일어난 signal을 system에 대입하여 나온 결과도 같은 shift가 일어나는 system
• These two above systems are Time invariant system
• Linear + time invariant = Linear Time Invariant system(LTI system)
• LTI system은 linear성질에 의해 matrix곱으로 볼 수 있고, Time invariant 성질을 이용해보면 matrix의 대각선마다 다 entry가 같음을 알 수 있다. 이런 matrix를 infinite signal에서 본다면 Toeplitz Matrices가 되고, finite signal에서 본다면 modular형태로 보았을때 circulent matrix가 된다.
• finite던 infinite던 결국 사방으로 대칭되기 때문에 0번째 column만 알면 그 행렬을 전부 알 수 있다. 그 0번째 column h를 구하는 방법으로 system에 delta function $\delta_{0}$를 대입하면 나오는게 딱 0번째 column이기 때문에 그 column에만 관심을 가지면 된다. 따라서 이 column을 impulse response라고 부르기도 한다.
• 이제 이 h를 이용해서 그 system의 특징을 찾을것인데,
• LTI system H가 bounded input bounded output stable (BIBO stable)하다는 것의 정의는 $\Vert x \Vert_{\infty}<\infty$일 때, system에 대입한 결과 $\Vert y \Vert_{\infty}<\infty$ 일때 그렇게 부른다. 이때 BIBO stable과 동치인 조건은 그 system의 impulse response인 h의 1 norm이 finite이면 된다($\Vert h \Vert_{1}<\infty$)

Discrete Time Signals and Systems, Part 1: Frequency Domain

• 핵심 :  Transform from Time domain to Frequency domain
• signal을 어떤  basis에 대해 linear combination으로 표현했을때, 그 앞 계수(weight)들을 transform이라 부른다
• LTI system의 eigenvector들은 딱 sinusoid인 $h[n]=\frac{1}{\sqrt{N}}e^{\frac{2\pi}{N}kni}$(k=0,1,...,N-1) 총 N개가 된다.
• 이 eigenvector에 따른 eigenvalue를 frequency response라고 말하는데, 왜냐면 이 eigenvector들이 system을 거쳐도 상수배만 되는 것들이니까 이 system의 기본들이라고 여겨서 그것들의 계수들을 바로 frequency response라고 하고 변환해서 넘어온 새로운 영역이 frequency 영역으로 보는 것이다.
• 다시 말해 H라는 system이 있을때, 이를 $H=S \Lambda S^H$로 대각화를 하고, 이때 S는 각 column이 위에서 설명한 sinusoid가 들어가있는 형태이다. 이때 $S^H$를 Discrete Fourier Transform(DFT), $S$를 Inverse Discrete Fourier Transform(IDFT)라고 말한다.
• 이때 signal x를 eigenvertor들 sinusoid n개를 모아놓은 basis들의 linear combination으로 쓸 수 있는데 그때의 그 계수들 X를 구하는 과정을 forward DFT라 하고 $X=S^Hx$가 된다. 반대로 계수들 X를 알 때 그 signal x를 구하는 과정을 inverse DFT라 하고 $x=SX$로 구할 수 있다. 이때 $X_1 X_2 ... X_N$은 그 basis의 계수들로 볼 수도 있지만, 다른 면으로 보면 $X_i = < s_i , x >$ 즉$x$와 $s_i$가 얼마나 닮아 있는지 비슷한 정도(내적값)이 나온다고도 볼 수 있다.
• 이제 time domain 과 frequemcy domain사이의 관계를 살펴보면, time domain에서의 signal을 system에 대입하여 나오는 과정이 convolution과정이었는데, frequency domain으로 옮겨 왔을때 보면 그냥 두 벡터의 곱으로 볼 수 있다.
• 이러한 DFT의 연산 복잡도를 보면 $n^2$이 되는데 이는 계산량이 많아 이를 효율적으로 계산량 줄인 방법이 Fast Fourier Transform 이다. FFT는 복잡도가 $n\log n$이 된다.
• 기존 Fourier Transform과 달리 time을 frequency로 아예 바꾸는 것이아니고, time과 frequency 그 중간 정도로 바꾸는 변환으로 크게 두 가지가 있다.Wavelet transform 그리고  Short Time Fourier Transform.
• Wavelet transform은 sin cos함수가 아닌 어떤 전구간이 아닌 local한 basis들로 시간에 따라 앞으로 나아가면서 계산하는 변환이다.
• Short Time Fourier Transform이란 적당한 window로 구간별로 FT를 적용하여 시간에 따라서 계속 옮겨주는 변환이다. 

파이썬에서!!

fast fourier transform은 numpy.fft 사용! https://bugra.github.io/work/notes/2014-03-31/outlier-detection-in-time-series-signals-fft-median-filtering/ 참고

아니면 scipy에도 이 툴이 있었다 - https://docs.scipy.org/doc/scipy-0.18.1/reference/tutorial/fftpack.html 참고

wavelet transform은 conda install pywavelets 해서 깔고 import pywt 해서 사용!

short time fourier transfrom은 https://kevinsprojects.wordpress.com/2014/12/13/short-time-fourier-transform-using-python-and-numpy/ 참고

내용 정리된 pdf - http://www.tvrl.lth.se/fileadmin/tvrl/files/vvr001f/Unit_4.pdf