Computational Complexity of Certifying Restricted Isometry Property

Abhiram Natarajan, Yi Wu

Given a matrix $A$ with $n$ rows, a number $k<n$, and $0<\delta <1$, $A$ is $(k,\delta )$-RIP (Restricted Isometry Property) if, for any vector $x\in {\mathbb{R}}^n$, with at most $k$ non-zero…