Rozproszona transformata Fouriera

Oryginalny tytuł:

The Sparse Fourier Transform

Zawartość książki:

Transformata Fouriera jest jednym z najbardziej podstawowych narzędzi do obliczania częstotliwościowej reprezentacji sygnałów. Odgrywa ona kluczową rolę w przetwarzaniu sygnałów, komunikacji, kompresji audio i wideo, obrazowaniu medycznym, genomice, astronomii i wielu innych dziedzinach. Ze względu na jego powszechne zastosowanie, szybkie algorytmy obliczania transformaty Fouriera mogą przynieść korzyści wielu aplikacjom. Najszybszym algorytmem do obliczania transformaty Fouriera jest szybka transformata Fouriera (FFT), która działa w czasie zbliżonym do liniowego, co czyni ją niezbędnym narzędziem w wielu zastosowaniach. Jednak obecnie czas działania algorytmu FFT nie jest już wystarczająco szybki, zwłaszcza w przypadku problemów związanych z dużymi zbiorami danych, gdzie każdy zbiór danych może mieć rozmiar kilku terabajtów. W związku z tym konieczne stało się opracowanie szybszych algorytmów, które działają w czasie podliniowym, tj. nie próbkują nawet wszystkich punktów danych.

Niniejsza książka odnosi się do powyższego problemu poprzez opracowanie algorytmów Sparse Fourier Transform i zbudowanie praktycznych systemów, które wykorzystują te algorytmy do rozwiązywania kluczowych problemów w sześciu różnych zastosowaniach: sieci bezprzewodowe; systemy mobilne; grafika komputerowa; obrazowanie medyczne; biochemia; i obwody cyfrowe.

Jest to poprawiona wersja rozprawy, która zdobyła nagrodę ACM Doctoral Dissertation Award w 2016 roku.