Tight bounds for the subspace sketch problem with applications

• Main Authors: Li, Yi, Wang, Ruosong, Woodruff, David P.
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2022
• 主題: Science::Mathematics; Subspace Sketch; Lower Bound
• 在線閱讀: https://hdl.handle.net/10356/153688
• 機構: 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...