Theory Seminar: Finding Significant Fourier Transform Coefficients

Adi Akavia (IAS/DIMACS)

Sunday, 11.01.2009, 12:00

Room 337-8 Taub Bld.

Computing the Fourier transform is a basic building block used in
numerous applications. For data intensive applications, even the O(N log
N) running time of the Fast Fourier Transform (FFT) algorithm may be too
slow, and sub-linear running time is necessary. Clearly, outputting the
entire Fourier transform in sub-linear time is infeasible, nevertheless,
in many applications it suffices to find only the \tau-significant
Fourier transform coefficients, that is, the Fourier coefficients whose
magnitude is at least \tau-fraction (say, 1%) of the energy (ie, the sum
of squared Fourier coefficients). We call algorithms achieving the
latter SFT algorithms.
In this work we present a deterministic algorithm that finds the
\tau-significant Fourier coefficients of functions f over any finite
abelian group G in time polynomial in log|G|, 1/\tau and L_1(f) (for
L_1(f) denoting the sum of absolute values of the Fourier coefficients
of f). Our algorithm is robust to random noise.

Our algorithm is the first deterministic and efficient (ie, polynomial in log|G|) SFT algorithm to handle functions over any finite abelian groups, as well as the first such algorithm to handle functions over Z_N that are neither compressible nor Fourier-sparse. Our analysis is the first to show robustness to noise in the context of deterministic SFT algorithms.

Using our SFT algorithm we obtain (1) deterministic (universal and explicit) algorithms for sparse Fourier approximation, compressed sensing and sketching; (2) an algorithm solving the Hidden Number Problem with advice, with cryptographic bit security implications; and (3) an efficient decoding algorithm in the random noise model for polynomial rate variants of Homomorphism codes and any other concentrated & recoverable codes.

Our algorithm is the first deterministic and efficient (ie, polynomial in log|G|) SFT algorithm to handle functions over any finite abelian groups, as well as the first such algorithm to handle functions over Z_N that are neither compressible nor Fourier-sparse. Our analysis is the first to show robustness to noise in the context of deterministic SFT algorithms.

Using our SFT algorithm we obtain (1) deterministic (universal and explicit) algorithms for sparse Fourier approximation, compressed sensing and sketching; (2) an algorithm solving the Hidden Number Problem with advice, with cryptographic bit security implications; and (3) an efficient decoding algorithm in the random noise model for polynomial rate variants of Homomorphism codes and any other concentrated & recoverable codes.