Adi Akavia

Finding Significant Fourier Transform Coefficients
Deterministically and Locally

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 {\em 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 {\em $\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
{\em SFT algorithms}.

In this work we present a {\em deterministic} algorithm that finds the
$\tau$-significant Fourier coefficients of functions $f$ over {\em any
finite abelian group $G$} in time polynomial in $\log\card 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\card G$) SFT algorithm to handle functions over
any finite abelian groups, as well as the first such algorithm to
handle functions over $\ZZ_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.