Banding Covariance Matrices Under Ordered Variables

Why Variable Order Matters

Some covariance matrices have a meaningful ordering of their variables. Measurements may be taken at successive times, at successive spatial locations, or at neighboring positions along a sequence. In such settings, variables that are far apart in the order may be expected to have weaker covariance. Banding uses this structure by setting sufficiently distant covariance entries to zero.

The order is part of the model, not a cosmetic choice. If the variables are permuted, the same numerical covariance matrix generally has a different pattern of near and distant entries. Banding is appropriate only when the chosen order represents meaningful proximity and the covariance is sufficiently small away from the diagonal.

The integer \(k\) is the bandwidth. At \(k=0\), only variances are retained; at \(k=p-1\), no entries are removed. The estimate \(B_k(A)\) is defined by its entries; it is not guaranteed to be positive semidefinite, even when \(A\) is. We focus here on the statistical effect of truncation and do not address repairs that may be needed for downstream uses.

A Bandable Covariance Assumption

For a covariance matrix \(\Sigma=(\sigma_{ij})\), small individual distant entries are not by themselves enough to control the total truncation error: many small entries can accumulate. A useful assumption bounds the sum of their absolute values in each row.

This is a structural assumption about the ordered variables. It does not say that the covariance matrix is exactly banded: it permits nonzero entries at every distance, provided their rowwise tails decay. The next result converts that tail condition into a squared-Frobenius bound for the entries discarded by banding.

Proof. Fix a row \(i\), and let \(T_i=\{j:|i-j|>k\}\). By the bandable condition, \(\sum_{j\in T_i}|\sigma_{ij}|\leq Mk^{-\alpha}\). Every summand satisfies \(|\sigma_{ij}|\leq Mk^{-\alpha}\), since it is nonnegative and no larger than the sum. Therefore, $$ \sum_{j\in T_i}\sigma_{ij}^2 \leq \left(\max_{j\in T_i}|\sigma_{ij}|\right)\sum_{j\in T_i}|\sigma_{ij}| \leq M^2k^{-2\alpha}. $$ If \(T_i\) is empty, the left side is zero and the same bound holds. Summing this row bound over all \(p\) rows gives the stated inequality. \(\square\)

Estimating by Banding the Sample Covariance

Suppose \(X_1,\ldots,X_n\) are independent observations from a \(p\)-variate normal distribution with mean vector \(\mu\) and covariance matrix \(\Sigma\). Define the usual centered sample covariance matrix $$ S=\frac{1}{n-1}\sum_{r=1}^n(X_r-\bar X)(X_r-\bar X)^\mathsf{T}, \qquad \bar X=\frac{1}{n}\sum_{r=1}^nX_r, $$ and the banded estimator \(\hat{\Sigma}_k=B_k(S)\). The sample covariance is unbiased, so the retained entries estimate their corresponding population covariances without bias. The entries removed by banding contribute truncation bias.

Proof. For any retained position \((i,j)\), \(E[S_{ij}]=\sigma_{ij}\). Under the stated multivariate normal model, $$ \operatorname{Var}(S_{ij})=\frac{\sigma_{ii}\sigma_{jj}+\sigma_{ij}^2}{n-1} \leq\frac{2v^2}{n-1}. $$ The inequality follows because \(\sigma_{ii}\sigma_{jj}\leq v^2\) and, by Cauchy–Schwarz for covariances, \(\sigma_{ij}^2\leq\sigma_{ii}\sigma_{jj}\leq v^2\).

At each retained position, the expected squared error is its variance, since \(S_{ij}\) is unbiased. At each removed position, \([\hat{\Sigma}_k]_{ij}=0\), so its squared error is \(\sigma_{ij}^2\). The squared Frobenius norm is the sum of squared entrywise errors, and expectation commutes with this finite sum. Consequently, $$ E\|\hat{\Sigma}_k-\Sigma\|_F^2 =\sum_{|i-j|\leq k}\operatorname{Var}(S_{ij}) +\sum_{|i-j|>k}\sigma_{ij}^2. $$ There are \(p+2\sum_{d=1}^k(p-d)\leq p(2k+1)\) retained positions. Applying the variance bound to that sum and the preceding truncation-bias result to the second sum proves the theorem. \(\square\)

The first term in the risk bound decreases as the bandwidth grows: retaining more entries reduces truncation bias. The second term increases with bandwidth: more noisy sample covariance entries are retained. This is the bias-variance tradeoff for banding. The bound is an upper bound, not a guarantee that the actual risk is minimized at its optimizer; in particular, it relies on the assumed tail decay and the Gaussian variance calculation.

Interpreting and Using the Estimator

Banding is useful when the variable order has scientific meaning and distant variables are expected to have weak aggregate covariance. In longitudinal data, for example, measurements far apart in time may be less strongly associated than nearby measurements. In that setting, the retained entries can capture local dependence while avoiding the estimation of every distant covariance.

The rate terms also explain how the bandwidth should respond to sample size and tail decay. A larger \(n\) lowers the variance cost of retaining entries, while a slower tail decay (smaller \(\alpha\)) makes truncation more costly and can favor a wider band. The numerical bound gives one way to compare candidate bandwidths when its assumptions and constants are credible. It should not be read as proof that the true covariance has exactly zero entries outside the chosen band.

Common Mistake

A common mistake is to assume that banding is invariant to reordering the variables. It is not. If a permutation moves two strongly related measurements far apart, banding can delete their covariance; if it places unrelated variables next to one another, it can retain noisy entries between them. The correction is to specify the order from the scientific structure first, then define distance and bandwidth in that order. Another mistake is to call \(B_k(S)\) an unbiased estimator of all of \(\Sigma\): its retained entries are unbiased, but its omitted entries have expectation zero and introduce bias whenever the corresponding population covariances are nonzero.