Title | ||
---|---|---|
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error |
Abstract | ||
---|---|---|
The Johnson-Lindenstrauss transform is a dimensionality reduction technique with a wide range of applications to theoretical computer science. It is specified by a distribution over projection matrices from Rn → Rk where k n and states that k = O(ϵ−2 log 1/δ) dimensions suffice to approximate the norm of any fixed vector in Rn to within a factor of 1 ± ϵ with probability at least 1 − δ. In this article, we show that this bound on k is optimal up to a constant factor, improving upon a previous Ω((ϵ−2 log 1/δ)/log(1/ϵ)) dimension bound of Alon. Our techniques are based on lower bounding the information cost of a novel one-way communication game and yield the first space lower bounds in a data stream model that depend on the error probability δ. For many streaming problems, the most naïve way of achieving error probability δ is to first achieve constant probability, then take the median of O(log 1/δ) independent repetitions. Our techniques show that for a wide range of problems, this is in fact optimal! As an example, we show that estimating the ℓp-distance for any p ∈ [0,2] requires Ω(ϵ−2 log n log 1/δ) space, even for vectors in {0,1}n. This is optimal in all parameters and closes a long line of work on this problem. We also show the number of distinct elements requires Ω(ϵ−2 log 1/δ + log n) space, which is optimal if ϵ−2 = Ω(log n). We also improve previous lower bounds for entropy in the strict turnstile and general turnstile models by a multiplicative factor of Ω(log 1/δ). Finally, we give an application to one-way communication complexity under product distributions, showing that, unlike the case of constant δ, the VC-dimension does not characterize the complexity when δ = o(1). |
Year | DOI | Venue |
---|---|---|
2013 | 10.1145/2483699.2483706 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
constant factor,streaming problems,constant probability,optimal bounds,error probability,fact optimal,log n,previous lower bound,n log,k n,subconstant error,multiplicative factor,wide range,johnson-lindenstrauss transforms,entropy,data streams,communication complexity | Binary logarithm,Discrete mathematics,Combinatorics,Data stream mining,Dimensionality reduction,Multiplicative function,Matrix (mathematics),Turnstile,Communication complexity,Mathematics,Bounding overwatch | Journal |
Volume | Issue | ISSN |
9 | 3 | 1549-6325 |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 43 | 1.50 |
References | Authors | |
52 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
T. S. Jayram | 1 | 1373 | 75.87 |
David P. Woodruff | 2 | 2156 | 142.38 |