DIMACS Theoretical Computer Science Seminar

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

Abstract:

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:

1. Local: The running time and number of function entries read by the algorithm is 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).
2. Universal: The algorithm reads the same set of function entries for all functions f, as long as they are over the same domain and have a common upper bound on L_1(f).
3. Robust to noise: The algorithm finds the significant Fourier coefficients of f, even if the function entries it receives are corrupted by random noise. Furthermore, we present extensions of this algorithm to handle adversarial noise in running time sub-linear in the domain size.

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.