Certifying the restricted isometry property is hard

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

doi:10.1109/TIT.2013.2248414

Certifying the restricted isometry property is hard

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

Mathematics

Research output: Contribution to journal › Article › peer-review

178 Scopus citations

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.

Original language	English (US)
Article number	6478822
Pages (from-to)	3448-3450
Number of pages	3
Journal	IEEE Transactions on Information Theory
Volume	59
Issue number	6
DOIs	https://doi.org/10.1109/TIT.2013.2248414
State	Published - 2013

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Compressed sensing
computational complexity
restricted isometry property

Access to Document

10.1109/TIT.2013.2248414

Cite this

@article{4a7b226588f44d6ca68a26858c8dd1ec,

title = "Certifying the restricted isometry property is hard",

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 = "Compressed sensing, computational complexity, restricted isometry property",

author = "Bandeira, {Afonso S.} and Edgar Dobriban and Mixon, {Dustin G.} and Sawin, {William F.}",

year = "2013",

doi = "10.1109/TIT.2013.2248414",

language = "English (US)",

volume = "59",

pages = "3448--3450",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "6",

}

TY - JOUR

T1 - Certifying the restricted isometry property is hard

AU - Bandeira, Afonso S.

AU - Dobriban, Edgar

AU - Mixon, Dustin G.

AU - Sawin, William F.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Compressed sensing

KW - computational complexity

KW - restricted isometry property

UR - http://www.scopus.com/inward/record.url?scp=84877892735&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877892735&partnerID=8YFLogxK

U2 - 10.1109/TIT.2013.2248414

DO - 10.1109/TIT.2013.2248414

M3 - Article

AN - SCOPUS:84877892735

SN - 0018-9448

VL - 59

SP - 3448

EP - 3450

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 6

M1 - 6478822

ER -

Certifying the restricted isometry property is hard

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this