Medians and Means in Riemannian Geometry: Existence, Uniqueness and Computation

Marc Arnaudon, Frederic Barbaresco, Le YangOpenalex Unknown 2012 · DOI · arXiv · OpenAlex

Introduction

In classical Euclidean statistics, the arithmetic mean is the ubiquitous estimator for central tendency. However, its sensitivity to outliers makes it "imprudent" in noisy environments—a single extreme value can significantly shift the result. While the median offers a robust alternative in flat space, many modern data types—such as diffusion tensors in medical imaging or covariance matrices in radar signal processing—do not reside in Euclidean space. Instead, they exist on curved Riemannian manifolds where the shortest path between points is a geodesic rather than a straight line.

This paper, authored by Marc Arnaudon, Frédéric Barbaresco, and Le Yang, provides a rigorous mathematical framework for performing robust statistics on these curved surfaces. By extending the concepts of means and medians to Riemannian manifolds, the authors bridge the gap between abstract differential geometry and practical signal processing applications.

The Challenge of Non-Euclidean Statistics

The standard Fréchet mean (the Riemannian generalization of the arithmetic mean) is defined as the point that minimizes the sum of squared Riemannian distances to all data points. Like its Euclidean counterpart, it is highly sensitive to outliers. The Fréchet median, which minimizes the sum of unsquared distances, is far more robust. However, computing the median on a manifold presents significant mathematical hurdles: the cost function is not differentiable at the data points themselves, rendering standard gradient descent methods ineffective.

Theoretical Foundations: Existence and Uniqueness

The authors establish the conditions under which a median is guaranteed to exist and be unique on a manifold. These conditions are intimately tied to the manifold's curvature:

  1. Curvature Constraints: In positively curved spaces (like a sphere), data must be localized within a specific radius to ensure a unique center. In contrast, in negatively curved spaces (such as Cartan-Hadamard manifolds), medians are generally better behaved.
  2. Generic Uniqueness: A key theoretical contribution of the paper is the proof that on compact manifolds, the Fréchet median of "generic" data points—essentially any random set of points—is almost always unique.
  3. The "Prudence" of the Median: The authors formalize the robustness of the median on manifolds, proving that it maintains its resistance to outliers even when the underlying geometry is curved.

Algorithmic Framework

To overcome the non-differentiability of the median's cost function, the paper introduces two primary algorithmic approaches:

Subgradient Algorithms

The authors propose a subgradient algorithm that does not require the cost function to be smooth. They prove its convergence on Riemannian manifolds without requiring specific signs of curvature, making it more versatile than previous algorithms that were restricted to non-negative curvature.

Stochastic Gradient Methods

For $p$-means (a generalization where $p=1$ is the median and $p=2$ is the mean), the authors introduce a stochastic gradient algorithm. By picking data points at random to determine the descent direction rather than computing the full gradient at every step, this method significantly reduces the computational burden for large datasets.

Application: Radar Target Detection

The practical utility of these methods is demonstrated through the geometry of Toeplitz covariance matrices, which are used to model radar signals. The authors treat the space of these matrices as a Cartan-Hadamard manifold. Using reflection coefficients and Levinson’s recursion, they map these matrices into a geometry where medians can be computed efficiently.

Experimental Results

The approach was validated using real-world coastal radar data consisting of 5,000 range cells. The results highlighted several advantages of the median-based approach over the traditional barycenter (mean):

  • Cleaner Background Estimation: The median spectra provided a stable estimate of sea clutter and noise, whereas the mean-based approach suffered from "distortion" where targets leaked into the background estimate.
  • Enhanced Target Contrast: By calculating the Riemannian distance between a specific cell and its local median, the authors successfully identified four distinct physical targets that were obscured when using standard mean-based methods.

Conclusion and Future Directions

While computing medians on manifolds is more computationally intensive than calculating Euclidean averages, the gains in robustness are substantial. This paper demonstrates that Riemannian medians are essential for high-stakes signal processing where outliers are common.

Future work may focus on optimizing these algorithms for real-time systems and extending the framework to more general, non-Toeplitz covariance matrices. The principles established here also hold promise for other fields where data is naturally non-Euclidean, such as Diffusion Tensor Magnetic Resonance Imaging (DT-MRI) and computer vision.

Summary updated

BibTeX
@inproceedings{arnaudon2012medians,
  author = {Marc Arnaudon and Frederic BARBARESCO and Le Yang},
  title = {{Medians and Means in Riemannian Geometry: Existence, Uniqueness and Computation}},
  booktitle = {Openalex Unknown},
  year = {2012},
  doi = {10.1007/978-3-642-30232-9\_8},
}
Figure