Consistency Regimes for Growing Dimension and Sparsity

Consistency Depends on the Norm

When the number of variables \(p\) grows with the sample size \(n\), an estimator can be accurate in one matrix norm and inaccurate in another. Frobenius error aggregates discrepancies across all entries, while operator error measures the largest change in a direction. Sparsity can make thresholding effective, but its guarantees also depend on how many nonzero covariances can occur in each row.

The conditions below are sufficient regimes, not universal necessary-and-sufficient characterizations. They use a common set of assumptions to compare sample covariance, linear shrinkage, and entrywise thresholding without implying that any one estimator is consistent in every high-dimensional setting.

Assume for the rate comparisons that \(X_1,\ldots,X_n\) are independent copies of a mean-zero \(p\)-vector \(X\) with covariance \(\Sigma\), and that the eigenvalues of \(\Sigma\) are bounded above by a constant \(M\) independent of \(p\). For operator-norm concentration, also assume a dimension-free bound on all standardized linear projections: \(\sup_{\|u\|_2=1}\|u^\top X\|_{\psi_2}\leq K\), for a constant \(K\) independent of \(p\). This is stronger than requiring each individual coordinate to be sub-Gaussian. The sample covariance in this comparison is \(S=n^{-1}\sum_{i=1}^n X_iX_i^\top\), using the known zero mean.

Sample Covariance: Two Different Dimension Conditions

Under these assumptions, sample covariance has the following rates:

For the operator bound, fix a unit vector \(u\). The projection \(u^\top X\) is sub-Gaussian with a dimension-free bound, and its variance is at most \(M\). Thus \((u^\top X)^2-E[(u^\top X)^2]\) has a sub-exponential norm bounded by a constant depending only on \(K\) and \(M\). Bernstein's inequality gives constants \(c,C>0\) such that \[ P\left(\left|u^\top(S-\Sigma)u\right|>t\right) \leq 2\exp\{-cn\min(t^2,t)\}. \]

To control all directions, take a \(1/4\)-net \(\mathcal N\) of the unit sphere with at most \(9^p\) points. For a symmetric matrix \(A\), approximation of a maximizing unit vector by a net point gives \(\|A\|_{\mathrm{op}}\leq 2\max_{u\in\mathcal N}|u^\top A u|\). A union bound therefore shows that, for a sufficiently large constant \(C_1\), the probability that \[ \|S-\Sigma\|_{\mathrm{op}}> C_1\left(\sqrt{\frac{p+x}{n}}+\frac{p+x}{n}\right) \] is at most \(2e^{-x}\). Taking, for example, \(x=p\) gives the asserted operator rate. For the Frobenius bound, each entry has variance at most \(C_2/n\), since the sub-Gaussian projection assumption bounds fourth moments and hence \(E[X_j^2X_k^2]\) uniformly. Summing over \(p^2\) entries gives \(E\|S-\Sigma\|_F^2\leq C_2p^2/n\); Markov's inequality yields the stated rate. \(\square\)

These conditions differ because the Frobenius norm accumulates error over many entries. The operator bound instead controls the maximum error over directions; its proof pays for a net whose size grows exponentially in \(p\).

Linear Shrinkage: The Target Matters

A linear shrinkage estimator combines the sample covariance with a target \(T\): \(\hat\Sigma_{\alpha}=(1-\alpha)S+\alpha T\), where \(0\leq\alpha\leq1\) may depend on \(n\) and \(p\). Its error has the exact decomposition \[ \hat\Sigma_\alpha-\Sigma=(1-\alpha)(S-\Sigma)+\alpha(T-\Sigma). \] For either norm, the triangle inequality gives \[ \|\hat\Sigma_\alpha-\Sigma\| \leq(1-\alpha)\|S-\Sigma\|+\alpha\|T-\Sigma\|. \] This bound makes the role of shrinkage precise: it can reduce the contribution from sample noise, but its target contributes its own approximation error.

For targets such as a scalar multiple of the identity, a small operator discrepancy does not necessarily mean a small Frobenius discrepancy: repeating a modest discrepancy across \(p\) diagonal entries can produce a Frobenius error of order \(\sqrt p\). This is why a shrinkage method cannot be declared consistent without specifying both the target and the norm.

Thresholding: Sparsity Changes the Regime

Suppose each row of \(\Sigma\) has at most \(s_p\) nonzero off-diagonal entries. Define a hard-thresholded estimator by leaving the diagonal of \(S\) unchanged and setting \(S_{jk}\) to zero when \(|S_{jk}|\leq\lambda\), for \(j\ne k\). With uniformly sub-Gaussian projections and bounded covariance eigenvalues, entrywise concentration and a union bound give \[ \max_{j,k}|S_{jk}-\Sigma_{jk}| =O_p\left(\sqrt{\frac{\log p}{n}}\right) \] when \(\log p/n\to0\). Choose \(\lambda=A\sqrt{\log p/n}\) for a sufficiently large fixed \(A\).

To see these bounds, work on the event that the largest entrywise sampling error is at most \(C\sqrt{\log p/n}\). For a true zero off-diagonal entry, a threshold larger than that error removes the entry. For a true nonzero off-diagonal entry, the thresholded estimate differs from the truth by at most the sampling error plus the threshold. Each row has at most \(s_p\) such entries. The diagonal is not thresholded, so its error must also be counted: there is one diagonal error per row. The maximum absolute row sum of the error is therefore at most \(C'(s_p+1)\sqrt{\log p/n}\). For a symmetric matrix the operator norm is bounded by the maximum absolute row sum, proving the operator rate.

The same event gives an entrywise error bounded by \(C'\sqrt{\log p/n}\), with at most \(p(s_p+1)\) potentially nonzero errors: at most \(ps_p\) off-diagonal errors and \(p\) diagonal errors. Summing their squares and taking a square root proves the Frobenius rate. Since the event has probability tending to one under the concentration assumption, both bounds hold in probability. \(\square\)

Reading the Regimes Correctly

The three estimators rely on different sources of structure. Sample covariance needs dimension to grow slowly enough relative to sample size. A shrinkage estimator additionally needs its target to be close enough in the chosen norm, or its weight to diminish enough to suppress target bias. Thresholding trades a potentially larger dimension for a sparse covariance structure, with the row sparsity \(s_p\) controlling the operator bound.

A useful comparison is:

A common mistake is to use coordinatewise sub-Gaussianity as though it automatically gave operator-norm covariance concentration. It does not: concentration must control all linear projections, or another condition with the same effect must be imposed. A second mistake is to count only off-diagonal support when bounding thresholding error. Because the diagonal is left unthresholded, its errors remain even when \(s_p=0\); the safe general operator rate contains \(s_p+1\), not \(s_p\).

Finally, an \(O_p\) rate that tends to zero establishes consistency, but a sufficient condition that fails does not by itself establish inconsistency. Conversely, consistency in operator norm does not imply consistency in Frobenius norm when \(p\) grows. The norm, the target error, and the structural assumptions must all be checked separately.