离散傅立叶变换和线性变换的关系:什么是线性空间?
离散傅立叶变换和线性变换的关系:什么是线性空间?
本篇博客是在学习线性空间知识的时候联想到的,通过分析DFT背后的数学原理,以便更好地理解什么是线性空间、什么是线性变换。
1、离散傅立叶变换(DFT)和Fourier矩阵
离散傅立叶变换是六种傅立叶变换的一种。特点是时域离散、频域离散、有限长度。公式如下:
X
[
k
]
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
j
k
2
π
N
n
(1)
X[k] = \sum_{n=0}^{N-1} x[n]e^{-j k \frac{2\pi}{N} n} \tag{1}
X[k]=n=0∑N−1x[n]e−jkN2πn(1)
x [ n ] = 1 N ∑ n = 0 N − 1 X [ k ] e j k 2 π N n (2) x[n] = \frac{1}{N}\sum_{n=0}^{N-1} X[k]e^{j k \frac{2\pi}{N} n} \tag{2} x[n]=N1n=0∑N−1X[k]ejkN2πn(2)
将(1)写成矩阵乘法的形式:X = Fx。下面用一段python代码来描述该过程。
import numpy as np
def F(N):
F = []
for k in range(N):
row_k =[]
for n in range(N):
row_k.append(np.exp(-1j*2*np.pi/N*k*n)
F.append(row_k)
return np.array(F)
t = np.arange(0,2*np.pi,0.1)
N = len(t)
x = np.sin(2*np.pi*t)
X_dft = F(N)@x
X_fft = np.fft.fft(x)
np.linalg.norm(X_dft-X_fft)
2、线性空间、基、标准正交基
线性空间:对加法和数乘封闭的数的集合。
基:极大线性无关向量组。
标准正交基:两两正交、每个基和自身的内积为1。
由基张成的线性空间:基的所有线性组合。
关注F矩阵。第k行:
e
k
=
[
e
j
2
π
N
k
∗
0
,
e
j
2
π
N
k
∗
1
,
e
j
2
π
N
k
∗
2
,
⋯
,
e
j
2
π
N
k
∗
(
N
−
1
)
]
\Large{e_k = [e^{j\frac{2\pi}{N}k*0},e^{j\frac{2\pi}{N}k*1},e^{j\frac{2\pi}{N}k*2},\cdots,e^{j\frac{2\pi}{N}k*(N-1)}]}
ek=[ejN2πk∗0,ejN2πk∗1,ejN2πk∗2,⋯,ejN2πk∗(N−1)]
( e i , e j ) = { N , i = j 0 , i ≠ j (e_i,e_j)=\begin{cases} N, i=j\\ 0, i\ne j \end{cases} (ei,ej)={N,i=j0,i=j
F矩阵的行向量组,构成一组正交基。但不是标准正交基。
X[k]是对应基向量的系数。
离散傅立叶逆变换,是用这组基向量和每个基向量的归一化分量,相乘再相加,来表示原始信号x[n]。
现在来关注原始信号x,它相当于一个N维复向量。它位于CN空间,这个N维复空间的基,类似于三维欧氏空间的i、j、k。x[n]相当于第n个分量。
从数学上,频率空间和时域空间是线性同构关系。两者可以通过矩阵F联系起来。
下面通过将F矩阵的行向量组修正为单位向量,从而构造出标准正交基。
X = Fx
X
′
[
k
]
=
1
N
∑
n
=
0
N
−
1
x
[
n
]
e
−
j
k
2
π
N
n
(3)
X'[k] = \frac{1}{\sqrt N}\sum_{n=0}^{N-1} x[n]e^{-j k \frac{2\pi}{N} n} \tag{3}
X′[k]=N1n=0∑N−1x[n]e−jkN2πn(3)
x = F-1X
x
′
[
n
]
=
1
N
∑
n
=
0
N
−
1
X
[
k
]
e
j
k
2
π
N
n
(4)
x'[n] = \frac{1}{\sqrt N}\sum_{n=0}^{N-1} X[k]e^{j k \frac{2\pi}{N} n} \tag{4}
x′[n]=N1n=0∑N−1X[k]ejkN2πn(4)
import numpy as np
def F(N):
F = []
for k in range(N):
row_k =[]
for n in range(N):
row_k.append(np.exp(-1j*2*np.pi/N*k*n)/np.sqrt(N)) #标准正交基
F.append(row_k)
return np.array(F)
t = np.arange(0,2*np.pi,0.1)
N = len(t)
x = np.sin(2*np.pi*t)
X = F(N)@x
x_inv = np.linalg.inv(F(N))@X
np.linalg.norm(x_inv-x)
3、V(Cn)和Vn©
在数学专著上,经常能看到这两个符号V(Cn)和Vn©,有了之前的基础,就很好解释了这两个概念了。
- 相同点:它们都是指n维线性空间,二者是同构关系,可通过一个过渡矩阵P联系起来。
- 不同点:二者的标准正交基不同。
具体而言:
V(Cn)的基:
e
1
=
[
1
,
0
,
0
,
⋯
,
0
]
T
e
i
=
[
0
,
⋯
,
0
,
1
i
,
0
,
⋯
,
0
]
T
e_1 = [1,0,0,\cdots,0]^T\\ e_i = [0,\cdots,0,1_{i},0,\cdots,0]^T
e1=[1,0,0,⋯,0]Tei=[0,⋯,0,1i,0,⋯,0]T
Vn©的基:
{
ε
1
,
⋯
,
ε
i
,
⋯
,
ε
n
}
\{\varepsilon_1,\cdots,\varepsilon_i,\cdots,\varepsilon_n\}
{ε1,⋯,εi,⋯,εn}
对于3维复空间(有的地方叫酉空间)中的一个向量x = [1,2,3]T。
在V(C3),x = i+2j+3k。
在V3©,比如在基为{ek}的V3©,
e
k
=
1
N
∗
[
e
j
2
π
N
k
∗
0
,
e
j
2
π
N
k
∗
1
,
e
j
2
π
N
k
∗
2
,
⋯
,
e
j
2
π
N
k
∗
(
N
−
1
)
]
T
\Large{e_k = \frac{1}{\sqrt N}*[e^{j\frac{2\pi}{N}k*0},e^{j\frac{2\pi}{N}k*1},e^{j\frac{2\pi}{N}k*2},\cdots,e^{j\frac{2\pi}{N}k*(N-1)}]^T}
ek=N1∗[ejN2πk∗0,ejN2πk∗1,ejN2πk∗2,⋯,ejN2πk∗(N−1)]T
In [37]: F(3)
Out[37]:
array([[ 0.577+0.j , 0.577+0.j , 0.577+0.j ],
[ 0.577+0.j , -0.289-0.5j, -0.289+0.5j],
[ 0.577+0.j , -0.289+0.5j, -0.289-0.5j]])
In [38]: F(3)@[1,2,3]
Out[38]: array([ 3.464+0.j , -0.866+0.5j, -0.866-0.5j])
In [51]: e1 = F(3)[0,:].conj()
In [52]: e2 = F(3)[1,:].conj()
In [53]: e3 = F(3)[2,:].conj()
In [54]: (3.464+0.j)*e1 + (-0.866+0.5j)*e2 + (-0.866-0.5j)*e3
Out[54]: array([1.+0.000e+00j, 2.+0.000e+00j, 3.-7.772e-16j])
x = [ 1 , 2 , 3 ] T = ( 3.464 + 0. j ) ∗ e 1 + ( − 0.866 + 0.5 j ) ∗ e 2 + ( − 0.866 − 0.5 j ) ∗ e 3 x = [1,2,3]^T = (3.464+0.j)*e_1 + (-0.866+0.5j)*e_2 + (-0.866-0.5j)*e_3 x=[1,2,3]T=(3.464+0.j)∗e1+(−0.866+0.5j)∗e2+(−0.866−0.5j)∗e3
通过以上的分析,我们发现,在不同的基下,同一个向量的有不同的表示方式(基、基的分量不同)。
需要注意,基=极大线性无关向量组,因此同一个向量在一组基下的表示是唯一的,也就是分量是唯一确定的。
4、酉变换和酉矩阵
酉变换:标准正交基。
酉变换就是指用一组标准正交基去重新表示一个向量x。
α
i
=
(
u
i
,
x
)
=
u
i
H
x
(5)
\alpha_i = (u_i,x) = u_i^H x \tag{5}
αi=(ui,x)=uiHx(5)
因此:
x
=
α
1
u
1
+
α
2
u
2
+
⋯
+
α
n
u
n
(6)
x = \alpha_1u_1 + \alpha_2u_2+\cdots+ \alpha_n u_n \tag{6}
x=α1u1+α2u2+⋯+αnun(6)
酉变换:保内积不变、保p-范数不变、保2-范数不变。
所谓保内积不变、保p-范数不变,可以导出帕赛瓦尔定理:
∑
−
∞
+
∞
∣
x
[
n
]
∣
2
=
1
2
π
∫
2
π
∣
X
(
e
j
w
)
∣
2
d
w
(7)
\sum_{-\infty}^{+\infty}|x[n]|^2 = \frac{1}{2\pi}\int_{2\pi} |X(e^{jw})|^2dw \tag{7}
−∞∑+∞∣x[n]∣2=2π1∫2π∣X(ejw)∣2dw(7)
∑ n = 0 N − 1 ∣ x [ n ] ∣ 2 = 1 N ∑ k = 0 N − 1 ∣ X [ k ] ∣ 2 (8) \sum_{n=0}^{N-1}|x[n]|^2 = \frac{1}{N}\sum_{k=0}^{N-1} |X[k]|^2 \tag{8} n=0∑N−1∣x[n]∣2=N1k=0∑N−1∣X[k]∣2(8)
式8是容易推导的:X=Fx
X
H
X
=
x
H
F
H
F
x
=
x
H
d
i
a
g
[
N
,
⋯
,
N
]
x
=
N
x
H
x
X^HX=x^HF^HFx = x^H diag[N,\cdots,N]x = Nx^Hx
XHX=xHFHFx=xHdiag[N,⋯,N]x=NxHx