A Near-Optimal Lower Bound for ${\ell }_p$-Subspace Embeddings, $1\le p<2$

Abstract

For $d\ge 2$, $p\ge 1$ and $\epsilon >0$, let $N_p(d,\epsilon )$ be the smallest integer $N$ such that for every integer $n$ and every $A\in {\mathbb{R}}^{n\times d}$, there exists a matrix $\Phi \in {\mathbb{R}}^{N\times n}$ satisfying $(1-\epsilon )\Vert Ax{\Vert }_p\le \Vert \Phi Ax{\Vert }_p\le (1+\epsilon )\Vert Ax{\Vert }_p$ for all $x\in {\mathbb{R}}^d$. For every constant $p\ge 1$ with $p\notin 2\mathbb{Z}$, when $d{\gtrsim }_p\log (1/\epsilon )$, the bound \[ N_p(d,ε) \gtrsim_{p} \frac{d}{ε^2 \operatorname{polylog}(d/ε)} \] is established. This improves the previous lower bound $\Omega (1/({\epsilon }^2\mathrm{polylog}(1/\epsilon )))$ due to Li et al. (SICOMP 2021) and is optimal up to logarithmic factors for $1\le p<2$. The central technical idea originated from ChatGPT 5.6 Sol.