A new metric on the manifold of kernel matrices with application to matrix geometric means

Suvrit SraNeurIPS 2012 · OpenReview

Symmetric positive definite (SPD) matrices are remarkably pervasive in scientific disciplines, serving as the backbone for covariance matrices in statistics, kernel matrices in machine learning, and various constructs in optimization. However, measuring the distance between two SPD matrices is a computationally demanding task because these matrices inhabit a curved, non-Euclidean manifold rather than a flat Euclidean space.

In this paper, author Suvrit Sra introduces a computationally efficient alternative to the traditional "gold standard" distance measure for SPD matrices. By proving that a specific log-determinant divergence is a true metric, this work provides a tool that respects the non-Euclidean geometry of matrices while being orders of magnitude faster to compute.

The Computational Bottleneck of the Riemannian Metric

To compare two SPD matrices, researchers typically rely on the Riemannian metric ($\delta_R$). While mathematically elegant and geometrically sound, $\delta_R$ is notoriously slow to compute. It requires calculating generalized eigenvalues—an expensive operation, especially when dealing with high-dimensional data or large databases.

Previous attempts to find faster proxies for this distance often failed to satisfy the formal properties of a metric, most notably the triangle inequality. Without the triangle inequality, these proxies are unreliable for rigorous geometric algorithms, such as nearest-neighbor searches or clustering.

A Log-Determinant Solution

To bypass the eigenvalue bottleneck, the paper focuses on a symmetrized "log-det" divergence, defined as: $$J(A, B) = \log \det \left( \frac{A+B}{2} \right) - \frac{1}{2} \log \det(AB)$$

The core methodological breakthrough of this paper is proving that the square root of this divergence, $\delta_{ld} = \sqrt{J}$, is a valid metric on the manifold of SPD matrices.

Proving the triangle inequality for this measure was previously a point of conjecture in the field. The author resolves this by leveraging the theory of negative definite functions and Schoenberg’s theorem, relating the matrix case back to a simpler scalar case, and employing determinantal inequalities to bridge the gap between diagonal and general SPD matrices.

Comparison of theoretical properties between the Riemannian metric and the new log-det metric.

As shown in the table above, the new $\delta_{ld}$ metric preserves many of the essential theoretical properties of the traditional Riemannian metric, ensuring it behaves intuitively while offering significant computational advantages. For the case of just two matrices, the new metric's midpoint is identical to the standard matrix geometric mean.

Key Insights and Performance Gains

The primary advantage of the $\delta_{ld}$ metric is that it is eigenvalue-free. It relies entirely on determinants, which can be computed rapidly using Cholesky decomposition. This leads to massive speed advantages:

  • Distance Computation: As matrix dimensionality increases, $\delta_{ld}$ is approximately 5 times faster than highly optimized Riemannian implementations and up to 50 times faster than naive implementations.
  • Matrix Geometric Means: Computing the geometric mean of multiple matrices using this metric is a non-convex optimization problem. However, the author proves it has a unique global minimizer. For a set of 10 matrices, computing the new geometric mean ($GM_{ld}$) is up to 1,000 times faster than computing the traditional Karcher mean.
Computation times for pairwise distances (left) and geometric means (right) across varying matrix dimensions.

Limitations and Future Directions

While $\delta_{ld}$ is highly efficient, it does have limitations. Unlike the Riemannian metric, it is not "geodesically convex," meaning it does not share all the same curvature properties as the standard manifold view. Additionally, while the paper identifies specific conditions (related to the Wallach set) under which this metric can be embedded into a Hilbert space, this embedding is not universally possible for all parameters.

Despite these limitations, the $\delta_{ld}$ metric represents a significant leap forward for practical computations. The author suggests future applications in computer vision tasks, such as covariance tracking, where the Riemannian metric is currently a major bottleneck.

Summary updated

Abstract

Symmetric positive definite (spd) matrices are remarkably pervasive in a multitude of scientific disciplines, including machine learning and optimization. We consider the fundamental task of measuring distances between two spd matrices; a task that is often nontrivial whenever an application demands the distance function to respect the non-Euclidean geometry of spd matrices. Unfortunately, typical non-Euclidean distance measures such as the Riemannian metric $\riem(X,Y)=\frob{\log(X\inv{Y})}$, are computationally demanding and also complicated to use. To allay some of these difficulties, we introduce a new metric on spd matrices: this metric not only respects non-Euclidean geometry, it also offers faster computation than $\riem$ while being less complicated to use. We support our claims theoretically via a series of theorems that relate our metric to $\riem(X,Y)$, and experimentally by studying the nonconvex problem of computing matrix geometric means based on squared distances.
BibTeX
@inproceedings{sra2012new,
  author = {Suvrit Sra},
  title = {{A new metric on the manifold of kernel matrices with application to matrix geometric means}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2012},
  url = {https://openreview.net/forum?id=ryVVtO-OWB},
}
Figure