Yi Li

A Near-Optimal Lower Bound for $\ell_p$-Subspace Embeddings, $1\leq p<2$

For $d \geq 2$, $p \geq 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)\lVert Ax\rVert_p\leq \lVert\Phi A x\rVert_p\leq (1+\epsilon)\lVert Ax\rVer...