|
第22講主要闡述了實數(shù)的情況，本節(jié)將進一步擴大研究范圍至復數(shù)范圍。上一節(jié)，介紹了實矩陣特征值是實數(shù)的處理方法，實際中也會有復數(shù)的特征值，特征向量也會是復數(shù)，因此后文會介紹如何處理復數(shù)。 復向量不在屬于n維實數(shù)空間，而是屬于n維復空間，每個元素都是復數(shù)；其中，H代表共軛轉(zhuǎn)置。這個公式說明，求模長前先求復數(shù)的共軛轉(zhuǎn)置。 大部分情況下，復向量內(nèi)積也是復數(shù)，若兩者相同就是模長平方。
實矩陣對稱：A的轉(zhuǎn)置等于矩陣A，只有在A是實矩陣時才成立。
這叫做埃爾米特矩陣，這些矩陣的特征值都是實數(shù)，特征向量互相垂直。垂直，假設(shè)有相互垂直的向量q1,q2....qn,模長為1，構(gòu)成標準正交基；垂直是指qi共軛轉(zhuǎn)置與qj內(nèi)積等于0（i不等于j，相等時內(nèi)積是1）對于復矩陣，若Q共軛轉(zhuǎn)置乘以矩陣Q是單位矩陣，則Q是正交矩陣，或酋矩陣，它與正交矩陣很類似，它是n階方陣，列向量是單位向量且正交。傅里葉矩陣是最重要的復矩陣，在傅里葉變換中及其重要。特殊情況下，叫做快速傅里葉變換FFT，特別是當涉及大數(shù)據(jù)的時候，可以實現(xiàn)快速的傅里葉變換，它將矩陣乘法的n方次運算減少到nlogn次運算。根據(jù)公式可以確定w，矩陣就可以確定，顯然在復平面內(nèi)，w是在單位圓上，則w的n次冪模長是1。舉例，當n=4時，逆時針旋轉(zhuǎn)90°，此時w=i，則w平方=-1，w的立方等于-i，w的四次方等于1?，F(xiàn)在可以寫出4階傅里葉矩陣，這個矩陣非常重要，通過它可以得到一個四點傅里葉變換（離散的）。這個變換實際作用于四維向量，向量分別左乘矩陣F4或其逆，一個是傅里葉變換另一個是傅里葉逆變換；傅里葉矩陣的逆的各列也是正交的，因此它的逆也是很容易求得。傅里葉矩陣還有非常特別性質(zhì)，可以分解為一系列“稀疏矩陣”，這些矩陣包含大量零元素，無論乘以它還是它的逆都是非常快捷的。 所以，根據(jù)前文酋矩陣性質(zhì)，傅里葉矩陣的逆等于其共軛轉(zhuǎn)置，即逆矩陣各列也是正交。舉例， 
所以F64和F32也存在一定聯(lián)系：F64與由兩個F32構(gòu)成的方陣有關(guān)，它包含兩個F32以及兩個零矩陣，零矩陣才是關(guān)鍵；如果這個矩陣乘以一個列向量，一般情況下需要64的平方次數(shù)值乘法，而現(xiàn)在減半；為使兩邊相等，必須補充一些修正矩陣，左右各一個矩陣，美妙的是這些修正矩陣也包含大量零元素，因此可以極大化簡64的平方次乘法運算，現(xiàn)在只需要2x32平方次在加上修正開銷。 右側(cè)修正矩陣是一個奇偶置換矩陣，它把奇數(shù)位置上的分量統(tǒng)統(tǒng)排到偶數(shù)位置上的分量前面，奇偶置換矩陣由上下兩個16x32的矩陣組成，具體如下，置換在電腦中基本瞬間完成； 左邊修正矩陣是由單位陣I和對角陣D（是由w的冪組成，1，w一直到w31次冪）組成，乘以單位矩陣I也是不需要花費時間的，因此修正開銷實際上是左乘對角陣D的計算開銷，因此總計約2x32的平方+32次運算。
（左乘P相當于依次獲得第一行、第三行...然后第2行、第4行....）
從F32->F16，運算次數(shù)變?yōu)?x{2x(16的平方)+16}+32，按照這個思路繼續(xù)分解，F(xiàn)16,F8,F4,F2，最后左邊簡化成由I和D構(gòu)成的修正矩陣，右邊都是置換矩陣，共有l(wèi)og64個修正矩陣，第一次32，然后16、8、4、2、1，共六步，共六個修正矩陣，F32-F16: 2x(2x(16的平方)+16)+32次運算F16-F8 : 2x(2x(2x((8的平方)+8))+16)+32次運算F8-F4 : 2x(2x(2x(2x4的平方+4)+8))+16)+32次運算F4-F2 : 2x(2x(2x(2x(2X2的平方+2)+4)+8))+16)+32次運算F2-F2 : 2x(2x(2x(2x(2x(2x1的平方+1)+2)+4)+8))+16)+32次運算簡化為6x32，即64/2xlog64，最終1/2nlogn。舉例，n=1024，即2的10次方，此時計算次數(shù)n的平方大于一百萬次，但是通過FFT運算開銷降到1/2x1024xlog2^100約5x1024，即原來的1/200。通過傅里葉矩陣的分解，極大提高了運算效率。
|
