HomePage

## 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

In [5]:
#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.plot(t,data)

plt.show()

Populating the interactive namespace from numpy and matplotlib


WARNING: pylab import has clobbered these variables: ['linalg', 'info']
%matplotlib prevents importing * from pylab and numpy



### 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:

In [28]:
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])

lamda1= 3.0
lamda2= 1.0
lamda3= -3.36770205564e-17


In [55]:
# 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])

Covariance Matrix Cx :
[[  9.96886724e-01  -7.64263088e-04   9.96122461e-01]
[ -7.64263088e-04   1.00117746e+00   1.00041320e+00]
[  9.96122461e-01   1.00041320e+00   1.99653566e+00]]
lamda1= 2.99481041225
lamda2= 0.999789435362
lamda3= 8.705860027e-16


In [63]:


  File "<ipython-input-63-ee69b6ed5ae7>", line 4
ToKeep=[ i>Tol: i for i in diag(eig)]
^
SyntaxError: invalid syntax

In []: