Certifying the restricted isometry property is hard

S.T. McCormick, A Combinatorial Approach to Some Sparse Matrix Problems. Ph.D. Thesis, Stanford University (1983)

1983

Earlier work this paper cites.

L. Khachiyan, On the complexity of approximating extremal determinants in matrices, J. Complexity 11 (1995) 128–153

1995

Earlier work this paper cites.

E.J. Candès, T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005) 4203–4215

2005

Earlier work this paper cites.

R. DeVore, Deterministic constructions of compressed sensing matrices, J. Complexity 23 (2007) 918–925

2007

Earlier work this paper cites.

T. Tao, Open question: Deterministic UUP matrices, Available online: http://terrytao.wordpress.com/2007/07/02/open-question-deterministic-uup-matrices

2007

Cited alongside, same era.

E.J. Candès, The restricted isometry property and its implications for compressed sensing, C. R. Acad. Sci. Paris, Ser. I 346 (2008) 589–592

2008

Cited alongside, same era.

D. Needell, J.A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal. 26 (2009) 301–321

2009

Cited alongside, same era.

A.S. Bandeira, M. Fickus, D.G. Mixon, P. Wong, The road to deterministic matrices with the restricted isometry property, Available online: arXiv:1202.1234

Original

Cited in the paper.

P. Koiran, A. Zouzias, On the certification of the restricted isometry property, Available online: arXiv:1103.4984

Original

Cited in the paper.

S. Cook, The P versus NP problem, Available online: http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf

Cited in the paper.

B. Alexeev, J. Cahill, D.G. Mixon, Full spark frames, Available online: arXiv:1110.3548

Original

Cited in the paper.

T. Blumensath, M.E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal. 27 (2009) 265–274

2009

Later among the works it cites.

D. Marx, A parameterized view on matroid optimization problems, Theor. Comput. Sci. 410 (2009) 4471–4479

2009

Later among the works it cites.

A.M. Tillmann, M.E. Pfetsch, The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing, Available online: arXiv:1205.2081

Original

2081

Closest in time.