所謂的快速傅立葉變換現(xiàn)在正在您的手機(jī)上運行。眾所周知，F(xiàn)FT是一種信號處理算法，其使用量超出了您的認(rèn)識。根據(jù)一篇研究論文的標(biāo)題，它是“整個家庭都可以使用的算法”。

亞歷山大·斯托伊切夫(Alexander Stoytchev)是愛荷華州立大學(xué)電氣與計算機(jī)工程系副教授，同時也是該大學(xué)虛擬現(xiàn)實應(yīng)用中心，其人機(jī)交互研究生計劃和計算機(jī)科學(xué)系的下屬。他說FFT算法及其逆運算(已知(例如IFFT)是信號處理的核心。

因此，“這些算法使數(shù)字革命成為可能，”他說。

它們是流音樂，打電話，瀏覽互聯(lián)網(wǎng)或自拍照的一部分。

FFT算法于1965年發(fā)布。四年后，研究人員開發(fā)了一種更加通用的通用版本，稱為線性調(diào)頻z變換(CZT)。但是，逆FFT算法的類似概括在50年來一直未解決。

直到斯托伊切夫(Stoytchev)和愛荷華州立大學(xué)的博士生弗拉基米爾·蘇霍伊(Vladimir Sukhoy)共同攻讀電氣和計算機(jī)工程專業(yè)以及人機(jī)交互專業(yè)-共同提出了長期以來一直在尋求的算法，稱為反向線性調(diào)頻z變換(ICZT)。

像所有算法一樣，這是解決問題的分步過程。在這種情況下，它將CZT算法的輸出映射回其輸入。Stoytchev解釋說，這兩種算法有點像一系列的兩個棱鏡-第一個算法將白光的波長分離為彩色光譜，第二個算法通過將光譜重新組合為白光來逆轉(zhuǎn)該過程。

Stoytchev和Sukhoy在最近由自然研究雜志Scientific Reports在線發(fā)表的一篇論文中描述了他們的新算法。他們的論文表明，該算法與計算復(fù)雜度或同類算法的速度相匹配，可以與指數(shù)衰減或增長的頻率分量一起使用(與IFFT不同)，并且已經(jīng)過數(shù)值精度測試。

斯托伊切夫(Stoytchev)說，他偶然發(fā)現(xiàn)了一種試圖制定缺失算法的想法，同時尋找類比來幫助研究生在“計算感知”課程中理解快速傅立葉變換。他閱讀了許多信號處理文獻(xiàn)，卻找不到與相關(guān)線性調(diào)頻z變換相反的信息。

他說：“我很好奇。”“那是因為他們無法解釋它，還是因為它不存在?事實證明它不存在。”

因此，他決定嘗試找到一種快速的逆算法。

Sukhoy說，逆算法比原始的正向算法更難，因此“我們需要更高的精度和更強大的計算機(jī)來進(jìn)行攻擊”。他還說，關(guān)鍵在于在結(jié)構(gòu)化矩陣的數(shù)學(xué)框架內(nèi)看到該算法。

即使到那時，也有很多計算機(jī)測試運行，“以證明一切正常-我們必須說服自己可以做到”。

愛荷華州立大學(xué)學(xué)生創(chuàng)新中心主任，該大學(xué)虛擬現(xiàn)實應(yīng)用中心前任主任詹姆斯·奧利弗說，勇敢地繼續(xù)解決這個問題。斯托伊切夫(Stoytchev)和蘇霍伊(Sukhoy)在奧利弗(Oliver)的論文中承認(rèn)“創(chuàng)造了我們可以在過去三年中從事這項工作的研究環(huán)境”。

奧利弗說，斯托伊切夫(Stoytchev)獲得了50年來一直沒有解決的數(shù)學(xué)和計算挑戰(zhàn)的支持：“亞歷克斯(Alex)一直以他對承擔(dān)重大研究挑戰(zhàn)的熱情和承諾給我留下深刻的印象。致力于多年的工作以解決一個基本問題。亞歷克斯是一位天才無畏的研究員。”