Title: Locally & Universally Finding Significant Fourier Coefficients
Speaker: Adi Akavia, IAS
Date: Wednesday, October 29, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
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 coefficients, that is, the Fourier coefficients whose magnitude is at least a \tau-fraction (say, 1%) of the total energy, i.e., the sum of squared Fourier coefficients.
In this paper we present a deterministic algorithm that finds the \tau-significant Fourier coefficients of functions f over any finite abelian group G, which is:
Our result gives the first deterministic local algorithm for finding significant Fourier coefficients that handle functions over Z_N, as well as the first such algorithm that handles functions over arbitrary finite abelian groups. Furthermore, our analysis is the first to show robustness to random noise in the context of universal algorithms.
We present applications of our algorithm to compressed sensing; to proving cryptographic bit security results; and to efficiently decoding polynomial rate variants of Homomorphism codes and other concentrated and recoverable codes. The universality of our algorithm is crucial to all the applications.