Approximately certifying the restricted isometry property is hard

Jonathan Weed

Research output: Contribution to journalArticlepeer-review


A matrix is said to possess the restricted isometry property (RIP), if it acts as an approximate isometry when restricted to sparse vectors. Previous work has shown it to be NP-hard to determine whether a matrix possess this property, but only in a narrow range of parameters. In this paper, we show that it is NP-hard to make this determination for any accuracy parameter, even when we restrict ourselves to instances which are either RIP or far from being RIP. This result implies that it is NP-hard to approximate the range of parameters for which a matrix possesses the RIP with accuracy better than some constant. Ours is the first work to prove such a claim without any additional assumptions.

Original languageEnglish (US)
Pages (from-to)5488-5497
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number8
StatePublished - Aug 2018


  • Compressed sensing
  • computational complexity
  • restricted isometry property

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Approximately certifying the restricted isometry property is hard'. Together they form a unique fingerprint.

Cite this