Recursive Karcher Expectation Estimators And Geometric Law of Large Numbers


Jeffrey Ho, Guang Cheng, Hesamoddin Salehian, Baba Vemuri ;
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:325-332, 2013.


This paper studies a form of law of large numbers on Pn, the space of nxn symmetric positive-definite matrices equipped with Fisher-Rao metric. Specifically, we propose a recursive algorithm for estimating the Karcher expectation of an arbitrary distribution defined on Pn, and we show that the estimates computed by the recursive algorithm asymptotically converge in probability to the correct Karcher expectation. The steps in the recursive algorithm mainly consist of making appropriate moves on geodesics in Pn, and the algorithm is simple to implement and it offers a tremendous gain in computation time of several orders in magnitude over existing non-recursive algorithms. We elucidate the connection between the more familiar law of large numbers for real-valued random variables and the asymptotic convergence of the proposed recursive algorithm, and our result provides an example of a new form of law of large numbers for random variables taking values in a Riemannian manifold. From the practical side, the computation of the mean of a collection of symmetric positive-definite (SPD) matrices is a fundamental ingredient in many algorithms in machine learning, computer vision and medical imaging applications. We report an experiment using the proposed recursive algorithm for K-means clustering, demonstrating the algorithm’s efficiency, accuracy and stability.

Related Material