On a Parametrization of Positive Semidefinite Matrices with Zeros

Mathias Drton, Josephine Yu

TL;DR

This paper introduces a new way to represent positive semidefinite matrices with specific zero entries, inspired by statistical models. They provide a detailed characterization of the images of these parametrizations, particularly for matrices associated with chordless cycles, which has implications for understanding statistical models and covariance structures.

What Problem Does This Paper Address?

In statistics and machine learning, covariance matrices play a crucial role in modeling relationships between variables. Positive semidefinite matrices form the set of all possible covariance matrices. Often, we are interested in covariance matrices that exhibit a specific pattern of zeros, indicating conditional independence between variables. These patterns are naturally represented by graphs. The paper addresses the challenge of parametrizing these structured positive semidefinite matrices. Specifically, they investigate a class of polynomial maps that generate these matrices and aim to understand precisely which matrices can be generated by these maps (i.e., the image of the map). This is important for tasks like statistical inference and understanding the algebraic properties of graphical models.

Methods

The core of the paper revolves around defining and analyzing a polynomial map, denoted $\Phi_\Delta$, associated with a simplicial complex $\Delta$. A simplicial complex is a collection of subsets (faces) of a ground set (here, indices of a matrix) that is closed under taking subsets. The map $\Phi_\Delta$ takes a vector of parameters indexed by the faces of $\Delta$ and produces a symmetric matrix. The key properties investigated are:

  • Image Characterization: Determining the set of all matrices that can be produced by $\Phi_\Delta$.
  • Convexity: Showing that the image of $\Phi_\Delta$ is always a convex cone.
  • Surjectivity: Identifying when $\Phi_\Delta$ can generate all positive semidefinite matrices with the specified zero pattern (i.e., the graphical cone $S_{\ge 0}(G)$). This is shown to occur if and only if the underlying graph is chordal and $\Delta$ is its clique complex.
  • Semi-algebraic Description: For specific cases, particularly chordless cycles, the paper derives explicit semi-algebraic conditions that a matrix must satisfy to be in the image of $\Phi_\Delta$. This involves analyzing determinants and solving systems of polynomial equations.
  • Statistical Connection: The paper connects these parametrizations to Gaussian statistical models with hidden variables, where the parameters of the map correspond to variances and relationships of these hidden variables.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and characterizations rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Geometric Interpretation of Statistical Models: The parametrization $\Phi_\Delta$ provides a geometric and algebraic lens through which to view certain Gaussian statistical models, linking covariance structures to simplicial complexes.
  • Chordality is Key for Surjectivity: The paper rigorously establishes that for the parametrization to cover the entire graphical cone of positive semidefinite matrices, the underlying graph must be chordal (meaning it doesn't contain induced cycles of length 4 or more), and the simplicial complex must be the clique complex of that graph.
  • Chordless Cycles as a Test Case: The analysis of chordless cycles is particularly insightful. It reveals that even for simple structures, the image of the parametrization is a proper subset of the graphical cone, and the condition for a matrix to be in the image is non-trivial, involving determinants and specific sign patterns.
  • Connection to Matrix Properties: The paper demonstrates how properties of the generated matrices (like their determinants and Schur complements) are directly related to the parameters of the map and the structure of the simplicial complex.

Key Results

  • The image of the parametrization $\Phi_\Delta$ is always a convex cone.
  • $\Phi_\Delta$ is surjective onto the graphical cone $S_{\ge 0}(G)$ if and only if $G$ is chordal and $\Delta$ is its clique complex.
  • A precise semi-algebraic description of the image of $\Phi_\Delta$ is given for chordless cycles $C_m$. This condition involves a determinantal inequality related to the matrix entries and their negations.
  • The paper shows that for a matrix $\Sigma$ to be in the image of the parametrization for $C_m$, its determinant and the determinant of $\Sigma$ with specific off-diagonal entries negated must both be non-negative.

Limitations and Future Work

  • Generality of Parametrization: The paper focuses on a specific class of parametrizations. While motivated by statistical models, other parametrizations might exist.
  • Complexity of Chordless Cycle Condition: The derived semi-algebraic condition for chordless cycles, while explicit, can be computationally intensive to check for large matrices.
  • Future Work: The authors suggest exploring the connection to statistical models further, particularly for computing maximum likelihood estimates and constructing prior distributions. They also hint at extending the semi-algebraic descriptions to other graph classes and investigating the properties of the fibers of these maps. The paper also mentions that the spherical volume of the image of $C_m$ can be computed using Monte Carlo integration, suggesting further geometric analysis.

Summary updated

Abstract

We study a class of parametrizations of convex cones of positive semidefinite matrices with prescribed zeros. Each such cone corresponds to a graph whose nonedges determine the prescribed zeros. Each parametrization in this class is a polynomial map associated with a simplicial complex supported on cliques of the graph. The images of the maps are convex cones, and the maps can only be surjective onto the cone of zero-constrained positive semidefinite matrices when the associated graph is chordal and the simplicial complex is the clique complex of the graph. Our main result gives a semialgebraic description of the images of the parametrizations for chordless cycles. The work is motivated by the fact that the considered maps correspond to Gaussian statistical models with hidden variables.
BibTeX
@article{drton2010parametrization,
  author = {Mathias Drton and Josephine Yu},
  title = {{On a Parametrization of Positive Semidefinite Matrices with Zeros}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2010},
  doi = {10.1137/100783170},
}
Figure