On-line catalogue and orders (secure paiement, VISA or MASTERCARD only)

Journals available by subscription

Annales scientifiques de l'ENS


Bulletin de la SMF

Mémoires de la SMF

Revue d'Histoire des Mathématiques

Gazette des Mathématiciens



Cours Spécialisés

Documents Mathématiques

Mémoires de la SMF

Panoramas et Synthèses

Séminaires et Congrès

Jean Morlet Chair Series

SMF/AMS Texts and Monographs

La Série T

Volumes "Journée Annuelle"

Other Books

Donald E. Knuth - French translations

Nicolas Bourbaki's seminar new edition

Jean Leray's scientific works new edition

Revue de l'Institut Elie Cartan

Electronic Editions

Annales scientifiques de l'ENS

Bulletin de la SMF

Revue d'Histoire des Mathématiques

Séminaires et Congrès

More information / Subscription

Publications for a general public

L'explosion des mathématiques (smf.emath.fr)

Mathématiques L'explosion continue (smf.emath.fr)

Zoom sur les métiers des maths (smf.emath.fr)

Zoom sur les métiers des mathématiques et de l'informatique (smf.emath.fr)

Où en sont les mathématiques ?

La Série T

For the authors

Submission of manuscripts

Formats and documentation

More info

Electronic distribution list (smf.emath.fr)

Information for bookselers and subscription agencies (smf.emath.fr)

Publications de la SMF
fr en
Your IP number:
Access to elec. publ.: SémCong


Presentation of the publication


Last Titles

Editorial staff committee / Secretary



Catalogue & orders

Astérisque - Titles - 390 (2017) 409-426

Titles < 2017 < 390

Séminaire Bourbaki, volume 2015/2016, exposés 1104-1119
Astérisque 390 (2017), xi+533 pages
Download the document
Presentation, Summary

Exposé 1117 : Parcimonie et systèmes linéaires sous-determinés
Francis BACH
Astérisque 390 (2017), 409-426
Download the document

Résumé :
Les systèmes linéaires sous-déterminés, avec plus d'inconnues que d'équations, sont très courants dans de nombreux domaines d'applications des mathématiques. Pour pallier l'absence de solutions uniques, certaines structures, dites de parcimonie, peuvent être imposées sur les solutions, comme le fait d'avoir un nombre maximal de composantes non nulles. Cette simple hypothèse donne lieu à une théorie riche mettant en jeu des concepts de convexité et de matrices aléatoires. Dans cet exposé, je présenterai les travaux d'Emmanuel Candès sur l'échantillonnage compressé et la complétion de matrices, qui sont deux instantiations marquantes de ces systèmes sous-déterminés.

Mots-clefs : Systèmes linéaires sous-déterminés, parcimonie, matrices aléatoires.

Exposé 1117 : Sparsity and undetermined linear systems
Undetermined linear systems, with more unknowns than equations, are very common in many application areas of mathematics. To remedy the lack of unique solutions, certain sparse structures can be imposed on the solutions, such as having a bounded number of non-zero components. This simple assumption leads to a rich theory mixing concepts from convex optimization and random matrices. In this seminar, I will present some of the contributions of Emmanuel Candès on compressed sensing and matrix completion, which are two remarkable instances of these underdetermined systems.

Keywords: Undetermined linear systems, sparcity, random matrices.

Class. math. : 52B55, 62H12, 42B05.

ISSN : 0303-1179
Publié avec le concours de : Centre National de la Recherche Scientifique


Achlioptas, Dimitris
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
J. Comput. System Sci. 66 (2003) 671–687
Math Reviews MR2005771
Ahlswede, Rudolf and Winter, Andreas
Strong converse for identification via quantum channels
IEEE Trans. Inform. Theory 48 (2002) 569–579
Math Reviews MR1889969
Amelunxen, Dennis and Lotz, Martin and McCoy, Michael B. and Tropp, Joel A.
Living on the edge: phase transitions in convex programs with random data
Inf. Inference 3 (2014) 224–294
Math Reviews MR3311453
Bach, F.
Learning with submodular functions: A convex optimization Perspective
Foundations and Trends in Machine Learning 6 (2013) 145–373
Bach, F. and Jenatton, R. and Mairal, J. and Obozinski, G.
Optimization with sparsity-inducing penalties
Foundations and Trends in Machine Learning 4 (2012) 1–106
Baraniuk, Richard and Davenport, Mark and DeVore, Ronald and Wakin, Michael
A simple proof of the restricted isometry property for random matrices
Constr. Approx. 28 (2008) 253–263
Math Reviews MR2453366
Beck, Amir and Teboulle, Marc
A fast iterative shrinkage-thresholding algorithm for linear inverse problems
SIAM J. Imaging Sci. 2 (2009) 183–202
Math Reviews MR2486527
Bickel, Peter J. and Ritov, Ya'acov and Tsybakov, Alexandre B.
Simultaneous analysis of lasso and Dantzig selector
Ann. Statist. 37 (2009) 1705–1732
Math Reviews MR2533469
Boucheron, Stéphane and Lugosi, Gábor and Massart, Pascal
Concentration inequalities
Oxford Univ. Press, Oxford, 2013
Math Reviews MR3185193
Bühlmann, Peter and van de Geer, Sara
Statistics for high-dimensional data
Springer, Heidelberg, 2011
Math Reviews MR2807761
Candès, Emmanuel J.
The restricted isometry property and its implications for compressed sensing
C. R. Math. Acad. Sci. Paris 346 (2008) 589–592
Math Reviews MR2412803
Candès, Emmanuel J.
Mathematics of sparsity (and a few other things)
in Proceedings of the International Congress of Mathematicians
(2014) 235–258
Candès, Emmanuel J. and Plan, Yaniv
A probabilistic and RIPless theory of compressed sensing
IEEE Trans. Inform. Theory 57 (2011) 7235–7254
Math Reviews MR2883653
Candès, Emmanuel J. and Recht, Benjamin
Exact matrix completion via convex optimization
Found. Comput. Math. 9 (2009) 717–772
Math Reviews MR2565240
Candès, Emmanuel J. and Romberg, Justin and Tao, Terence
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
IEEE Trans. Inform. Theory 52 (2006) 489–509
Math Reviews MR2236170
Candes, Emmanuel J. and Tao, Terence
Decoding by linear programming
IEEE Trans. Inform. Theory 51 (2005) 4203–4215
Math Reviews MR2243152
Candes, Emmanuel J. and Tao, Terence
Near-optimal signal recovery from random projections: universal encoding strategies?
IEEE Trans. Inform. Theory 52 (2006) 5406–5425
Math Reviews MR2300700
Candès, Emmanuel J. and Tao, Terence
The power of convex relaxation: near-optimal matrix completion
IEEE Trans. Inform. Theory 56 (2010) 2053–2080
Math Reviews MR2723472
Chafaï, Djalil and Guédon, Olivier and Lecué, Guillaume and Pajor, Alain
Interactions between compressed sensing random matrices and high dimensional geometry
Soc. Math. France, Paris, 2012
Math Reviews MR3113826
Chandrasekaran, Venkat and Recht, Benjamin and Parrilo, Pablo A. and Willsky, Alan S.
The convex geometry of linear inverse problems
Found. Comput. Math. 12 (2012) 805–849
Math Reviews MR2989474
Chen, Scott Shaobing and Donoho, David L. and Saunders, Michael A.
Atomic decomposition by basis pursuit
SIAM Rev. 43 (2001) 129–159
Math Reviews MR1854649
d'Aspremont, Alexandre and El Ghaoui, Laurent and Jordan, Michael I. and Lanckriet, Gert R. G.
A direct formulation for sparse PCA using semidefinite programming
SIAM Rev. 49 (2007) 434–448
Math Reviews MR2353806
Donoho, David L. and Elad, Michael
Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization
Proc. Natl. Acad. Sci. USA 100 (2003) 2197–2202
Math Reviews MR1963681
Donoho, David L. and Tanner, Jared
Counting faces of randomly projected polytopes when the projection radically lowers dimension
J. Amer. Math. Soc. 22 (2009) 1–53
Math Reviews MR2449053
Fazel, M. and Hindi, H. and Boyd, S.P.
A rank minimization heuristic with application to minimum order system approximation
Proceedings of the American Control Conference 6 (2001) 4734–4739
Foucart, Simon and Rauhut, Holger
A mathematical introduction to compressive sensing
Birkhäuser, 2013
Math Reviews MR3100033
Giraud, Christophe
Introduction to high-dimensional statistics
CRC Press, Boca Raton, FL, 2015
Math Reviews MR3307991
Gordon, Y.
On Milman's inequality and random subspaces which escape through a mesh in <b>R</b>n
in Geometric aspects of functional analysis (1986/87)
Lecture Notes in Math. 1317 (1988) 84–106
Math Reviews MR950977
Gribonval, Rémi and Nielsen, Morten
Sparse representations in unions of bases
IEEE Trans. Inform. Theory 49 (2003) 3320–3325
Math Reviews MR2045813
Gross, David
Recovering low-rank matrices from few coefficients in any basis
IEEE Trans. Inform. Theory 57 (2011) 1548–1566
Math Reviews MR2815834
Hastie, Trevor and Tisbshirani, Robert and Wainwright, Martin
Statistical learning with sparsity: the Lasso and generalizations
CRC Press, 2015
Johnson, William B. and Lindenstrauss, Joram
Extensions of Lipschitz mappings into a Hilbert space
in Conference in modern analysis and probability (New Haven, Conn., 1982)
Contemp. Math. 26 (1984) 189–206
Math Reviews MR737400
Kashin, B. S. and Temlyakov, V. N.
A remark on the problem of compressed sensing
Mat. Zametki 82 (2007) 829–837
Math Reviews MR2399963
Mallat, S. and Zhang, Z.
Matching pursuits with time-frequency dictionaries
IEEE Transactions on Signal Processing 41 (1993) 3397–3415
Natarajan, B. K.
Sparse approximate solutions to linear systems
SIAM J. Comput. 24 (1995) 227–234
Math Reviews MR1320206
Needell, Deanna and Vershynin, Roman
Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
Found. Comput. Math. 9 (2009) 317–334
Math Reviews MR2496554
Nesterov, Yurii and Nemirovskii, Arkadii
Interior-point polynomial algorithms in convex programming
Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994
Math Reviews MR1258086
Rudelson, Mark and Vershynin, Roman
On sparse reconstruction from Fourier and Gaussian measurements
Comm. Pure Appl. Math. 61 (2008) 1025–1045
Math Reviews MR2417886
Spielman, Daniel A. and Teng, Shang-Hua
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
J. ACM 51 (2004) 385–463
Math Reviews MR2145860
Strohmer, Thomas and Heath, Robert W. Jr.
Grassmannian frames with applications to coding and communication
Appl. Comput. Harmon. Anal. 14 (2003) 257–275
Math Reviews MR1984549
Tibshirani, Robert
Regression shrinkage and selection via the lasso
J. Roy. Statist. Soc. Ser. B 58 (1996) 267–288
Math Reviews MR1379242
Tropp, Joel A.
User-friendly tail bounds for sums of random matrices
Found. Comput. Math. 12 (2012) 389–434
Math Reviews MR2946459
Tropp, Joel A. and Gilbert, Anna C.
Signal recovery from random measurements via orthogonal matching pursuit
IEEE Trans. Inform. Theory 53 (2007) 4655–4666
Math Reviews MR2446929
Wainwright, Martin J.
Sharp thresholds for high-dimensional and noisy sparsity recovery using 1-constrained quadratic programming (Lasso)
IEEE Trans. Inform. Theory 55 (2009) 2183–2202
Math Reviews MR2729873