Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
File(s)
Accepted version
Author(s)
Cheraghchi, M
Indyk, P
Type
Conference Paper
Abstract
For every fixed constant α > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard
transform of an N-dimensional vector x ∈ R
N in time k
1+α(log N)
O(1). Specifically, the algorithm is
given query access to x and computes a k-sparse x˜ ∈ R
N satisfying kx˜ − xˆk1 ≤ ckxˆ − Hk(ˆx)k1, 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
k
1+α(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 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 polylogarithmic
factor, and eliminating the extra parameter α).
By allowing the algorithm to use randomness, while still using non-adaptive queries, the running
time of the algorithm can be improved to O˜(k log3 N).
transform of an N-dimensional vector x ∈ R
N in time k
1+α(log N)
O(1). Specifically, the algorithm is
given query access to x and computes a k-sparse x˜ ∈ R
N satisfying kx˜ − xˆk1 ≤ ckxˆ − Hk(ˆx)k1, 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
k
1+α(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 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 polylogarithmic
factor, and eliminating the extra parameter α).
By allowing the algorithm to use randomness, while still using non-adaptive queries, the running
time of the algorithm can be improved to O˜(k log3 N).
Editor(s)
Krauthgamer, R
Date Issued
2016-01-10
Date Acceptance
2015-09-11
Citation
SODA '16 Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016, pp.298-317
ISBN
978-1-61197-433-1
Publisher
ACM
Start Page
298
End Page
317
Journal / Book Title
SODA '16 Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
Copyright Statement
© ACM, 2016. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SODA '16 Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms http://dx.doi.org/10.1137/1.9781611974331.ch23
Source
ACM-SIAM Symposium on Discrete Algorithms (SODA16)
Publication Status
Published
Start Date
2016-01-10
Finish Date
2016-01-12
Coverage Spatial
Arlington, Virginia USA