Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 59, Issue 6, Pages 3448-3450Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2013.2248414
Keywords
Compressed sensing; computational complexity; restricted isometry property
Funding
- National Science Foundation [DMS-0914892]
- A. B. Krongard Fellowship
Ask authors/readers for more resources
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 not equal NP.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
