The Average-Case Time Complexity of Certifying the Restricted Isometry Property

Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein +1

In compressed sensing, the restricted isometry property (RIP) on $M\times N$ sensing matrices (where $M<N$) guarantees efficient reconstruction of sparse vectors. A matrix has t…