精华内容
下载资源
问答
  • 线性代数系列(十七)--复数矩阵傅里叶矩阵
    千次阅读
    2019-08-15 22:15:03

    主要内容

    • 复向量和复矩阵
    • 傅里叶矩阵

    正文

    这一讲主要介绍复数矩阵,其中一个最重要的例子就是傅里叶矩阵,它可以进行傅里叶变换。另外我们还会有快速傅里叶变换。

    复向量和复矩阵

    首先我们面对的问题是如何求复向量的模长。 我们可以回想一下,如何求一个复数的长度,比如: z 1 = a + b i z_1=a+bi z1=a+bi,那么 ∣ z 1 ∣ 2 = z 1 ˉ z 1 |z_1|^2=\bar{z_1}z_1 z12=z1ˉz1。对于向量,也是同样的方法,只不过还要遵循向量的乘法规律,也就是需要转置一下。那么求模长的公式,就比较显然了,对于复向量 z z z ∣ z ∣ 2 = z ˉ T z |z|^2=\bar{z}^Tz z2=zˉTz实际上可以简写为: ∣ z ∣ 2 = z H z |z|^2=z^Hz z2=zHz公式上的 H H H是埃尔米特 ( H e r m i t e ) (Hermite) (Hermite)的简称,意味着取共轭然后转置。那么,类似的就可以得到两个复向量的乘法公式了,比如复向量 x , y x,y x,y的乘积: y H x y^Hx yHx

    复数下的对称矩阵。 在实矩阵中对于对称矩阵我们有 A T A A^TA ATA,但是在复矩阵中,对称矩阵满足 Z H = Z Z^H=Z ZH=Z,并且这样的矩阵我们称之为:埃尔米特矩阵。这样的矩阵的特征值都为实数,并且特征向量相互垂直。在实矩阵中我们将由相互垂直的向量组成的矩阵称为正交矩阵 Q Q Q,并且它满足 Q T Q = I Q^TQ=I QTQ=I。但是对于复矩阵,它的相互垂直的特征向量组成的矩阵 U U U,满足: U H U = I U^HU=I UHU=I。此外,它不叫正交矩阵,它交酉矩阵 ( U n i t a r y ) (Unitary) (Unitary)

    傅里叶矩阵

    我们先给出一个示例是一个 n × n n\times n n×n的傅里叶矩阵。傅里叶矩阵有一个特殊的地方那就是它的索引是从 0 0 0开始的,而不是从 1 1 1。如下: F n = [ 1 1 1 . . . 1 1 w w 2 . . . w n − 1 1 w 2 w 4 . . . w 2 ( n − 1 ) : : : : : 1 w n − 1 w 2 ( n − 1 ) . . . w ( n − 1 ) 2 ] F_n=\begin{bmatrix}1&1&1&...&1\\1&w&w^2&...&w^{n-1}\\1&w^2&w^4&...&w^{2(n-1)}\\:&:&:&:&:\\1&w^{n-1}&w^{2(n-1)}&...&w^{(n-1)^2}\end{bmatrix} Fn=111:11ww2:wn11w2w4:w2(n1).........:...1wn1w2(n1):w(n1)2我们可以发现,每一项 F i j = w i j i , j = 0 , 1 , 2... n − 1 。 F_{ij}=w^{ij}\qquad i,j=0,1,2...n-1。 Fij=wiji,j=0,1,2...n1其中: w = e 2 π n i w=e^{\frac{2\pi}{n}i} w=en2πi关于 w w w,我们可以计算得到 w n = 1 w^n=1 wn=1 n n n是矩阵的阶数。 w w w是位于单位圆上的,可以参考欧拉公式,了解更过的复数细节。这是一个一般性的例子,我们可以看一个实际数字的例子,比如当 n = 4 n=4 n=4的时候: F 4 = [ 1 1 1 1 1 i i 2 i 3 1 i 2 i 4 i 6 1 i 3 i 6 i 9 ] = [ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ] F_4=\begin{bmatrix}1&1&1&1\\1&i&i^2&i^3\\1&i^2&i^4&i^6\\1&i^3&i^6&i^9\end{bmatrix}=\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix} F4=11111ii2i31i2i4i61i3i6i9=11111i1i11111i1i这个矩阵的各列都是正交的,验证的时候注意复向量的正交和实向量的正交是不同的。由于矩阵的各列都是正交的,我们可以把这个矩阵分解成许多个稀疏矩阵。另外由于矩阵的各列都是正交的,我们得到 F 4 H F 4 = I F_4^HF_4=I F4HF4=I,所以我们很快就得到了矩阵的逆为 F 4 H F_4^H F4H

    快速傅里叶变换

    快速傅里叶变换是通过分解矩阵来减少计算消耗。具体的内容参考其他资料。

    更多相关内容
  • 在不同的研究领域,傅立叶变换具有多种不同的变体形式,如连续傅立叶变换和离散傅立叶变换。 一维连续傅里叶变换 傅里叶变换 F(ω)=F[f(t)]=∫−∞+∞f(t)e−iωtdtF(\omega)=\mathcal{F}[f(t)]=\int_{-\infty}^{+...


    傅里叶变换

    傅立叶变换,表示能将满足一定条件的某个函数表示成三角函数(正弦和/或余弦函数)或者它们的积分的线性组合。在不同的研究领域,傅立叶变换具有多种不同的变体形式,如连续傅立叶变换和离散傅立叶变换。

    一维连续傅里叶变换

    1. 傅里叶变换
      F ( ω ) = F [ f ( t ) ] = ∫ − ∞ + ∞ f ( t ) e − i ω t d t (1) F(\omega)=\mathcal{F}[f(t)]=\int_{-\infty}^{+\infty}f(t)e^{-i\omega t}dt \quad\tag{1} F(ω)=F[f(t)]=+f(t)eiωtdt(1)
    2. 傅里叶逆变换
      f ( t ) = F − 1 [ F ( ω ) ] = 1 2 π ∫ − ∞ + ∞ F ( ω ) e i ω t d ω (2) f(t)=\mathcal{F}^{-1}[F(\omega)]=\dfrac{1}{2\pi} \int_{-\infty}^{+\infty}F(\omega) e^{i \omega t} d\omega \quad\tag{2} f(t)=F1[F(ω)]=2π1+F(ω)eiωtdω(2)
    • 其中由欧拉公式 e x = cos ⁡ x + i sin ⁡ x e^x=\cos x +i \sin x ex=cosx+isinx e − i ω t = cos ⁡ ω t − i sin ⁡ ω t e^{-i\omega t}=\cos \omega t -i \sin \omega t eiωt=cosωtisinωt .

    这样,把 e − i ω t = cos ⁡ ω t − i sin ⁡ ω t e^{-i\omega t}=\cos \omega t -i \sin \omega t eiωt=cosωtisinωt 代入傅里叶变换右端,直观地看,该公式实际上就是把左边关于 ω \omega ω的函数 F ( ω ) F(\omega) F(ω)用右边(无穷项)三角函数的线性组合来表示。(积分本质是求和)。

    可以注意到的一点是,右端项的函数 f f f的自变量是 t t t,左端项函数 F F F的自变量是 ω \omega ω,实际上这两个字母在通信领域有自己的含义: t t t 代表时间, ω \omega ω 代表 角 频 率 角频率 ,所以说傅里叶变换的核心是从时域到频域的变换,而这种变换是通过一组特殊的正交基三角函数正交基)来实现的。

    • 为什么要有这样的变换?

    • 三角函数正交基(也称为三角函数正交系)
      { 1 , cos ⁡ x , sin ⁡ x , cos ⁡ 2 x , sin ⁡ 2 x , … cos ⁡ n x , sin ⁡ n x } \{1,\cos x,\sin x,\cos 2x,\sin 2x,\dots \cos nx,\sin nx\} {1,cosx,sinx,cos2x,sin2x,cosnx,sinnx}
      三角函数系中,任何两个不相同的函数的乘积在 [ − π , π ] [-\pi,\pi] [π,π]上的积分都是零,即:
      ∫ − π π cos ⁡ n x d x = ∫ − π π sin ⁡ n x d x = 0 , ∫ − π π cos ⁡ m x cos ⁡ n x d x = 0 ( m ≠ n ) ∫ − π π sin ⁡ m x sin ⁡ n x d x = 0 ( m ≠ n ) ∫ − π π cos ⁡ m x sin ⁡ n x d x = 0 \int_{-\pi}^{\pi}\cos nx dx=\int_{-\pi}^{\pi}\sin nx dx=0,\\ \int_{-\pi}^{\pi}\cos mx\cos nx dx=0\quad (m \neq n)\\ \int_{-\pi}^{\pi}\sin mx\sin nx dx=0\quad (m \neq n)\\ \int_{-\pi}^{\pi}\cos mx\sin nx dx=0\quad ππcosnxdx=ππsinnxdx=0,ππcosmxcosnxdx=0(m=n)ππsinmxsinnxdx=0(m=n)ππcosmxsinnxdx=0
      而任何一个函数的平方在 [ − π , π ] [-\pi,\pi] [π,π]上的积分都不等于零,即:
      ∫ − π π cos ⁡ 2 n x d x = ∫ − π π sin ⁡ 2 n x d x = π , ∫ − π π 1 2 d x = 2 π . \int_{-\pi}^{\pi}\cos^2 nx dx=\int_{-\pi}^{\pi}\sin^2 nx dx=\pi,\\ \int_{-\pi}^{\pi}1^2 dx=2\pi. ππcos2nxdx=ππsin2nxdx=π,ππ12dx=2π.

    正交函数系:若两个函数 φ \varphi φ ψ \psi ψ [ a , b ] [a,b] [a,b] 上可积,且 ∫ a b φ ( x ) ψ ( x ) d x = 0 , \int_a^b \varphi(x)\psi(x)dx=0, abφ(x)ψ(x)dx=0, 则称函数 φ \varphi φ ψ \psi ψ [ a , b ] [a,b] [a,b] 上是正交的。

    \quad 因此三角函数系是正交函数系。

    一维离散傅里叶变换

    其实函数可以被理解为无限维的向量(这里考虑有限向量),只是需要把它们的定义域理解成自然数集合 { 0 , 1 , 2 , 3 …   } \{0,1 ,2 ,3\dots\} {0,1,2,3}。所以上上面的连续傅里叶变换公式实际上也可以被离散称为向量的形式,关键在于怎么把连续的自变量离散成有限的自然数点集。

    现在我们用向量 x = { x ( k ) } k = 0 N − 1 x=\{x(k)\}_{k=0}^{N-1} x={x(k)}k=0N1 代表被离散的函数 f f f y = { y ( n ) } n = 0 N − 1 y=\{y(n)\}_{n=0}^{N-1} y={y(n)}n=0N1 代表被离散的函数 F F F

    再次将傅里叶变换公式抄下来:
    F ( ω ) = F [ f ( t ) ] = ∫ − ∞ + ∞ f ( t ) e − i ω t d t F(\omega)=\mathcal{F}[f(t)]=\int_{-\infty}^{+\infty}f(t)e^{-i\omega t}dt F(ω)=F[f(t)]=+f(t)eiωtdt

    • 注意到需要被离散的自变量有 t t t ω \omega ω :
      t : { 0 , 1 , 2 , … , N − 1 } t:\{0,1,2,\dots,N-1\} t:{0,1,2,,N1};
      ω : { 0 , 2 π N , 2 2 π N ˙ , … , ( N − 1 ) 2 π N } \omega:\{0,\dfrac{2 \pi}{N},2 \dot \dfrac{2 \pi}{N},\dots,(N-1)\dfrac{2 \pi}{N}\} ω:{0,N2π,2N2π˙,,(N1)N2π}

    所以:

    1. 一维离散傅里叶公式:
      y ( k ) = ∑ n = o N − 1 x ( n ) ( e − 2 π N i ) k n , k = 0 , 1 , … N − 1 (3) y(k)=\sum_{n=o}^{N-1}x(n)(e^{-\frac{2 \pi}{N}i})^{kn},\quad k=0,1,\dots N-1\quad\tag{3} y(k)=n=oN1x(n)(eN2πi)kn,k=0,1,N1(3)
    2. 一维离散逆傅里叶公式:
      x ( n ) = 1 n ∑ k = o N − 1 y ( k ) ( e 2 π N i ) k n , n = 0 , 1 , … N − 1 (4) x(n)=\dfrac{1}{n}\sum_{k=o}^{N-1}y(k)(e^{\frac{2 \pi}{N}i})^{kn},\quad n=0,1,\dots N-1 \quad\tag{4} x(n)=n1k=oN1y(k)(eN2πi)kn,n=0,1,N1(4)

    将一维离散傅里叶公式展开成矩阵向量相乘的形式:

    ( y ( 0 ) y ( 1 ) ⋮ y ( N − 1 ) ) = ( w − 0 ⋅ 0 w − 0 ⋅ 1 ⋯ w − 0 ⋅ ( N − 1 ) w − 1 ⋅ 1 w − 1 ⋅ 1 ⋯ w − 1 ⋅ ( N − 1 ) ⋮ ⋮ ⋱ ⋮ w − ( N − 1 ) ⋅ 1 w − ( N − 1 ) ⋅ 1 ⋯ w − ( N − 1 ) ⋅ ( N − 1 ) ) ( x ( 0 ) x ( 1 ) ⋮ x ( N − 1 ) ) ( 5 ) \left( \begin{matrix} y(0)\\ y(1)\\ \vdots \\y(N-1) \end{matrix} \right)= \left( \begin{matrix} w^{-0\cdot0}& w^{-0\cdot1} &\cdots & w^{-0\cdot(N-1)}\\ w^{-1\cdot1}& w^{-1\cdot1} &\cdots & w^{-1\cdot(N-1)}\\ \vdots&\vdots&\ddots & \vdots\\ w^{-(N-1)\cdot1}& w^{-(N-1)\cdot1} &\cdots & w^{-(N-1)\cdot(N-1)} \end{matrix} \right) \left( \begin{matrix} x(0)\\ x(1)\\ \vdots \\x(N-1) \end{matrix} \right) \quad(5) y(0)y(1)y(N1)=w00w11w(N1)1w01w11w(N1)1w0(N1)w1(N1)w(N1)(N1)x(0)x(1)x(N1)(5)

    • 其中 w = e 2 π N i w=e^{\frac{2 \pi}{N}i} w=eN2πi.

    傅里叶矩阵

    其实 ( 5 ) (5) (5)式中右端矩阵中的 w w w复数n阶单位根 n t h n^{th} nth roots of unity):
    { 1 , w , w 2 , ⋯   , w n − 1 } \{1,w,w^2,\cdots,w^{n-1}\} {1,w,w2,,wn1}

    • 说明: n n n为 给定正实数
      w = e 2 π n i = cos ⁡ 2 π n + i sin ⁡ 2 π n w=e^{\frac{2 \pi}{n}i}=\cos \dfrac{2\pi}{n}+i \sin \dfrac{2\pi}{n} w=en2πi=cosn2π+isinn2π.
    • 解释:复数n阶单位根是方程 z n = 1 z^n=1 zn=1 的所有解。
    • 性质:
      a.) w n = 1 w^n=1 wn=1 ,
      b.) w w ˉ = 1 w\bar{w}=1 wwˉ=1,
      c.) w ˉ = w − 1 \bar{w}=w^{-1} wˉ=w1,
      d.) w ˉ k = w − k = w n − k \bar{w}^k=w^{-k}=w^{n-k} wˉk=wk=wnk,
      e.) 1 + w + w 2 + ⋯ + w n − 1 = 0. 1+w+w^2+\cdots+w^{n-1}=0. 1+w+w2++wn1=0.

    我们用 F ( = F n ) F(=F_n) F(=Fn)来表示 n n n傅里叶矩阵,则:
    F ∗ = 1 n { w ( i − 1 ) ( j − 1 ) } = 1 n ( 1 1 1 ⋯ 1 1 w w 2 ⋯ w ( n − 1 ) 1 w 2 w 4 ⋯ w 2 ( n − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 w n − 1 w 2 ( n − 1 ) ⋯ w ( n − 1 ) ( n − 1 ) ) (6) F^*=\dfrac{1}{\sqrt{n}}\{w^{(i-1)(j-1)}\}=\dfrac{1}{\sqrt{n}}\left( \begin{matrix} 1&1&1&\cdots&1\\ 1&w&w^2&\cdots&w^{(n-1)}\\ 1&w^2&w^4&\cdots&w^{2(n-1)}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&w^{n-1}&w^{2(n-1)}&\cdots&w^{(n-1)(n-1)} \end{matrix} \right) \quad\tag{6} F=n 1{w(i1)(j1)}=n 111111ww2wn11w2w4w2(n1)1w(n1)w2(n1)w(n1)(n1)(6)
    根据上面所述的复数n阶单位根的性质我们知道序列 w k , k = 0 , 1 , ⋯ w^k,k=0,1,\cdots wk,k=0,1,是周期序列,因此实际上矩阵 F F F中只有 n n n个不同的元素,即:
    F ∗ = 1 n ( 1 1 1 ⋯ 1 1 w w 2 ⋯ w ( n − 1 ) 1 w 2 w 4 ⋯ w ( n − 2 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 w n − 1 w ( n − 2 ) ⋯ w ) (7) F^*=\dfrac{1}{\sqrt{n}}\left( \begin{matrix} 1&1&1&\cdots&1\\ 1&w&w^2&\cdots&w^{(n-1)}\\ 1&w^2&w^4&\cdots&w^{(n-2)}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&w^{n-1}&w^{(n-2)}&\cdots&w \end{matrix} \right) \quad\tag{7} F=n 111111ww2wn11w2w4w(n2)1w(n1)w(n2)w(7)

    • 注意 * 代表共轭对称
    • F ∗ F^* F矩阵的放缩系数 1 n \dfrac{1}{\sqrt{n}} n 1 是为了保证 F ∗ F^* F的每一列都是单位向量(长度为1).
    • F F F F ∗ F^* F都是对称矩阵: F = F T , F ∗ = ( F ∗ ) T = F ˉ , F = F ˉ ∗ . F=F^{T} ,\quad F^*=(F^*)^T=\bar{F},\quad F=\bar{F}^*. F=FT,F=(F)T=Fˉ,F=Fˉ.
    • F F F是酉矩阵: F F ∗ = F ∗ F = I o r F − 1 = F ∗ FF^*=F^*F=I \quad or\quad F^{-1}=F^* FF=FF=IorF1=F.

    这时候回头看 ( 5 ) (5) (5)式会发现右端的 N × N N \times N N×N 矩阵实际上就是 N ⋅ F ∗ \sqrt{N}\cdot F^* N F

    Matlab中fft函数和ifft的含义

    具体参看:官方文档_fft

    这里以最简单的一种用法为例, x x x y y y 表示两个 n n n 维向量:

    • y=fft(x)= N ⋅ F ∗ x \sqrt{N}\cdot F^*x N Fx
    • x=ifft(y)= 1 N ⋅ F y \dfrac{1}{\sqrt{N}}\cdot Fy N 1Fy
    展开全文
  • 在 Welch 边界附近具有不相干性的确定性裁剪(逆)傅立叶矩阵([M,N] 矩阵的理论最小值)在涉及压缩感知、稀疏编码、字典学习等的许多应用中非常有用。这是根据报告的工作实现的在“使用几乎差集的基于傅立叶的压缩...
  • 这一讲我们来讲一下复矩阵。线性代数中,复矩阵是避免不了的话题,因为一个简单实矩阵都有可能有复数特征值。 复矩阵 我们着重看一下复矩阵和实矩阵在运算上的区别。 距离 首先,一个复数向量的的距离求法发生了...

    这一讲我们来讲一下复矩阵。线性代数中,复矩阵是避免不了的话题,因为一个简单实矩阵都有可能有复数特征值。

    复矩阵

    我们着重看一下复矩阵和实矩阵在运算上的区别。

    1. 距离

    首先,一个复数向量的的距离求法发生了变化
    x ⊤ x    →    x H x \bm{x}^\top\bm{x}~~\rightarrow~~ \bm{x}^H\bm{x} xx    xHx

    其中, x H \bm{x}^H xH 指的是共轭转置。

    相应的,内积也发生了变化

    1. 内积
      x ⊤ y    →    x H y \bm{x}^\top\bm{y}~~\rightarrow ~~ \bm{x}^H\bm{y} xy    xHy

    2. 对称矩阵 symmetric matrix → \rightarrow 厄米矩阵 Hermitian matrix

    之前讲到对阵矩阵时说过,对称矩阵很好的性质在复数矩阵的情况下应该变为
    A ⊤ = A    →    A H = A \bm{A}^\top=\bm{A}~~\rightarrow ~~ \bm{A}^H=\bm{A} A=A    AH=A

    1. 正交矩阵 orthogonal matrix → \rightarrow 酉矩阵 Unitary matrix

    Q ⊤ Q = I    →    Q H = Q \bm{Q}^\top\bm{Q}=I~~\rightarrow ~~ \bm{Q}^H=\bm{Q} QQ=I    QH=Q

    傅里叶矩阵

    下面我们讲一下目前为止最重要的复数矩阵: 傅里叶矩阵 Fourier Matrix. 它实际上是傅里叶变换的矩阵形式。

    定义

    我们来看看什么是傅里叶矩阵
    F n = [ 1 1 1 ⋯ 1 1 W 1 W 2 ⋯ W n − 1 1 W 2 W 4 ⋯ W 2 ( n − 1 ) ⋮ ⋮ ⋮ ⋮ ⋮ 1 W n − 1 W 2 ( n − 1 ) ⋯ W ( n − 1 ) 2 ] \bm{F}_n=\begin{bmatrix} 1 & 1 & 1& \cdots & 1\\ 1 & W^1 & W^2& \cdots & W^{n-1}\\ 1 & W^2 & W^4& \cdots & W^{2(n-1)}\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ 1 & W^{n-1}& W^{2(n-1)}& \cdots& W^{(n-1)^2}\\ \end{bmatrix} Fn=11111W1W2Wn11W2W4W2(n1)1Wn1W2(n1)W(n1)2

    可以看出,其中每一项 ( F n ) i j = W i j (F_n)_{ij}=W^{ij} (Fn)ij=Wij, i , i = 0 , 1 , 2 , . . . , n − 1 i,i=0,1,2,...,n-1 i,i=0,1,2,...,n1, 其中 W W W 是复平面单元圆分割成 n n n 份得到的向量,即
    W = e j 2 π n W=e^{j\frac{2\pi}{n}} W=ejn2π

    一个最简单的例子是 F 4 \bm{F}_4 F4, 因为相位刚刚好取到坐标轴上,此时
    F 4 = [ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ] \bm{F}_4=\begin{bmatrix} 1 & 1 & 1& 1\\ 1 & i & -1 & -i\\ 1 & -1 & 1 & -1\\ 1 & -i& -1& i\\ \end{bmatrix} F4=11111i1i11111i1i

    这个矩阵有什么特点尼?它是一个酉矩阵,且其中的每一项都是单位圆上的一个相位。
    F n H F n = I \bm{F}_n^H\bm{F}_n=I FnHFn=I

    它的逆也很容易写出来
    F n − 1 = F n H {\bm{F}}_n^{-1}= \bm{F}_n^H Fn1=FnH

    因此,傅里叶变换和逆傅里叶变换可以写成矩阵形式为
    y = F n x \bm{y=F_n}\bm{x} y=Fnx

    x = F n H y \bm{x=F^{H}_n}\bm{y} x=FnHy

    快速傅里叶变换

    长久以来,傅里叶变换的运算复杂度 O ( n 2 ) \mathcal{O}(n^2) O(n2) 对没有高速计算机的时代非常不友好。快速傅里叶变换 FFT 应运而生。FFT的基本原理是divide and conquer,就是把一个 高维的傅里叶变换用低维表示出来,看下图就很明了了。

    在这里插入图片描述
    从矩阵角度我们也能得到相似的结论,
    在这里插入图片描述
    即,把一个高维 F 64 F_{64} F64 分解为 三部分乘积,其中最右侧是一个permutation matrix,是对输入的 x \bm{x} x 做 odd-even shuffle,中间的是俩低维 F 32 F_{32} F32 matrix组成的分块对角阵,左侧是butterfly network。这个分解与上图一一对应。

    我们可以继续divide and conquer把FFT进一步分解直至最低维度,最终写成矩阵连乘结果,复杂度降为 O ( 1 2 n log ⁡ 2 n ) \mathcal{O} (\frac{1}{2}n\log_2 n) O(21nlog2n), 只要看下图就非常明了了。

    在这里插入图片描述

    展开全文
  • 傅里叶矩阵及其MATLAB实现 小波变换矩阵及其MATLAB实现  傅里叶矩阵及其MATLAB实现 傅里叶矩阵的定义:(来源: http://mathworld.wolfram.com/FourierMatrix.html) 傅里叶矩阵的MATLAB实现:  dftmtx(N...

    主要内容:

    1. 傅里叶矩阵及其MATLAB实现
    2. 小波变换矩阵及其MATLAB实现 

    傅里叶矩阵及其MATLAB实现

    傅里叶矩阵的定义:(来源: http://mathworld.wolfram.com/FourierMatrix.html

    傅里叶矩阵的MATLAB实现:

      dftmtx(N) is the N-by-N complex matrix of values around the unit-circle whose inner product with a column vector of length N yields the discrete Fourier transform of the vector. If X is a column vector of length N, then dftmtx(N)*X yields the same result as FFT(X); however, FFT(X) is more efficient.

      The inverse discrete Fourier transform matrix is CONJ(dftmtx(N))/N.

    复制代码
    % clc;clear;
    N = 16;
    X = randn(N,1);
    dft_result1 = dftmtx(N)*X;
    dft_result2 = fft(X);
    % isEqual = all(dft_result1 == dft_result2);
    err = norm(dft_result1(:)-dft_result2(:));
    if err < 0.01
        fprintf('dftmtx(N)*X yields the same result as FFT(X)');
    else
        fprintf('dftmtx(N)*X does not yield the same result as FFT(X)');
    end
    复制代码

    小波变换矩阵及其MATLAB实现

    小波变换矩阵的概念:

    参考:http://blog.csdn.net/jbb0523/article/details/42470103

    小波变换矩阵的MATLAB实现:

    复制代码
    function [ ww ] = dwtmtx( N,wtype,wlev )
    %DWTMTX Discrete wavelet transform matrix
    %   This function generates the transform matrix ww according to input
    %   parameters N,wtype,wlev .
    %Detailed explanation goes here
    %   N is the dimension of ww
    %   wtype is the wavelet type
    %   wlev is the number of decomposition level
    %NOTE: The extension mode must be Periodization('per')
    [h,g]= wfilters(wtype,'d');         %Decomposition low&high pass filter
    L=length(h);                        %Filter length
    h_1 = fliplr(h);                    %Flip matrix left to right
    g_1 = fliplr(g);
    loop_max = log2(N);
    loop_min = double(int8(log2(L)))+1;
    if wlev>loop_max-loop_min+1
        fprintf('\nWaring: wlev is too big\n');
        fprintf('The biggest wlev is %d\n',loop_max-loop_min+1);
        wlev = loop_max-loop_min+1;
    end
    ww=1;
    for loop = loop_max-wlev+1:loop_max
        Nii = 2^loop;
        p1_0 = [h_1 zeros(1,Nii-L)];
        p2_0 = [g_1 zeros(1,Nii-L)];
        p1 = zeros(Nii/2,Nii);
        p2 = zeros(Nii/2,Nii);
        for ii=1:Nii/2
            p1(ii,:)=circshift(p1_0',2*(ii-1)+1-(L-1)+L/2-1)';
            p2(ii,:)=circshift(p2_0',2*(ii-1)+1-(L-1)+L/2-1)';
        end
        w1=[p1;p2];
        mm=2^loop_max-length(w1);
        w=[w1,zeros(length(w1),mm);zeros(mm,length(w1)),eye(mm,mm)];
        ww=ww*w;
        clear p1;clear p2;
    end
    
    %The end!!!
    end
    复制代码

    验证是否与Matlab自带的函数wavedec所得结果一致:

    复制代码
    %验证函数dwtmtx的正确性
    clear all;close all;clc;
    N = 2^7;
    % 'db1' or 'haar', 'db2', ... ,'db10', ... , 'db45'
    % 'coif1', ... , 'coif5'
    % 'sym2', ... , 'sym8', ... ,'sym45'
    % 'bior1.1', 'bior1.3', 'bior1.5'
    % 'bior2.2', 'bior2.4', 'bior2.6', 'bior2.8'
    % 'bior3.1', 'bior3.3', 'bior3.5', 'bior3.7'
    % 'bior3.9', 'bior4.4', 'bior5.5', 'bior6.8'
    % 'rbio1.1', 'rbio1.3', 'rbio1.5'
    % 'rbio2.2', 'rbio2.4', 'rbio2.6', 'rbio2.8'
    % 'rbio3.1', 'rbio3.3', 'rbio3.5', 'rbio3.7'
    % 'rbio3.9', 'rbio4.4', 'rbio5.5', 'rbio6.8'
    wtype = 'rbio6.8';
    wlev_max = wmaxlev(N,wtype);
    if wlev_max == 0
        fprintf('\nThe parameter N and wtype does not match!\n');
    end
    dwtmode('per');
    for wlev = 1:wlev_max
        ww = dwtmtx(N,wtype,wlev);
        x = randn(1,N);
        y1 = (ww*x')';
        [y2,y2l] = wavedec(x,wlev,wtype);
        y_err = sum((y1-y2).*(y1-y2));
        fprintf('wlev = %d: y_err = %f\n',wlev,y_err);
    end
    复制代码
    展开全文
  • 傅里叶变换的矩阵分析

    万次阅读 多人点赞 2017-11-16 22:59:22
    离散傅里叶变换在矩阵中的分析本文是对 [Matrix Analysis and Applied Linear Algebra][1] 一书中第5.8章离散傅里叶变换(DISCRETE FOURIER TRANSFORM)的浅显解读和翻译。因个人能力有限,理解难免出现偏差,仅作...
  • 这种移位将图像或其他 2D 矩阵循环移位任意数量的像素(可以是小数)。 我没有对其进行太多测试,但代码很短,因此应该很容易适应。 用法: y = FourierShift(x, [delta_x delta_y]) x 是输入矩阵。 y 是输出。 ...
  •  矩阵当然也有可能包含复数,最重要的复矩阵是傅立叶矩阵,它用于傅立叶变换。一种特殊的傅立叶变换是快速傅立叶变换(fast Fourier transform),简称FFT,在计算机中很常用,特别是涉及到大数...
  • 循环矩阵傅里叶变换

    千次阅读 2020-07-31 10:56:30
    \cdots,w_n^{(n-1)i})|0\le i \lt n\}{(wn0​,wni​,wn2i​,⋯,wn(n−1)i​)∣0≤i即 AAA可对角化为 W−1DWW^{-1}DWW−1DW,其中 WWW为傅里叶变换的矩阵, DDD为傅里叶变换后的点值所组成的矩阵。 证明 直接搬运了。
  • 傅里叶变换矩阵

    千次阅读 2020-10-10 16:31:08
    1. matlab 的fft()函数是没有归一化的DFT ... %将n倒置之后与矩阵k进行矩阵的代数运算,为N*N矩阵,此处发生了N*N次乘法运算 Wnnk = Wn.^nk; %将常数Wn与nk进行点幂运算,为N*N矩阵,此处发生了N*N次点幂
  • 二维傅立叶变换矩阵 离散傅立叶变换的矩阵表示 可以通过编程实现矩阵表示,但是运算量很大。 我这里用MATLAB自带的dftmtx函数实现。 dftmtx()函数——离散傅立叶变换矩阵 句法 a = dftmtx(n); n — 离散傅立叶变换...
  • 二维傅里叶变换的矩阵表示

    千次阅读 2020-03-30 23:25:29
    二维傅里叶变换的矩阵表示二维傅里叶变换公式二维傅里叶矩阵公式表达1. F(v,u)F(v,u)F(v,u) 为 R1×1R^{1\times1}R1×1 时2. F(v,u)F(v,u)F(v,u) 为 RNv×MuR^{N_v\times M_u}RNv​×Mu​ 时 说明: 做完了图像处理...
  • 傅立叶变换则是完全的频域分析,傅里叶级数适用于对周期性现象做数学上的分析,傅里叶变换可以看作傅里叶级数的极限形式,也可以看作是对周期现象进行数学上的分析,同时也适用于非周期性现象的分析。傅里叶级数...
  • matlab傅里叶变换矩阵

    千次阅读 2017-03-17 18:57:23
    matlab傅里叶变换矩阵
  • All circulant matrices are made diagonal by the Discrete Fourier Transform (DFT)...任意循环矩阵可以被傅里叶变换矩阵对角化。 文献中,一般用如下方式表达这一概念: 其中XXX是循环矩阵,x^\hat{x}x^是原向量x
  • DFT的matlab源代码傅里叶 傅立叶实现用于执行离散傅立叶变换(DFT)的功能。 有关更多信息,请参阅文档。
  • 压缩感知的常见测量矩阵

    万次阅读 多人点赞 2015-03-28 13:50:20
     下面首先给出十篇参考文献中有关测量矩阵的叙述,然后以一篇硕士论文中对七种常见测量矩阵的描述依据,给出了这七种常见测量矩阵的MATLAB实现代码,以为以后的研究提供一个参考,由于目前还没有一个简单有效的测量...
  • 添加链接描述
  • 使用频域对图像/矩阵/向量(可以是复数)进行上/下采样。 矩阵/向量应该是高度连续的(具有连续导数)以获得合理的上/下采样 如果用户上采样到接近 2 的幂,则可以实现加速。在此代码中没有进行优化以实现有效的 fft...
  • 定义 $T_n(i,j)=t_{j-i} $ 为$n\times n$ 阶$\tt Toeplitz$矩阵通过令矩阵$B_n=$ 从而构造出$2n\times 2n$阶循环矩阵 假设有一$n\times 1$阶列向量$\bf u$ 其中,$C_{2n}$可以由快速傅里叶对角化...
  • 矩阵傅里叶变换的理解

    万次阅读 2019-03-19 16:27:44
    可以查看:...当X是一个矩阵时, fft(X)是把每个列作为向量,得到每列元素的傅里叶变换。 本人就是因为忽略了这一点,程序跑出的代码不对,调试了很久才找到原因。难受,前车之鉴呀 ...
  • 本代码是一个 Matlab 函数,它提供给定信号 x[n] 的短时傅立叶变换 (STFT)。 该函数是 Matlab 命令“spectrogram”的替代方法。 函数的输出是: 1) 具有复数 STFT 系数的矩阵,列上有时间,行上有频率; 2) 频率向量...
  • 计算以下图像的离散傅里叶变换 f=[1441244224421441] f=\begin{bmatrix}1&4&4&1\\2&4&4&2\\2&4&4&2\\1&4&4&1\end{bmatrix} f=⎣⎢⎢⎡​1221​4444​4444​1221​...
  • 关于傅立叶变换,无论是书本还是在网上可以很容易找到关于傅立叶变换的描述,但是大都是些故弄玄虚的文章,太过抽象,尽是一些让人看了就望而生畏的公式的罗列,让人很难能够从感性上得到理解,最近,我偶尔从网上...
  • 原创短时傅立叶变换matlab分析-短时傅立叶变换matlab仿真程序.txt RT 程序的一小部分: clear all; clc; %------------------>Basic Parameters f1 = 500; f2 = 1000; fN = 8000; n = 10000; t = ...
  • DCF跟踪论文,其用到了循环矩阵来生产密集采样样本,并且用循环矩阵傅里叶变换的关系来简化计算,即在频域用循环矩阵的基向量就可以表述循环矩阵。现对文章中循环矩阵傅里叶相关的两个重要公式进行推导和证明。 ...
  • 本文是Gilbert Strang的线性代数导论课程笔记。... 第二十七课时:复数矩阵和快速傅里叶变换 本讲学习有关复数的相关...一个重要的复矩阵的例子就是傅里叶矩阵。 还将介绍傅里叶变换,简称FFT,在计算机里常用,特别是

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,011
精华内容 9,604
关键字:

傅里叶矩阵

友情链接: 新建文件夹.zip