Loading...
Please wait, while we are loading the content...
Similar Documents
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
| Content Provider | CiteSeerX |
|---|---|
| Author | Cheraghchi, Mahdi Indyk, Piotr |
| Abstract | For every fixed constant α> 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform of an N-dimensional vector x ∈ RN in time k1+α(logN)O(1). Specifically, the algorithm is given query access to x and computes a k-sparse x ̃ ∈ RN satisfying ‖x̃ − x̂‖1 ≤ c‖x̂−Hk(x̂)‖1, for an absolute constant c> 0, where x ̂ is the transform of x and Hk(x̂) is its best k-sparse approximation. 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). 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). Moreover, we design a deterministic and non-adaptive `1/`1 compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time k1+α(logN)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, Strauss (Allerton 2008). Our methods use linear lossless condensers in a black box fashion; therefore, any future |
| File Format | |
| Access Restriction | Open |
| Content Type | Text |
