Restricted Riemannian geometry for positive semidefinite matrices

Ahn Martina Neuman, Yuying Xie, Qiang SunOpenReview 2021 · arXiv · OpenReview

TL;DR

This paper introduces a new geometric framework for a specific subset of positive semidefinite matrices, called "restricted" matrices ($S(n, p)^*$). This framework provides a complete and convenient Riemannian geometry, enabling analytical solutions for key operations like geodesics and parallel transport. This is crucial for statistical applications where these matrices arise, such as in covariance estimation and principal component analysis.

What Problem Does This Paper Address?

Positive semidefinite matrices (PSD) of fixed rank are fundamental in many areas of applied mathematics, including statistics (covariance matrices) and machine learning (kernel matrices). While the geometry of these matrices is rich, existing geometric approaches for PSD matrices of fixed rank ($S(n, p)$) have limitations. Some lack geodesic completeness, while others provide closed-form solutions only for certain operations (e.g., geodesics but not endpoint geodesics). This paper addresses the need for a statistically meaningful and computationally tractable geometric framework for PSD matrices of fixed rank, particularly for applications where these matrices are often encountered.

Methods

The authors introduce a special subset of $S(n, p)$, denoted $S(n, p)^*$, which is an open and dense submanifold of $S(n, p)$. This subset is chosen because it allows for a geodesically complete Riemannian geometry with convenient analytical forms for various operations. The key to their approach is utilizing a "reduced Cholesky decomposition" to map matrices in $S(n, p)^*$ to a simpler space called the "reduced Cholesky space" ($L^{\times p}$). This space is essentially a Euclidean space with a modified coordinate system.

They then define a Riemannian metric on $L^{\times p}$ and, by pulling it back to $S(n, p)^*$, establish a Riemannian manifold structure on $S(n, p)^*$. This allows them to derive closed-form expressions for:

  • Endpoint geodesics: The shortest paths between two matrices.
  • Parallel transports: Moving tangent vectors along geodesics while keeping them "constant" in a geometric sense.
  • Fréchet means: A generalized notion of average for matrices on the manifold.
  • Exponential and logarithmic maps: Essential tools for navigating the manifold.

They also introduce an algorithm for computing the reduced Cholesky factor and an LRC (Low Rank Cholesky) algorithm for estimating principal eigenspaces.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and uses synthetic data for evaluation in its application sections.

Key Insights and Ideas

  • The "Restricted" Manifold ($S(n, p)^*$): By focusing on a specific, dense subset of PSD matrices, the authors achieve a mathematically tractable and geometrically rich structure that is still statistically relevant.
  • Reduced Cholesky Decomposition as a Bridge: The Cholesky decomposition, when adapted to this restricted setting, acts as a powerful tool to map complex matrix geometry to a simpler Euclidean-like space, enabling analytical solutions.
  • Geodesic Completeness and Analytical Forms: The derived geometry is geodesically complete, and crucially, provides closed-form solutions for operations like geodesics and parallel transport. This is a significant advantage for computational efficiency and theoretical analysis.
  • Fréchet Mean as a Geodesic Midpoint (for two points): A particularly elegant finding is that the Fréchet mean of two points on $S(n, p)^*$ coincides with their geodesic midpoint, simplifying the interpretation of the average.
  • LRC Algorithm for Eigenspace Estimation: The developed geometric framework leads to a practical algorithm (LRC) that demonstrates superior performance in estimating principal eigenspaces from noisy data compared to existing methods.

Key Results

  • Manifold Structure: $S(n, p)^*$ is shown to be an open and dense submanifold of $S(n, p)$ with dimension $np - p(p-1)/2$.
  • Riemannian Geometry: A geodesically complete Riemannian manifold structure is established for $S(n, p)^*$, with analytical forms for geodesics, parallel transport, exponential/logarithmic maps, and Fréchet means.
  • Algorithm for Reduced Cholesky Factor: An algorithm is provided to compute the reduced Cholesky factor.
  • LRC Algorithm Performance: The LRC algorithm, used for estimating principal eigenspaces from noisy covariance matrices, demonstrates superior performance over dPCA and EigenV-ave methods, especially under higher noise levels, as shown in simulation results (Table 1 and Figures 3 & 4).

Limitations and Future Work

  • "Restricted" Nature: While $S(n, p)^*$ is dense in $S(n, p)$, it is not closed under similarity transformations. This means that if $M \in S(n, p)^*$, then $O^T M O$ is not necessarily in $S(n, p)^*$ for an orthogonal matrix $O$. The authors note this is not a detrimental effect in practice for applications where matrices arise as covariance matrices and changing bases is not feasible.
  • Comparison with Existing Geometries: The paper compares its approach to a geometry proposed in [7], noting that while [7]'s geometry covers the entire $S(n, p)$ space, its metrics are not true geodesic metrics. The authors' geometry, though restricted to $S(n, p)^*$, offers true geodesic properties and unique midpoints.
  • Future Work: The paper suggests that the developed framework has potential for further applications in statistical analysis and machine learning, particularly in areas involving low-rank matrix structures. The efficiency of the LRC algorithm in estimating eigenspaces from noisy data points to its utility in distributed learning scenarios.

Summary updated

Abstract

We introduce the manifold of restricted n×n positive semidefinite matrices of fixed rank p, denoted S (n, p)∗ . The manifold itself is an open and dense submanifold of S (n, p), the manifold of n × n positive semidefinite matrices of the same rank p, when both are viewed as manifolds in Rn×n . This density is the key fact that makes the consideration of S (n, p)∗ statistically meaningful. We furnish S (n, p)∗ with a convenient, and geodesically complete, Riemannian geometry, as well as a Lie group structure, that permits analytical closed forms for endpoint geodesics, parallel transports, Fre ́chet means, exponential and logarithmic maps. This task is done partly through utilizing a reduced Cholesky decomposition, whose algorithm is also provided. We produce a second algorithm from this framework to esti- mate principal eigenspaces and demonstrate its superior performance over other existing algorithms.
BibTeX
@misc{neuman2021restricted,
  author = {Ahn Martina Neuman and Yuying Xie and Qiang Sun},
  title = {{Restricted Riemannian geometry for positive semidefinite matrices}},
  year = {2021},
  eprint = {2105.14691},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.14691},
  howpublished = {OpenReview},
}
Figure