Geometric mean of partial positive definite matrices with missing entries

Hayoung Choi, Sejong Kim, Yuanming Shi

TL;DR

This paper extends the concept of the geometric mean—traditionally used for full positive definite matrices—to "partial" matrices with missing entries. By leveraging graph theory and maximum determinant completions, the authors provide a framework for averaging incomplete covariance matrices, a common challenge in signal processing and computer vision.

What Problem Does This Paper Address?

In fields like statistics, signal processing, and image analysis, data is often represented as Positive Definite (PD) matrices (e.g., covariance matrices). The "geometric mean" is a powerful tool for averaging these matrices because it respects their underlying non-Euclidean geometry.

However, real-world data is frequently incomplete. Sensors fail, or certain measurements are simply unavailable, resulting in "partial" matrices where some entries are missing. Standard techniques often involve deleting incomplete records, which wastes valuable information. The authors tackle the fundamental question: How do we calculate a mathematically rigorous geometric mean for two matrices when we don't know all their values?

Methods

The authors bridge the gap between matrix analysis and graph theory through several key steps:

  1. Graph Representation: They use undirected graphs to represent the structure of a partial matrix, where edges correspond to known entries and missing edges represent unknown values.
  2. Chordal Graphs: They rely on the property of "chordality." If the graph of known entries is chordal (meaning every cycle of length four or more has a "shortcut" or chord), a positive definite completion is guaranteed to exist.
  3. Set-Based Geometric Mean: Since a partial matrix represents a set of all possible valid completions, the authors define the geometric mean of two partial matrices as the set of geometric means of all their respective completions.
  4. Maximum Determinant Completion: To find a unique representative from these sets, they use the "Maximum Determinant" approach. This specific completion is significant because it corresponds to the maximum entropy of a multivariate Gaussian distribution—essentially filling in the blanks with the "least biased" information.
  5. Loewner Order: They define a partial order for incomplete Hermitian matrices, allowing them to compare "greater than" or "less than" relationships even with missing data.

Datasets

This is primarily a theoretical mathematics paper. No large-scale real-world datasets were used for training. Instead, the authors used:

  • Synthetic Partial Matrices: Small-scale (3x3 and 5x5) matrices with variable parameters ($x, y$) to demonstrate the behavior of determinants and eigenvalues.
  • MATLAB Simulations: Used to generate 3D surface plots (Figures 1-4) that visualize how changing missing entries affects the resulting geometric mean's properties.

Key Insights and Ideas

  • The Chordal Requirement: The paper reinforces that chordal graphs are the "gold standard" for matrix completion. Without chordality, you might define a partial matrix that has no valid positive definite completion at all.
  • Entropy Connection: A major "aha" moment is the link between the geometric mean and Shannon entropy. The authors show that the difference in entropy between two Gaussian distributions can be expressed through an integral involving the geometric mean of their covariance matrices.
  • Property Breakdown: Interestingly, some properties of the standard geometric mean do not carry over to the partial case. For example, while $A \# A = A$ for full matrices, for partial matrices, the set-based mean of a partial matrix with itself is actually a superset of its original completions.
  • Uniqueness of Max-Det Mean: They prove that the maximum determinant completion of a geometric mean is uniquely determined by the maximum determinant completions of the original partial matrices.

Key Results

  • Theorem 4.1: Proves that the set of all positive semi-definite completions for a partial matrix is non-empty, convex, and compact (provided the graph is chordal).
  • Theorem 6.11: Establishes that the "best" (maximum determinant) completion of the geometric mean of two partial matrices is exactly the geometric mean of their individual "best" completions.
  • Computational Visualization: The authors demonstrate that for partial matrices $A(x)$ and $B(y)$, there exists a specific range for the missing values $x$ and $y$ that maintains positive definiteness, and within that range, the determinant is a strictly concave function with a unique maximum.

Limitations and Future Work

  • Convexity of the Mean Set: While the individual completion sets are convex, the authors note it is still an open question whether the resulting geometric mean set ($S \#_t T$) is always convex.
  • Computational Complexity: The paper focuses on the existence and properties of the mean. Implementing this for very large-scale matrices with complex missing data patterns (non-chordal graphs) remains a significant challenge.
  • Loewner Order Gaps: The authors suggest that the relationship between the maximum determinant completion and the Loewner order needs further characterization to be fully utilized in optimization problems.

Summary updated

Abstract

In this paper the geometric mean of partial positive definite matrices with missing entries is considered. The weighted geometric mean of two sets of positive matrices is defined, and we show whether such a geometric mean holds certain properties which the weighted geometric mean of two positive definite matrices satisfies. Additionally, counterexamples demonstrate that certain properties do not hold. A Loewner order on partial Hermitian matrices is also defined. The known results for the maximum determinant positive completion are developed with an integral representation, and the results are applied to the weighted geometric mean of two partial positive definite matrices with missing entries. Moreover, a relationship between two positive definite completions is established with respect to their determinants, showing relationship between their entropy for a zero-mean,multivariate Gaussian distribution. Computational results as well as one application are shown.
BibTeX
@inproceedings{choi2019geometric,
  author = {Hayoung Choi and Sejong Kim and Yuanming Shi},
  title = {{Geometric mean of partial positive definite matrices with missing entries}},
  booktitle = {Linear},
  year = {2019},
  doi = {10.1080/03081087.2019.1585741},
}
Figure