The DOI matches its Crossref record; 256 of the 256 references it cites were found in a registry or an index.
Statistical physics of inference: thresholds and algorithms
Open accessAbstract
Many questions of fundamental interest in today's science can be formulated as inference problems: some partial, or noisy, observations are performed over a set of variables and the goal is to recover, or infer, the values of the variables based on the indirect information contained in the measurements. For such problems, the central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? A growing body of work has shown that often we can understand and locate these fundamental barriers by thinking of them as phase transitions in the sense of statistical physics. Moreover, it turned out that we can use the gained physical insight to develop new promising algorithms. The connection between inference and statistical physics is currently witnessing an impressive renaissance and we review here the current state-of-the-art, with a pedagogical focus on the Ising model which, formulated as an inference problem, we call the planted spin glass. In terms of applications we review two classes of problems: (i) inference of clusters on graphs and networks, with community detection as a special case and (ii) estimating a signal from its noisy linear measurements, with compressed sensing as a case of sparse estimation. Our goal is to provide a pedagogical review for researchers in physics and other fields interested in this fascinating topic.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Items 201–256 of 256
The Random First‐Order Transition Theory of Glasses: A Critical Assessment
Biroli, G., & Bouchaud, J. (2012) · Wiley eBooks · doi:10.1002/9781118202470.ch2 · Cited by 100
The dynamics of message passing on dense graphs, with applications to compressed sensing
Bayati, M., & Andrea Montanari, A. (2010) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2010.5513529 · Cited by 92
Statistical physics of hard optimization problems
Zdeborová, L. (2009) · Acta Physica Slovaca Reviews and Tutorials · doi:10.2478/v10155-010-0096-6 · Cited by 89
Self-citationOpper, M., & Winther, O. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.3695 · Cited by 87
The cavity method at zero temperaturePreprint
Mézard, M., & Giorgio Parisi, A. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.cond-mat/0207121 · Cited by 80
Iterative estimation of constrained rank-one matrices in noise
Rangan, S., & Fletcher, A. K. (2012) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2012.6283056 · Cited by 78
Generalization of the cavity method for adiabatic evolution of Gibbs states
Zdeborová, L., & Krząkała, F. (2010) · Physical Review B · doi:10.1103/physrevb.81.224205 · Cited by 78
Self-citationGaussian belief propagation solver for systems of linear equations
Shental, O., Siegel, P. H., Wolf, J. K., Bickson, D., & Dolev, D. (2008) · Cited by 77
Cavity approach to the spectral density of non-Hermitian sparse matrices
Rogers, T., & Castillo, I. P. (2009) · Physical Review E · doi:10.1103/physreve.79.012101 · Cited by 75
Statistical Mechanics of Compressed Sensing
Ganguli, S., & Sompolinsky, H. (2010) · Physical Review Letters · doi:10.1103/physrevlett.104.188701 · Cited by 74
Tight Lower Bound for Percolation Threshold on an Infinite Graph
Hamilton, K. E., & Pryadko, L. P. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.208701 · Cited by 73
The Nishimori line and Bayesian StatisticsPreprint
Iba, Y. (n.d.) · Cited by 71
Watkin, T. L. H., & Nadal, J. (1994) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/27/6/016 · Cited by 69
Phase transitions in semisupervised clustering of sparse networks
Zhang, P., Moore, C., & Zdeborová, L. (2014) · Physical Review E · doi:10.1103/physreve.90.052802 · Cited by 68
Self-citationRangan, S., Fletcher, A. K., Schniter, P., & Kamilov, U. S. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2619373 · Cited by 68
Phase Transitions in Sparse PCAPreprint
Lesieur, T., Krząkała, F., & Zdeborová, L. (2015) · HAL · Cited by 66
Self-citationEstimating random variables from random sparse observations
Andrea Montanari, A. (2008) · European Transactions on Telecommunications · doi:10.1002/ett.1289 · Cited by 60
Warmuth, W. (1977) · Biometrical Journal · doi:10.1002/bimj.4710190515 · Cited by 58
Numerical detection of the Gardner transition in a mean-field glass former
Charbonneau, P., Jin, Y., Giorgio Parisi, A., Rainone, C., Seoane, B., & Zamponi, F. (2015) · Physical Review E · doi:10.1103/physreve.92.012316 · Cited by 55
Following Gibbs states adiabatically —The energy landscape of mean-field glassy systems
Krząkała, F., & Zdeborová, L. (2010) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/90/66002 · Cited by 55
Self-citationQuiet Planting in the Locked Constraint Satisfaction Problems
Zdeborová, L., & Krząkała, F. (2011) · SIAM Journal on Discrete Mathematics · doi:10.1137/090750755 · Cited by 54
Self-citationOn the Complexity of Random Satisfiability Problems with Planted Solutions
Feldman, V., Perkins, W., & Vempala, S. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746577 · Cited by 51
Carlson, J. M., Chayes, J., Chayes, L., Sethna, J. P., & Thouless, D. J. (1990) · Journal of Statistical Physics · doi:10.1007/bf01014364 · Cited by 50
Community detection in networks with unequal groups
Zhang, P., Moore, C., & Newman, M. E. J. (2016) · Physical review. E · doi:10.1103/physreve.93.012303 · Cited by 49
Kabashima, Y. (2012) · Cited by 49
Statistical mechanics of unsupervised structure recognition
Biehl, M. L., & Mietzner, A. (1994) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/27/6/015 · Cited by 48
Signal recovery using expectation consistent approximation for linear observations
Kabashima, Y., & Vehkaperä, M. (2014) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2014.6874828 · Cited by 44
Finding Planted Partitions in Random Graphs with General Degree Distributions
Coja‐Oghlan, A., & Lanka, A. (2009) · SIAM Journal on Discrete Mathematics · doi:10.1137/070699354 · Cited by 44
Phase diagram and approximate message passing for blind calibration and dictionary learning
Krząkała, F., Mézard, M., & Zdeborová, L. (2013) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2013.6620308 · Cited by 42
Self-citationAutomorphic Forms and Geometry of Arithmetic Varieties
(1989) · Advanced studies in pure mathematics · doi:10.2969/aspm/01510000 · Cited by 41
Replica analysis and approximate message passing decoder for superposition codes
Barbier, J., & Krząkała, F. (2014) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2014.6875082 · Cited by 40
Asymptotic Analysis of MAP Estimation via the Replica Method and Compressed Sensing
Rangan, S., Goyal, V. K., & Fletcher, A. K. (2009) · neural information processing systems · Cited by 40
Approximate message passing with restricted Boltzmann machine priors
Tramel, E. W., Drémeau, A., & Krząkała, F. (2016) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2016/07/073401 · Cited by 39
A conjecture on the maximum cut and bisection width in random regular graphs
Zdeborová, L., & Boettcher, S. (2010) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2010/02/p02020 · Cited by 38
Self-citationCastellani, T., Krząkała, F., & Ricci‐Tersenghi, F. (2005) · The European Physical Journal B · doi:10.1140/epjb/e2005-00293-1 · Cited by 38
Ising spin glass at zero temperature on the Bethe lattice
Kwon, C., & Thouless, D. J. (1988) · Physical review. B, Condensed matter · doi:10.1103/physrevb.37.7649 · Cited by 33
On melting dynamics and the glass transition. II. Glassy dynamics as a melting process
Krząkała, F., & Zdeborová, L. (2011) · The Journal of Chemical Physics · doi:10.1063/1.3506843 · Cited by 33
Self-citationPropagating Beliefs in Spin-Glass Models
KABASHIMA, Y. (2003) · Journal of the Physical Society of Japan · doi:10.1143/jpsj.72.1645 · Cited by 32
Comparative Study for Inference of Hidden Classes in Stochastic Block ModelsPreprint
Zhang, P., & Krząkała, F. (n.d.) · Cited by 30
Assessing node risk and vulnerability in epidemics on networks
Rogers, T. (2015) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/109/28005 · Cited by 29
Belief-propagation reconstruction for discrete tomography
Gouillart, E., Krząkała, F., Mézard, M., & Zdeborová, L. (2013) · Inverse Problems · doi:10.1088/0266-5611/29/3/035003 · Cited by 27
Self-citationNeural Reconstruction with Approximate Message Passing (NeuRAMP)
Fletcher, A. K., Rangan, S., Varshney, L. R., & Bhargava, A. (2011) · Cited by 27
Random matrices, nonbacktracking walks, and orthogonal polynomials
Sodin, S. (2007) · Journal of Mathematical Physics · doi:10.1063/1.2819599 · Cited by 26
Comparative study for inference of hidden classes in stochastic block models
Zhang, P., Krząkała, F., Reichardt, J., & Zdeborová, L. (2012) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2012/12/p12021 · Cited by 26
Self-citationBinary Linear Classification and Feature Selection via Generalized Approximate Message Passing
Ziniel, J., Schniter, P., & Sederberg, P. B. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2407311 · Cited by 25
On melting dynamics and the glass transition. I. Glassy aspects of melting dynamics
Krząkała, F., & Zdeborová, L. (2011) · The Journal of Chemical Physics · doi:10.1063/1.3506841 · Cited by 24
Self-citationQuasi-equilibrium in glassy dynamics: an algebraic view
Franz, S., & Giorgio Parisi, A. (2013) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2013/02/p02003 · Cited by 23
Dynamical critical exponents for the mean-field Potts glass
Caltagirone, F., Giorgio Parisi, A., & Rizzo, T. (2012) · Physical Review E · doi:10.1103/physreve.85.051504 · Cited by 22
Carlson, J. M., Chayes, J., Sethna, J. P., & Thouless, D. J. (1990) · Journal of Statistical Physics · doi:10.1007/bf01014365 · Cited by 21
Belief Propagation Reconstruction for Discrete Tomography
Gouillart, E., Krząkała, F., Mézard, M., & Zdeborová, L. (2012) · Cited by 21
Self-citationThouless-Anderson-Palmer equations for neural networks
Shamir, M., & Sompolinsky, H. (2000) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.61.1839 · Cited by 19
Following states in temperature in the sphericals+p-spin glass model
Sun, Y., Crisanti, A., Krząkała, F., Leuzzi, L., & Zdeborová, L. (2012) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2012/07/p07002 · Cited by 17
Self-citationNonbacktracking operator for the Ising model and its applications in systems with multiple states
Zhang, P. (2015) · Physical Review E · doi:10.1103/physreve.91.042120 · Cited by 13
Validity Estimates for Loopy Belief Propagation on Binary Real-world Networks
Mooij, J. M., & Kappen, H. J. (2004) · Radboud Repository (Radboud University) · Cited by 11
Matrix Completion from Fewer Entries: Spectral Detectability and Rank EstimationPreprint
Saade, A., Krząkała, F., & Zdeborová, L. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.03498 · Cited by 10
Self-citationEffect of quantum fluctuations on the coloring of random graphs
Bapst, V., Semerjian, G., & Zamponi, F. (2013) · Physical Review A · doi:10.1103/physreva.87.042322 · Cited by 3
Cited by
Machine learning and the physical sciences
Carleo, G., Cirac, I., Cranmer, K., Daudet, L., Schuld, M., Tishby, N., Vogt-Maranto, L., & Zdeborová, L. (2019) · Reviews of Modern Physics · doi:10.1103/revmodphys.91.045002 · Cited by 2,417
Self-citationA high-bias, low-variance introduction to Machine Learning for physicists
Mehta, P., Bukov, M., Wang, C.-H., Day, A. G. R., Richardson, C., Fisher, C. K., & Schwab, D. J. (2019) · Physics Reports · doi:10.1016/j.physrep.2019.03.001 · Cited by 920
Plug-and-Play Methods for Magnetic Resonance Imaging: Using Denoisers for Image Recovery
Ahmad, R., Bouman, C. A., Buzzard, G. T., Chan, S., Liu, S., Reehorst, E. T., & Schniter, P. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2019.2949470 · Cited by 261
Inverse statistical problems: from the inverse Ising problem to data science
Nguyen, H. C., Zecchina, R., & Berg, J. (2017) · Advances in Physics · doi:10.1080/00018732.2017.1341604 · Cited by 258
Spectral Entropies as Information-Theoretic Tools for Complex Network Comparison
De Domenico, M., & Biamonte, J. (2016) · Physical Review X · doi:10.1103/physrevx.6.041062 · Cited by 160
Metadata
- Authors
- Zdeborová, L., & Krzakala, F.
- Venue
- Advances in Physics
- Publisher
- Informa UK Limited
- Published
- 2016-08-19
- Volume
- 65
- Issue
- 5
- Pages
- 453-552
- ISSN
- 0001-8732 (ISSN-L)
- 1460-6976
- OpenAlex
- W2151781750
- Cited by
- 440
- References
- 256
- FWCI
- 21.50
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.