Certifying the restricted isometry property is hard
  This paper is concerned with an important matrix condition in compressed sensing known as the restricted isometry property (RIP). We demonstrate that testing whether a matrix satisfies RIP is NP-hard. As a consequence of our result, it is impossible to efficiently test for RIP provided P \neq NP. 
Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, William F. Sawin
math.FA cs.CC cs.IT math.IT