Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We consider an Ising model in which the spins are coupled by infinite-ranged random interactions independently distributed with a Gaussian probability density. Both "spinglass" and ferromagnetic phases occur. The competition between the phases and the type of order present in each are studied. <s> BIB001 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> Abstract The Sherrmgton-Kirkpatrick model of a spin glass is solved by a mean field technique which is probably exact in the limit of infinite range interactions. At and above T c the solution is identical to that obtained by Sherrington and Kirkpatrick (1975) using the n → O replica method, but below T c the new result exhibits several differences and remains physical down to T = 0. <s> BIB002 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> This Letter shows that in the mean-field approximation spin-glasses must be described by an infinite number of order parameters in the framework of the replica theory. <s> BIB003 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> This book contains a detailed and self-contained presentation of the replica theory of infinite range spin glasses. The authors also explain recent theoretical developments, paying particular attention to new applications in the study of optimization theory and neural networks. About two-thirds of the book are a collection of the most interesting and pedagogical articles on the subject. <s> BIB004 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We consider a gauge symmetric version of the p-spin glass model on a complete graph. The gauge symmetry guarantees the absence of replica symmetry breaking and allows to fully use the interpolation scheme of Guerra to rigorously compute the free energy. In the case of pairwise interactions (p = 2), where we have a gauge symmetric version of the Sherrington- Kirkpatrick model, we get the free energy and magnetization for all values of external parameters. Our analysis also works for even p ≥ 4 except in a range of parameters surrounding the phase transition line, and for odd p ≥ 3 in a more restricted region. We also obtain concentration estimates for the magnetization and overlap parameter that play a crucial role in the proofs for odd p and justify the absence of replica symmetry breaking. Our initial motivation for considering this model came from problems related to communication over a noisy channel, and is briefly explained. <s> BIB005 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> Compressed sensing aims to undersample certain high-dimensional signals, yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity-undersampling tradeoff is achieved when reconstructing by convex optimization -- which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alternatives to convex optimization for large-scale problems. Unfortunately known fast algorithms offer substantially worse sparsity-undersampling tradeoffs than convex optimization. We introduce a simple costless modification to iterative thresholding making the sparsity-undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity-undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity-undersampling tradeoff. There is a surprising agreement between earlier calculations based on random convex polytopes and this new, apparently very different theoretical formalism. <s> BIB006 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> “Approximate message passing” (AMP) algorithms have proved to be effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper, we provide rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed Gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with a large number of short cycles in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory. <s> BIB007 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We propose an iterative scheme for the solutions of the TAP-equations in the Sherrington–Kirkpatrick model which is shown to converge up to and including the de Almeida–Thouless line. The main tool is a representation of the iterations which reveals an interesting structure of them. This representation does not depend on the temperature parameter, but for temperatures below the de Almeida–Thouless line, it contains a part which does not converge to zero in the limit. <s> BIB008 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We consider the problem of estimating a rank-one matrix in Gaussian noise under a probabilistic model for the left and right factors of the matrix. The probabilistic model can impose constraints on the factors including sparsity and positivity that arise commonly in learning problems. We propose a simple iterative procedure that reduces the problem to a sequence of scalar estimation computations. The method is similar to approximate message passing techniques based on Gaussian approximations of loopy belief propagation that have been used recently in compressed sensing. Leveraging analysis methods by Bayati and Montanari, we show that the asymptotic behavior of the estimates from the proposed iterative procedure is described by a simple scalar equivalent model, where the distribution of the estimates is identical to certain scalar estimates of the variables in Gaussian noise. Moreover, the effective Gaussian noise level is described by a set of state evolution equations. The proposed method thus provides a computationally simple and general method for rank-one estimation problems with a precise analysis in certain high-dimensional settings. <s> BIB009 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We consider a class of approximated message passing (AMP) algorithms and characterize their high-dimensional behavior in terms of a suitable state evolution recursion. Our proof applies to Gaussian matrices with independent but not necessarily identically distributed entries. It covers --in particular-- the analysis of generalized AMP, introduced by Rangan, and of AMP reconstruction in compressed sensing with spatially coupled sensing matrices. The proof technique builds on the one of [BM11], while simplifying and generalizing several steps. <s> BIB010 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> The replica extension theory has been developed for the purpose of investigating spin glass systems in the replica symmetry breaking phase. The replica extension theory is a replica theory for a specific sample and has the scheme of the one-step replica symmetry breaking ansatz. In this paper, using the Plefka expansion, we propose the perturbative expansion of Gibbs free energies of Ising systems with the replica extension theory, and we derive the explicit form of the second-?and third-order approximations. Our Plefka expansion systematically provides perturbative approximations taking the one-step replica symmetry breaking into account. In some numerical experiments, we show that our perturbative approximations are quantitatively superior to conventional perturbative approximations that do not take the one-step replica symmetry breaking into account in the spin glass phase. <s> BIB011 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We study the problem of reconstructing low-rank matrices from their noisy observations. We formulate the problem in the Bayesian framework, which allows us to exploit structural properties of matrices in addition to low-rankedness, such as sparsity. We propose an efficient approximate message passing algorithm, derived from the belief propagation algorithm, to perform the Bayesian inference for matrix reconstruction. We have also successfully applied the proposed algorithm to a clustering problem, by reformulating it as a low-rank matrix reconstruction problem with an additional structural property. Numerical experiments show that the proposed algorithm outperforms Lloyd's K-means algorithm. <s> BIB012 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> Sparse Principal Component Analysis (PCA) is a dimensionality reduction technique wherein one seeks a low-rank representation of a data matrix with additional sparsity constraints on the obtained representation. We consider two probabilistic formulations of sparse PCA: a spiked Wigner and spiked Wishart (or spiked covariance) model. We analyze an Approximate Message Passing (AMP) algorithm to estimate the underlying signal and show, in the high dimensional limit, that the AMP estimates are information-theoretically optimal. As an immediate corollary, our results demonstrate that the posterior expectation of the underlying signal, which is often intractable to compute, can be obtained using a polynomial-time scheme. Our results also effectively provide a single-letter characterization of the sparse PCA problem. <s> BIB013 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> Many questions of fundamental interest in todays 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. 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. <s> BIB014 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> This paper considers probabilistic estimation of a low-rank matrix from non-linear element-wise measurements of its elements. We derive the corresponding approximate message passing (AMP) algorithm and its state evolution. Relying on non-rigorous but standard assumptions motivated by statistical physics, we characterize the minimum mean squared error (MMSE) achievable information theoretically and with the AMP algorithm. Unlike in related problems of linear estimation, in the present setting the MMSE depends on the output channel only trough a single parameter - its Fisher information. We illustrate this striking finding by analysis of submatrix localization, and of detection of communities hidden in a dense stochastic block model. For this example we locate the computational and statistical boundaries that are not equal for rank larger than four. <s> BIB015 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We study optimal estimation for sparse principal component analysis when the number of non-zero elements is small but on the same order as the dimension of the data. We employ approximate message passing (AMP) algorithm and its state evolution to analyze what is the information theoretically minimal mean-squared error and the one achieved by AMP in the limit of large sizes. For a special case of rank one and large enough density of non-zeros Deshpande and Montanari [1] proved that AMP is asymptotically optimal. We show that both for low density and for large rank the problem undergoes a series of phase transitions suggesting existence of a region of parameters where estimation is information theoretically possible, but AMP (and presumably every other polynomial algorithm) fails. The analysis of the large rank limit is particularly instructive. <s> BIB016 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We develop an information-theoretic view of the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph G from such a model is generated by first assigning vertex labels at random from a finite alphabet, and then connecting vertices with edge probabilities depending on the labels of the endpoints. In the case of the symmetric two-group model, we establish an explicit ‘single-letter’ characterization of the per-vertex mutual information between the vertex labels and the graph, when the graph average degree diverges. The explicit expression of the mutual information is intimately related to estimation-theoretic quantities, and -in particular- reveals a phase transition at the critical point for community detection. Below the critical point the per-vertex mutual information is asymptotically the same as if edges were independent of the vertex labels. Correspondingly, no algorithm can estimate the partition better than random guessing. Conversely, above the threshold, the per-vertex mutual information is strictly smaller than the independent-edges upper bound. In this regime there exists a procedure that estimates the vertex labels better than random guessing. <s> BIB017 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We consider the estimation of a n-dimensional vector x from the knowledge of noisy and possibility non-linear element-wise measurements of xxT , a very generic problem that contains, e.g. stochastic 2-block model, submatrix localization or the spike perturbation of random matrices. We use an interpolation method proposed by Guerra and later refined by Korada and Macris. We prove that the Bethe mutual information (related to the Bethe free energy and conjectured to be exact by Lesieur et al. on the basis of the non-rigorous cavity method) always yields an upper bound to the exact mutual information. We also provide a lower bound using a similar technique. For concreteness, we illustrate our findings on the sparse PCA problem, and observe that (a) our bounds match for a large region of parameters and (b) that it exists a phase transition in a region where the spectum remains uninformative. While we present only the case of rank-one symmetric matrix estimation, our proof technique is readily extendable to low-rank symmetric matrix or low-rank symmetric tensor estimation <s> BIB018 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> Factorizing low-rank matrices has many applications in machine learning and statistics. For probabilistic models in the Bayes optimal setting, a general expression for the mutual information has been proposed using heuristic statistical physics computations, and proven in few specific cases. Here, we show how to rigorously prove the conjectured formula for the symmetric rank-one case. This allows to express the minimal mean-square-error and to characterize the detectability phase transitions in a large set of estimation problems ranging from community detection to sparse PCA. We also show that for a large set of parameters, an iterative algorithm called approximate message-passing is Bayes optimal. There exists, however, a gap between what currently known polynomial algorithms can do and what is expected information theoretically. Additionally, the proof technique has an interest of its own and exploits three essential ingredients: the interpolation method introduced in statistical physics by Guerra, the analysis of the approximate message-passing algorithm and the theory of spatial coupling and threshold saturation in coding. Our approach is generic and applicable to other open problems in statistical estimation where heuristic statistical physics predictions are available. <s> BIB019 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> We consider the high-dimensional inference problem where the signal is a low-rank symmetric matrix which is corrupted by an additive Gaussian noise. Given a probabilistic model for the low-rank matrix, we compute the limit in the large dimension setting for the mutual information between the signal and the observations, as well as the matrix minimum mean squared error, while the rank of the signal remains constant. We also show that our model extends beyond the particular case of additive Gaussian noise and we prove an universality result connecting the community detection problem to our Gaussian framework. We unify and generalize a number of recent works on PCA, sparse PCA, submatrix localization or community detection by computing the information-theoretic limits for these problems in the high noise regime. In addition, we show that the posterior distribution of the signal given the observations is characterized by a parameter of the same dimension as the square of the rank of the signal (i.e. scalar in the case of rank one). This allows to locate precisely the information-theoretic thresholds for the above mentioned problems. Finally, we connect our work with the hard but detectable conjecture in statistical physics. <s> BIB020 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> In recent years important progress has been achieved towards proving the validity of the replica predictions for the (asymptotic) mutual information (or"free energy") in Bayesian inference problems. The proof techniques that have emerged appear to be quite general, despite they have been worked out on a case-by-case basis. Unfortunately, a common point between all these schemes is their relatively high level of technicality. We present a new proof scheme that is quite straightforward with respect to the previous ones. We call it the stochastic interpolation method because it can be seen as an extension of the interpolation method developped by Guerra and Toninelli in the context of spin glasses, with a trial"parameter"which becomes a stochastic process. In order to illustrate our method we show how to prove the replica formula for three non-trivial inference problems. The first one is symmetric rank-one matrix estimation (or factorisation), which is the simplest problem considered here and the one for which the method is presented in full details. Then we generalize to symmetric tensor estimation and random linear estimation. In addition, we show how to prove a tight lower bound for the mutual information of non-symmetric tensor estimation. We believe that the present method has a much wider range of applicability and also sheds new insights on the reasons for the validity of replica formulas in Bayesian inference. <s> BIB021 </s> Approximate Survey Propagation for Statistical Inference <s> C. Ferromagnetically biased SK model and related work <s> This article is an extended version of previous work of the authors [40, 41] on low-rank matrix estimation in the presence of constraints on the factors into which the matrix is factorized. Low-rank matrix factorization is one of the basic methods used in data analysis for unsupervised learning of relevant features and other types of dimensionality reduction. We present a framework to study the constrained low-rank matrix estimation for a general prior on the factors, and a general output channel through which the matrix is observed. We draw a paralel with the study of vector-spin glass models - presenting a unifying way to study a number of problems considered previously in separate statistical physics works. We present a number of applications for the problem in data analysis. We derive in detail a general form of the low-rank approximate message passing (Low- RAMP) algorithm, that is known in statistical physics as the TAP equations. We thus unify the derivation of the TAP equations for models as different as the Sherrington-Kirkpatrick model, the restricted Boltzmann machine, the Hopfield model or vector (xy, Heisenberg and other) spin glasses. The state evolution of the Low-RAMP algorithm is also derived, and is equivalent to the replica symmetric solution for the large class of vector-spin glass models. In the section devoted to result we study in detail phase diagrams and phase transitions for the Bayes-optimal inference in low-rank matrix estimation. We present a typology of phase transitions and their relation to performance of algorithms such as the Low-RAMP or commonly used spectral methods. <s> BIB022
The numerical and example section of this paper will focus on one of the simplest cases of of rank-one r 0 = r = 1 estimation with binary signal, i.e. In physics language such a prior corresponds to the Ising spins and the Boltzmann measure (2) is then the one of a Sherrington-Kirkpatrick (SK) model BIB001 with interaction matrix Y ij . After a gauge transformation j this is equivalent to the SK model at temperature ∆ with random iid interactions of mean 1/N and variance ∆ 0 /N (see for instance the discussion in Sec. II.B of BIB014 or Sec. II.F of  ). This variant of the SK model with ferromagnetically biased interactions is very well known in the statistical physics literature. The original paper BIB001 presents the replica symmetric phase diagram of this model,  computes the AT line below which the replica symmetry is broken and Parisi famously presents the exact solution of this model below the AT line in BIB003 . A rather complete account for the physical properties of this model is reviewed in BIB004 . Note that while the replica solution and phase diagram of this model is very well known in the physics literature, the algorithmic interpretation of the phase diagram in terms of the AMP algorithm is recent. It is due to Bolthausen BIB008 who noticed that in order for the TAP equations BIB002 to converge and to reproduce the features of the well known phase diagram, one needs to adjust the iteration indices in the TAP equations. We will call the TAP equations with adjusted time indices the AMP algorithm. Bolthausen proved that in the Sherrington-Kirkpatrick model the AMP algorithm converges if and only if above the de Almeida-Thouless (AT) line  . The work of Bolthausen together with the development of AMP for sparse linear estimation and compressed sensing BIB006 revived the interest in the algorithmic aspects of dense spin glasses. For a review of the recent progress see e.g. BIB014 . AMP for low-rank matrix estimation was studied e.g. in BIB015 BIB009 BIB012 BIB013 BIB016 BIB017 , its rigorous asymptotic analysis called the state evolution in BIB007 BIB010 BIB009 BIB017 . Correctness of the replica theory in the Bayes-optimal setting was proven rigorously in a sequence of work BIB018 BIB013 BIB017 BIB019 BIB020 BIB021  . While the first complete proof is due to BIB018 , the Ising case discussed here is equivalent the Gauge-Symmetric Sherrington-Kirkpatrick proven earlier in BIB005 . Various applications and phase diagrams for the problem are discussed in detail in e.g. BIB022 . While it is well known in the physics literature BIB004  BIB003 that below the AT line replica symmetry breaking is needed to describe correctly the Boltzmann measure (2) the algorithmic consequences of that stay unexplored up to date. There are several versions of the TAP equations embodying a replica symmetry breaking structure in the literature BIB004 BIB011 but they do not include the proper time-indices and hence will not be able to reproduce quantitatively the RSB phase diagram (just as it was the case for the TAP equations before the work of BIB006 BIB008 ). In this paper we close this gap and derive approximate survey propagation, an AMP-type of algorithm that takes into account replica symmetry breaking. Using the state evolution theory BIB009 BIB013 BIB017 we prove that the ASP algorithm reproduces the 1RSB phase diagram in the limit of large system sizes. We study properties of the ASP algorithm, resulting estimation error as a function of the Parisi parameter, its convergence and finite size behavior.