Please use this identifier to cite or link to this item:
Title: Tight bounds for the subspace sketch problem with applications
Authors: Li, Yi
Wang, Ruosong
Woodruff, David P.
Keywords: Science::Mathematics
Issue Date: 2021
Source: Li, Y., Wang, R. & Woodruff, D. P. (2021). Tight bounds for the subspace sketch problem with applications. SIAM Journal On Computing, 50(4), 1287-1335.
Project: MOE2018-T2-1-013
Journal: SIAM Journal on Computing
Abstract: In the subspace sketch problem one is given an n × d matrix A with O(log(nd)) bit entries, and would like to compress it in an arbitrary way to build a small space data structure Qp, so that for any given x ∊ ℝd, with probability at least 2/3, one has Qp(x) = (1 ± ∊ )|| Ax||p, where p ≥ 0 and the randomness is over the construction of Qp. The central question is, how many bits are necessary to store Qp? This problem has applications to the communication of approximating the number of nonzeros in a matrix product, the size of coresets in projective clustering, the memory of streaming algorithms for regression in the row-update model, and embedding subspaces of Lp in functional analysis. A major open question is the dependence on the approximation factor ∊. We show if p ≥ 0 is not a positive even integer and d = Ω (log(1/∊ )), then Ω (∊-2d) bits are necessary. On the other hand, if p is a positive even integer, then there is an upper bound of O(dp log(nd)) bits independent of \varepsilon. Our results are optimal up to logarithmic factors. As corollaries of our main lower bound, we obtain new lower bounds for a wide range of applications, including the above, which in many cases are optimal.
ISSN: 0097-5397
DOI: 10.1137/20M1311831
Rights: © 2021 Society for Industrial and Applied Mathematics. All rights reserved. This paper was published in SIAM Journal on Computing and is made available with permission of Society for Industrial and Applied Mathematics.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
20m1311831.pdf700.8 kBAdobe PDFView/Open

Page view(s)

Updated on Jan 21, 2022


Updated on Jan 21, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.