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

@inproceedings{Cheraghchi:2016:10.1137/1.9781611974331.ch23,
author = {Cheraghchi, M and Indyk, P},
doi = {10.1137/1.9781611974331.ch23},
pages = {298--317},
publisher = {ACM},
title = {Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.},
url = {http://dx.doi.org/10.1137/1.9781611974331.ch23},
year = {2016}
}
Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - For every fixed constant α > 0, we design an algorithm for computing the k-sparse Walsh-Hadamardtransform of an N-dimensional vector x ∈ RN in time k1+α(log N)O(1). Specifically, the algorithm isgiven query access to x and computes a k-sparse x˜ ∈ RN satisfying kx˜ − xˆk1 ≤ ckxˆ − Hk(ˆx)k1, for anabsolute constant c > 0, where xˆ is the transform of x and Hk(ˆx) is its best k-sparse approximation. Ouralgorithm is fully deterministic and only uses non-adaptive queries to x (i.e., all queries are determinedand performed in parallel when the algorithm starts).An important technical tool that we use is a construction of nearly optimal and linear lossless condenserswhich is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan, JACM2009). Moreover, we design a deterministic and non-adaptive `1/`1 compressed sensing scheme basedon general lossless condensers that is equipped with a fast reconstruction algorithm running in timek1+α(log N)O(1) (for the GUV-based condenser) and is of independent interest. Our scheme signifi-cantly simplifies and improves an earlier expander-based construction due to Berinde, Gilbert, Indyk,Karloff, Strauss (Allerton 2008).Our methods use linear lossless condensers in a black box fashion; therefore, any future improvementon explicit constructions of such condensers would immediately translate to improved parameters in ourframework (potentially leading to k(log N)O(1) reconstruction time with a reduced exponent in the polylogarithmicfactor, and eliminating the extra parameter α).By allowing the algorithm to use randomness, while still using non-adaptive queries, the runningtime of the algorithm can be improved to O˜(k log3 N).
AU  - Cheraghchi,M
AU  - Indyk,P
DO  - 10.1137/1.9781611974331.ch23
EP  - 317
PB  - ACM
PY  - 2016///
SP  - 298
TI  - Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
UR  - http://dx.doi.org/10.1137/1.9781611974331.ch23
UR  - http://hdl.handle.net/10044/1/31210
ER  -
Download