We study asymptotic properties of expectation propagation (EP) - a method for approximate inference originally developed in the field of machine learning. Applied to generalized linear models, EP iteratively computes a multivariate Gaussian approximation to the exact posterior distribution. The computational complexity of the repeated update of covariance matrices severely limits the application of EP to large problem sizes. In this study, we present a rigorous analysis by means of free probability theory that allows us to overcome this computational bottleneck if specific data matrices in the problem fulfill certain properties of asymptotic freeness. We demonstrate the relevance of our approach on the gene selection problem of a microarray dataset.
This paper is about the relation of random matrix theory and the subordination phenomenon in complex analysis. We find that the resolvent of the sum of two random matrices is approximately subordinated to the resolvents of the original matrices. We estimate the error terms in this relation and in the subordination relation for the traces of the resolvents. This allows us to prove a local limit law for eigenvalues and a delocalization result for eigenvectors of the sum of two random matrices. In addition, we use subordination to determine the limit of the largest eigenvalue for the rank-one deformations of unitary-invariant random matrices. The eigenvalue distribution of the sum of two large Hermitian matrices, when one of them is conjugated by a Haar distributed unitary matrix, is asymptotically given by the free convolution of their spectral distributions. We prove that this convergence also holds locally in the bulk of the spectrum, down to the optimal scales larger than the eigenvalue spacing. The corresponding eigenvectors are fully delocalized. Similar results hold for the sum of two real symmetric matrices, when one is conjugated by Haar orthogonal matrix.