FFT e SODA, ancora più veloce la trasformata di Fourier

In occasione di SODA 2012, il simposio sugli algoritmi discreti della ACM-SIAM un team di ricercatori del MIT ha presentato una versione ottimizzata di una precedente versione "sparsa" dell'algoritmo FFT, o Fast Fourier Transform. La procedura consente di modellare l'andamento di un segnale nel tempo attraverso le sue principali componenti frequenziali. Un'onda sinusoidale pura ha una unica componente, la sua frequenza fondamentale, ma anche i segnali più complicati e variabili possono essere "frantumati" in una serie di valori discreti, di coefficienti assegnati alle singole frequenze che lo compongono. In questo modo manipolare l'informazione originaria diventa molto più facile, ma ovviamente richiede del tempo di calcolo.

Introducendo delle approssimazioni rispetto all'FFT originale (sviluppato negli anni 60 da James Cooley e John Tukey), questo nuovo algoritmo permette di ridurre di parecchio i tempi di esecuzione di una trasformata di Fourier - la tecnica fondamentale per il trattamento numerico di un segnale analogico (analisi, compressione, filtraggio) - o viceversa consente di utilizzare risorse di calcolo meno impegnative. Per i matematici del MIT il guadagno può essere cospicuo, addirittura di un fattore dieci. E' ancora presto per capire quali potranno essere i risvolti pratici di questa scoperta, ma considerando che la trasformata veloce è uno dei capisaldi di tutti i programmi per la software defined radio potrebbe esserci una ricaduta positiva, per esempio con software di demodulazione e filtraggio ancora più efficienti o rapidi.

Per i più versati in matematica ecco un articolo da iProgrammer che spiega meglio le caratteristiche del nuovo algoritmo. Qui invece ci sono i link alla pagina Web del gruppo di ricercatori del MIT e ai loro articoli

Simple and Practical Algorithm for Sparse Fourier Transform (la prima versione dell'algoritmo)

Haitham Hassanieh, Piotr Indyk ,Dina Katabi, and Eric Price. PDF

Nearly Optimal Sparse Fourier Transform (la versione appena presentata al SODA)

Haitham Hassanieh, Piotr Indyk ,Dina Katabi, and Eric Price. PDF On ArXiv

sFFT: Sparse Fast Fourier Transform Group Page

(...)The basic idea of the FFT is to simply use the divide and conquer strategy. If the size of the data vector n is factorable, n=n1n2 say, then you can compute a Fourier transform on n1 elements and then on n2 elements and put the result together to give you the full result. If n is highly factorable, you can repeat the division down to just sets of two data points. This is the FFT and you can show that it takes time proportional to nlogn, which is a big improvement over n2 for large n. You can also construct similar algorithms even if n isn't highly composite and FFT algorithms exist even if n is prime.

Until recently the FFT was the best you could do in general, but it still isn't known if it is an optimal algorithm. It is obvious that a theoretical lower bound for complexity is n as you have to compute n Fourier coefficients. However, if the frequency spectrum if sparse, i.e. there are only k non-zero frequencies, then you could hope for an algorithm that has complexity proportional to k.

Now a research group at MIT has demonstrated an algorithm that takes klogn time. The algorithm takes a data vector with n elements and returns the k largest Fourier components - which is exactly what you want in the case of most compression and approximate signal manipulation algorithms.

If you are hoping for an elegant algorithm that exploits the symmetry of the situation, using a modified butterfly say, this is not the case. The ideas and implementation is based on using filters to divide the bandwidth up into bins so that each bin contains at most one of the significant frequencies. The filters (Gaussian and Dolph-Chebyshev) are constructed in a clever way so that they overlap in just the right way to make sure that you don't miss a significant component. After this, a divisive search is used to isolate the regions that contain the significant Fourier coefficients. The resulting transform is only an approximation to the true transform, but the accuracy can be quantified.

Many signals are sparse, and if they aren't the compression algorithms that manipulate them assume that they are. In other words, a k-sparse approximate algorithm is good enough for many practical applications.

What this means is that, using this sort of approach. you could implement faster MP3 or MP4 style compression or use a much less powerful processor.

The important point about this new algorithm is that, even if k approaches n, the algorithm can be shown to be about as good as a conventional FFT.

(...)