27.復(fù)數(shù)矩陣，快速傅里葉變換

對(duì)于實(shí)矩陣而言，特征值為復(fù)數(shù)時(shí)，特征向量一定為復(fù)向量，由此引入對(duì)復(fù)向量的學(xué)習(xí)

1. 求模長(zhǎng)及內(nèi)積

   假定一個(gè)復(fù)向量 z ? = [ z 1 z 2 ? z n ] \vec{z} = \begin{bmatrix} z_1 \\ z_2 \\ \vdots\\ z_n \end{bmatrix} z = ?z1?z2??zn?? ?，其中$z_1,z_2,?,z_n$為復(fù)數(shù)，所以該向量不再屬于$R^n$，而是屬于$n$維復(fù)空間$C^n$

   顯然再使用$\sqrt{z^{T}z}$無(wú)法求出模長(zhǎng)，比如對(duì)于$z=\left[\begin{array}{c}1\\ i\end{array}\right]$有$\sqrt{z^{T}z}=\left[\begin{array}{cc}1& i\end{array}\right]\left[\begin{array}{c}1\\ i\end{array}\right]=0\ne \sqrt{2}$

   由上一講的內(nèi)容可以得到$|z|=\sqrt{{\overline{z}}^{T}z}$，我們把求共軛和轉(zhuǎn)置兩步操作一起記作$H$（來(lái)自$Hermite$），即$z^H={\overline{z}}^T$

   同理，求內(nèi)積時(shí)也使用$H$，即對(duì)于兩個(gè)復(fù)向量$x,y$，有$x?y=x^{H}y$，此時(shí)內(nèi)積為$0$仍然可以說(shuō)明向量正交，對(duì)于矩陣也類(lèi)似

2. 對(duì)稱(chēng)矩陣的推廣

   對(duì)于實(shí)矩陣，對(duì)稱(chēng)矩陣即滿(mǎn)足$A^T=A$的矩陣，推廣到復(fù)矩陣，我們把滿(mǎn)足$A^H=A$的矩陣稱(chēng)作厄米特矩陣

   可以發(fā)現(xiàn)厄米特矩陣的對(duì)角線(xiàn)元素均為實(shí)數(shù)，因?yàn)樗鼈冊(cè)谵D(zhuǎn)置時(shí)不變，所以在求共軛時(shí)也不變，其它元素與轉(zhuǎn)置后的對(duì)應(yīng)元素互為共軛

   由上一講可知厄米特矩陣的特征值一定為實(shí)數(shù)

3. 正交矩陣的推廣

   對(duì)于實(shí)矩陣，正交矩陣即滿(mǎn)足$Q^{T}Q=I$的方陣，推廣到復(fù)矩陣，我們把滿(mǎn)足$Q^{H}Q=I$的方陣稱(chēng)作酉矩陣

   可以發(fā)現(xiàn)酉矩陣的列向量組成復(fù)空間下的一組標(biāo)準(zhǔn)正交基，其轉(zhuǎn)置與正交一致且均為酉矩陣

4. 傅里葉矩陣

   傅里葉變換是一種分析信號(hào)的方法，它可分析信號(hào)的成分，也可用這些成分合成信號(hào)。許多波形可作為信號(hào)的成分，比如正弦波、方波、鋸齒波等，傅里葉變換用正弦波作為信號(hào)的成分。由于傅里葉變換經(jīng)常用在計(jì)算機(jī)上，而在電子工程或計(jì)算機(jī)中，方陣的行和列都是從$0$開(kāi)始到$n?1$結(jié)束的，所以在討論傅里葉矩陣時(shí)遵從這種下標(biāo)規(guī)則。

   傅里葉矩陣是一種酉矩陣，它滿(mǎn)足$(F_n{)}_{i,j}=\frac{1}{n}{w}^{i?j},i,j=0,?,n?1$（$w=e^{2\pi i/n}$），即：

   F n = 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 ) 2 ] F_n = \dfrac{1}{n} \begin{bmatrix} 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)^2} \end{bmatrix} Fn?=n1? ?111?1?1ww2?wn?1?1w2w4?w2(n?1)???????1wn?1w2(n?1)?w(n?1)2? ?

   可以發(fā)現(xiàn)$w=e^{2\pi i/n}=cos\frac{2\pi }{n}+isin\frac{2\pi }{n}$，落在復(fù)平面原點(diǎn)為圓心的單位圓上，且對(duì)應(yīng)的角度為一圈的$\frac{1}{n}$，所以$w$乘上自己相當(dāng)于增加角度$\frac{2\pi }{n}$，因此$w^{kn}=(w^n{)}^k=1,k\in Z$

   證明傅里葉矩陣是酉矩陣：

   ? ???設(shè)$F_n$的列向量分別為$f_0,f_2,?,f_{n?1}$，即證$f_a^H{f}_b=\{\begin{array}{c}0,a\ne b\\ 1,a=b\end{array}$

   ? ???$\begin{array}{rl}{f}_a^H{f}_b& =\overline{(F_n{)}_{0,a}}?(F_n{)}_{0,b}+\overline{(F_n{)}_{1,a}}?(F_n{)}_{1,b}+?+\overline{(F_n{)}_{n?1,a}}?(F_n{)}_{n?1,b}\\ & =w^{0(a+b)}+w^{a+b}+?+w^{(n?1)(a+b)}\end{array}$

   ? $暫時(shí)不會(huì)證明$

5. 傅里葉變換

   當(dāng)$n=4$時(shí)，$\frac{2\pi }{n}=\frac{\pi }{2}$，所以$w$的乘方落在實(shí)軸和虛軸上2，由此得到四階傅里葉矩陣 F 4 = 1 4 [ 1 1 1 1 1 i ? 1 ? i 1 ? 1 1 ? 1 1 ? i ? 1 i ] F_4 = \dfrac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix} F4?=41? ?1111?1i?1?i?1?11?1?1?i?1i? ?

   用$F_4$左乘四維向量即為四點(diǎn)離散傅里葉變換（$DFT$），用$F_4^{?1}$左乘四維向量即為傅里葉逆變換

6. 快速傅里葉變換

   實(shí)際上可以將傅里葉矩陣分解為一系列“稀疏矩陣”，這些矩陣具有大量零元素，可以很方便地求逆及用于相乘

   現(xiàn)在考慮$F_{64}$與$F_{32}$之間的聯(lián)系，假設(shè)$F_{32},F_{64}$中的$w$分別為$w_{32},w_{64}$，則$w_{64}^2=w_{32}$

   先說(shuō)結(jié)論： F 64 = 1 2 [ I D I ? D ] [ F 32 O O F 32 ] [ 1 0 0 0 ? 0 0 1 0 ? ? ? ? ? ? 0 1 0 0 ? 0 0 0 1 ? ? ? ? ? ? ] F_{64} = \dfrac{1}{2} \begin{bmatrix} I & D \\ I & -D\end{bmatrix} \begin{bmatrix} F_{32} & O \\ O & F_{32}\end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 & \cdots \\ 0 & 0 & 1 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 1 & 0 & 0 & \cdots \\ 0 & 0 & 0 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots \end{bmatrix} F64?=21?[II?D?D?][F32?O?OF32??] ?10?00??00?10??01?00??00?01????????? ?，其中 D = [ 1 0 0 ? 0 0 w 0 ? 0 0 0 w 64 2 ? 0 ? ? ? ? ? 0 0 0 ? w 64 31 ] D = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 \\ 0 & w_{} & 0 & \cdots & 0 \\ 0 & 0 & w_{64}^2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & w_{64}^{31} \end{bmatrix} D= ?100?0?0w?0?0?00w642??0???????000?w6431?? ?

   證明： 可以發(fā)現(xiàn)$F_{64}$拆分出的第三個(gè)矩陣將用于進(jìn)行傅里葉變換的向量的偶數(shù)位元素提到了前面而將奇數(shù)位元素放到了后面，然后拆分出的第二個(gè)矩陣對(duì)剛才得到的新向量中的前后兩部分分別做一次$32$階傅里葉變換

   ? ???對(duì)于新向量前半部分，第$i$個(gè)元素在求$32$階傅里葉變換后的第$j$行時(shí)乘上了$w_{32}^{ji}$，而新向量前半部分的第$i$個(gè)元素是原向量的第$2?i$個(gè)元素，這說(shuō)明它在求$64$階傅里葉變換后的第$j$行時(shí)應(yīng)該乘上$w_{64}^{2ji}$，剛好$w_{32}^{ji}=w_{64}^{2ji}$，所以$F_{64}$拆分出的第一個(gè)矩陣左半部分上方是單位向量，對(duì)于下方，新向量前半部分的第$i$個(gè)元素在求$64$階傅里葉變換后的第$32+j$行時(shí)應(yīng)乘上$w_{64}^{2(32+j)i}=w_{32}^{(32+j)i}=w_{32}^{ji}{w}_{32}^{32i}=w_{32}^{ji}(?1{)}^i=w_{32}^{ji}$，所以左半部分下方也是單位矩陣

   ? ???對(duì)于新向量后半部分，第$i$個(gè)元素在求$32$階傅里葉變換后的第$j$行時(shí)乘上了$w_{32}^{ji}$，而在求$64$階傅里葉變換后的第$j$行時(shí)應(yīng)該乘上$w_{64}^{j(2i+1)}$，即$w_{32}^{ji}?w_{64}^j$，由此得到$D$，對(duì)于拆分出的第一個(gè)矩陣右半部分下方，新向量后半部分的第$i$個(gè)元素在求$64$階傅里葉變換后的第$32+j$行時(shí)應(yīng)乘上$w_{64}^{2(32+j)i}=w_{32}^{ji}(?1{)}^i=?w_{32}^{ji}$，所以右半部分下方是$?D$

   ? ???最后說(shuō)明$\frac{1}{2}$，因?yàn)榍懊孢M(jìn)行$32$階傅里葉變換時(shí)只除以了$32$，所以最后還要再除以$2$才能達(dá)到除以$64$

   ? ???為了直觀(guān)地說(shuō)明，此處只證明了$F_{64}$到$F_{32}$的拆分，對(duì)于$F_{2n}$到$F_n$的拆分，將具體的數(shù)字換為字母后也可得證

   直接進(jìn)行$64$階傅里葉變換的時(shí)間復(fù)雜度是$O(n^2)$，而拆分為三個(gè)矩陣后，第三個(gè)矩陣和原向量相乘時(shí)間復(fù)雜度為$O(n)$，第二個(gè)矩陣和新向量相乘時(shí)間復(fù)雜度為$O(\frac{n^2}{2})$，此時(shí)得到的向量和第一個(gè)矩陣相乘時(shí)間復(fù)雜度為$O(n)$，總時(shí)間復(fù)雜度為$O(2(\frac{n}{2}{)}^2+n)$，當(dāng)然這還沒(méi)有結(jié)束，因?yàn)榈诙€(gè)矩陣的$F_{32}$可以進(jìn)行類(lèi)似的拆分得到含有$F_{16}$的三個(gè)矩陣，這樣剛才求得的總時(shí)間復(fù)雜度進(jìn)一步簡(jiǎn)化得到$O(2(2(\frac{n}{4}{)}^2+\frac{n}{2})+n)=O(2^2(\frac{n}{4}{)}^2+2n)$，以此類(lèi)推，一層層拆分下去，時(shí)間復(fù)雜度就會(huì)降為$O(n+nlogn)$，即$O(nlogn)$

打賞

制作不易，若有幫助，歡迎打賞！

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-753522.html

到了這里，關(guān)于MIT線(xiàn)性代數(shù)筆記-第27講-復(fù)數(shù)矩陣，快速傅里葉變換的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！