La trasformata di Fourier sparsa

Titolo originale:

The Sparse Fourier Transform

Contenuto del libro:

La trasformata di Fourier è uno degli strumenti fondamentali per calcolare la rappresentazione in frequenza dei segnali. Svolge un ruolo centrale nell'elaborazione dei segnali, nelle comunicazioni, nella compressione audio e video, nell'imaging medico, nella genomica, nell'astronomia e in molti altri settori. A causa del suo uso diffuso, gli algoritmi veloci per il calcolo della trasformata di Fourier possono essere utili per un gran numero di applicazioni. L'algoritmo più veloce per il calcolo della trasformata di Fourier è la trasformata di Fourier veloce (FFT), che viene eseguita in tempi quasi lineari, rendendola uno strumento indispensabile per molte applicazioni. Tuttavia, oggi il tempo di esecuzione dell'algoritmo FFT non è più sufficientemente veloce, soprattutto per i problemi di big data, dove ogni set di dati può essere di alcuni terabyte. Di conseguenza, sono diventati necessari algoritmi più veloci che funzionano in tempi sublineari, cioè che non campionano nemmeno tutti i punti di dati.

Questo libro affronta il problema di cui sopra sviluppando gli algoritmi della Trasformata di Fourier Sparse e costruendo sistemi pratici che utilizzano questi algoritmi per risolvere problemi chiave in sei diverse applicazioni: reti wireless, sistemi mobili, computer grafica, imaging medico, biochimica e circuiti digitali.

Si tratta di una versione rivista della tesi che ha vinto il premio ACM Doctoral Dissertation Award 2016.