P. Armand, J. Ch, and S. Gilbert, A Feasible BFGS Interior Point Algorithm for Solving Convex Minimization Problems, SIAM Journal on Optimization, vol.11, issue.1, pp.199-222, 2000.
DOI : 10.1137/S1052623498344720

URL : https://hal.archives-ouvertes.fr/inria-00073185

M. L. Balinski and A. W. Tucker, Duality Theory of Linear Programs: A Constructive Approach with Applications, SIAM Review, vol.11, issue.3, pp.347-377, 1969.
DOI : 10.1137/1011060

D. P. Bertsekas, Nonlinear Programming (second edition), Athena Scientific, vol.7, issue.15, p.24, 1999.

J. D. Blanchard, C. Cartis, and J. Tanner, Compressed Sensing: How Sharp Is the Restricted Isometry Property?, SIAM Review, vol.53, issue.1, pp.105-125, 2011.
DOI : 10.1137/090748160

J. F. Bonnans, J. Ch, C. Gilbert, C. Lemaréchal, and . Sagastizábal, Numerical Optimization ? Theoretical and Practical Aspects (second edition). Universitext, p.24, 2006.

J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization ? Theory and Examples, CMS Books in Mathematics, vol.3, issue.4, 2000.

J. V. Burke and M. C. Ferris, Weak Sharp Minima in Mathematical Programming, SIAM Journal on Control and Optimization, vol.31, issue.5, pp.1340-1359, 1993.
DOI : 10.1137/0331063

E. J. Candès and B. Recht, Simple bounds for recovering low-complexity models, Mathematical Programming, pp.577-589, 2013.
DOI : 10.1007/s10107-012-0540-0

E. J. Candès, J. K. Romberg, and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, vol.52, issue.2, pp.489-509, 2006.
DOI : 10.1109/TIT.2005.862083

E. J. Candès and T. Tao, Decoding by Linear Programming, IEEE Transactions on Information Theory, vol.51, issue.12, pp.4203-4215, 2005.
DOI : 10.1109/TIT.2005.858979

E. J. Candès and T. Tao, Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?, IEEE Transactions on Information Theory, vol.52, issue.12, pp.5406-5425, 2006.
DOI : 10.1109/TIT.2006.885507

V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, The Convex Geometry of Linear Inverse Problems, Foundations of Computational Mathematics, vol.1, issue.10, pp.805-849, 2012.
DOI : 10.1007/s10208-012-9135-7

S. S. Chen, D. L. Donoho, and M. A. Saunders, Atomic Decomposition by Basis Pursuit, SIAM Journal on Scientific Computing, vol.20, issue.1, pp.33-61, 1998.
DOI : 10.1137/S1064827596304010

A. Cohen, W. Dahmen, and R. Devore, Compressed sensing and best $k$-term approximation, Journal of the American Mathematical Society, vol.22, issue.1, pp.211-231, 2009.
DOI : 10.1090/S0894-0347-08-00610-3

A. Aspremont and L. Ghaoui, Testing the nullspace property using semidefinite programming, Mathematical Programming, vol.11, issue.2, pp.123-144, 2011.
DOI : 10.1007/s10107-010-0416-0

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

D. L. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Transactions on Information Theory, vol.47, issue.7, pp.2845-2862, 2001.
DOI : 10.1109/18.959265

M. Friedlander, I. Macêdo, and T. K. Pong, Gauge Optimization and Duality, SIAM Journal on Optimization, vol.24, issue.4, pp.1999-2022, 2014.
DOI : 10.1137/130940785

J. J. Fuchs, On Sparse Representations in Arbitrary Redundant Bases, IEEE Transactions on Information Theory, vol.50, issue.6, pp.1341-1344, 2004.
DOI : 10.1109/TIT.2004.828141

J. Ch, C. Gilbert, E. Gonzaga, and . Karas, Examples of ill-behaved central paths in convex optimization, Mathematical Programming, pp.63-94, 2005.

A. J. Goldman and A. W. Tucker, 4. Theory of Linear Programming, Linear Inequalities and Related Systems, pp.53-97, 1956.
DOI : 10.1515/9781400881987-005

URL : https://hal.archives-ouvertes.fr/hal-00387136

M. Grasmair, M. Haltmeier, and O. Scherzer, Necessary and sufficient conditions for linear convergence of ???1-regularization, Communications on Pure and Applied Mathematics, vol.52, issue.3, pp.161-182, 2011.
DOI : 10.1002/cpa.20350

Z. Harchaoui, A. Juditsky, and A. Nemirovski, Conditional gradient algorithms for normregularized smooth convex optimization, Mathematical Programming, issue.2, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00978368

J. Hiriart-urruty and C. , Convex Analysis and Minimization Algorithms. Grundlehren der mathematischen Wissenschaften 305-306, p.7, 1993.

A. Juditsky, F. K?l?nç-karzan, and A. Nemirovski, Verifiable conditions of ??? 1-recovery for sparse signals with sign restrictions, Mathematical Programming, vol.41, issue.12, pp.89-122, 2011.
DOI : 10.1007/s10107-010-0418-y

A. Juditsky and A. Nemirovski, Accuracy Guarantees for <formula formulatype="inline"> <tex Notation="TeX">$\ell_1$</tex></formula>-Recovery, IEEE Transactions on Information Theory, vol.57, issue.12, pp.7818-7839, 2011.
DOI : 10.1109/TIT.2011.2162569

A. Juditsky and A. Nemirovski, On verifiable sufficient conditions for sparse signal recovery via ??? 1 minimization, Mathematical Programming, pp.57-88, 2011.
DOI : 10.1007/s10107-010-0417-z

URL : https://hal.archives-ouvertes.fr/hal-00321775

J. Moreau, Proximit?? et dualit?? dans un espace hilbertien, Bulletin de la Soci&#233;t&#233; math&#233;matique de France, vol.79, pp.273-299, 1965.
DOI : 10.24033/bsmf.1625

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

Y. E. Nesterov and A. S. Nemirovski, On first-order algorithms for l 1/nuclear norm minimization, Acta Numerica, vol.22, issue.2, pp.509-575, 2013.
DOI : 10.1017/S096249291300007X

B. T. Polyak, Sharp minima, 1979.

B. T. Polyak, Introduction to Optimization. Optimization Software, 1987.

R. T. Rockafellar, Convex Analysis. Princeton Mathematics Ser. 28, p.26, 1970.

C. Roos, T. Terlaky, and J. , Theory and Algorithms for Linear Optimization ? An Interior Point Approach, Vial, vol.23, p.24, 1997.

R. Saigal, Linear Programming ? A Modern Integrated Analysis, p.15, 1995.

S. J. Wright, Primal-Dual Interior-Point Methods, p.24, 1997.
DOI : 10.1137/1.9781611971453

H. Zhang, W. Yin, and L. Cheng, Necessary and Sufficient Conditions of Solution Uniqueness in 1-Norm Minimization, Journal of Optimization Theory and Applications, vol.61, issue.5???8, pp.109-122, 2015.
DOI : 10.1007/s10957-014-0581-z

Y. Zhang, A simple proof for recoverability of ? 1 -minimization: go over or under?, 2005.

Y. Zhao and Z. Luo, -Algorithms for the Sparsest Points of Polyhedral Sets, Mathematics of Operations Research, vol.42, issue.1, 2016.
DOI : 10.1287/moor.2016.0791

URL : https://hal.archives-ouvertes.fr/hal-00807197