Tight bounds for the subspace sketch problem with applications

• Main Authors: Li, Yi, Wang, Ruosong, Woodruff, David P.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2022
• Subjects: Science::Mathematics; Subspace Sketch; Lower Bound
• Online Access: https://hdl.handle.net/10356/153688
• Institution: Nanyang Technological University

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 ra...