Matrix-Inversion-Free Expectation Propagation for Massive Connectivity

This paper presents expectation propagation-conjugate gradient (EP-CG), a novel matrix-inversion-free EP framework designed for activity detection in massive connectivity scenarios. Conventional EP requires repeated inversions of large covariance matrices, becoming computationally prohibitive as the number of devices increases. In contrast, EP-CG computes the posterior mean via a few preconditioned CG iterations and estimates the required marginal variances using a Hutchinson diagonal estimator with Rademacher probe vectors. This approach reduces the cost per-iteration from O(N³) to O(ULNR). By demonstration, we further theoretically specify the number of probe vectors required to achieve a desired level of estimation accuracy. Numerical results confirm our analysis: EP-CG achieves detection accuracy comparable to standard EP with a remarkable complexity reduction, even when the number of users is very large.