Back to Search
Start Over
Certifying the Restricted Isometry Property is Hard.
- Source :
-
IEEE Transactions on Information Theory . Jun2013, Vol. 59 Issue 6, p3448-3450. 3p. - Publication Year :
- 2013
-
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 \ssr NP-hard. As a consequence of our result, it is impossible to efficiently test for RIP provided \ssr P\ne\ssr NP. [ABSTRACT FROM PUBLISHER]
- Subjects :
- *MATRICES (Mathematics)
*PAPER arts
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 59
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 87617995
- Full Text :
- https://doi.org/10.1109/TIT.2013.2248414