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.
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.
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