13.1
The DFT transformation proposed takes the form of an f x n Vandermonde matrix, where
\[ W = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&e^{2 \pi i \over N}&e^{{2 \pi i \over N}*2}&e^{{2 \pi i \over N}*3}&\cdots&e^{{2 \pi i \over N}*{N-1}} \\ 1&e^{{2 \pi i \over N}*2}&e^{{2 \pi i \over N}*4}&e^{{2 \pi i \over N}*6}&\cdots&e^{{2 \pi i \over N}*{2(N-1)}}\\ 1&e^{{2 \pi i \over N}*3}&e^{{2 \pi i \over N}*6}&e^{{2 \pi i \over N}*9}&\cdots&e^{{2 \pi i \over N}*{3(N-1)}}\\ \vdots&\vdots&\vdots&\vdots&&\vdots\\ 1&e^{{2 \pi i \over N}*{N-1}}&e^{{2 \pi i \over N}*{2(N-1)}}&e^{{2 \pi i \over N}*{3(N-1)}}&\cdots&e^{{2 \pi i \over N}*{(N-1)(N-1)}}\\ \end{bmatrix} \]
and where the inverse transform is just the complex conjugate of the transpose of the Vandermonde matrix and is given by an n x f \(W^\dagger \) matrix:
\[ W\dagger = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&e^{-{2 \pi i \over N}}&e^{-{2 \pi i \over N}*2}&e^{-{2 \pi i \over N}*3}&\cdots&e^{-{2 \pi i \over N}*{N-1}} \\ 1&e^{-{2 \pi i \over N}*2}&e^{-{2 \pi i \over N}*4}&e^{-{2 \pi i \over N}*6}&\cdots&e^{-{2 \pi i \over N}*{2(N-1)}}\\ 1&e^{-{2 \pi i \over N}*3}&e^{-{2 \pi i \over N}*6}&e^{-{2 \pi i \over N}*9}&\cdots&e^{-{2 \pi i \over N}*{3(N-1)}}\\ \vdots&\vdots&\vdots&\vdots&&\vdots\\ 1&e^{-{2 \pi i \over N}*{N-1}}&e^{-{2 \pi i \over N}*{2(N-1)}}&e^{-{2 \pi i \over N}*{3(N-1)}}&\cdots&e^{-{2 \pi i \over N}*{(N-1)(N-1)}}\\ \end{bmatrix} \]
Multiplying \(W\) by \(W^\dagger\) yields on the on-diagonal terms ####\[ eg. element (2,2) : \frac{1}{\sqrt{N}}*\frac{1}{\sqrt{N}}(1*1+\underbrace{e^{2 \pi i \over N} * e^{-{2 \pi i \over N}}}_{conjugates} + \underbrace{e^{{2 \pi i \over N}*2}*e^{-{2 \pi i \over N}*2}}_{conjugates} + ....) = \frac{1}{N}(1*1 + \underbrace{1 + 1 ...}_{N-1})= \frac{1}{N} N = 1\]
In general the sum is the following ####\[ \frac{1}{\sqrt{N}}*\frac{1}{\sqrt{N}} \sum_{j=0}^{N-1}e^{2 \pi i f j \over N} * e^{-{2 \pi i n j \over N}} = \frac{1}{N} \sum_{j=0}^{N-1} e^0 = \frac{1}{N} \sum_{j=0}^{N-1} 1 = \frac{1}{N} N = 1 \]
Looking at an off-diagonal term : eg. (2,3) : ####\[ \frac{1}{\sqrt{N}}*\frac{1}{\sqrt{N}}(1*1+e^{2 \pi i \over N} * e^{-{2 \pi i \over N}*2} + e^{{2 \pi i \over N}*2} * e^{-{2 \pi i \over N}*4}) + .... = \frac{1}{N} (1*1+\cos {-2\pi \over N}+i \sin {-2\pi \over N} + \cos {-4\pi \over N}+i \sin {-4\pi \over N} )+... = 1 + -1 + 0 = 0 \] since ####\[ cos {2 \pi k x \over N}+ cos {4 \pi k x \over N} + ... cos { \pi k x } =-1 \]
and ####\[ sin {2 \pi k x \over N}+ sin {4 \pi k x \over N} + ... sin { \pi k x } =0 \]
then \[ W*W^\dagger = \begin{bmatrix} 1&0&0&0&\cdots&0 \\ 0&1&0&0&\cdots& 0 \\ \cdots& \cdots &\cdots& \cdots &\cdots&0 \\ 0&0&0&0&1&0\\0&0&0&0&0&1 \end{bmatrix} = I \]
Wavelets
#Inverse wavelet transform:
from numpy import *
import matplotlib.pyplot as plt
from numpy.linalg import *
%pylab inline
c0=(1+sqrt(3))/(4*sqrt(2));
c1=(3+sqrt(3))/(4*sqrt(2));
c2=(3-sqrt(3))/(4*sqrt(2));
c3=(1-sqrt(3))/(4*sqrt(2));
Size=2**12
data=zeros([Size,1])
data[4]=1
data[29]=1
for i in range(11):
#MatrixtoOrder=Data[0:3]
#Put unOrdered matrix on top of random
SizeSplit=(2**(i+2))
splitting=zeros([SizeSplit,SizeSplit])
for j in range(int(SizeSplit/2)):
splitting[j,2*j]=1
for k in range(int(SizeSplit/2)):
splitting[k+SizeSplit/2,2*k+1]=1
SizeCirculant= SizeSplit
Circulant=zeros([SizeCirculant,SizeCirculant])
Circulant[SizeCirculant-2,0]=c2
Circulant[SizeCirculant-2,1]=c3
Circulant[SizeCirculant-1,0]=c1
Circulant[SizeCirculant-1,1]=-c0
Circulant[SizeCirculant-2,SizeCirculant-2]=c0
Circulant[SizeCirculant-2,SizeCirculant-1]=c1
Circulant[SizeCirculant-1,SizeCirculant-2]=c3
Circulant[SizeCirculant-1,SizeCirculant-1]=-c2
for l in range(0,SizeCirculant-2,2):
Circulant[l,l]=c0
Circulant[l,l+1]=c1
Circulant[l,l+2]=c2
Circulant[l,l+3]=c3
Circulant[l+1,l]=c3
Circulant[l+1,l+1]=-c2
Circulant[l+1,l+1]=c1
Circulant[l+1,l+1]=-c0
Circulant=Circulant.transpose()
data[:SizeSplit]=dot(inv(splitting),data[:SizeSplit])
#inverse wavelet
data[:SizeCirculant]=dot(Circulant, data[:SizeCirculant])
t=arange(0,Size)
fig=plt.figure()
ax=fig.add_subplot(111)
ax.plot(t,data)
plt.show()
PCA
\[ Cx = \begin{bmatrix} C_{x_1,x_1}&C_{x_1,x_2}&C_{x_1,x_3} \\ C_{x_2,x_1}&C_{x_2,x_2}&C_{x_2,x_3} \\ C_{x_3,x_1}&C_{x_3,x_2}&C_{x_3,x_3} \end{bmatrix} = I \]
where
-
- \(C_{x_1,x_1} = E(x_1*x_1)= E(x_1^2)=1\)
<li>$C_{x_1,x_2} = E(x_1*x_2)= 0 $ since x1 and x2 are independent</li> <li>$C_{x_1,x_3} = E(x_1*x_3)= E(x_1*(x_1+x_2))= E(x_1*x_1+x_1*x_2)=1 $</li> </ul> -
- \(C_{x_2,x_1} = E(x_2*x_1)= 0 \)
<li>$C_{x_2,x_2} = E(x_2*x_2)= E(x_2^2)=1 $</li> <li>$C_{x_2,x_3} = E(x2*(x_1+x_2))= E(x_2*x_1+x_2*x_2)=E(x_2*x_2)=1 $</li> </ul> -
- \(C_{x_3,x_1} = E(x_3*x_1)= E(x_1*x_3) =1 \)
<li>$C_{x_3,x_2} = E(x_3*x_2)= E(x_2*x_3)=1 $</li> <li>$C_{x_3,x_3} = E(x_3*x_3)= E{(x_1+x_2)}^2= E(x_1^2)+2*E(x_1 x_2)+E(x_2^2)=1+2*0+1 =2 $</li> </ul>
Therefore
\[ Cx = \begin{bmatrix} 1&0&1 \\ 0&1&1 \\ 1&1&2 \end{bmatrix} = I \]
By solving the charecteristic equation of $ det |C_x - v| = 0 $ we can find the following eigenvalues:
Cx=np.zeros([3,3])
Cx[0,:]=[1,0,1]
Cx[1,:]=[0,1,1]
Cx[2,:]=[1,1,2]
w, v = linalg.eig(Cx)
print "lamda1= "+ str(w[0])
print "lamda2= "+ str(w[1])
print "lamda3= "+ str(w[2])
# Taking a sample of a 100000 points
from random import *
nsample=100000
x1=normal(0,1,nsample)
x2=normal(0,1,nsample)
x3=x1+x2
x1=asarray(x1)
x=zeros([3,nsample])
x[0,:]=x1
x[1,:]=x2
x[2,:]=x3
x=asarray(x)
Cx=cov(x)
print "Covariance Matrix Cx : "
print Cx
eig, M = linalg.eig(Cx)
print "lamda1= "+ str(eig[0])
print "lamda2= "+ str(eig[1])
print "lamda3= "+ str(eig[2])