Positive definite matrices and the Symmetric Stein Divergence

Suvrit SraarXiv 2011 · arXiv

Abstract

Positive definite matrices abound in a dazzling variety of applications. This ubiquity can be in part attributed to their rich geometric structure: positive definite matrices form a self-dual convex cone whose strict interior is a Riemannian manifold. The manifold view is endowed with a natural distance function while the conic view is not. Nevertheless, drawing motivation from the conic view, we introduce the S-Divergence as a natural distance-like function on the open cone of positive definite matrices. We motivate the S-divergence via a sequence of results that connect it to the Riemannian distance. In particular, we show that (a) this divergence is the square of a distance; and (b) that it has several geometric properties similar to those of the Riemannian distance, though without being computationally as demanding. The S-divergence is even more intriguing: although nonconvex, we can still compute matrix means and medians using it to global optimality. We complement our results with some numerical experiments illustrating our theorems and our optimization algorithm for computing matrix medians.

The Computational Bottleneck of Riemannian Geometry

Hermitian Positive Definite (HPD) matrices are fundamental components in fields ranging from diffusion tensor imaging and computer vision to convex optimization. Because these matrices reside on a curved manifold rather than a flat Euclidean space, measuring the distance between two matrices is non-trivial.

The traditional "gold standard" for this measurement is the Affine-Invariant Riemannian Metric (AIRM), denoted as $\delta_R$. While mathematically elegant and physically meaningful, $\delta_R$ is computationally expensive, requiring matrix logarithms or eigenvalue decompositions. In big-data applications or real-time systems, this overhead becomes a significant bottleneck. This research seeks a "distance-like" function that is fast to compute while respecting the rich geometric structure—such as congruence invariance and convexity—of HPD matrices.

Introducing the S-Divergence

This paper proposes the Symmetric Stein Divergence (S-Divergence), denoted as $\delta_S^2$, as a computationally efficient alternative. Derived from the Log-Determinant divergence (Stein’s loss), it is defined as a "Jensen-Bregman" symmetrization:

$$\delta_S^2(X, Y) = \log \det \left( \frac{X+Y}{2} \right) - \frac{1}{2} \log \det(XY)$$

Key Insights and Metricity

A major contribution of this work is the proof of metrization. While it was previously conjectured that the square root of the S-divergence ($\delta_S = \sqrt{\delta_S^2}$) was a metric, proofs were limited to commuting matrices. This paper provides a general proof for all HPD matrices using the theory of negative definite kernels, confirming that it satisfies the triangle inequality.

Furthermore, the S-Divergence exhibits Geometric Parity with the Riemannian metric. It is invariant under congruence transformations (multiplying both matrices by the same invertible matrix) and inversion, mimicking the behavior of the more expensive AIRM.

Empirical Performance and Efficiency

The primary advantage of the S-Divergence is its reliance on Cholesky factorizations rather than eigenvalue decompositions. This shift leads to dramatic performance gains in practical applications.

Comparison of computation times for the Riemannian distance (delta_R) and the S-Divergence (S) across varying matrix dimensions.

As shown in the benchmarking of synthetic HPD matrices, computing the S-Divergence is approximately 50 times faster than the Riemannian distance as dimensionality increases.

Optimization and Matrix Means

The paper also addresses the "matrix mean" problem—finding a central matrix that minimizes the sum of distances to a set of points. Through the lens of geodesic convexity (g-convexity), the author proves that $\delta_S^2$ is "jointly g-convex." This property ensures that iterative algorithms will converge to a unique global optimum, even if the problem appears non-convex in Euclidean space.

Computation time for the geometric mean (GM) using Riemannian methods versus the S-Divergence based mean (GM_ld).

In practical optimization tasks, such as calculating the geometric mean of 10 matrices, the S-Divergence approach ($GM_{ld}$) proved to be up to 1,000 times faster than standard Riemannian "Karcher mean" algorithms. This efficiency is supported theoretically by a "Sandwich Inequality," which establishes that $8\delta_S^2 \le \delta_R^2$, positioning the S-Divergence as a reliable and high-speed proxy for the Riemannian metric.

Limitations and Future Work

Despite its advantages, the metric space $(\mathcal{P}_n, \delta_S)$ does not isometrically embed into a Hilbert space, meaning these distances cannot be treated as simple flat Euclidean distances in higher dimensions. Future research remains to fully characterize the subclass of matrices for which the S-Divergence kernel is always positive definite for any scaling factor $\beta$, and to further test these methods in domains like brain-computer interfacing and radar signal processing.

Summary updated

Abstract

Positive definite matrices abound in a dazzling variety of applications. This ubiquity can be in part attributed to their rich geometric structure: positive definite matrices form a self-dual convex cone whose strict interior is a Riemannian manifold. The manifold view is endowed with a natural distance function while the conic view is not. Nevertheless, drawing motivation from the conic view, we introduce the S-Divergence as a natural distance-like function on the open cone of positive definite matrices. We motivate the S-divergence via a sequence of results that connect it to the Riemannian distance. In particular, we show that (a) this divergence is the square of a distance; and (b) that it has several geometric properties similar to those of the Riemannian distance, though without being computationally as demanding. The S-divergence is even more intriguing: although nonconvex, we can still compute matrix means and medians using it to global optimality. We complement our results with some numerical experiments illustrating our theorems and our optimization algorithm for computing matrix medians.
BibTeX
@misc{sra2011positive,
  author = {Suvrit Sra},
  title = {{Positive definite matrices and the Symmetric Stein Divergence}},
  year = {2011},
  eprint = {1110.1773},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1110.1773},
}
Figure