Block-Sparse Covariance with Cross-Block Links

Why Add Cross-Block Links?

A block-diagonal covariance model treats entire groups of measurements as independent. That is useful when the groups truly have no cross-covariance, but can be too restrictive when a small number of relationships connect them. A block-sparse covariance model keeps the zero pattern for most cross-group pairs while permitting selected links. It can represent, for example, measurements organized by site where only neighboring sites are allowed to share covariance.

The key distinction is between an allowed covariance and a covariance that is required to be nonzero. A sparse pattern specifies which entries may be estimated freely and which must be zero. An allowed entry can still have an estimate of zero. Requiring it to be strictly nonzero would add a separate, non-closed constraint and would change the likelihood optimization problem.

Equivalently, form a graph with one vertex for each block and an edge between blocks whose cross-covariance is allowed. The graph records the block-level zero pattern; it does not by itself guarantee positive definiteness. If block \(a\) has size \(p_a\), the number of free covariance parameters before imposing positive definiteness is \(\sum_a p_a(p_a+1)/2+\sum_{(a,b)\in E}p_ap_b\). Every cross-block edge contributes all \(p_ap_b\) entries of its cross-covariance matrix under this definition.

Constructing and Checking a Block-Sparse Matrix

A proposed covariance matrix must satisfy both parts of the model: its forbidden cross-block entries must be zero, and it must be positive definite. Positive diagonal blocks alone do not suffice. A useful sufficient check for a concrete matrix is strict diagonal dominance: a symmetric matrix with positive diagonal entries and each diagonal entry greater than the sum of the absolute values of the other entries in its row is positive definite. This follows, for example, from the eigenvalue bounds for symmetric matrices.

Gaussian Likelihood and Its Score Equations

Suppose \(X_1,\ldots,X_n\) are independent and identically distributed \(N_p(\mu,\Sigma)\), with the block-sparse restriction imposed on \(\Sigma\). If the mean is unrestricted, its maximum-likelihood estimate is the sample mean \(\bar X\). For the covariance likelihood, use the centered sample covariance with divisor \(n\), \(S=n^{-1}\sum_{i=1}^n(X_i-\bar X)(X_i-\bar X)^\mathsf{T}\). For a known mean, replace \(\bar X\) in this definition by that known mean. Up to a constant independent of \(\Sigma\), the log-likelihood is

For a general sparse pattern, the likelihood estimates are coupled: changing one allowed covariance can change the determinant and inverse of the full matrix. The next result gives the necessary score equations for an interior maximum.

Proof. For a symmetric perturbation \(H\), the differential identities are \(d\log\det(\Sigma)=\operatorname{tr}(\Sigma^{-1}H)\) and \(d\Sigma^{-1}=-\Sigma^{-1}H\Sigma^{-1}\). Substitution into the log-likelihood gives

The matrix \(G\) is symmetric. Varying one diagonal parameter gives \(H_{ii}=1\), with all other entries zero, so \(d\ell=(n/2)G_{ii}\). Varying one allowed off-diagonal parameter gives \(H_{ij}=H_{ji}=1\), so \(d\ell=(n/2)(G_{ij}+G_{ji})=nG_{ij}\). Each allowed coordinate can vary in both directions locally at an interior positive-definite matrix. At an interior maximum its directional derivative must therefore be zero, proving the stated equations. A forbidden entry cannot be varied in the model, so the same argument gives no equation for it. \(\square\)

These equations are necessary, not a universal closed-form solution or a guarantee that a finite maximum exists. In practice, a general block-sparse likelihood fit must optimize the displayed likelihood over the positive-definite matrices with the specified zeros. The score equations also explain why simply copying the allowed entries from \(S\) is generally wrong.

When the Likelihood Estimate Is Blockwise

There is an important special case with an exact blockwise answer. Suppose the covariance is block diagonal across a collection of independent groups, and within each group every covariance entry is unrestricted. The likelihood separates by group. If the sample covariance within each group is positive definite, it is that group's maximum-likelihood estimate. Positive definiteness is essential: a singular sample covariance cannot be used as a covariance parameter in the positive-definite model.

Proof. Let \(\lambda_1,\ldots,\lambda_p\) be the positive eigenvalues of \(S^{-1/2}\Sigma S^{-1/2}\). The difference between the negative log-likelihood objective \(\log\det(\Sigma)+\operatorname{tr}(S\Sigma^{-1})\) at \(\Sigma\) and at \(S\) is \(\sum_{j=1}^p(\log\lambda_j+1/\lambda_j-1)\). For \(\lambda>0\), the function \(\log\lambda+1/\lambda-1\) is nonnegative: its derivative is \((\lambda-1)/\lambda^2\), so it decreases up to \(1\), increases thereafter, and equals zero at \(1\). Equality in the sum holds only when every \(\lambda_j=1\), or \(\Sigma=S\). Thus \(S\) uniquely maximizes the likelihood.

If \(S\) is singular, choose an orthonormal basis in which \(S\) is diagonal with at least one zero eigenvalue. In that basis take \(\Sigma\) diagonal with variance \(\varepsilon\) in each zero-eigenvalue direction and fixed positive variances in the other directions. As \(\varepsilon\downarrow0\), the log-determinant contribution for each such direction is \(\log\varepsilon\to-\infty\), while the trace contribution in that direction is zero. The negative log-likelihood tends to \(-\infty\), so the likelihood is unbounded above and has no attained maximum over positive-definite \(\Sigma\). \(\square\)

A Linked Path: Why Allowed Sample Covariances Are Not the Estimates

Once selected links join blocks within a sparse pattern, the likelihood usually does not separate into independent unrestricted pieces. The following calculation illustrates the score equations directly. It uses known unit marginal variances to keep the covariance model to two free parameters; this is a special case designed to expose the effect of a forbidden covariance.

Common Pitfalls and Practical Implications

• Equating allowed with nonzero. An allowed cross-block entry is a free parameter; a fitted value of zero is still compatible with the model. A zero pattern ordinarily describes fixed zeros, not a promise that every permitted entry is nonzero.
• Assuming positive diagonal blocks ensure a valid covariance. Cross-block entries can make the full matrix indefinite. Check positive definiteness of the full matrix, not just its diagonal blocks.
• Copying allowed entries from the sample covariance. This works for an unrestricted covariance block with a positive-definite sample covariance, not generally for a sparse pattern that imposes additional zeros. The full inverse in the score equations couples the free parameters.
• Using a singular sample covariance as an estimate. A covariance parameter in the Gaussian model must be positive definite. In the unrestricted likelihood, singular \(S\) means the likelihood has no attained maximum, not that the singular \(S\) is an admissible estimate.
• Treating zero score as proof of a maximum. Score equations identify stationary points in the allowed coordinates. They do not by themselves establish a global maximum or existence; the constrained likelihood must be checked or optimized appropriately.

The block graph is valuable because it expresses scientific assumptions in a compact form and reduces the number of free parameters. Its practical benefit depends on getting both the pattern and the likelihood right: zeros encode the intended restrictions, while positive definiteness ensures the result remains a valid covariance matrix. With independent unrestricted groups, estimates are available block by block; with selected links inside a sparse pattern, the likelihood equations generally require joint fitting.