Answers are grounded in this paper and cite their sources.
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 Qₚ, so that for any given x ∈ Rᵈ, with probability at least 2/3, one has Qₚ(x) = (1 ± ε) \|Ax\|ₚ, where p ≥ 0 and the randomness is over the construction of Qₚ. The central question is, how many bits are necessary to store Qₚ? 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 Lₚ 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 Ω(ε⁻² d) bits are necessary. On the other hand, if p is a positive even integer, then there is an upper bound of O(dᵖ log(nd)) bits independent of ε. 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.
No takes yet. Share an insight, caveat, or question.
Li et al. (2021) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: