Approximate Survey Propagation for Statistical Inference <s> Rigorous approach reloaded <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> BIB001 </s> Approximate Survey Propagation for Statistical Inference <s> Rigorous approach reloaded <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> BIB002
Interestingly, we can use the rigorous result for state evolution of AMP from Sec. II A 4 in the present context as well, and show that ASP follows rigorously a state evolution corresponding to the 1RSB equations. Theorem 2 (State Evolution for Approximate Survey Propagation). For the ASP algorithm, the empircal averages for a large class of function ψ (see BIB002 ) converge, when N → ∞, to their state evolution predictions where where Z is a random Gaussian variable with mean ∆ and variance , and x (0) is distributed according to the prior P 0 . Proof. First, let us rewrite the ASP algorithm in a AMP-like form as considered in BIB001 BIB002  with, again With the particular choice of the following denoising function where 