, estimation error and convergence in comparison to AMP and ASP. This is also left for future work

R. M. Neal, Markov chain sampling methods for dirichlet process mixture models, Journal of computational and graphical statistics, vol.9, issue.2, pp.249-265, 2000.

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

L. Bottou, Large-scale machine learning with stochastic gradient descent, Proceedings of COMPSTAT'2010, pp.177-186, 2010.

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

D. L. Donoho, A. Maleki, and A. Montanari, Message-passing algorithms for compressed sensing, Proc. Natl. Acad. Sci, vol.106, pp.18914-18919, 2009.

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.

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.

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

M. Mézard, G. Parisi, and M. A. Virasoro, Spin glass theory and beyond, 1987.

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.

M. Advani and S. Ganguli, Statistical mechanics of optimal convex inference in high dimensions, Physical Review X, vol.6, issue.3, p.31034, 2016.

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

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

H. Nishimori, Statistical Physics of Spin Glasses and Information Processing: An Introduction, 2001.

D. Sherrington and S. Kirkpatrick, Solvable model of a spin-glass, Phys. Rev. Lett, vol.35, pp.1792-1796, 1975.

M. Mézard, G. Parisi, and R. Zecchina, Analytic and algorithmic solution of random satisfiability problems, Science, vol.297, issue.5582, pp.812-815, 2002.

A. Braunstein, M. Mézard, and R. Zecchina, Survey propagation: An algorithm for satisfiability, Random Structures & Algorithms, vol.27, pp.201-226, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00008893

M. Yasuda, Y. Kabashima, and K. Tanaka, Replica plefka expansion of ising systems, Journal of Statistical Mechanics: Theory and Experiment, vol.2012, issue.04, p.4002, 2012.

J. De-almeida and D. J. Thouless, Stability of the sherrington-kirkpatrick solution of a spin glass model, Journal of Physics A: Mathematical and General, vol.11, issue.5, p.983, 1978.

J. Wright, A. Ganesh, S. Rao, Y. Peng, and Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization, Advances in neural information processing systems, pp.2080-2088, 2009.

E. J. Candès, X. Li, Y. Ma, and J. Wright, Robust principal component analysis?, Journal of the ACM (JACM), vol.58, issue.3, p.11, 2011.

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

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

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

L. Zdeborová and F. Krzakala, Generalization of the cavity method for adiabatic evolution of gibbs states, Physical Review B, vol.81, issue.22, p.224205, 2010.

G. Parisi, Infinite number of order parameters for spin-glasses, Physical Review Letters, vol.43, issue.23, p.1754, 1979.

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

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

Y. Deshpande and A. Montanari, Information-theoretically optimal sparse PCA, IEEE International Symposium on Information Theory (ISIT), pp.2197-2201, 2014.
DOI : 10.1109/isit.2014.6875223

URL : http://arxiv.org/pdf/1402.2238

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

Y. Deshpande, E. Abbe, and A. Montanari, Asymptotic mutual information for the binary stochastic block model, 2016 IEEE International Symposium on Information Theory (ISIT), pp.185-189, 2016.

J. Barbier, M. Dia, N. Macris, F. Krzakala, T. Lesieur et al., Mutual information for symmetric rankone 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

M. Lelarge and L. Miolane, Fundamental limits of symmetric low-rank matrix estimation, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01648368

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

A. E. Alaoui and F. Krzakala, Asymptotic mutual information for the binary stochastic block modelestimation in the spiked wigner model: A short proof of the replica formula, 2018 IEEE International Symposium on Information Theory (ISIT), 2018.

S. B. Korada and N. 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.

M. Mézard, Mean-field message-passing equations in the hopfield model and its generalizations, Phys. Rev. E, vol.95, p.22117, 2017.

M. Gabrié, E. W. Tramel, and F. Krzakala, Training restricted boltzmann machine via the thouless-andersonpalmer free energy, Advances in Neural Information Processing Systems, vol.28, pp.640-648, 2015.

E. W. Tramel, A. Manoel, F. Caltagirone, M. Gabrié, and F. Krzakala, Inferring sparsity: Compressed sensing using generalized restricted boltzmann machines, Information Theory Workshop (ITW), pp.265-269, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01416262

J. Tubiana and R. Monasson, Emergence of compositional representations in restricted boltzmann machines, Phys. Rev. Lett, vol.118, p.138301, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01555107

J. S. Yedidia, W. T. Freeman, and Y. Weiss, Understanding belief propagation and its generalizations, Exploring artificial intelligence in the new millennium, vol.8, pp.236-239, 2003.

T. Plefka, Convergence condition of the tap equation for the infinite-ranged ising spin glass model, Journal of Physics A: Mathematical and general, vol.15, issue.6, p.1971, 1982.

A. Georges and J. S. Yedidia, How to expand around mean-field theory using high-temperature expansions, Journal of Physics A: Mathematical and General, vol.24, issue.9, p.2173, 1991.
DOI : 10.1088/0305-4470/24/9/024

S. Rangan, P. Schniter, E. Riegler, A. K. Fletcher, and V. Cevher, Fixed points of generalized approximate message passing with arbitrary matrices, IEEE Transactions on Information Theory, vol.62, issue.12, pp.7464-7474, 2016.

J. Vila, P. Schniter, S. Rangan, F. Krzakala, and L. Zdeborová, Adaptive damping and mean removal for the generalized approximate message passing algorithm, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.2021-2025, 2015.
DOI : 10.1109/icassp.2015.7178325

URL : https://hal.archives-ouvertes.fr/cea-01140721

H. Nishimori and D. Sherrington, Absence of replica symmetry breaking in a region of the phase diagram of the ising spin glass, AIP Conference Proceedings, vol.553, pp.67-72, 2001.

M. Mézard and G. Parisi, The bethe lattice spin glass revisited, The European Physical Journal B-Condensed Matter and Complex Systems, vol.20, issue.2, pp.217-233, 2001.

M. Mézard and G. Parisi, The cavity method at zero temperature, Journal of Statistical Physics, vol.111, issue.1-2, pp.1-34, 2003.

R. Monasson, Structural glass transition and the entropy of the metastable states, Phys. Rev. Lett, vol.75, pp.2847-2850, 1995.

P. Charbonneau, J. Kurchan, G. Parisi, P. Urbani, and F. Zamponi, Glass and jamming transitions: From exact results to finite-dimensional descriptions, Annual Review of Condensed Matter Physics, vol.8, pp.265-288, 2017.
DOI : 10.1146/annurev-conmatphys-031016-025334

URL : https://hal.archives-ouvertes.fr/cea-01464295

P. Charbonneau, J. Kurchan, G. Parisi, P. Urbani, and F. Zamponi, Fractal free energies in structural glasses, Nature Communications, vol.5, p.3725, 2014.
DOI : 10.1038/ncomms4725

URL : https://www.nature.com/articles/ncomms4725.pdf

P. Charbonneau, J. Kurchan, G. Parisi, P. Urbani, and F. Zamponi, Exact theory of dense amorphous hard spheres in high dimension. iii. the full replica symmetry breaking solution, J. Stat. Mech.: Theor. Exp, vol.2014, issue.10, p.10009, 2014.
URL : https://hal.archives-ouvertes.fr/cea-01464503

H. Sommers and W. Dupont, Distribution of frozen fields in the mean-field theory of spin glasses, Journal of Physics C: Solid State Physics, vol.17, issue.32, p.5785, 1984.

A. Montanari and F. Ricci-tersenghi, On the nature of the low-temperature phase in discontinuous mean-field spin glasses, Eur. Phys. J. B, vol.33, issue.3, pp.339-346, 2003.

A. Montanari, G. Parisi, and F. Ricci-tersenghi, Instability of one-step replica-symmetry-broken phase in satisfiability problems, Journal of Physics A: Mathematical and General, vol.37, issue.6, p.2073, 2004.
URL : https://hal.archives-ouvertes.fr/hal-00008647

F. Krzakala, A. Pagnani, and M. Weigt, Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs, Phys. Rev. E, vol.70, p.46705, 2004.

S. Mertens, M. Mézard, and R. Zecchina, Threshold values of random ksat from the cavity method, Random Structures & Algorithms, vol.28, issue.3, pp.340-373, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00023254