|
|
今年1月，四位來自麻省理工學院的研究人員提出了一種新算法，以替代計算機科學領域最重要的算法之一。這四位研究者——蒂娜·卡塔比（Dina Katabi）、海塞姆·哈桑（Haitham Hassanieh）、比歐特·因迪克（Piotr Indyk）和埃里克·普里斯（Eric Price）——設計出了一種能更快執行傅里葉變換的算法。傅里葉變換是一種用于處理數據流的數學算法，是數字醫學成像、Wi-Fi路由器和4G無線通信網絡等眾多技術的運算基礎。
' l+ ?9 D& o: r6 P' K傅里葉變換的提出可追溯至19世紀，它的基本原理是，所有信號，例如錄音，都可以表現為一系列不同頻率和波幅的正弦和余弦波組合。進行變換之后，對這組波的處理會相對容易些——比方說，可以壓縮一段錄音或消除噪音。20世紀60年代中期，研究人員創造出了一種利用計算機實現的算法，稱之為快速傅里葉變換（FFT）。相比未壓縮的錄音版本，MP3格式文件的體積之小簡直令人驚嘆，這讓我們真正見識到了快速傅里葉變換的威力。
3 p3 A, }; f |& P* A8 x
1 P, C. b* I- i) ~而利用被稱為稀疏傅里葉變換（SFT）的新算法，數據流的處理速度會比快速傅里葉變換還要快上10倍至100倍。之所以能夠如此大幅地提速，是因為我們關注的信息大多擁有大量的結構：例如音樂與不規則噪聲就完全不是一回事。這些有意義的信號通常只能取一小部分可能值；用技術術語來表達，即這些信息是“稀疏”的。由于稀疏傅里葉變換算法不需要對所有可能的數據流都進行處理，因此它可以使用其他算法無法做到的某些快捷處理方式。從理論上看，如果一種算法只能用來處理稀疏信號，它受到的限制會比快速傅里葉變換多得多。但正如該算法的共同發明者、電子工程和計算機科學教授卡塔比所指出的那樣，“稀疏性無處不在”，“它存在于大自然中，存在于視頻信號中，存在于音頻信號中。”
* B8 ~" S' g! g
3 D7 i5 [$ `7 k. C" @) h! Q$ x4 ?9 a& R
更快速的變換意味著，在處理既定量的信息時需要更少的計算能力——這對于智能手機這類能耗敏感型移動多媒體設備來說，不啻于天賜福音。或者，利用同樣的運算能力，工程師們可以考慮一些對于傳統快速傅里葉變換的計算需求而言有些不現實的工作。舉例來說，當下因特網的骨干網和路由都只能讀取或處理穿梭于其中的數據洪流的極小一部分，而憑借稀疏傅里葉變換，研究人員就可以更為詳細地研究這種以每秒數十億次速度發射的信息流了
+ S; G" g0 ~% x) w6 n2 q6 l1 `' }5 ^
# e) I' ?8 T* C2 U6 S+ } |
|
發表于 2012-7-4 20:20:42
QQ好友和群
QQ空間
