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

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

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

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

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

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

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

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

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

他說(shuō)：“我很好奇。”“那是因?yàn)樗麄儫o(wú)法解釋它，還是因?yàn)樗淮嬖?事實(shí)證明它不存在。”

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

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

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

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

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