Abstract
For every fixed constant α > 0, we design a *deterministic* algorithm for computing the k-sparse Walsh-Hadamard
transform of an N-dimensional vector x in time k^(1+α) polylog n. Specifically, the algorithm is given query access to x and computes an approximate minimizer of the L1 approximation error ||y^ − x^||_1 over all k-sparse y^, where x^ denotes the spectrum of x. This is the first sub-linear time deterministic algorithm for this problem with sub-quadratic dependence on k.
An important technical tool that we use is a construction of nearly optimal and linear lossless
condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan,
JACM 2009).
Joint work with Mahdi Cheraghchi. Appeared in SODA'16.