Introduction
In statistical modeling and signal processing, the structure of covariance matrices often reflects underlying dependencies between variables. Specifically, when certain variables are known to be conditionally independent, the corresponding entries in the covariance matrix (or its inverse) are constrained to be zero. These constraints define a convex cone of positive semidefinite (PSD) matrices, denoted as $\mathcal{S}_+(G)$, where $G$ is a graph representing the sparsity pattern.
A central challenge in working with these matrices is finding an efficient and expressive parametrization. This paper investigates a class of polynomial maps, $\phi_\Delta$, which attempt to represent $\mathcal{S}_+(G)$ using parameters associated with a simplicial complex $\Delta$. This approach is particularly relevant for Gaussian statistical models involving hidden (latent) variables.
The Simplicial Parametrization
The authors define a map $\phi_\Delta$ that constructs a PSD matrix by summing outer products of vectors whose supports are determined by the faces of a simplicial complex $\Delta$. Formally, if $\Delta$ is a simplicial complex on the vertex set $[m]$, the map is defined as: $$\phi_\Delta(x) = \sum_{F \in \Delta} x_F x_F^T$$ where $x_F$ is a vector that is non-zero only on the indices in $F$. The image of this map, $\text{im}(\phi_\Delta)$, is always a convex cone contained within $\mathcal{S}_+(G)$. The fundamental question addressed is: under what conditions does $\text{im}(\phi_\Delta)$ actually cover the entire cone $\mathcal{S}_+(G)$?
The Role of Chordality
The study's primary theoretical contribution establishes a strict link between the geometry of the graph $G$ and the surjectivity of the parametrization. A graph is chordal if every cycle of length four or more has a "chord" (an edge connecting two non-adjacent vertices of the cycle).
The authors prove that the map $\phi_\Delta$ is surjective onto the cone $\mathcal{S}_+(G)$ if and only if:
- The graph $G$ is chordal.
- The simplicial complex $\Delta$ is the clique complex of $G$.
This result generalizes classical findings in matrix completion. It implies that for any graph containing a "hole" (a chordless cycle), there exist valid PSD matrices with the required zeros that cannot be represented by this simplicial parametrization.
Characterizing Chordless Cycles
For non-chordal graphs, the image of $\phi_\Delta$ is a proper subset of the PSD cone. The authors provide a detailed semi-algebraic description for the case where $G$ is a chordless cycle $C_m$.
Theorem 5.3 provides the exact condition for a matrix $\Sigma$ to lie within the image of the map for a cycle. The matrix must satisfy a specific inequality involving its diagonal entries and its matchings: $$\sum_{M \in \mathcal{M}(C_m)} (-1)^{|M|} \prod_{\{i,j\} \in M} \sigma_{ij}^2 \prod_{i \in [m] \setminus M} \sigma_{ii} \ge 2 \prod_{i=1}^m |\sigma_{i,i+1}|$$ where $\mathcal{M}(C_m)$ represents the set of all matchings of the cycle. This inequality suggests that the "cycle-product" of the off-diagonal entries cannot be too large relative to the diagonal entries if the matrix is to be representable via the simplicial complex.
Numerical Analysis and Volume Ratios
To quantify the "gap" between the image of the map and the full PSD cone, the authors conducted Monte Carlo simulations. By generating 100,000 random matrices for cycle lengths $m=3$ to $7$, they estimated the "spherical volume" of the reachable set compared to the total valid space.
Interestingly, while the parametrization is never surjective for cycles, the "coverage" increases with the size of the cycle. For a 3-cycle ($K_3$), the map covers approximately 78.5% of the valid PSD space. This ratio grows steadily as the cycle length increases, reaching over 99% for a 7-cycle ($C_7$). This suggests that while the theoretical gap exists, the practical limitation might diminish as the sparsity pattern becomes more complex or sparse.
Statistical Implications and Conclusion
The maps $\phi_\Delta$ are not merely abstract constructions; they correspond to Gaussian models where observed variables are influenced by independent latent factors. Each face in the simplicial complex represents a hidden variable that affects a specific subset of observed variables.
The finding that these models cannot represent all PSD matrices for non-chordal graphs has significant implications for latent variable modeling. It suggests that certain covariance structures cannot be explained by independent hidden factors if the underlying dependency graph contains cycles. Future work remains to extend the explicit semi-algebraic descriptions to more complex non-chordal graphs and to further explore the statistical consequences of these "unreachable" covariance states.
Summary updated