Approximate Survey Propagation for Statistical Inference <s> Low-RAMP equations. <s> It is shown that the power expansion of the Gibbs potential of the SK model up to second order in the exchange couplings leads to the TAP equation. This result remains valid for the general (including a ferromagnetic exchange) SK model. Theorems of power expansions and resolvent techniques are employed to solve the convergence problem. The convergence condition is presented for the whole temperature range and for general distributions of the local magnetisations. <s> BIB001 </s> Approximate Survey Propagation for Statistical Inference <s> Low-RAMP equations. <s> High-temperature expansions performed at a fixed-order parameter provide a simple and systematic way to derive and correct mean-field theories for statistical mechanical models. For models like spin glasses which have general couplings between spins, the authors show that these expansions generate the Thouless-Anderson-Palmer equations at low order. They explicitly calculate the corrections to TAP theory for these models. For ferromagnetic models, they show that their expansions can easily be converted into 1/d expansions around mean-field theory, where d is the number of spatial dimensions. Only a small finite number of graphs need to be calculated to generate each order in 1/d for thermodynamic quantities like free energy or magnetization. Unlike previous 1/d expansions, the expansions are valid in the low-temperature phases of the models considered. They consider alternative ways to expand around mean-field theory besides 1/d expansions. In contrast to the 1/d expansion for the critical temperature, which is presumably asymptotic, these schemes can be used to devise convergent expansions for the critical temperature. They also appear to give convergent series for thermodynamic quantities and critical exponents. They test the schemes using the spherical model, where their properties can be studied using exact expressions. <s> BIB002 </s> Approximate Survey Propagation for Statistical Inference <s> Low-RAMP equations. <s> "Inference" problems arise in statistical physics, computer vision, error-correcting coding theory, and AI. We explain the principles behind the belief propagation (BP) algorithm, which is an efficient way to solve inference problems based on passing local messages. We develop a unified approach, with examples, notation, and graphical models borrowed from the relevant disciplines.We explain the close connection between the BP algorithm and the Bethe approximation of statistical physics. In particular, we show that BP can only converge to a fixed point that is also a stationary point of the Bethe approximation to the free energy. This result helps explaining the successes of the BP algorithm and enables connections to be made with variational approaches to approximate inference.The connection of BP with the Bethe approximation also suggests a way to construct new message-passing algorithms based on improvements to Bethe's approximation introduced Kikuchi and others. The new generalized belief propagation (GBP) algorithms are significantly more accurate than ordinary BP for some problems. We illustrate how to construct GBP algorithms with a detailed example. <s> BIB003 </s> Approximate Survey Propagation for Statistical Inference <s> Low-RAMP equations. <s> The generalized approximate message passing (GAMP) algorithm is an efficient method of MAP or approximate-MMSE estimation of x observed from a noisy version of the transform coefficients z = Ax. In fact, for large zero-mean i.i.d sub-Gaussian A, GAMP is characterized by a state evolution whose fixed points, when unique, are optimal. For generic A, however, GAMP may diverge. In this paper, we propose adaptive-damping and mean-removal strategies that aim to prevent divergence. Numerical results demonstrate significantly enhanced robustness to non-zero-mean, rank-deficient, column-correlated, and ill-conditioned A. <s> BIB004 </s> Approximate Survey Propagation for Statistical Inference <s> Low-RAMP equations. <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> BIB005 </s> Approximate Survey Propagation for Statistical Inference <s> Low-RAMP equations. <s> The estimation of a random vector with independent components passed through a linear transform followed by a componentwise (possibly nonlinear) output map arises in a range of applications. Approximate message passing (AMP) methods, based on Gaussian approximations of loopy belief propagation, have recently attracted considerable attention for such problems. For large random transforms, these methods exhibit fast convergence and admit precise analytic characterizations with testable conditions for optimality, even for certain non-convex problem instances. However, the behavior of AMP under general transforms is not fully understood. In this paper, we consider the generalized AMP (GAMP) algorithm and relate the method to more common optimization techniques. This analysis enables a precise characterization of the GAMP algorithm fixed points that applies to arbitrary transforms. In particular, we show that the fixed points of the so-called max-sum GAMP algorithm for MAP estimation are critical points of a constrained maximization of the posterior density. The fixed points of the sum-product GAMP algorithm for estimation of the posterior marginals can be interpreted as critical points of a certain free energy. <s> BIB006 </s> Approximate Survey Propagation for Statistical Inference <s> Low-RAMP equations. <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> BIB007
Let us state the Low-RAMP equations to emphasize the differences and similarities with the replica symmetry breaking approach of Sec. III. The Low-RAMP algorithm evaluates the marginals of Eq. (2) starting from the belief propagation (BP) equations BIB003 (cf. the factor graph of Fig. 5 in the case where s = 1). The main assumptions of BP is that the incoming messages are probabilistically independent when conditioned on the value of the root. In the present case the factor 1/ √ N in Eq. (1) makes the interactions sufficiently weak so that the assumption of independence of incoming messages is plausible at the leading order in the large size limit. Moreover, this assumption is particularly beneficial in the case of continuous variables: since we have an accumulation of many independent messages, the central limit theorem assures that it is sufficient to consider only means and variances to represent the result (relaxed-belief propagation) instead of dealing with whole probability distributions. To finally obtain the Low-RAMP equations, the further step is the so-called  where Note also that these equations can be further simplified replacing S  2. Bethe Free Energy. The fixed-points of the Low-RAMP equations are stationary points of the Bethe free energy of the model. In general, the free energy of a probability measure is defined as the logarithm of its normalization 1 . Within the same assumptions of Low-RAMP, the free energy can be approximated using the Plefka expansion BIB001 BIB002 , obtaining the Bethe free energy BIB007 Φ Bethe = max wherex i and σ i are considered explicit functions of A and B as in Eqs. (11), BIB005 . The Bethe free energy is useful to analyze situations in which the AMP equations have more than one fixed-point: the best achievable mean squared error is associated to the largest free energy. The Bethe free energy is also useful in order to use adaptive damping to improve the convergence of the Low-RAMP equations BIB006 BIB004 . 3. State Evolution. One of the advantages of AMP-type algorithms is that one can analyze their performance in the large size limit via the so-called State Evolution (SE), equivalent to the cavity method in the physics literature. Assume that Y is generated from the following process: the signal {x r0 } is extracted from a probability distribution i ) and then it is measured through a Gaussian channel of zero mean and variance ∆ 0 , so that the probability distribution of the matrix elements Y ij is given by Note as here we are considering the general situation in which the prior P 0 (x) and the noise channel P out (Y ij ) (and possibly also the rank r 0 ) are not known and are in principle different from the ones used in the posterior Eq. (2). If both the prior and the channel are exactly known, we say to be in the Bayes-optimal case. Central limit theorem assures that the averages of B i and A i over Y are Gaussian with while the variance of A i is of smaller order in N and where we have defined the order parameters Using then Eqs. (11), BIB005 to fix self-consistently the values of the order parameters, one obtains the state evolution equations BIB007  where x (0) is distributed according to P 0 (x), W is a Gaussian noise of zero mean and unit covariance matrix and we have defined Similarly, the large size limit of the Bethe free energy Eq. (17) is given by with For Low-RAMP, the mean squared error (MSE) can be evaluated from the state evolution as allowing us to assess the typical performance of the algorithm.