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.
While invariant matrices are important ensembles for the asymptotic freeness to hold, there are important matrix ensemble that are not invariant but the asymptotic freeness can still holds. For example, consider @math as above. Then, by substituting the Haar matrix @math with randomly permuted Fourier or Hadamard matrices the asymptotic freeness still holds, see @cite_5 for further information.
@cite_5
2044172468
A fundamental result of free probability theory due to Voiculescu and subsequently refined by many authors states that conjugation by independent Haar-distributed random unitary matrices delivers asymptotic freeness. In this paper we exhibit many other systems of random unitary matrices that, when used for conjugation, lead to freeness. We do so by first proving a general result asserting “asymptotic liberation” under quite mild conditions, and then we explain how to specialize these general results in a striking way by exploiting Hadamard matrices. In particular, we recover and generalize results of the second-named author and of Tulino, Caire, Shamai and Verdu.