Approximately certifying the restricted isometry property is hard

Jonathan Weed

doi:10.1109/TIT.2017.2776131

Approximately certifying the restricted isometry property is hard

Jonathan Weed

Mathematics

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

Abstract

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 language	English (US)
Pages (from-to)	5488-5497
Number of pages	10
Journal	IEEE Transactions on Information Theory
Volume	64
Issue number	8
DOIs	https://doi.org/10.1109/TIT.2017.2776131
State	Published - Aug 2018

Keywords

Compressed sensing
computational complexity
restricted isometry property

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Access to Document

10.1109/TIT.2017.2776131

Cite this

@article{2c868aa30b4544c1853dae1c7c9d3f35,

title = "Approximately certifying the restricted isometry property is hard",

abstract = "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.",

keywords = "Compressed sensing, computational complexity, restricted isometry property",

author = "Jonathan Weed",

note = "Funding Information: Manuscript received April 3, 2017; revised September 13, 2017; accepted November 11, 2017. Date of publication November 21, 2017; date of current version July 12, 2018. This work was supported by NSF Graduate Research Fellowship under Grant DGE-1122374. The author is with the Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139 USA (e-mail: jweed@mit.edu). Communicated by G. Kutyniok, Associate Editor for Signal Processing. Digital Object Identifier 10.1109/TIT.2017.2776131 Publisher Copyright: {\textcopyright} 1963-2012 IEEE.",

year = "2018",

month = aug,

doi = "10.1109/TIT.2017.2776131",

language = "English (US)",

volume = "64",

pages = "5488--5497",

journal = "IRE Professional Group on Information Theory",

issn = "0018-9448",

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

number = "8",

}

TY - JOUR

T1 - Approximately certifying the restricted isometry property is hard

AU - Weed, Jonathan

N1 - Funding Information: Manuscript received April 3, 2017; revised September 13, 2017; accepted November 11, 2017. Date of publication November 21, 2017; date of current version July 12, 2018. This work was supported by NSF Graduate Research Fellowship under Grant DGE-1122374. The author is with the Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139 USA (e-mail: jweed@mit.edu). Communicated by G. Kutyniok, Associate Editor for Signal Processing. Digital Object Identifier 10.1109/TIT.2017.2776131 Publisher Copyright: © 1963-2012 IEEE.

PY - 2018/8

Y1 - 2018/8

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

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

KW - Compressed sensing

KW - computational complexity

KW - restricted isometry property

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

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

U2 - 10.1109/TIT.2017.2776131

DO - 10.1109/TIT.2017.2776131

M3 - Article

AN - SCOPUS:85035759316

SN - 0018-9448

VL - 64

SP - 5488

EP - 5497

JO - IRE Professional Group on Information Theory

JF - IRE Professional Group on Information Theory

IS - 8

ER -

Approximately certifying the restricted isometry property is hard

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this