Certifying the Restricted Isometry Property is Hard

被引：162

作者：

Bandeira, Afonso S. ^{[1
]}

Dobriban, Edgar ^{[2
]}

Mixon, Dustin G. ^{[3
]}

Sawin, William F. ^{[4
]}

机构：

[1] Princeton Univ, Program Appl & Computat Math, Princeton, NJ 08544 USA

[2] Stanford Univ, Dept Stat, Stanford, CA 94305 USA

[3] AF Inst Technol, Dept Math & Stat, Wright Patterson AFB, OH 45433 USA

[4] Princeton Univ, Dept Math, Princeton, NJ 08544 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2013年 / 59卷 / 06期

基金：

美国国家科学基金会;

关键词：

Compressed sensing; computational complexity; restricted isometry property;

D O I：

10.1109/TIT.2013.2248414

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：3448 / 3450

页数：3

共 17 条

[1] Full Spark Frames [J].

Alexeev, Boris ;

Cahill, Jameson ;

Mixon, Dustin G. .

JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS, 2012, 18 (06) :1167-1194

[2]

Bandeira A. S., ROAD DETERMINISTIC M

[3] Iterative hard thresholding for compressed sensing [J].

Blumensath, Thomas ;

Davies, Mike E. .

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 2009, 27 (03) :265-274

[4] Decoding by linear programming [J].

Candes, EJ ;

Tao, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (12) :4203-4215

[5] The restricted isometry property and its implications for compressed sensing [J].

Candes, Emmanuel J. .

COMPTES RENDUS MATHEMATIQUE, 2008, 346 (9-10) :589-592

[6] Vandermonde matrices, NP-completeness, and transversal subspaces [J].

Chistov, A ;

Fournier, H ;

Gurvits, L ;

Koiran, P .

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2003, 3 (04) :421-427

[7]

COOK SA, P VERSUS NP PROBLEM

[8] Deterministic constructions of compressed sensing matrices [J].

DeVore, Ronald A. .

JOURNAL OF COMPLEXITY, 2007, 23 (4-6) :918-925

[9] New lower bounds for convex hull problems in odd dimensions [J].

Erickson, J .

SIAM JOURNAL ON COMPUTING, 1999, 28 (04) :1198-1214

[10] ON THE COMPLEXITY OF APPROXIMATING EXTREMAL DETERMINANTS IN MATRICES [J].

KHACHIYAN, L .

JOURNAL OF COMPLEXITY, 1995, 11 (01) :138-153

← 1 2 →