Matrix geometric means based on shuffled inductive sequences

We propose a new deterministic sequence converging to the least squares mean of N sym- metric positive definite (SPD) matrices. By "least squares mean", we refer to the Rie- mannian barycenter with respect to the natural metric (also known as the trace metric or affine-invariant metric) on the set Pn of n × n SPD matrices. In some papers, this mean is also referred to as the Karcher mean. The sequence we propose belongs to the family of Inductive sequences, obtained by letting a point take successive steps towards the data points, with step lengths progressively diminishing to zero. We use the word "Inductive" since each point of those sequences can be seen as the Inductive mean of a well-chosen set of points containing multiple replications of the data points. We show that visiting the data points in a cyclic order usually results in a slow convergence, and remedy this weak- ness by reordering repeatedly the data points using a shuffling algorithm. We prove the convergence of the resulting Inductive sequence to the least squares mean of the data in the general framework of NPC spaces (complete metric spaces with non-positive curvature), which includes the set Pn. We also illustrate numerically on Pn that some points of this sequence are fairly accurate estimates of the least squares mean, while being considerably cheaper to compute, and perform well as initializers for state-of-the-art algorithms. To reduce further the computation time, we finally exploit Inductive sequences to produce a family of parallelizable algorithms for estimating the least squares mean.