Approximate Survey Propagation for Statistical Inference <s> B. The low-rank estimation model and Bayesian setting <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> B. The low-rank estimation model and Bayesian setting <s> 1. Mean-field theory of phase transitions 2. Mean-field theory of spin glasses 3. Replica symmetry breaking 4. Gauge theory of spin glasses 5. Error-correcting codes 6. Image restoration 7. Associative memory 8. Learning in perceptron 9. Optimization problems A. Eigenvalues of the Hessian B. Parisi equation C. Channel coding theorem D. Distribution and free energy of K-Sat References Index <s> BIB002 </s> Approximate Survey Propagation for Statistical Inference <s> B. The low-rank estimation model and Bayesian setting <s> This paper has been withdrawn due to a critical error near equation (71). This error causes the entire argument of the paper to collapse. ::: Emmanuel Candes of Stanford discovered the error, and has suggested a correct analysis, which will be reported in a separate publication. <s> BIB003 </s> Approximate Survey Propagation for Statistical Inference <s> B. The low-rank estimation model and Bayesian setting <s> We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? ::: ::: We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys $$m\ge C\,n^{1.2}r\log n$$ for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information. <s> BIB004 </s> Approximate Survey Propagation for Statistical Inference <s> B. The low-rank estimation model and Bayesian setting <s> This paper is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the L1 norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces. <s> BIB005 </s> Approximate Survey Propagation for Statistical Inference <s> B. The low-rank estimation model and Bayesian setting <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> BIB006 </s> Approximate Survey Propagation for Statistical Inference <s> B. The low-rank estimation model and Bayesian setting <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> BIB007 </s> Approximate Survey Propagation for Statistical Inference <s> B. The low-rank estimation model and Bayesian setting <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> BIB008
As this is a kind of exploratory paper we focus on the problem of rank-one matrix estimation. This problem is (among) the simplest where the ASP algorithm can be tested. In particular, for binary (Ising) variables it is equivalent to the Sherrington-Kirkpatrick model with ferromagnetically biased couplings as studied e.g. in BIB002 BIB001  . Low-rank matrix estimation is a problem ubiquitous in modern data processing. Commonly it is stated in the following way: Given an observed matrix Y one aims to write it as Y ij = λu i v j + ξ ij , where u i , v j ∈ R r with r being the rank, and ξ ij is a noise or a part of the data matrix Y that is not well explained via this decomposition. Commonly used methods such as principal component analysis or clustering can be formulated as low-rank matrix estimation. Applications of these methods range from medicine over to signal processing or marketing. From an algorithmic point of view and under various constraints on the factors u i , v j and the noise ξ ij the problem is highly non-trivial (non-convex and NP-hard in worst case). Development of algorithms for low-rank matrix estimation and their theoretical properties is an object of numerous studies in statistics, machine learning, signal processing, applied mathematics, etc. BIB003 BIB005 BIB004 . In this paper we focus on the symmetric low-rank matrix estimation where the matrix Y ij is symmetric, i.e. Y ij = Y ji and the desired decomposition is Y ij = λx i x j + ξ ij , where x i ∈ R r . A model for low-rank matrix estimation that can be solved exactly in the large size limit using the techniques studied in this paper is the so-called general-output low-rank matrix estimation model BIB008 BIB006 where the matrix Y ij ∈ R N ×N is generated from a given probability distribution P out (Y ij |w (0) ij ) with and where each component x (0) i ∈ R r0 is generated independently from a probability distribution P 0 (x (0) i ). The N × r matrix X (0) can then be seen as an unknown signal that is to be reconstructed from the observation of the matrix Y ij . Following Bayesian approach, a way to infer X (0) given Y is to analyze the posterior probability distribution where P X (x i ) is the assumed prior on signal components x i ∈ R r and P out (Y ij |w ij ) = exp [g (Y ij |w ij )] is the assumed model for the noise. The normalization Z X (Y ) is the partition function in the statistical physics notation. And the posterior distribution (2) is nothing else but the Boltzmann measure on the r-dimensional spin variables x i . In a Bayes-optimal estimation, we know exactly the model that generated the data, i.e. The Bayes-optimal estimator is defined as the one that among all the estimators minimizes the mean-squared error to the ground truth signal x i . This is computed as the mean of the posterior marginals or, in physics language, the local magnetizations. In this paper we will focus on inference with the mismatching model where at least one of the above equalities (3) does not hold. Yet, we will still aim to evaluate the estimator that computes the mean of the posterior marginalsx We will call this the marginalization estimator. Another common estimator in inference is the maximum posterior probability (MAP) estimator wherê Generically, optimizing a complicated cost function is simpler than marginalizing over it, because optimization is in general simpler than counting. Thus MAP is often thought of as a simpler estimator to evaluate. Moreover, in statistics the problems are usually set in a regime where the MAP and the marginalization estimator coincide. However, this is not the case in the setting considered in the present paper and we will comment on the difference in the subsequent sections. In our analysis we are interested in the high-dimensional statistics limit, N → ∞ whereas r = O(1). The factor 1/ √ N in Eq. (1) in this limit ensures that the estimation error we are able to obtain is in a regime where it goes from zero to randomly bad as the parameters vary. This case is different from traditional statistics, where one is typically concerned with estimation error going to zero as N grows. In the N → ∞ limit, the above defined model benefits of an universality property in the noise channel BIB008 BIB006 (see BIB007 for a rigorous proof) as the estimation error depends on the function g only through the matrices Because of this universality, in the following we will restrict the assumed output channel to be Gaussian with The ground truth channel P out (Y ij |w (0) ij ) that was used to generate the observation Y ij is also Gaussian centered around w N with variance ∆ 0 .