工業技術研究院

速度更快的傅立葉轉換 數學升級可望加快數位世界的運轉

一月間，麻省理工學院（MIT）的四位研究員迪娜‧卡塔畢（Dina Katabi）、海賽姆‧哈薩尼耶（Haitham Hassanieh）、彼得‧英迪克（Piotr Indyk）和艾立克‧普萊斯（Eric Price）找到執行傅立葉轉換更快的方法，並展示這種電腦科學最重要演算式之一的替代方法。傅立葉轉換是一種數學技術，用於處理資料串流，而資料串流是數位醫療影像、無線相容認證（Wi-Fi）路由器和第四代蜂巢式網路等運算的基礎。

傅立葉轉換可以上溯到十九世紀，它的原理是任何訊號（例如聲音錄製）可以用一組頻率和振幅不同的正弦波（sine wave）和餘弦波（cosine wave）之和來代表。操弄這些波的集合相當簡單──例如壓縮一段錄音或者抑制噪音。1960年代中期，有一種稱做快速傅立葉轉換（fast Fourier transform；FFT）的親電腦演算法發展出來。MP3檔案和未經壓縮的相同錄音比起來，容量小得多，為此驚歎不已的人，已經見識到FFT發揮的力量。

利用稱做稀疏傅立葉轉換（sparse Fourier transform；SFT）的新演算法，處理資料串流的速度可以比FFT快十到一百倍。速度可以加快，是因為我們最在意的資訊，例如不是隨機噪音的音樂，具備很大的資訊結構。這些有意義的訊號，再訊號能夠擁有的可能數值中，通常只占一小部分而已；用技術名詞來說，資訊是「稀疏」的。由於SFT演算式並沒有打算用在所有可能的資料串流上，所以能走其他情況下不能走的捷徑。理論上，只能處理稀疏訊號的演算式，遠比FFT受到更多的限制。但是「處處有稀疏資訊」的共同發明人、電機工程和電腦科學教授卡塔畢指出：「它存在於大自然之中，存在於視頻訊號之中，存在於音頻訊號之中。」

轉換速度較快，表示處理一定數量的資訊，所需的電腦電力較小──這對於智慧型手機等耗電很快的行動多媒體裝置來說，是一大福音。或者，工程師使用相同的電力，可以考慮執行原來的FFT不可行的運算需求。舉例來說，今天的網際網路骨幹和路由器實際上只能讀取或處理流過其間的位元之河中的涓涓細流。SFT允許研究工作者在位元以每秒數十億次的速度飛經時，遠比從前更為詳細地研究流量。

創新人物
麻省理工學院（MIT）麻州劍橋

技術
用新的演算式處理資料串流，可以做出更好的多媒體裝置。

其他著名的創新者
1.理查‧巴拉尼亞克（Richard Baraniuk），德州休士頓萊斯大學（Rice University）
2.安娜‧吉爾伯特（Anna Gilbert）和馬丁‧史特勞斯（Martin Strauss），密西根大學
3.裘爾‧特洛普（Joel A. Tropp），加州理工學院（Caltech）
4.馬克‧艾文（Mark Iwen），北卡羅來納州達勒姆杜克大學（Duke University）