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

J. Baik, G. B. Arous, and S. Péché, Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices, The Annals of Probability, vol.33, issue.5, pp.1643-1697, 2005.

J. Banks, C. Moore, R. Vershynin, and J. Xu, Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization, 2016.

J. Barbier, M. Dia, N. Macris, and F. Krzakala, Thibault Lesieur, and Lenka Zdeborov'a. Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula, Advances In Neural Information Processing Systems, pp.424-432, 2016.

N. Barkai and H. Sompolinsky, Statistical mechanics of the maximum-likelihood density estimation, Physical Review E, vol.50, issue.3, p.1766, 1994.

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.

Q. Berthet and P. Rigollet, Computational lower bounds for sparse PCA. arXiv preprint, 2013.

M. Biehl and A. Mietzner, Statistical mechanics of unsupervised structure recognition, Journal of Physics A: Mathematical and General, vol.27, issue.6, p.1885, 1994.

F. Caltagirone, L. Zdeborová, and F. Krzakala, On convergence of approximate message passing, 2014 IEEE International Symposium on Information Theory, pp.1812-1816, 2014.

Y. Cheng, M. George, and . Church, Biclustering of expression data, Ismb, pp.93-103, 2000.

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.

A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Inference and Phase Transitions in the Detection of Modules in Sparse Networks, Physical Review Letters, vol.107, issue.6, p.65701, 2011.

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.

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 and A. Montanari, Finding Hidden Cliques of Size $$\sqrt{N/e}$$ N / e in Nearly Linear Time, Foundations of Computational Mathematics, vol.15, issue.4, pp.1-60, 2015.

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

C. Eckart and G. Young, The approximation of one matrix by another of lower rank, Psychometrika, vol.1, issue.3, pp.211-218, 1936.
DOI : 10.1007/BF02288367

S. Fortunato, Community detection in graphs, Physics Reports, vol.486, issue.3-5, pp.75-174, 2010.

M. Gabrié, W. Eric, F. Tramel, and . Krzakala, Training restricted Boltzmann machine via the Thouless-Anderson- Palmer free energy, Advances in Neural Information Processing Systems, pp.640-648, 2015.

A. Georges and J. 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.

D. J. Gross, I. Kanter, and H. Sompolinsky, Mean-field theory of the Potts glass, Physical Review Letters, vol.55, issue.3, pp.304-307, 1985.

T. Hastie, R. Tibshirani, J. Friedman, and J. Franklin, The elements of statistical learning: data mining, inference and prediction. The Mathematical Intelligencer, pp.83-85, 2005.

G. Hinton, A Practical Guide to Training Restricted Boltzmann Machines, Momentum, vol.79, issue.7, p.926, 2010.

E. Geoffrey, S. Hinton, Y. Osindero, and . Teh, A fast learning algorithm for deep belief nets, Neural computation, vol.18, issue.7, pp.1527-1554, 2006.

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

C. David, M. Hoyle, and . Rattray, Principal-component-analysis eigenvalue spectra from data with symmetry-breaking structure, Physical Review E, vol.69, issue.2, p.26124, 2004.

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

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

Y. Kabashima, F. Krzakala, M. Mézard, A. Sakata, and L. Zdeborová, Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization, IEEE Transactions on Information Theory, vol.62, issue.7, pp.4228-4265, 2016.

J. Hilbert, F. Kappen, and . Rodriguez, Boltzmann machine learning using mean field theory and linear response correction Advances in neural information processing systems, pp.280-286, 1998.

J. Kosterlitz, R. C. Thouless, and . Jones, Spherical Model of a Spin-Glass, Physical Review Letters, vol.36, issue.20, p.1217, 1976.

R. Krauthgamer, B. Nadler, and D. Vilenchik, Do semidefinite relaxations solve sparse PCA up to the information limit? The Annals of Statistics, pp.1300-1322, 2015.

F. Krzakala, A. Manoel, W. Eric, L. Tramel, and . Zdeborová, Variational free energies for compressed sensing, 2014 IEEE International Symposium on Information Theory, pp.1499-1503, 2014.

F. Krzakala, M. Mézard, and L. Zdeborová, Phase diagram and approximate message passing for blind calibration and dictionary learning, 2013 IEEE International Symposium on Information Theory, pp.659-663, 2013.

F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly et al., Spectral redemption in clustering sparse networks, Proceedings of the National Academy of Sciences, vol.110, issue.52, pp.20935-20940, 2013.

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

Y. Lecun, Y. Bengio, and G. Hinton, Deep learning, Nature, vol.9, issue.7553, pp.436-444, 2015.

T. Lesieur, C. D. Bacco, J. Banks, F. Krzakala, C. Moore et al., Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering, 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2016.

T. Lesieur, F. Krzakala, and L. Zdeborová, MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel, 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.680-687, 2015.

T. Lesieur, F. Krzakala, and L. Zdeborová, Phase transitions in sparse PCA, 2015 IEEE International Symposium on Information Theory (ISIT), pp.1635-1639, 2015.

S. Lloyd, Least squares quantization in PCM, IEEE Transactions on Information Theory, vol.28, issue.2, pp.129-137, 1982.

C. Sara, . Madeira, L. Arlindo, and . Oliveira, Biclustering algorithms for biological data analysis: a survey, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), vol.1, issue.1, pp.24-45, 2004.

M. Léo-miolane and . Lelarge, Fundamental limits of symmetric low-rank matrix estimation, 2016.

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

M. Mézard, G. Parisi, and M. A. Virasoro, Spin-Glass Theory and Beyond, Lecture Notes in Physics. World Scientific, vol.9, 1987.

M. Mézard, Mean-field message-passing equations in the Hopfield model and its generalizations. arXiv preprint, 2016.

R. Monasson and D. Villamaina, Estimating the principal components of correlation matrices from all their empirical eigenvectors, EPL (Europhysics Letters), vol.112, issue.5, p.50001, 2015.

A. Montanari, Finding One Community in a Sparse Graph, Journal of Statistical Physics, vol.92, issue.4, pp.273-299, 2015.

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

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, pp.67-72, 2001.
DOI : 10.1063/1.1358165

T. Jason, P. Parker, V. Schniter, and . Cevher, Bilinear generalized approximate message passing part I: Derivation, IEEE Transactions on Signal Processing, vol.62, issue.22, pp.5839-5853, 2014.

L. Parsons, E. Haque, and H. Liu, Subspace clustering for high dimensional data, ACM SIGKDD Explorations Newsletter, vol.6, issue.1, pp.90-105, 2004.

A. Perry, S. Alexander, . Wein, S. Afonso, A. Bandeira et al., Message-passing algorithms for synchronization problems over compact groups, 2016.

A. Perry, S. Alexander, . Wein, S. Afonso, A. Bandeira et al., Optimality and sub-optimality of PCA for spiked random matrices and synchronization. arXiv preprint, 2016.

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.

S. Rangan, Estimation with random linear mixing, belief propagation and compressed sensing, 2010 44th Annual Conference on Information Sciences and Systems (CISS), pp.1-6, 2010.

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

P. Sundeep-rangan, E. Schniter, A. Riegler, V. Fletcher, and . Cevher, Fixed points of generalized approximate message passing with arbitrary matrices, IEEE International Symposium on Information Theory Proceedings (ISIT), pp.664-668, 2013.

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

D. Sherrington and S. Kirkpatrick, Solvable Model of a Spin-Glass, Physical Review Letters, vol.35, issue.26, pp.1792-1796, 1975.

H. Sommers, Theory of a Heisenberg spin glass, Journal of Magnetism and Magnetic Materials, vol.22, issue.3, pp.267-270, 1981.

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.

W. Eric, A. Tramel, F. Manoel, M. Caltagirone, F. Gabrié et al., Inferring sparsity: Compressed sensing using generalized restricted Boltzmann machines, IEEE Information Theory Workshop (ITW), pp.265-269, 2016.

J. Tubiana and R. Monasson, Emergence of compositional representations in restricted Boltzmann machines. arXiv preprint, 2016.

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

L. Wasserman, All of statistics: a concise course in statistical inference, 2013.

T. Watkin and J. Nadal, Optimal unsupervised learning, Journal of Physics A: Mathematical and General, vol.27, issue.6, p.1899, 1994.

J. S. Yedidia, W. T. Freeman, and Y. Weiss, Exploring artificial intelligence in the new millennium. chapter Understanding Belief Propagation and Its Generalizations, pp.239-269, 2003.

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

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.