https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/
해당 강의에서는 다음과 같은 내용을 배운다.
change of basis
compression of images
Transformation <-> Matrix
먼저 이미지를 생각해보자. 일반적으로 이미지는 여러 개의 pixel로 이루어져있다.R 51 2 2 \R^{512^2} R 5 1 2 2
basis 에 대해서 좀더 생각해보자.
Standard Basis \text{Standard Basis} Standard Basis [ 1 0 ∣ ∣ 0 ] , [ 0 1 0 ∣ 0 ] , . . . , [ 0 0 0 ∣ 1 ] \begin{bmatrix} 1 \\ 0 \\ | \\ | \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \\ | \\ 0 \end{bmatrix}, ... , \begin{bmatrix} 0 \\ 0 \\ 0 \\ | \\ 1 \end{bmatrix} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 0 ∣ ∣ 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 1 0 ∣ 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , . . . , ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 0 0 ∣ 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ 위는 standard basis 의 예시이다. 이러한 basis 로 이미지를 표현하면 비효율적일 것이다. (ex. 51 2 2 512^2 5 1 2 2 51 2 2 512^2 5 1 2 2
다음은 better basis 의 예시이다.
Better Basis \text{Better Basis} Better Basis [ 1 1 ∣ ∣ 1 ] , [ 1 ∣ 1 − 1 ∣ − 1 ] , [ 1 − 1 1 − 1 1 − 1 ] \begin{bmatrix} 1 \\ 1 \\ | \\ | \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ | \\ 1 \\ -1 \\ | \\ -1 \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 1 ∣ ∣ 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 ∣ 1 − 1 ∣ − 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 − 1 1 − 1 1 − 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ 위에서 [ 1 ∣ 1 − 1 ∣ − 1 ] \begin{bmatrix} 1 \\ | \\ 1 \\ -1 \\ | \\ -1 \end{bmatrix} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 ∣ 1 − 1 ∣ − 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ [ 1 − 1 1 − 1 1 − 1 ] \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 − 1 1 − 1 1 − 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
다음은 Fourier basis 의 예시이다. (8 x 8)
[ 1 1 1 1 1 1 1 1 ] , [ 1 w w 2 ∣ ∣ ∣ ∣ w n − 1 ] , . . . \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ w \\ w^2 \\ | \\ | \\ | \\ | \\ w^{n-1} \end{bmatrix}, ... ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 1 1 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 w w 2 ∣ ∣ ∣ ∣ w n − 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , . . . 빠르게 basis 를 구할 수 있다는 장점이 있다.
즉, Compression of Image 에서 필요한 절차는 다음과 같다.
S i g n a l x → ⏟ c h a n g e ( l o s s l e s s ) c o e f f s c → ⏟ c o m p r e s s i o n ( l o s s y ) c ^ ( m a n y z e r o s ) Signal~x \underbrace{\to}_{change(lossless)} coeffs~c \underbrace{\to}_{compression(lossy)} \hat c~(many~zeros) S i g n a l x c h a n g e ( l o s s l e s s ) → c o e f f s c c o m p r e s s i o n ( l o s s y ) → c ^ ( m a n y z e r o s ) x ^ = ∑ c ^ i v i \hat x=\sum \hat c_i v_i x ^ = ∑ c ^ i v i 그리고 video 의 경우,
다음은 wavelets basis 의 예시이다. (∈ R 8 \in\R^8 ∈ R 8
[ 1 1 1 1 1 1 1 1 ] , [ 1 1 1 1 − 1 − 1 − 1 − 1 ] , [ 1 1 − 1 − 1 0 0 0 0 ] , [ 0 0 0 0 1 1 − 1 − 1 ] , [ 1 − 1 0 0 0 0 0 0 ] , . . . \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ -1 \\ -1 \\ -1 \\ -1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ -1 \\ -1 \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}, ... ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 1 1 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 − 1 − 1 − 1 − 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 1 − 1 − 1 0 0 0 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 0 0 0 1 1 − 1 − 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 − 1 0 0 0 0 0 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ , . . . 보다시피 orthogonal basis 라는 것을 알 수가 있다.
p = c 1 w 1 + . . . + c 8 w 8 p=c_1w_1+...+c_8w_8 p = c 1 w 1 + . . . + c 8 w 8 p = [ 1 1 . . . 1 1 . . . 1 1 . . . 1 1 . . . 1 − 1 . . . 1 − 1 . . . 1 − 1 . . . 1 − 1 . . . ] [ c 1 c 2 . . . . . c 8 ] p=\begin{bmatrix} 1 & 1 & ... \\ 1 & 1 & ... \\ 1 & 1 & ... \\ 1 & 1 & ... \\ 1 & -1 & ... \\ 1 & -1 & ... \\ 1 & -1 & ... \\ 1 & -1 & ... \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ . \\ . \\ . \\ . \\ . \\ c_8 \end{bmatrix} p = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 1 1 1 1 1 1 1 − 1 − 1 − 1 − 1 . . . . . . . . . . . . . . . . . . . . . . . . ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ c 1 c 2 . . . . . c 8 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ 위 수식에서 coefficients c 를 구할 수도 있다.
다음은 good basis 의 조건이다.
Fast. (ex. FFT (Fast-Fourier-Transform), FWT (Fast-Wavelets-Transform) )
Few is enough. (적은 수의 basis 로도 표현이 가능해야 함.)
따라서 Change of Basis 는 다음과 같다.
위에서 W W W x old basis → c new basis x\text{ old basis}\to c\text{ new basis} x old basis → c new basis
이제 Transformation <-> Matrix 를 알아보자.
about T , \text{about}~T, about T , with respect to v 1 , . . . , v 8 it has matrix A \text{with respect to $v_1,...,v_8$ it has matrix $A$} with respect to v 1 , ... , v 8 it has matrix A with respect to w 1 , . . . , w 8 it has matrix B \text{with respect to $w_1,...,w_8$ it has matrix $B$} with respect to w 1 , ... , w 8 it has matrix B 위에서 A A A B B B A A A B B B
위에서 M M M change of basis matrix \text{change of basis matrix} change of basis matrix
그렇다면 어떻게 A A A
x = c 1 v 1 + . . . + c 8 v 8 x=c_1v_1+...+c_8v_8 x = c 1 v 1 + . . . + c 8 v 8 T ( x ) = c 1 T ( v 1 ) + . . . + c 8 T ( v 8 ) T(x)=c_1T(v_1)+...+c_8T(v_8) T ( x ) = c 1 T ( v 1 ) + . . . + c 8 T ( v 8 ) T ( v 1 ) = a 11 v 1 + a 21 v 2 + . . . + a 81 v 8 T(v_1)=a_{11}v_1+a_{21}v_2+...+a_{81}v_8 T ( v 1 ) = a 1 1 v 1 + a 2 1 v 2 + . . . + a 8 1 v 8 T ( v 2 ) = a 12 v 1 + a 22 v 2 + . . . + a 82 v 8 T(v_2)=a_{12}v_1+a_{22}v_2+...+a_{82}v_8 T ( v 2 ) = a 1 2 v 1 + a 2 2 v 2 + . . . + a 8 2 v 8 [ A ] = [ a 11 a 21 ∣ ∣ . . . a 18 a 28 ] [A]= \begin{bmatrix} a_{11} & a_{21} & \\ | & | & ...\\ a_{18} & a_{28} & \\ \end{bmatrix} [ A ] = ⎣ ⎢ ⎡ a 1 1 ∣ a 1 8 a 2 1 ∣ a 2 8 . . . ⎦ ⎥ ⎤ 그렇다면 만약 v v v
T ( v i ) = λ i v i T(v_i)=\lambda_i v_i T ( v i ) = λ i v i A = [ λ 1 0 0 λ 2 ∣ ∣ . . . 0 0 ] A= \begin{bmatrix} \lambda_1 & 0 & \\ 0 & \lambda_2 & \\ | & | & ...\\ 0 & 0 & \\ \end{bmatrix} A = ⎣ ⎢ ⎢ ⎢ ⎡ λ 1 0 ∣ 0 0 λ 2 ∣ 0 . . . ⎦ ⎥ ⎥ ⎥ ⎤ 