D. L. Donoho, Compressed sensing, IEEE Transactions on Information Theory, vol.52, issue.4, pp.1289-1306, 2006.
DOI : 10.1109/TIT.2006.871582
URL : https://hal.archives-ouvertes.fr/inria-00369486

M. Elad, Sparse and redundant representations: From theory to applications in signal and image processing, 2010.
DOI : 10.1007/978-1-4419-7011-4

M. Fornasier and H. Rauhut, Compressive sensing, " in Handbook of mathematical methods in imaging, pp.187-228, 2011.

M. R. Garey and D. S. Johnson, Computers and intractability . A guide to the theory of NP-completeness

B. K. Natarajan, Sparse Approximate Solutions to Linear Systems, SIAM Journal on Computing, vol.24, issue.2, pp.227-234, 1995.
DOI : 10.1137/S0097539792240406

G. Davis, S. Mallat, and M. Avellaneda, Adaptive greedy approximations, Constructive Approximation, vol.21, issue.1, pp.57-98, 1997.
DOI : 10.1007/BF02678430
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.7530

S. Nam, M. E. Davies, M. Elad, and R. Gribonval, The cosparse analysis model and algorithms, Applied and Computational Harmonic Analysis, vol.34, issue.1, pp.30-56, 2013.
DOI : 10.1016/j.acha.2012.03.006
URL : https://hal.archives-ouvertes.fr/inria-00602205

T. Blumensath and M. E. Davies, Iterative hard thresholding for compressed sensing, Applied and Computational Harmonic Analysis, vol.27, issue.3, pp.265-274, 2009.
DOI : 10.1016/j.acha.2009.04.002

T. Blumensath and M. E. Davies, Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance, IEEE Journal of Selected Topics in Signal Processing, vol.4, issue.2, pp.298-309, 2010.
DOI : 10.1109/JSTSP.2010.2042411

R. Baraniuk, M. Davenport, R. Devore, and M. Wakin, A Simple Proof of the Restricted Isometry Property for Random Matrices, Constructive Approximation, vol.159, issue.2, pp.253-263, 2008.
DOI : 10.1007/s00365-007-9003-x

A. M. Tillmann and M. E. Pfetsch, The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing, IEEE Transactions on Information Theory, vol.60, issue.2, pp.1248-1259, 2014.
DOI : 10.1109/TIT.2013.2290112

R. Giryes, S. Nam, R. Gribonval, and M. E. Davies, Iterative Cosparse Projection Algorithms for the Recovery of Cosparse Vectors, Proc. EUSIPCO 2011, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00611592

R. Giryes, S. Nam, M. Elad, R. Gribonval, and M. E. Davies, Greedy-like algorithms for the cosparse analysis model, Linear Algebra and its Applications, vol.441, pp.22-60, 2014.
DOI : 10.1016/j.laa.2013.03.004
URL : https://hal.archives-ouvertes.fr/hal-00716593

T. Blumensath, Sampling and Reconstructing Signals From a Union of Linear Subspaces, IEEE Transactions on Information Theory, vol.57, issue.7, pp.4660-4671, 2011.
DOI : 10.1109/TIT.2011.2146550

B. Korte and J. Vygen, Combinatorial optimization. Theory and algorithms, 4th ed., ser, Algorithms and Combinatorics, vol.21, 2008.

E. Amaldi and V. Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoretical Computer Science, vol.147, issue.1-2, pp.181-210, 1995.
DOI : 10.1016/0304-3975(94)00254-G

S. Arora, L. Babai, J. Stern, and Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pp.724-733, 1993.
DOI : 10.1109/SFCS.1993.366815

E. Amaldi and V. Kann, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoretical Computer Science, vol.209, issue.1-2, pp.237-260, 1998.
DOI : 10.1016/S0304-3975(97)00115-1