A Fourier-transzformáció egyike a legalapvetőbb koncepcióknak az információtudományban. Segítségével egy szabálytalan jelet leírhatunk periodikus jelek összegeként. Mindenütt használják a jelfeldolgozásban, de többek közt kép- és hangfájlok tömörítésében, differenciálegyenletek megoldásában és a tőzsdei árfolyamok ingadozásának leírásában is gyakran alkalmazzák.

Elterjedt használatát a hatvanas években kidolgozott gyors Fourier-transzformáció nevű algoritmus (FFT) teszi lehetővé, amely automatikusan elvégzi a jelfelbontást. Megalkotása óta időről időre felmerül azonban a kérdés: van-e még gyorsabb módszer a művelet elvégzésére?

A héten Japánban megrendezett Symposium on Discrete Algorithms (SODA) alkalmából az MIT kutatói egy új algoritmust mutattak be, amely számos alkalmazásában gyorsabbnak bizonyult az FFT-nél. Egyes feladatoknál tízszeres gyorsaságot is elértek. Az új módszer különösen jól hasznosítható lesz a képi információk tömörítésében, lehetővé téve például az okostelefonokon keresztüli videófájl-küldést az akkuk lemerülése és a havi adatforgalom „elfogyasztása” nélkül.

Ahogy az FFT, az új algoritmus is digitális jeleken működik: mintákat vesz a jelből és a frekvenciák súlyozott összegeként állítja elő az új értékeket. Súlyozott abból a szempontból, hogy némely frekvenciák fontosabban, mint mások, amelyek közt akadnak minimális információveszteséggel elhagyhatók is. Ezért is hasznos a transzformáció a tömörítésnél. Ha elképzelünk egy 8x8-as pixelblokkot, azt felfoghatjuk egy 64 különböző szignálból álló jelsornak, ezt összeadva 64 különböző frekvenciával dolgozunk. De ahogy az MIT kutatói rámutattak: ezen frekvenciák közül 57 nyugodtan elhagyható a képminőség észrevehető romlása nélkül.

Azokat a jeleket, amelyek néhány frekvenciával leírhatók veszteségek nélkül, ritkás jeleknek nevezzük. Az új algoritmus gyorsan felméri a jelek leginkább súlyozandó frekvenciáit: így minél ritkásabb a jel, annál gyorsabban dolgozik. A módszer során kisebb sávszélességű szeletekre bontják a jelet, hogy az egyes szeletek egyetlen súlyozott frekvenciával leírhatók legyenek. Dina Katabi, Piotr Indyk, Eric Price és Haitham Hassanieh egy olyan algoritmust dolgoztak ki tehát, amely nagyon gyorsan kiválogatja, hogy mi is kell nekünk feltétlenül egy adott jelből.