M. Amini and . Wainwright, using an integration by part w.r.t w kl (the boundary terms can be shown to vanish), then Bayes formula, and finally (153), one obtains References Arash A, Information Theory, pp.2454-2458, 2008.

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.

B. Barak, B. Samuel, J. Hopkins, . Kelner, K. Pravesh et al., A nearly tight sum-of-squares lower bound for the planted clique problem, 2016.

J. Barbier and N. Macris, The adaptive interpolation method: a simple scheme to prove replica formulas in bayesian inference. Probability Theory and Related Fields, 2018.

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, vol.29, pp.424-432, 2016.
URL : https://hal.archives-ouvertes.fr/cea-01568705

J. Barbier, M. Dia, and N. Macris, Universal sparse superposition codes with spatial coupling and gamp decoding, 2017.

J. Barbier, N. Macris, M. Dia, and F. Krzakala, Mutual information and optimality of approximate message-passing in random linear estimation, 2017.

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

J. Peter, A. Bickel, and . Chen, A nonparametric view of network models and newmangirvan and other modularities, Proceedings of the National Academy of Sciences, vol.106, issue.50, pp.21068-21073, 2009.

J. Cai, E. J. Candès, and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, vol.20, issue.4, pp.1956-1982, 2010.

F. Caltagirone, S. Franz, R. G. Morris, and L. Zdeborová, Dynamics and termination cost of spatially coupled mean-field models, Phys. Rev. E, vol.89, p.12102, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00996993

J. Emmanuel, B. Candès, and . Recht, Exact matrix completion via convex optimization, Foundations of Computational mathematics, vol.9, issue.6, pp.717-772, 2009.

Y. Chen and J. Xu, Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices, 2014.

L. E. Alexandre-d'aspremont, . Ghaoui, G. Michael-i-jordan, and . Lanckriet, A direct formulation for sparse pca using semidefinite programming, SIAM review, vol.49, issue.3, pp.434-448, 2007.

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

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

Y. Deshpande, E. Abbe, and A. Montanari, Asymptotic mutual information for the two-groups stochastic block model, 2015.

M. Dia, High-Dimensional Inference on Dense Graphs with Applications to Coding Theory and Machine Learning, EPFL IC School, 2018.

S. Franz and F. L. Toninelli, Finite-range spin glasses in the kac limit: free energy and local observables, Journal of Physics A: Mathematical and General, vol.37, issue.30, p.7433, 2004.

A. Giurgiu, N. Macris, and R. Urbanke, Spatial coupling as a proof technique and three applications, IEEE Transactions on Information Theory, vol.62, issue.10, pp.5281-5295, 2016.

F. Guerra, An introduction to mean field spin glass theory: methods and results, Mathematical Statistical Physics, pp.243-271, 2005.

F. Guerra and F. L. Toninelli, The thermodynamic limit in mean field spin glass models, Commun. Math. Phys, vol.230, issue.1, pp.71-79, 2002.

D. Guo, S. Shamai, and S. Verdú, Mutual information and minimum mean-square error in gaussian channels, IEEE Trans. on Information Theory, vol.51, 2005.

B. Hajek, Y. Wu, and J. Xu, Submatrix localization via message passing, 2015.

N. S-hamed-hassani, R. Macris, and . Urbanke, Coupled graphical models and their thresholds, IEEE Information Theory Workshop (ITW), 2010.

A. Javanmard and A. Montanari, State evolution for general approximate message passing algorithms, with applications to spatial coupling, Journal of Information and Inference, vol.2, issue.2, pp.115-144, 2013.

M. Iain, A. Johnstone, and . Lu, , vol.7, 2004.

M. Iain, A. Johnstone, and . Lu, On consistency and sparsity for principal components analysis in high dimensions, Journal of the American Statistical Association, 2012.

B. Karrer, . Mark, and . Newman, Stochastic blockmodels and community structure in networks, Physical Review E, vol.83, issue.1, p.16107, 2011.

S. Raghunandan-h-keshavan, A. Oh, and . Montanari, Matrix completion from a few entries, IEEE International Symposium on, pp.324-328, 2009.

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

F. Krzakala, J. Xu, and L. Zdeborová, Mutual information in rank-one matrix estimation, 2016.

S. Kudekar, R. Thomas-j-richardson, and . Urbanke, Threshold saturation via spatial coupling: Why convolutional ldpc ensembles perform so well over the bec, IEEE Trans. on Inf. Th, vol.57, 2011.

M. Lelarge and L. Miolane, Fundamental limits of symmetric low-rank matrix estimation, 2017.
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 (Allerton), 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, pp.1635-1639, 2015.
URL : https://hal.archives-ouvertes.fr/cea-01140712

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.

S. Rangan and A. Fletcher, Iterative estimation of constrained rank-one matrices in noise, 2012 IEEE International Symposium on, pp.1246-1250, 2012.

F. Ricci-tersenghi, A. Javanmard, and A. Montanari, Performance of a community detection algorithm based on semidefinite programming, Journal of Physics: Conference Series, vol.699, p.12015, 2016.

A. Saade, F. Krzakala, and L. Zdeborová, Spectral clustering of graphs with the bethe hessian, Advances in Neural Information Processing Systems, pp.406-414, 2014.
URL : https://hal.archives-ouvertes.fr/cea-01140852

A. Saade, F. Krzakala, and L. Zdeborová, Matrix completion from fewer entries: Spectral detectability and rank estimation, Advances in Neural Information Processing Systems, pp.1261-1269, 2015.
URL : https://hal.archives-ouvertes.fr/cea-01222302

A. Yedla, Y. Jian, H. Phong-s-nguyen, and . Pfister, A simple proof of maxwell saturation for coupled scalar recursions, IEEE Trans. on Inf. Theory, vol.60, issue.11, pp.6943-6965, 2014.

H. Zou, T. Hastie, and R. Tibshirani, Journal of computational and graphical statistics, vol.15, pp.265-286, 2006.