Why Naive Covariance Bandeding Can Fail

Why Zeroing Entries Is Not Automatically Safe

A covariance matrix must be positive semidefinite: every linear combination of the variables has nonnegative variance. If the matrix is positive definite, every nonzero linear combination has strictly positive variance, and the matrix is invertible. These properties matter in structured covariance analysis because calculations such as Gaussian likelihoods require a valid covariance matrix, and often its inverse as well.

Hard banding imposes a pattern by setting entries outside a chosen band to zero. It can be tempting to assume that this harmlessly simplifies a covariance estimate, especially when the starting estimate is itself a valid covariance matrix. The difficulty is that positive semidefiniteness is a joint constraint on all the entries. Keeping some covariances while deleting others can break that constraint.

A sample covariance matrix \(S\) is positive semidefinite, since for every vector \(x\), its quadratic form is a sample variance. But that fact applies to \(S\), not automatically to \(B_k(S)\). The following example shows the distinction even when the input is positive definite.

Conditions That Guarantee a Safe Result

There is no general guarantee from the input matrix alone: the counterexample starts with a positive-definite matrix. There are, however, useful conditions on the result or on the operation that do guarantee positive semidefiniteness or positive definiteness.

Proof. For any real vector \(x\), symmetry and \(2|x_i x_j|\leq x_i^2+x_j^2\) imply $$ \begin{aligned} x^\mathsf{T}Ax &=\sum_i A_{ii}x_i^2+2\sum_{i<j}A_{ij}x_ix_j\\ &\geq \sum_i A_{ii}x_i^2-2\sum_{i<j}|A_{ij}|\,|x_i x_j|\\ &\geq \sum_i\left(A_{ii}-\sum_{j\ne i}|A_{ij}|\right)x_i^2. \end{aligned} $$ Every coefficient in the last sum is strictly positive. Therefore, if \(x\ne 0\), at least one \(x_i^2\) is positive and \(x^\mathsf{T}Ax>0\). This is the definition of positive definiteness. \(\square\)

This condition is sufficient, not necessary: a positive-definite matrix need not be diagonally dominant. For a banded estimate, the row sums in the condition involve only the retained entries, so the test is straightforward to apply after banding.

A second guarantee concerns the masking operation itself. Write \(M\) for a symmetric mask with \(M_{ij}=1\) when an entry is retained and \(M_{ij}=0\) when it is deleted. Entrywise masking is the Hadamard product \(S\circ M\), whose \((i,j)\) entry is \(S_{ij}M_{ij}\). The Schur product theorem says that the Hadamard product of two positive-semidefinite matrices is positive semidefinite.

Proof. Since \(M\) is positive semidefinite, write \(M=UU^\mathsf{T}\), and let \(u_\ell\) be column \(\ell\) of \(U\). Define \(D_\ell\) to be the diagonal matrix whose diagonal is \(u_\ell\). Then \(M_{ij}=\sum_\ell (u_\ell)_i(u_\ell)_j\), so entry by entry, $$ S\circ M=\sum_\ell D_\ell S D_\ell. $$ For any \(x\), each term has quadratic form $$ x^\mathsf{T}D_\ell S D_\ell x=(D_\ell x)^\mathsf{T}S(D_\ell x)\geq 0, $$ because \(S\) is positive semidefinite. Summing these nonnegative quantities proves that \(x^\mathsf{T}(S\circ M)x\geq 0\) for all \(x\), as required. \(\square\)

A hard-band mask is not always positive semidefinite. For three variables and bandwidth one, it is $$ M= \begin{pmatrix} 1&1&0\\ 1&1&1\\ 0&1&1 \end{pmatrix}. $$ The vector \((1,-\sqrt{2},1)^\mathsf{T}\) is an eigenvector with eigenvalue \(1-\sqrt{2}<0\). Thus the Schur product theorem cannot provide a general guarantee for this hard-band mask. The counterexample above shows that this failure of the mask condition can matter in practice.

Practical Repairs and Checks

When the row-sum condition does not hold, it does not prove that the banded matrix is indefinite; it means only that this particular guarantee is unavailable. One can check positive definiteness directly using eigenvalues or, for a symmetric matrix, Sylvester’s criterion. A failed check should be treated as a substantive issue rather than ignored because the original sample covariance was valid.

Another simple safe case is when the covariance matrix is already banded in the chosen ordering: then \(B_k(S)=S\), and the operation cannot introduce a failure. More generally, if the matrix produced by banding satisfies the strict diagonal-dominance condition, positive definiteness follows from the theorem. These are conditions to verify, not conclusions that follow merely from choosing a bandwidth.

Why the Failure Matters

An indefinite banded estimate is not a valid covariance matrix. In particular, it assigns a negative value to the quadratic form for some linear combination, which cannot be a variance. If a downstream calculation needs a determinant, inverse, or Gaussian covariance model, the failure can make that calculation undefined or misleading. Positive semidefiniteness is the minimum validity requirement; positive definiteness is additionally needed for ordinary matrix inversion and a nonsingular Gaussian density.

The ordering also matters. Banding keeps covariances between nearby indices and discards those between distant indices. Reordering the variables changes which entries are discarded and can change the result’s definiteness. A sensible ordering may be important for the scientific structure, but it is not by itself a mathematical guarantee.

• Mistake: “The sample covariance is positive semidefinite, and banding only replaces some entries by zero, so the result must remain positive semidefinite.”
• Correction: Positive semidefiniteness constrains entries jointly. Replacing entries changes the quadratic form, and the explicit three-variable example produces a negative eigenvalue.
• Useful safeguards: Confirm the input is already banded, verify a sufficient condition such as strict diagonal dominance, or explicitly check the eigenvalues or principal minors of the resulting matrix. If altering the diagonal is acceptable, diagonal loading can be chosen to exceed the magnitude of the most negative eigenvalue.