Approximate Survey Propagation for Statistical Inference <s> The rigorous approach <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> BIB001 </s> Approximate Survey Propagation for Statistical Inference <s> The rigorous approach <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> BIB002 </s> Approximate Survey Propagation for Statistical Inference <s> The rigorous approach <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> BIB003 </s> Approximate Survey Propagation for Statistical Inference <s> The rigorous approach <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> BIB004 </s> Approximate Survey Propagation for Statistical Inference <s> The rigorous approach <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> BIB005
The fact that state evolution accurately tracks the behavior of the AMP algorithm has been proven BIB002 BIB001 BIB003 BIB004 BIB005 . In this section, we shall discuss the main lines of this progress. First, let us rewrite the AMP equations (9-12) as follows, using a vectorial form: where the scalar quantity b is computed as is the average value of the square of each element of the matrix S. The link with the AMP equations written previously is direct when one choose the denoising function η t (B) to be The strong advantage of the rigorous theorem is that it can be stated for any function η t () (under some Lipschitz conditions), and we shall make advantage of this in the next chapter. With these notations, the state evolution is rigorous thanks to a set of works due to Rangan and Fletcher BIB003 , Deshpande and Montanari BIB004 , and Deshpande, Abbe, and Montanari BIB005 1 Theorem 1 (State Evolution for Low-RAMP BIB003 BIB004 BIB005 (1), and define S = Y /∆. Let η t (B t ) be a sequence of functions such that both η and η and Lipschitz continuous, then the empirical averages for a large class of function ψ (see BIB005 ) converge, when N → ∞, to their state evolution predictions where where Z is a random Gaussian variable with mean This means that the variable B t i converges to a Gaussian with mean M t X 0 /∆ and variance ∆ 0 Q t /∆ 2 as predicted within the cavity method in  . This provides a rigorous basis for the analysis of AMP. In particular, one can choose and this covers the AMP algorithm discussed in this section.