Global Identifiability of Simple Cyclic Graphs

We present Macaulay2 sessions proving that \(A(\Sigma)_{\cdot,E}\) is full rank for every \(\Sigma \in \mathrm{PD}_p\) for almost all \(G=(V,E)\) complete and up to \(p=5\) nodes. This does not only prove global identifiability, but also that \(\mathcal{M}_{G,C}=\mathrm{PD}_p\), see Corollary 4.4. Proposition 2.6. and Proposition 2.8. show that global identifiability is inherited by the subgraphs of a gloabally identifiable graph. The direct approach using \(A(\Sigma)\) can be found in SimpleCyclicASigma and the approach using the kernel \(H(\Sigma)\) can be found in SimpleCyclicKernel. Both require downloading LyapunovModel.

We illustrate the computations using the graph in Example 5.1. The graph is a completion of the 4-cycle such that \(|E|=p(p+1)/2\) and is displayed below.

alternate text

Using the Cholesky decomposition of \(\Sigma=LL^{\top}\), we factor \(\det A(\Sigma)\).

-- Completion of 4-cycle, ASigma --
restart
loadPackage "LyapunovModel"

-- completion of the 4-cycle

G=digraph {{1, 2}, {1, 3}, {2, 3}, {2,  4}, {3, 4}, {4, 1}}
(R,M,SL,S)=lyapunovDataPD G
AS=ASigmaGraphPD(G)
F=extractFactors(factor det AS) --factors det AS
netList F

Some factors, as the determinant of the positive-definite \(\Sigma\), are obviously non-vanishing. For the critical factor we compute the SOS decomposition, list the generators and search for one that is non-negative due to the positive-definiteness of \(\Sigma\). In this example, it is \(l_{2,2} l_{3,3} l_{4,4}>0\).

--SOS decomposition of relevant factor of the determinant
F_4
loadPackage "SemidefiniteProgramming"
loadPackage "SumsOfSquares"
sol=solveSOS F_4
s=sosPoly sol
netList s#generators
--l_(2,2)l_(3,3)l_(4,4)>0

Alternatively, it is possible to use the kernel to prove global identifiability of the completion of the 4-cycle. We calculate \(\det(H(\Sigma)_{E^c,\cdot})\), which is exactly the critical factor of \(\det(A(\Sigma)_{\cdot,E})\) we observed in the previous code chunk.

-- Completion of 4-cycle, kernel --

--compute restricted kernel
kernE=(syz A)^(kernelPattern G);
f=det kernE;
F=extractFactors factor f;
netList F
F_2

sol=solveSOS F_2
s=sosPoly sol
peek s
netList s#generators
--l_(2,2)l_(3,3)l_(4,4)>0


--Check that it is a proper SOS decomposition
F_2==sum apply(s#generators,s#coefficients,(i,j)->i^2*j)

These examples were computed using Macaulay2, version 1.17, on a Surface Pro (2017) with a 2,6 GHz Intel Core i5-7300U processor and 8 GB.