Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

Efficient computation of the discrete Fourier transform is a classical problem in computer science, which can be accomplished by the celebrated FFT algorithm in time O(n log n), where n is the dimension of the signal. Recent years has witnessed a great interest in estimation of the Fourier transform when the signal is known to be (approximately) sparse in the frequency domain, in which case exponentially faster algorithms are desired. In practice, naturally acquired data (such as digital images and audio) tend to exhibit a strong degree of sparsity, and this phenomenon is the basis for major lossy compression algorithms. This talk will focus on the Walsh-Hadamard transform, which is the Fourier transform over the Boolean cube. Curiously, synthetic data (for example truth tables of Boolean functions implemented by certain "weak" computational models) may exhibit sparsity in the Hadamard domain as well, and this is the basis for several fundamental results in computational learning theory and Boolean analysis. I will sketch a fully deterministic and non-adaptive algorithm for approximation of the top k Hadamard coefficients of an n-dimensional vector in essentially optimal time; more precisely in time O(k^(1+eps) polylog n) for any constant eps > 0. As a corollary, we also obtain a nearly optimal, and explicit, measurement design for compressed sensing with respect to the L1 norm that is equipped with a sublinear time reconstruction algorithm.

Based on joint work with Piotr Indyk.