Recursive Estimation of the Stein Center of SPD Matrices and Its Applications

Hesamoddin Salehian, Guang Cheng, Baba C. Vemuri, Jeffrey HoICCV 2013 · OpenReview

Abstract

Symmetric positive-definite (SPD) matrices are ubiquitous in Computer Vision, Machine Learning and Medical Image Analysis. Finding the center/average of a population of such matrices is a common theme in many algorithms such as clustering, segmentation, principal geodesic analysis, etc. The center of a population of such matrices can be defined using a variety of distance/divergence measures as the minimizer of the sum of squared distances/divergences from the unknown center to the members of the population. It is well known that the computation of the Karcher mean for the space of SPD matrices which is a negatively-curved Riemannian manifold is computationally expensive. Recently, the LogDet divergence-based center was shown to be a computationally attractive alternative. However, the LogDet-based mean of more than two matrices can not be computed in closed form, which makes it computationally less attractive for large populations. In this paper we present a novel recursive estimator for center based on the Stein distance - which is the square root of the LogDet divergence - that is significantly faster than the batch mode computation of this center. The key theoretical contribution is a closed-form solution for the weighted Stein center of two SPD matrices, which is used in the recursive computation of the Stein center for a population of SPD matrices. Additionally, we show experimental evidence of the convergence of our recursive Stein center estimator to the batch mode Stein center. We present applications of our recursive estimator to K-means clustering and image indexing depicting significant time gains over corresponding algorithms that use the batch mode computations. For the latter application, we develop novel hashing functions using the Stein distance and apply it to publicly available data sets, and experimental results have shown favorable comparisons to other competing methods.

Introduction

Symmetric Positive-Definite (SPD) matrices are foundational data structures in modern computer vision and medical imaging, representing everything from image textures and motion descriptors to diffusion tensors in brain imaging. A fundamental task in processing these matrices is finding the "center" or average of a population, a step required for clustering, building representative atlases, or dimensionality reduction.

However, the space of SPD matrices is a curved Riemannian manifold rather than a flat Euclidean space. The standard "Karcher mean" is computationally expensive, requiring iterative algorithms involving numerous matrix eigen-decompositions. While the LogDet divergence (and its square root, the Stein metric) was proposed as a faster alternative, it previously lacked a closed-form solution for the mean of more than two matrices. This forced researchers to rely on slow, batch-mode iterative optimization, creating a bottleneck for large-scale datasets.

Methodology

This research introduces a mathematical bridge between simple two-matrix averages and complex population means through three key innovations:

  1. The Stein Metric: The authors utilize the Stein metric (the square root of the Jensen-Bregman LogDet divergence). Unlike the standard Riemannian metric, calculating Stein distance avoids eigen-decompositions, relying instead on determinants and logs, which are inherently faster to compute.
  2. Closed-Form Weighted Mean: The core contribution is a closed-form solution for the weighted Stein center of just two matrices ($A$ and $B$). The authors demonstrate that the minimizer satisfies a specific matrix quadratic equation solvable via direct computation.
  3. Recursive Estimation: Leveraging this closed-form solution, the paper proposes a recursive estimator: $M_{k+1} = f(M_k, X_{k+1}, w_{k+1})$. To find the mean of $N$ matrices, one only needs the current mean ($M_k$) and the new incoming matrix ($X_{k+1}$), eliminating the need to store or re-process the entire dataset as new samples arrive.

Experimental Results

The authors evaluated the Recursive Stein Mean (RSM) against the batch-mode Stein Mean (SM) and other Riemannian averages using synthetic and real-world datasets (COREL and MPEG-7).

Comparison of computation time between non-recursive and recursive Stein center estimation.

As shown in the figure above, the recursive approach offers a massive computational advantage. While the non-recursive batch mode time grows linearly with the number of samples, the recursive update time remains near zero, enabling real-time processing of large streams of SPD data.

Convergence of the recursive Stein center (RSM) error compared to the batch mode Stein mean (SM).

Crucially, this speed does not come at the cost of accuracy. Empirical tests demonstrate that the RSM converges to the same result as the batch-mode SM as the number of samples increases, with the error curves for both methods overlapping almost perfectly.

Applications: Clustering and Hashing

The efficiency of the RSM was further demonstrated in practical applications:

  • K-means Clustering: In K-means, cluster centers change slightly each iteration. The recursive formula allows for incremental updates—adding or removing a single point—without recomputing the entire cluster mean from scratch. This outperformed Karcher and Log-Euclidean means by orders of magnitude in high-dimensional settings.
  • Stein Hashing: The authors extended "spherical hashing" to the SPD manifold using the Stein distance. On the MPEG-7 dataset, this achieved a retrieval precision of ~73%, matching the accuracy of slower Karcher-based methods while running nearly 4x faster.

Conclusion

The recursive Stein center estimator represents a significant step forward for manifold-based learning. By providing a closed-form solution for the weighted mean of two matrices, the authors enabled an incremental update rule that is both mathematically grounded and computationally superior to existing batch methods. While formal theoretical proofs of convergence in non-length spaces remain a subject for future work, the empirical evidence strongly supports the use of RSM for high-performance computer vision applications.

Summary updated

Abstract

Symmetric positive-definite (SPD) matrices are ubiquitous in Computer Vision, Machine Learning and Medical Image Analysis. Finding the center/average of a population of such matrices is a common theme in many algorithms such as clustering, segmentation, principal geodesic analysis, etc. The center of a population of such matrices can be defined using a variety of distance/divergence measures as the minimizer of the sum of squared distances/divergences from the unknown center to the members of the population. It is well known that the computation of the Karcher mean for the space of SPD matrices which is a negatively-curved Riemannian manifold is computationally expensive. Recently, the LogDet divergence-based center was shown to be a computationally attractive alternative. However, the LogDet-based mean of more than two matrices can not be computed in closed form, which makes it computationally less attractive for large populations. In this paper we present a novel recursive estimator for center based on the Stein distance - which is the square root of the LogDet divergence - that is significantly faster than the batch mode computation of this center. The key theoretical contribution is a closed-form solution for the weighted Stein center of two SPD matrices, which is used in the recursive computation of the Stein center for a population of SPD matrices. Additionally, we show experimental evidence of the convergence of our recursive Stein center estimator to the batch mode Stein center. We present applications of our recursive estimator to K-means clustering and image indexing depicting significant time gains over corresponding algorithms that use the batch mode computations. For the latter application, we develop novel hashing functions using the Stein distance and apply it to publicly available data sets, and experimental results have shown favorable comparisons to other competing methods.
BibTeX
@inproceedings{salehian2013recursive,
  author = {Hesamoddin Salehian and Guang Cheng and Baba C. Vemuri and Jeffrey Ho},
  title = {{Recursive Estimation of the Stein Center of SPD Matrices and Its Applications}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  url = {https://openreview.net/forum?id=r14oF-G_-S},
}
Figure