# Tight Bounds for the Subspace Sketch Problem with Applications

arXiv: https://arxiv.org/abs/1904.05543 · HTML: https://mlsanity.com/paper/1904.05543/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2019.

## Built on by (most cited first, 6 of 6)

- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Feature Space Sketching for Logistic Regression](https://mlsanity.com/paper/2303.14284/) (2023)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Coresets for Multiple ℓp Regression](https://mlsanity.com/paper/2406.02432/) (2024)
- [The Space Complexity of Approximating Logistic Loss](https://mlsanity.com/paper/2412.02639/) (2024)

## Abstract (arXiv)

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 where 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 non-zeros 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=Omega(log(1/ε)), then tildeOmega(ε-2d) bits are necessary. On the other hand, if p is a positive even integer, then there is an upper bound of O(dplog(nd)) bits independent of ε. Our results are optimal up to logarithmic factors, and show in particular that one cannot compress A to O(d) "directions" v1,dots,vO(d), such that for any x, |Ax|1 can be well-approximated from langle v1,xrangle,dots,langle vO(d),xrangle. Our lower bound rules out arbitrary functions of these inner products (and in fact arbitrary data structures built from A), and thus rules out the possibility of a singular value decomposition for ℓ1 in a very strong sense. Indeed, as ε→ 0, for p = 1 the space complexity becomes arbitrarily large, while for p = 2 it is at most O(d2 log(nd)). 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.