Paper ID sheet UCLINMA2016.12
 Title

Matrix geometric means based on shuffled inductive sequences
 Authors
 Estelle M. Massart, Julien M. Hendrickx, P.A. Absil
 Abstract

We propose a new deterministic sequence converging to the least squares mean of $N$ symmetric positive definite (SPD) matrices. By "least squares mean", we refer to the Riemannian barycenter with respect to the natural metric (also known as the trace metric or affineinvariant metric) on the set $\mathbb{P}_n$ of $n \times 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 wellchosen 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 weakness 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 nonpositive curvature), which includes the set $\mathbb{P}_n$. We also illustrate numerically on $\mathbb{P}_n$ 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 stateoftheart 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.
 Key words
 geometric means; Karcher mean; least squares mean; inductive mean; symmetric positive definite matrices; NPC spaces
 Status
 Accepted for publication in Linear Algebra and its Applications
 Download

[Home]