Sparsity and ${\ell }_p$-Restricted Isometry

Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff

A matrix $A$ is said to have the ${\ell }_p$-Restricted Isometry Property (${\ell }_p$-RIP) if for all vectors $x$ of up to some sparsity $k$, $\Vert Ax{\Vert }_p$ is roughly proportional to $\|…