A Majorization-Minimization Algorithm for the Karcher Mean of Positive Definite Matrices

Teng ZhangarXiv 2013 · arXiv

Abstract

A majorization-minimization (MM) algorithm for the Karcher mean of $n$ $p \times p$ positive definite matrices is proposed and it is guaranteed to converge linearly. Simulations show that the MM algorithm performs faster than other current algorithms for the Karcher mean of positive definite matrices, including steepest descent, conjugate gradient descent and trust region methods.

Introduction

In many scientific and engineering applications—ranging from Diffusion Tensor Imaging (DTI) in medical physics to radar signal processing and brain-computer interfaces—data is often represented as positive definite (PD) matrices. A fundamental task in these fields is finding a representative "average" of a set of such matrices. However, because the space of PD matrices is a curved Riemannian manifold and matrix multiplication is non-commutative, the standard arithmetic mean is often inappropriate.

The Karcher mean (also known as the Riemannian mean or Fréchet mean) is the standard solution. It is defined as the point that minimizes the sum of squared Riemannian distances to all matrices in a given set. While mathematically elegant, computing the Karcher mean is a non-trivial optimization problem that traditionally requires iterative manifold-based algorithms.

The Majorization-Minimization (MM) Approach

Existing optimization techniques, such as steepest descent or conjugate gradient methods on manifolds, often rely on "line searches" to determine an appropriate step size. These sub-routines are computationally expensive and can be sensitive to initialization.

This paper introduces a novel algorithm based on the Majorization-Minimization (MM) principle. Instead of minimizing the complex Karcher mean objective function directly, the MM algorithm constructs a simpler "surrogate" function. This surrogate function has two critical properties:

  1. It always stays above (majorizes) the actual objective function.
  2. It touches the objective function at the current estimate.

By minimizing this simpler surrogate, the algorithm generates a new estimate that is guaranteed to reduce the original objective. This process is repeated until convergence.

Key Advantages

  • No Step-Size Tuning: Unlike gradient-based methods, the MM algorithm does not require a step-size parameter or a line search. The step size is inherently determined by the geometry of the surrogate function.
  • Guaranteed Convergence: The author provides a theoretical proof that the algorithm converges linearly to the global minimum from any starting point, providing high reliability and removing the need for a perfect initial guess.
  • Exploiting Matrix Structure: While general-purpose manifold solvers treat PD matrices as abstract points, the proposed MM algorithm uses the specific algebraic properties of the PD manifold to optimize the update rule, leading to higher efficiency.

Experimental Evaluation

The performance of the MM algorithm was evaluated through a series of simulations involving sets of 40 random PD matrices. To test the algorithm's scalability, experiments were conducted across different matrix dimensions ($5 \times 5$, $7 \times 7$, and $10 \times 10$).

The MM algorithm was benchmarked against several state-of-the-art methods:

  • Steepest Descent (SD)
  • Conjugate Gradient (CG)
  • Riemannian BFGS (a quasi-Newton method)
  • Trust Region (TR) methods

Results

The simulations demonstrated that the MM algorithm consistently reaches high-accuracy solutions faster than first-order methods like SD and CG. While second-order methods like BFGS can exhibit faster convergence once they are very close to the solution, the MM algorithm is often more efficient in the initial "discovery" phase and maintains a lower per-iteration computational cost.

Furthermore, the MM algorithm showed remarkable stability. While other methods sometimes exhibited erratic behavior or plateaus depending on the specific configuration, the MM approach showed a steady and predictable decline in the gradient norm across all tested dimensions.

Conclusion

The proposed MM algorithm represents a significant step forward in the efficient computation of the Karcher mean. By moving away from general-purpose manifold optimization and toward a "specialist" approach that exploits the specific geometry of positive definite matrices, the author has developed a tool that is both faster and more robust than existing standards.

Future research may explore extending this MM framework to other types of manifold-constrained optimization problems, potentially simplifying the computational pipeline for a wide variety of geometric data types.

Summary updated

Abstract

A majorization-minimization (MM) algorithm for the Karcher mean of n p × p positive definite matrices is proposed and it is gauranteed to converge linearly. Simulations show that the MM algorithm performs faster than other current algorithms for the Karcher mean of positive definite matrices, including steepest descent, conjugate gradient descent and trust region methods. 1
BibTeX
@misc{zhang2013majorization,
  author = {Teng Zhang},
  title = {{A Majorization-Minimization Algorithm for the Karcher Mean of Positive Definite Matrices}},
  year = {2013},
  eprint = {1312.4654},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1312.4654},
}
Figure