Imperial College London
Portrait Picture

Dr Mahdi Cheraghchi

Faculty of Engineering, Department of Computing

Honorary Senior Lecturer
 
 
 
//

Contact

 

m.cheraghchi Website CV

 
 
//

Location

 

353ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Cheraghchi:2017:10.1145/3029050,
author = {Cheraghchi, M and Indyk, P},
doi = {10.1145/3029050},
journal = {ACM TRANSACTIONS ON ALGORITHMS},
title = {Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform},
url = {http://dx.doi.org/10.1145/3029050},
volume = {13},
year = {2017}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - For every fixed constant α > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform (i.e., Discrete Fourier Transform over the Boolean cube) of an N-dimensional vector x ∈ RN in time k1 + α(log N)O(1). Specifically, the algorithm is given query access to x and computes a k-sparse &xtilde; ∈ RN satisfying  &xtilde;− &xhat;1 ≤ c  &xhat;− Hk(&xhat)1 for an absolute constant c > 0, where &xhat; is the transform of x and Hk(&xhat) is its best k-sparse approximation. Our algorithm is fully deterministic and only uses nonadaptive queries to x (i.e., all queries are determined and performed in parallel when the algorithm starts).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 et al. [2009]). Moreover, we design a deterministic and nonadaptive 1/1 compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time k1 + α(log N)O(1) (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander-based construction due to Berinde, Gilbert, Indyk, Karloff, and Strauss [Berinde et al. 2008].Our methods use linear lossless condensers in a black box fashion; therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to k(log N)O(1) reconstruction time with a reduced exponent in the poly-logarithmic factor, and eliminating the extra parameter α).By allowing the algorithm to use randomness while still using nonadaptive queries, the runtime of the algorithm can be improved to õ(k log3 N).
AU  - Cheraghchi,M
AU  - Indyk,P
DO  - 10.1145/3029050
PY  - 2017///
SN  - 1549-6325
TI  - Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
T2  - ACM TRANSACTIONS ON ALGORITHMS
UR  - http://dx.doi.org/10.1145/3029050
UR  - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000408666100005&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - http://hdl.handle.net/10044/1/52000
VL  - 13
ER  -
Download