. =-p-|-?-?-|-?, ] and |?(? x + ? * Z x , ? * ? * )| ? (0, 2 2 ] and ? ? ? ?(? x + ? * Z x , ? * ? * ) ? 2 +

, By an easy extension of the I-MMSE relation (1.3.4) we have for all t ? [0, 1]: Let us now prove the second part of the Proposition: we now assume that f and g are differentiable, strictly convex. Let (q 1 , q 2 ) now that q 1 = 0 (the case q 2 = 0 follows by symmetry), We have f (0) = F P 2 (?) and f (1) = F P 1 (?)

, g(0) = sup ? ? ? g (0), f (0) = f (0) + g(0) + f (0)g (0) ? f (0) + g(0)

, f (0)) ? ?. From (C.4) we get also that f (0) = 0 or g (0) = 0. Assume that f (0) = 0 (the case g (0) = 0 follows by symmetry), then 0 ? ?f (g (0)) because (g (0), f (0)) ? ?. Since f is strictly increasing, We get that (g (0), f (0)) achieves the supremum of ?, which implies that (g (0)

E. Abbe and C. Sandon, Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic bp, and the information-computation gap, 2015.

M. Aizenman, R. Sims, and S. Starr, Extended variational principle for the sherrington-kirkpatrick spin-glass model, Physical Review B, vol.68, issue.21, p.214403, 2003.

A. El-alaoui, F. Krzakala, and M. , Finite size corrections and likelihood ratio fluctuations in the spiked wigner model, 2017.

J. David and . Aldous, Representations for partially exchangeable arrays of random variables, Journal of Multivariate Analysis, vol.11, issue.4, pp.581-598, 1981.

D. Amelunxen, M. Lotz, B. Michael, J. A. Mccoy, and . Tropp, Living on the edge: Phase transitions in convex programs with random data. Information and Inference: A, Journal of the IMA, vol.3, issue.3, pp.224-294, 2014.

A. Arash, M. Amini, and . Wainwright, High-dimensional analysis of semidefinite relaxations for sparse principal components, IEEE International Symposium on, pp.2454-2458, 2008.

F. Antenucci, S. Franz, P. Urbani, and L. Zdeborová, Glassy nature of the hard phase in inference problems, Physical Review X, vol.9, issue.1, p.11020, 2019.
URL : https://hal.archives-ouvertes.fr/cea-01930645

G. Ben-arous, R. Gheissari, and A. Jagannath, Algorithmic thresholds for tensor pca, 2018.

G. Ben-arous, S. Mei, A. Montanari, and M. Nica, The landscape of the spiked tensor model, 2017.

A. Auffinger, G. Ben-arous, and J. , Random matrices and complexity of spin glasses, Communications on Pure and Applied Mathematics, vol.66, issue.2, pp.165-201, 2013.

A. Auffinger and G. Ben-arous, Complexity of random smooth functions on the high-dimensional sphere, The Annals of Probability, vol.41, issue.6, pp.4214-4247, 2013.

T. Austin, Exchangeable random measures, Annales de l'IHP Probabilités et statistiques, vol.51, pp.842-861, 2015.

J. Baik, G. Ben-arous, and S. Péché, Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices, Annals of Probability, pp.1643-1697, 2005.

J. Baik and . Jack-w-silverstein, Eigenvalues of large sample covariance matrices of spiked population models, Journal of Multivariate Analysis, vol.97, issue.6, pp.1382-1408, 2006.

C. Baldassi, A. Braunstein, N. Brunel, and R. Zecchina, Efficient supervised learning in networks with binary synapses, BMC neuroscience, vol.8, issue.2, p.13, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00174082

J. Banks, C. Moore, R. Vershynin, N. Verzelen, and J. Xu, Information-theoretic bounds and phase transitions in clustering, sparse pca, and submatrix localization, 2017 IEEE International Symposium on, pp.1137-1141, 2017.

J. Barbier, M. Dia, N. Macris, and F. Krzakala, The mutual information in random linear estimation, 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.625-632, 2016.

J. Barbier, M. Dia, N. Macris, F. Krzakala, T. Lesieur et al., Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula, Advances in Neural Information Processing Systems, pp.424-432, 2016.
URL : https://hal.archives-ouvertes.fr/cea-01568705

J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová, Optimal errors and phase transitions in high-dimensional generalized linear models, Proceedings of the National Academy of Sciences, 2019.

J. Barbier and N. Macris, The stochastic interpolation method: A simple scheme to prove replica formulas in bayesian inference, 2017.

J. Barbier, N. Macris, and L. Miolane, The layered structure of tensor estimation and its mutual information, 2017.

A. Barra, G. Genovese, and F. Guerra, Equilibrium statistical mechanics of bipartite spin systems, Journal of Physics A: Mathematical and Theoretical, vol.44, issue.24, p.245002, 2011.

B. Eric, Y. Baum, and . Lyuu, The transition to perfect generalization in perceptrons, Neural computation, vol.3, issue.3, pp.386-401, 1991.

M. Bayati, A. Murat, A. Erdogdu, and . Montanari, Estimating lasso risk and noise level, Advances in Neural Information Processing Systems, pp.944-952, 2013.

M. Bayati, M. Lelarge, and A. Montanari, Universality in polytope phase transitions and message passing algorithms, The Annals of Applied Probability, vol.25, issue.2, pp.753-822, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01254901

M. Bayati and A. Montanari, The dynamics of message passing on dense graphs, with applications to compressed sensing, IEEE Transactions on Information Theory, vol.57, issue.2, pp.764-785, 2011.

M. Bayati and A. Montanari, The lasso risk for gaussian matrices, IEEE Transactions on Information Theory, vol.58, issue.4, pp.1997-2017, 2012.

F. Benaych, -. Georges, and R. Rao-nadakuditi, The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices, Advances in Mathematics, vol.227, issue.1, pp.494-521, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00423593

F. Benaych, -. Georges, and R. Rao-nadakuditi, The singular values and vectors of low rank perturbations of large rectangular random matrices, Journal of Multivariate Analysis, vol.111, pp.120-135, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00575203

Q. Berthet and P. Rigollet, Optimal detection of sparse principal components in high dimension, The Annals of Statistics, vol.41, issue.4, pp.1780-1815, 2013.

R. Berthier, A. Montanari, and P. Nguyen, State evolution for approximate message passing with non-separable functions. Information and Inference: A, Journal of the IMA, 2017.

J. Peter, . Bickel, A. J. Chris, . Klaassen, J. Peter et al., Efficient and adaptive estimation for semiparametric models, vol.4, 1993.

J. Peter, . Bickel, A. Ya'acov-ritov, and . Tsybakov, Simultaneous analysis of Lasso and Dantzig selector, The Annals of Statistics, vol.37, issue.4, pp.1705-1732, 2009.

I. Vladimir and . Bogachev, Measure theory, vol.1, 2007.

E. Bolthausen, An iterative construction of solutions of the tap equations for the sherrington-kirkpatrick model, Communications in Mathematical Physics, vol.325, issue.1, pp.333-366, 2014.

C. Bordenave, M. Lelarge, and L. Massoulié, Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs, Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pp.1347-1357, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01226796

S. Boucheron, G. Lugosi, and P. Massart, Concentration inequalities: A nonasymptotic theory of independence, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00794821

T. Petros, R. G. Boufounos, and . Baraniuk, 1-bit compressive sensing, 42nd Annual Conference on Information Sciences and Systems (CISS), pp.16-21, 2008.

P. Bühlmann, S. Van-de, and . Geer, Statistics for high-dimensional data: methods, theory and applications, 2011.

F. Caltagirone, M. Lelarge, and L. Miolane, Recovering asymmetric communities in the stochastic block model, IEEE Transactions on Network Science and Engineering, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01391609

E. Candes and T. Tao, The Dantzig selector: Statistical estimation when p is much larger than n. The Annals of Statistics, vol.35, pp.2313-2351, 2007.

J. Emmanuel, T. Candes, and . Tao, Decoding by linear programming, IEEE transactions on information theory, vol.51, issue.12, pp.4203-4215, 2005.

J. Emmanuel, T. Candes, and . Tao, Near-optimal signal recovery from random projections: Universal encoding strategies?, IEEE transactions on information theory, vol.52, pp.5406-5425, 2006.

M. Capitaine, C. Donati-martin, and D. Féral, The largest eigenvalues of finite rank deformation of large wigner matrices: convergence and nonuniversality of the fluctuations, The Annals of Probability, pp.1-47, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00939972

S. Chatterjee, A generalization of the lindeberg principle. The Annals of Probability, vol.34, pp.2061-2076, 2006.

S. Chen, L. David, and . Donoho, Examples of basis pursuit, Wavelet Applications in Signal and Image Processing III, vol.2569, pp.564-575, 1995.

W. Chen, Phase transition in the spiked random tensor with rademacher prior, 2017.

W. Chen, The aizenman-sims-starr scheme and parisi formula for mixed p-spin spherical models, Electron. J. Probab, vol.18, issue.94, pp.1-14, 2013.

W. Chen, M. Handschy, and G. Lerman, Phase transition in random tensors with multiple spikes, 2018.

W. Chen and D. Panchenko, On the tap free energy in the mixed p-spin models, Communications in Mathematical Physics, vol.362, issue.1, pp.219-252, 2018.

W. Chen and A. Sen, Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed p-spin models, Communications in Mathematical Physics, vol.350, issue.1, pp.129-173, 2017.

F. Chollet, , 2015.

A. Crisanti and H. Sommers, Thouless-anderson-palmer approach to the spherical p-spin spin glass model, Journal de Physique I, vol.5, issue.7, pp.805-813, 1995.
URL : https://hal.archives-ouvertes.fr/jpa-00247104

A. Crisanti and H. Sommers, The sphericalp-spin interaction spin glass model: the statics, Zeitschrift für Physik B Condensed Matter, vol.87, issue.3, pp.341-354, 1992.

A. , &. Aspremont, L. E. Ghaoui, M. I. Jordan, and G. R. Lanckriet, A direct formulation for sparse pca using semidefinite programming, Advances in neural information processing systems, pp.41-48, 2005.

A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Physical Review E, vol.84, issue.6, p.66106, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00661643

B. Derrida, Random-energy model: Limit of a family of disordered models, Physical Review Letters, vol.45, issue.2, p.79, 1980.

B. Derrida, Random-energy model: An exactly solvable model of disordered systems, Physical Review B, vol.24, issue.5, p.2613, 1981.

Y. Deshpande, E. Abbe, and A. Montanari, Asymptotic mutual information for the balanced binary stochastic block model. Information and Inference: A, Journal of the IMA, vol.6, issue.2, pp.125-170, 2016.

Y. Deshpande and A. Montanari, Information-theoretically optimal sparse pca, 2014 IEEE International Symposium on Information Theory, pp.2197-2201, 2014.

Y. Deshpande and A. Montanari, Sparse pca via covariance thresholding, Advances in Neural Information Processing Systems, pp.334-342, 2014.

Y. Deshpande, S. Sen, A. Montanari, and E. Mossel, Contextual stochastic block models, Advances in Neural Information Processing Systems, pp.8590-8602, 2018.

L. Devroye, L. Györfi, and G. Lugosi, A probabilistic theory of pattern recognition, vol.31, 2013.

S. Diamond and S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, Journal of Machine Learning Research, 2016.

E. Dobriban, Sharp detection in pca under correlations: all eigenvalues matter, The Annals of Statistics, vol.45, issue.4, pp.1810-1833, 2017.

E. Dobriban, W. Leeb, and A. Singer, Pca from noisy, linearly reduced data: the diagonal case, 2016.

D. Donoho and A. Montanari, High dimensional robust m-estimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, vol.166, pp.935-969, 2016.

L. David and . Donoho, High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete & Computational Geometry, vol.35, issue.4, pp.617-652, 2006.

L. David and I. Donoho, Minimax risk over p -balls for q -error, Probability Theory and Related Fields, vol.99, pp.277-303, 1994.

L. David and J. Donoho, Ideal spatial adaptation by wavelet shrinkage, biometrika, vol.81, issue.3, pp.425-455, 1994.

A. David-l-donoho, A. Maleki, and . Montanari, Message-passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences, vol.106, issue.45, pp.18914-18919, 2009.

A. David-l-donoho, A. Maleki, and . Montanari, The noise-sensitivity phase transition in compressed sensing, IEEE Transactions on Information Theory, vol.57, issue.10, pp.6920-6941, 2011.

L. David, J. Donoho, and . Tanner, Neighborliness of randomly projected simplices in high dimensions, Proceedings of the National Academy of Sciences, vol.102, pp.9452-9457, 2005.

L. David, J. Donoho, and . Tanner, Sparse nonnegative solution of underdetermined linear equations by linear programming, Proceedings of the National Academy of Sciences of the United States of America, vol.102, pp.9446-9451, 2005.

V. N. Ln-dovbysh and . Sudakov, On the gram-de finetti matrices, Zapiski Nauchnykh Seminarov POMI, vol.119, pp.77-86, 1982.

M. E. Dyer and A. M. Frieze, The solution of some random np-hard problems in polynomial expected time, Journal of Algorithms, vol.10, issue.4, pp.451-489, 1989.

S. F. Edwards and R. , The eigenvalue spectrum of a large symmetric random matrix, Journal of Physics A: Mathematical and General, vol.9, issue.10, p.1595, 1976.

B. Efron, The estimation of prediction error: covariance penalties and crossvalidation, Journal of the American Statistical Association, vol.99, issue.467, pp.619-632, 2004.

A. E. , A. , and M. , Detection limits in the high-dimensional spiked rectangular model, Conference On Learning Theory, pp.410-438, 2018.

A. E. , A. , and F. Krzakala, Estimation in the spiked wigner model: A short proof of the replica formula, 2018 IEEE International Symposium on Information Theory (ISIT), pp.1874-1878, 2018.

N. E. Karoui, On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators, Probability Theory and Related Fields, vol.170, pp.95-175, 2018.

W. Evans, C. Kenyon, Y. Peres, and L. J. Schulman, Broadcasting on trees and the ising model, Annals of Applied Probability, pp.410-433, 2000.

S. Zhou-fan, A. Mei, and . Montanari, Tap free energy, spin glasses, and variational inference, 2018.

D. Féral and S. Péché, The largest eigenvalue of rank one deformation of large wigner matrices, Communications in mathematical physics, vol.272, issue.1, pp.185-228, 2007.

N. Fournier and A. Guillin, On the rate of convergence in wasserstein distance of the empirical measure. Probability Theory and Related Fields, vol.162, pp.707-738, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00915365

V. Yan and . Fyodorov, Complexity of random energy landscapes, glass transition, and absolute value of the spectral determinant of random matrices, Physical review letters, vol.92, issue.24, p.240601, 2004.

E. Gardner and . Derrida, Optimal storage properties of neural network models, Journal of Physics A: Mathematical and general, vol.21, issue.1, p.271, 1988.

E. Gardner, The space of interactions in neural network models, Journal of physics A: Mathematical and general, vol.21, issue.1, p.257, 1988.

E. Gardner and B. Derrida, Three unfinished works on the optimal storage capacity of networks, Journal of Physics A: Mathematical and General, vol.22, issue.12, 1983.

S. Ghirlanda and F. Guerra, General properties of overlap probability distributions in disordered spin systems. towards parisi ultrametricity, Journal of Physics A: Mathematical and General, vol.31, issue.46, p.9149, 1998.

P. Gillin and D. Sherrington, p > 2 spin glasses with first-order ferromagnetic transitions, Journal of Physics A: Mathematical and General, vol.33, issue.16, p.3081, 2000.

T. Goldstein and C. Studer, Phasemax: Convex phase retrieval via basis pursuit, IEEE Transactions on Information Theory, 2018.

Y. Gordon, Some inequalities for gaussian processes and applications, Israel Journal of Mathematics, vol.50, issue.4, pp.265-289, 1985.

Y. Gordon, On milman's inequality and random subspaces which escape through a mesh in rn, Geometric Aspects of Functional Analysis, pp.84-106

. Springer, , 1988.

F. Guerra, Broken replica symmetry bounds in the mean field spin glass model, Communications in mathematical physics, vol.233, issue.1, pp.1-12, 2003.

D. Guo, S. Shamai, and S. Verdú, Mutual information and minimum mean-square error in gaussian channels, IEEE Transactions on Information Theory, vol.51, issue.4, pp.1261-1282, 2005.

D. Guo, Y. Wu, S. Shlomo, S. Shitz, and . Verdú, Estimation in gaussian noise: Properties of the minimum mean-square error, IEEE Transactions on Information Theory, vol.57, issue.4, pp.2371-2385, 2011.

G. Györgyi, First-order transition to perfect generalization in a neural network with binary synapses, Physical Review A, vol.41, issue.12, p.7097, 1990.

D. Hansel, C. Mato, and . Meunier, Memorization without generalization in a multilayered neural network, Europhysics Letters), vol.20, issue.5, p.471, 1992.
URL : https://hal.archives-ouvertes.fr/hal-02387185

P. Hartman, Ordinary Differential Equations. Society for Industrial and Applied Mathematics, 1964.

S. Heimlicher, M. Lelarge, and L. Massoulié, Community detection in the labelled stochastic block model, 2012.

J. Christopher, L. Hillar, and . Lim, Most tensor problems are np-hard, Journal of the ACM (JACM), vol.60, issue.6, p.45, 2013.

W. Paul, K. B. Holland, S. Laskey, and . Leinhardt, Stochastic blockmodels: First steps, Social networks, vol.5, issue.2, pp.109-137, 1983.

N. Douglas and . Hoover, Relations on probability spaces and arrays of random variables. Preprint, Institute for Advanced Study, 1979.

J. John and . Hopfield, Neural networks and physical systems with emergent collective computational abilities, Proceedings of the national academy of sciences, vol.79, pp.2554-2558, 1982.

B. Samuel, T. Hopkins, J. Schramm, D. Shi, and . Steurer, Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp.178-191, 2016.

B. Samuel, J. Hopkins, D. Shi, and . Steurer, Tensor principal component analysis via sum-of-square proofs, Conference on Learning Theory, pp.956-1006, 2015.

T. Hosaka, Y. Kabashima, and H. Nishimori, Statistical mechanics of lossy data compression using a nonmonotonic perceptron, Physical Review E, vol.66, issue.6, p.66126, 2002.

C. David, M. Hoyle, and . Rattray, Statistical mechanics of learning multiple orthogonal signals: asymptotic theory and fluctuation effects, Physical review E, vol.75, issue.1, p.16101, 2007.

A. Jagannath, P. Lopatto, and L. Miolane, Statistical thresholds for tensor pca, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01960964

A. Jagannath and I. Tobasco, Low temperature asymptotics of spherical mean field spin glasses, Communications in Mathematical Physics, vol.352, issue.3, pp.979-1017, 2017.

A. Javanmard and A. Montanari, State evolution for general approximate message passing algorithms, with applications to spatial coupling. Information and Inference, p.4, 2013.

A. Javanmard and A. Montanari, Confidence intervals and hypothesis testing for high-dimensional regression, The Journal of Machine Learning Research, vol.15, issue.1, pp.2869-2909, 2014.

M. Iain and . Johnstone, On the distribution of the largest eigenvalue in principal components analysis, Annals of statistics, pp.295-327, 2001.

M. Iain and . Johnstone, Function estimation and gaussian sequence models, 2002.

M. Iain, A. Y. Johnstone, and . Lu, Sparse principal components analysis. Unpublished manuscript, vol.7, 2004.

Y. Kabashima, Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels, Journal of Physics: Conference Series, vol.95, issue.1, p.12001, 2008.

S. Sham-m-kakade, A. Shalev-shwartz, and . Tewari, Regularization techniques for learning with matrices, Journal of Machine Learning Research, vol.13, pp.1865-1890, 2012.

O. Kallenberg, Random measures, theory and applications, 2017.

E. Varun-kanade, T. Mossel, and . Schramm, Global and local information in clustering labeled block models, IEEE Transactions on Information Theory, vol.62, issue.10, pp.5906-5917, 2016.

N. E. Karoui, Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results, 2013.

C. Kim, S. Afonso, M. X. Bandeira, and . Goemans, Community detection in hypergraphs, spiked tensor models, and sum-of-squares, 2017 International Conference on Sampling Theory and Applications (SampTA), pp.124-128, 2017.

J. Kim and D. Pollard, Cube root asymptotics. The Annals of Statistics, vol.18, pp.191-219, 1990.

B. Satish, N. Korada, and . Macris, Exact solution of the gauge symmetric pspin glass model on a complete graph, Journal of Statistical Physics, vol.136, issue.2, pp.205-230, 2009.

B. Satish, N. Korada, and . Macris, Tight bounds on the capacity of binary input random cdma systems, IEEE Transactions on Information Theory, vol.56, issue.11, pp.5590-5613, 2010.

B. Satish, A. Korada, and . Montanari, Applications of the lindeberg principle in communications and statistical learning, IEEE Transactions on Information Theory, vol.57, issue.4, pp.2440-2450, 2011.

F. Krzakala, M. Mézard, F. Sausset, L. Sun, and . Zdeborová, Statistical-physics-based reconstruction in compressed sensing, Physical Review X, vol.2, issue.2, p.21005, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00716897

F. Krzakala, M. Mézard, F. Sausset, Y. Sun, and L. Zdeborová, Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices, Journal of Statistical Mechanics: Theory and Experiment, vol.2012, issue.08, p.8009, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00764645

F. Krzakala, J. Xu, and L. Zdeborová, Mutual information in rankone matrix estimation, Information Theory Workshop (ITW), pp.71-75, 2016.

M. Ledoux and M. Talagrand, Probability in Banach Spaces: isoperimetry and processes, 2013.

M. Lelarge, L. Massoulié, and J. Xu, Reconstruction in the labelled stochastic block model, IEEE Transactions on Network Science and Engineering, vol.2, issue.4, pp.152-163, 2015.

M. Lelarge and L. Miolane, Fundamental limits of symmetric low-rank matrix estimation, Probability Theory and Related Fields, pp.1-71, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01648368

T. Lesieur, F. Krzakala, and L. Zdeborová, MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel, 53rd Annual Allerton Conference on Communication, Control, and Computing, pp.680-687, 2015.
URL : https://hal.archives-ouvertes.fr/cea-01222294

T. Lesieur, F. Krzakala, and L. Zdeborová, Phase transitions in sparse PCA, IEEE International Symposium on Information Theory, pp.1635-1639, 2015.
URL : https://hal.archives-ouvertes.fr/cea-01140712

T. Lesieur, F. Krzakala, and L. Zdeborová, Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications, Journal of Statistical Mechanics: Theory and Experiment, vol.2017, issue.7, p.73403, 2017.
URL : https://hal.archives-ouvertes.fr/cea-01447222

T. Lesieur, L. Miolane, and M. Lelarge, Florent Krzakala, and Lenka Zdeborová. Statistical and computational phase transitions in spiked tensor estimation, IEEE International Symposium on Information Theory (ISIT), pp.511-515, 2017.

J. Ma, J. Xu, and A. Maleki, Optimization-based amp for phase retrieval: The impact of initialization and 2 -regularization, IEEE Transactions on Information Theory, 2019.

L. Massoulié, Community detection thresholds and the weak ramanujan property, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp.694-703, 2014.

R. Matsushita and T. Tanaka, Low-rank matrix reconstruction and clustering via approximate message passing, Advances in Neural Information Processing Systems, pp.917-925, 2013.

P. Mccullagh, Generalized linear models. Routledge, 2018.

C. Méasson, A. Montanari, J. Thomas, R. Richardson, and . Urbanke, The generalized area theorem and some of its consequences, IEEE Transactions on Information Theory, vol.55, issue.11, pp.4793-4821, 2009.

M. Mezard, The space of interactions in neural networks: Gardner's computation with the cavity method, Journal of Physics A: Mathematical and General, vol.22, issue.12, p.2181, 1989.

M. Mézard, G. Parisi, and M. Virasoro, Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, vol.9, 1987.

P. Milgrom and I. Segal, Envelope theorems for arbitrary choice sets. Econometrica, vol.70, pp.583-601, 2002.

L. Miolane, Fundamental limits of low-rank matrix estimation: the non-symmetric case, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01648369

L. Miolane and A. Montanari, The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01960945

M. Mondelli and A. Montanari, Fundamental limits of weak recovery with applications to phase retrieval, Foundations of Computational Mathematics, pp.1-71, 2017.

A. Montanari, Estimating random variables from random sparse observations, European Transactions on Telecommunications, vol.19, issue.4, pp.385-403, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00290792

A. Montanari, Finding one community in a sparse graph, Journal of Statistical Physics, vol.161, issue.2, pp.273-299, 2015.

A. Montanari, D. Reichman, and O. Zeitouni, On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors, Advances in Neural Information Processing Systems, pp.217-225, 2015.

A. Montanari and E. Richard, Non-negative principal component analysis: Message passing algorithms and sharp asymptotics, IEEE Transactions on Information Theory, vol.62, issue.3, pp.1458-1484, 2016.

A. Montanari and R. Venkataramanan, Estimation of low-rank matrices via approximate message passing, 2017.

E. Mossel, Survey-information flow on trees. DIMACS series in discrete mathematics and theoretical computer science, vol.63, pp.155-170, 2004.

E. Mossel, J. Neeman, and A. Sly, A proof of the block model threshold conjecture, 2013.

E. Mossel, J. Neeman, and A. Sly, Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, vol.162, pp.431-461, 2015.

E. Mossel and Y. Peres, Information flow on trees, The Annals of Applied Probability, vol.13, issue.3, pp.817-844, 2003.

E. Mossel and J. Xu, Density evolution in the degree-correlated stochastic block model, 29th Annual Conference on Learning Theory, pp.1319-1356, 2016.

J. Mourrat, Hamilton-jacobi equations for mean-field disordered systems, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01913504

A. Mousavi, A. Maleki, and R. G. Baraniuk, Consistent parameter estimation for lasso and approximate message passing, The Annals of Statistics, vol.45, issue.6, pp.2427-2454, 2017.

B. Nadler, Finite sample approximation results for principal component analysis: A matrix perturbation approach. The Annals of Statistics, pp.2791-2817, 2008.

J. Neeman and P. Netrapalli, Non-reconstructability in the stochastic block model, 2014.

P. Sahand-n-negahban, . Ravikumar, J. Martin, B. Wainwright, and . Yu, A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers, Statistical Science, vol.27, issue.4, pp.538-557, 2012.

H. Nishimori, Exact results and critical properties of the ising model with competing interactions, Journal of Physics C: Solid State Physics, vol.13, issue.21, p.4071, 1980.

H. Nishimori, Internal energy, specific heat and correlation function of the bond-random ising model, Progress of Theoretical Physics, vol.66, issue.4, pp.1169-1181, 1981.

A. Ca, On convergence proofs for perceptrons, 1963.

A. Onatski, J. Marcelo, M. Moreira, and . Hallin, Asymptotic power of sphericity tests for high-dimensional data, The Annals of Statistics, vol.41, issue.3, pp.1204-1231, 2013.

M. Opper and D. Haussler, Generalization performance of bayes optimal classification algorithm for learning a perceptron, Physical Review Letters, vol.66, issue.20, p.2677, 1991.

S. Oymak, A. Jalali, M. Fazel, Y. C. Eldar, and B. Hassibi, Simultaneously structured models with application to sparse and low-rank matrices, IEEE Transactions on Information Theory, vol.61, issue.5, pp.2886-2908, 2015.

A. Panahi and B. Hassibi, A universal analysis of large-scale regularized least squares solutions, Advances in Neural Information Processing Systems, pp.3381-3390, 2017.

D. Panchenko, The Sherrington-Kirkpatrick model, 2013.

D. Panchenko, On the dovbysh-sudakov representation result, Electronic Communications in Probability, vol.15, pp.330-338, 2010.

D. Paul, Asymptotics of sample eigenstructure for a large dimensional spiked covariance model, Statistica Sinica, pp.1617-1642, 2007.

S. Péché, The largest eigenvalue of small rank perturbations of hermitian random matrices. Probability Theory and Related Fields, vol.134, pp.127-173, 2006.

A. Perry, A. Alexander-s-wein, and . Bandeira, Statistical limits of spiked tensor models, 2016.

A. Perry, . Alexander-s-wein, S. Afonso, A. Bandeira, and . Moitra, Optimality and sub-optimality of pca i: Spiked random matrix models, The Annals of Statistics, vol.46, issue.5, pp.2416-2451, 2018.

. Sundeep-rangan, Generalized approximate message passing for estimation with random linear mixing, Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, pp.2168-2172, 2011.

S. Rangan and A. K. Fletcher, Iterative estimation of constrained rank-one matrices in noise, Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, pp.1246-1250, 2012.

G. Raskutti, J. Martin, B. Wainwright, and . Yu, Minimax rates of estimation for high-dimensional linear regression over q -balls, IEEE Transactions on Information Theory, vol.57, issue.10, pp.6976-6994, 2011.

G. Reeves, D. Henry, and . Pfister, The replica-symmetric prediction for compressed sensing with gaussian matrices is exact, Information Theory (ISIT), 2016 IEEE International Symposium on, pp.665-669, 2016.

E. Richard and A. Montanari, A statistical model for tensor pca, Advances in Neural Information Processing Systems, pp.2897-2905, 2014.

T. Richardson and R. Urbanke, Modern coding theory, 2008.

R. Tyrell and R. , Convex analysis, 2015.

V. Ros, G. Ben-arous, G. Biroli, and C. Cammarota, Complex energy landscapes in spiked-tensor and simple glassy models: Ruggedness, arrangements of local minima, and phase transitions, Physical Review X, vol.9, issue.1, p.11003, 2019.

F. Rosenblatt, The perceptron: a probabilistic model for information storage and organization in the brain, Psychological review, vol.65, issue.6, p.386, 1958.

F. Rosenblatt, Principles of neurodynamics. CORNELL AERONAUTICAL LAB INC BUFFALO, 1962.

A. Saade, F. Krzakala, M. Lelarge, and L. Zdeborová, Fast randomized semi-supervised clustering, Journal of Physics: Conference Series, vol.1036, p.12015, 2018.

A. Saade, M. Lelarge, F. Krzakala, and L. Zdeborová, Clustering from sparse pairwise measurements, Information Theory (ISIT), 2016 IEEE International Symposium on, pp.780-784, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01391585

P. Schniter and S. Rangan, Compressive phase retrieval via generalized approximate message passing, IEEE Transactions on Signal Processing, vol.63, issue.4, pp.1043-1055, 2015.

H. Hs-seung, N. Sompolinsky, and . Tishby, Statistical mechanics of learning from examples, Physical review A, vol.45, issue.8, p.6056, 1992.

M. Shcherbina and B. Tirozzi, Rigorous solution of the gardner problem, Communications in mathematical physics, vol.234, issue.3, pp.383-422, 2003.

D. Sherrington and S. Kirkpatrick, Solvable model of a spin-glass, Physical review letters, vol.35, issue.26, p.1792, 1975.

M. Soltanolkotabi, Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization, 2017.

J. Aart and . Stam, Some inequalities satisfied by the quantities of information of fisher and shannon, Information and Control, vol.2, issue.2, pp.101-112, 1959.

M. Charles and . Stein, Estimation of the mean of a multivariate normal distribution. The annals of Statistics, pp.1135-1151, 1981.

M. Stojnic, Recovery thresholds for 1 optimization in binary compressed sensing, Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, pp.1593-1597, 2010.

M. Stojnic, A framework to characterize performance of lasso algorithms, 2013.

E. Subag, The complexity of spherical p-spin models-a second moment approach. The Annals of Probability, vol.45, pp.3385-3450, 2017.

P. Sur and . Candès, A modern maximum-likelihood theory for high-dimensional logistic regression, 2018.

T. Takahashi and Y. Kabashima, A statistical mechanics approach to de-biasing and uncertainty estimation in lasso for random measurements, Journal of Statistical Mechanics: Theory and Experiment, issue.7, p.73405, 2018.

M. Talagrand, Free energy of the spherical mean field model. Probability theory and related fields, vol.134, pp.339-382, 2006.

M. Talagrand, Mean field models for spin glasses: Volume I: Basic examples, vol.54, 2010.

M. Talagrand, Mean field models for spin glasses, Advanced Replica-Symmetry and Low Temperature, vol.II, 2011.

J. David, . Thouless, W. Philip, R. Anderson, and . Palmer, Solution of'solvable model of a spin glass, Philosophical Magazine, vol.35, issue.3, pp.593-601, 1977.

C. Thrampoulidis, E. Abbasi, and B. Hassibi, Precise error analysis of regularized m-estimators in high-dimensions, IEEE Transactions on Information Theory, 2018.

C. Thrampoulidis, S. Oymak, and B. Hassibi, Regularized linear regression: A precise analysis of the estimation error, Conference on Learning Theory, pp.1683-1709, 2015.

R. Tibshirani, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society. Series B (Methodological), pp.267-288, 1996.

J. Ryan, J. Tibshirani, and . Taylor, Degrees of freedom in lasso problems, The Annals of Statistics, vol.40, issue.2, pp.1198-1232, 2012.

A. Joel and . Tropp, Convex recovery of a structured signal from independent random linear measurements, Sampling Theory, a Renaissance, pp.67-101, 2015.

S. Van-de-geer, P. Bühlmann, R. Ritov, and . Dezeure, On asymptotically optimal confidence regions and tests for high-dimensional models. The Annals of Statistics, vol.42, pp.1166-1202, 2014.

. Sara-a-van-de, P. Geer, and . Bühlmann, On the conditions used to prove oracle results for the lasso, Electronic Journal of Statistics, vol.3, pp.1360-1392, 2009.

R. Van-der and . Hofstad, Random graphs and complex networks, 2016.

P. Jeremy, P. Vila, and . Schniter, Expectation-maximization gaussian-mixture approximate message passing, IEEE Transactions on Signal Processing, vol.61, issue.19, pp.4658-4672, 2013.

C. Villani, Optimal transport: old and new, vol.338, 2008.

J. Martin, M. I. Wainwright, and . Jordan, Graphical models, exponential families, and variational inference. Foundations and Trends R in Machine Learning, vol.1, pp.1-305, 2008.

Y. Wu and S. Verdú, Mmse dimension, IEEE Transactions on Information Theory, vol.57, issue.8, pp.4857-4879, 2011.

Y. Wu and S. Verdú, Functional properties of minimum mean-square error and mutual information, IEEE Transactions on Information Theory, vol.58, issue.3, pp.1289-1301, 2012.

Y. Wu and S. Verdú, Optimal phase transitions in compressed sensing, IEEE Transactions on Information Theory, vol.58, issue.10, pp.6241-6263, 2012.

Y. Xu, Y. Kabashima, and L. Zdeborová, Bayesian signal reconstruction for 1-bit compressed sensing, Journal of Statistical Mechanics: Theory and Experiment, issue.11, p.11015, 2014.

C. Zalinescu, Convex analysis in general vector spaces, 2002.

L. Zdeborová and F. Krzakala, Statistical physics of inference: Thresholds and algorithms, Advances in Physics, vol.65, issue.5, pp.453-552, 2016.

C. Zhang and S. S. Zhang, Confidence intervals for low dimensional parameters in high dimensional linear models, Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol.76, issue.1, pp.217-242, 2014.

J. Ziniel, P. Schniter, and P. Sederberg, Binary linear classification and feature selection via generalized approximate message passing, Information Sciences and Systems (CISS), 2014 48th Annual Conference on, pp.1-6, 2014.

H. Zou, T. Hastie, and R. Tibshirani, Sparse principal component analysis, Journal of computational and graphical statistics, vol.15, issue.2, pp.265-286, 2006.

, Nous observons alors un phénomène surprenant: dans de nombreux cas il existe une valeur critique de l'intensité du bruit au-delà de laquelle il n'est plus possible d'extraire de l'information des données. En dessous de ce seuil, nous comparons la performance d'algorithmes polynomiauxà celle optimale, RÉSUMÉ Nousétudions des problèmes statistiques classiques, tels que la détection de communautés dans un graphe, l'analyse en composantes principales, les modèles de mélanges Gaussiens, les modèles linéaires (généralisés ou non), dans un cadre Bayésien

M. Dans-ce, nous adoptons une approche issue de la physique statistique qui explique ces phénomènes en termes de transitions de phase. Les méthodes et outils que nous utilisons proviennent donc de la physique

. Mots-clés-inférence-statistique, théorie de l'information, physique statistique, verres de spin, détection de communauté dans des graphs, estimation de structure de faible rang