• DocumentCode
    1755907
  • Title

    Certifying the Restricted Isometry Property is Hard

  • Author

    Bandeira, Afonso S. ; Dobriban, E. ; Mixon, Dustin G. ; Sawin, W.F.

  • Author_Institution
    Program in Appl. & Comput. Math., Princeton Univ., Princeton, NJ, USA
  • Volume
    59
  • Issue
    6
  • fYear
    2013
  • fDate
    41426
  • Firstpage
    3448
  • Lastpage
    3450
  • 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 ≠ NP.
  • Keywords
    computational complexity; matrix algebra; NP-hard; RIP; important matrix condition; restricted isometry property; Complexity theory; Compressed sensing; Educational institutions; Polynomials; Sparks; Testing; Compressed sensing; computational complexity; restricted isometry property;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/TIT.2013.2248414
  • Filename
    6478822
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1755907