## An even faster Fourier transform

January 23, 2012 by dwellangle

A group of MIT researchers have found a way to speed-up the fast Fourier transform for certain types of input data. The technique is described in an unpublished paper, which can be downloaded at this link.

From their abstract:

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show:

• An O(k log n)-time algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and

• An O(k log n log(n/k))-time algorithm for general input signals.

Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k = o(n). Further, they are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = nΩ(1).

We complement our algorithmic results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least Ω(k log(n/k)/ log log n) signal samples, even if it is allowed to perform adaptive sampling.

### Like this:

Like Loading...

*Related*

## An even faster Fourier transform

January 23, 2012 by dwellangle

A group of MIT researchers have found a way to speed-up the fast Fourier transform for certain types of input data. The technique is described in an unpublished paper, which can be downloaded at this link.

From their abstract:

## Share this:

## Like this:

RelatedPosted in Commentary | Tagged FFT | Leave a Comment

Comments RSS