EECS Spring 2015 Seminar

Mahdi Cheraghchi
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
White 411
May 28, 2015

The Hadamard transform, also known as the Fourier transform over the hypercube, is an orthogonal transformation extensively used in signal processing, learning theory, coding theory, and Boolean function analysis. Using the standard FFT algorithm, the N-dimensional Hadamard transform can be computed deterministically and exactly in time O(N log N). However, when one wishes to only approximate the most significant coefficients of the transformation, it is possible to obtain faster algorithms that work in sublinear time in the signal's dimension. We design an algorithm for computing a k-sparse approximation of the Hadamard transform of an N-dimensional vector x in time O(k^1.01 polylog N). Our algorithm is fully deterministic and only uses non-adaptive queries to x (i.e., all queries are determined and performed in parallel when the algorithm starts). Along the way, we also obtain a nearly optimal and explicit compressed sensing scheme equipped with a deterministic sublinear-time recovery algorithm.


Mahdi Cheraghchi is Adjunct Assistant Professor in the Department of Electrical Engineering and Computer Science at Case Western Reserve University and a Visiting Assistant Project Scientist at the Simons Institute for Theoretical Computer Science.  Previously, he served as a post-doctoral fellow at the Computer Science and Artificial Intelligence Lab of MIT, at the Computer Science Department of Carnegie Mellon University and the University of Texas at Austin. He obtained his Ph.D. and M.Sc. degrees in computer science from EPFL, Switzerland, in 2010 and 2005, respectively and B.Sc. in computer engineering from Sharif University of Technology, Iran, in 2004. He has been awarded two Swiss NSF research grants and EPFL’s Patrick Denantes thesis prize. His research interests include the interconnections between coding theory and theoretical computer science, sparse recovery and high-dimensional geometry, information-theoretic privacy and security, and approximation algorithms.