Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

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.