Certifying the restricted isometry property is hard

Afonso S. Bandeira , Edgar Dobriban , Dustin G. Mixon , William F. Sawin

Authors on Pith no claims yet

classification 🧮 math.FA cs.CCcs.ITmath.IT

keywords isometrymatrixpropertyrestrictedcertifyingcompressedconcernedcondition

read the original abstract

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.

This paper has not been read by Pith yet.

Certifying the restricted isometry property is hard

discussion (0)