A ritkított Fourier-transzformáció

Eredeti címe:

The Sparse Fourier Transform

Könyv tartalma:

A Fourier-transzformáció az egyik legalapvetőbb eszköz a jelek frekvenciareprezentációjának kiszámítására. Központi szerepet játszik a jelfeldolgozásban, a kommunikációban, az audio- és videotömörítésben, az orvosi képalkotásban, a genomikában, a csillagászatban, valamint számos más területen. Széleskörű használata miatt a Fourier-transzformáció kiszámítására szolgáló gyors algoritmusok számos alkalmazás számára előnyösek lehetnek. A Fourier-transzformáció kiszámításának leggyorsabb algoritmusa a gyors Fourier-transzformáció (FFT), amely közel lineáris idő alatt fut, így számos alkalmazásban nélkülözhetetlen eszköz. Napjainkban azonban az FFT algoritmus futási ideje már nem elég gyors, különösen a nagy adatproblémák esetében, ahol az egyes adatkészletek néhány terabájtosak lehetnek. Ezért szükségessé váltak a gyorsabb algoritmusok, amelyek szublineáris időben futnak, azaz nem is mintavételezik az összes adatpontot.

Ez a könyv a fenti problémával foglalkozik a Sparse Fourier Transform algoritmusok kifejlesztésével és olyan gyakorlati rendszerek létrehozásával, amelyek ezeket az algoritmusokat használják hat különböző alkalmazás kulcsfontosságú problémáinak megoldására: vezeték nélküli hálózatok; mobil rendszerek; számítógépes grafika; orvosi képalkotás; biokémia; és digitális áramkörök.

Ez a könyv annak a dolgozatnak az átdolgozott változata, amely 2016-ban elnyerte az ACM Doctoral Dissertation Award díját.