Tight Bounds for the Subspace Sketch Problem with Applications

Yi Li, Ruosong Wang, David P. Woodruff

In the subspace sketch problem one is given an $n\times 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…