Operator-Norm Rates for Sparse Covariance Thresholding

Why Entrywise Accuracy Is Not Enough

In a high-dimensional problem, a sample covariance matrix can estimate each covariance entry accurately while still accumulating substantial error across a row. Operator norm measures the largest overall directional effect of that matrix error, so controlling it requires attention both to entrywise noise and to how many entries can matter in each row. Thresholding addresses this accumulation by removing entries that are small relative to the noise level.

For an exactly row-sparse covariance matrix, the resulting rate has a simple interpretation: it is the maximum number of nonzero entries in a row multiplied by the typical largest entrywise error. Under sub-Gaussian sampling, that entrywise scale is of order \(\sqrt{\log p/n}\), where \(p\) is the dimension and \(n\) is the sample size.

Sampling Conditions and the Thresholded Estimator

Let \(X_1,\ldots,X_n\) be independent and identically distributed mean-zero random vectors in \(\mathbb{R}^p\), with covariance matrix \(\Sigma=E[X_iX_i^\top]\). Write \(M=\max_{1\le j\le p}\Sigma_{jj}\), and assume \(0<M<\infty\). For a random variable \(Z\), define \(\|Z\|_{\psi_2}=\inf\{t>0:E[\exp(Z^2/t^2)]\le 2\}\). Assume there is a constant \(K\ge 1\) such that, for every \(u\in\mathbb{R}^p\), \(\|u^\top X_i\|_{\psi_2}\le K\sqrt{u^\top\Sigma u}\). This is a relative sub-Gaussian condition: each linear combination has a tail scale controlled by its variance.

The threshold is applied symmetrically, so \(T_\tau(S)\) is symmetric. We measure error using the operator norm \(\|A\|_{\mathrm{op}}=\sup_{\|v\|_2=1}\|Av\|_2\). The thresholding operation need not preserve positive definiteness; the result below concerns its estimation error, not a positive-definite repair.

Uniform Entrywise Concentration

The key input is a simultaneous bound on all covariance entries. The earlier material on concentration bounds for sample covariance error gives the relevant concentration principle. In precise form, for a centered sub-exponential random variable \(Y\) with \(\|Y\|_{\psi_1}\le B\), Bernstein's inequality gives \(P(|n^{-1}\sum_iY_i|>C B(\sqrt{t/n}+t/n))\le 2e^{-t}\), for a universal constant \(C\). Here \(\|Y\|_{\psi_1}=\inf\{a>0:E[\exp(|Y|/a)]\le2\}\).

To see why this bound applies, the sub-Gaussian condition with \(u=e_j\) implies \(\|X_{ij}\|_{\psi_2}\le K\sqrt M\) for each coordinate. Products of sub-Gaussian variables are sub-exponential, so \(\|X_{ij}X_{ik}-E[X_{ij}X_{ik}]\|_{\psi_1}\le C K^2M\). Apply Bernstein's inequality to each of the \(p^2\) entries of \(n^{-1}\sum_iX_iX_i^\top\), and take a union bound. With \(t=\log(4p^2/\eta)\), the resulting probability of any entrywise failure is at most \(\eta/2\), after adjusting universal constants. The condition \(n\ge t\) makes \(t/n\le\sqrt{t/n}\), so both terms in Bernstein's bound are of the stated order.

For the sample-centered covariance, subtracting \(\bar X\bar X^\top\) adds at most \(\max_j|\bar X_j|^2\) to the maximum entrywise error. Sub-Gaussian tail bounds and a union bound over the \(p\) coordinates give \(\max_j|\bar X_j|^2\le C K^2M t/n\) with probability at least \(1-\eta/2\), again after adjusting constants. Since \(t/n\le\sqrt{t/n}\), this term is absorbed into the displayed bound. Combining the two events proves the claim.

The Operator-Norm Rate

Set \(D=C_0K^2M\sqrt{\log(4p^2/\eta)/n}\), so the concentration result says that, with probability at least \(1-\eta\), every entry of \(S-\Sigma\) has absolute value at most \(D\). Choose \(\tau\ge 2D\). On this event, every truly zero off-diagonal entry is removed: its sample value has absolute value at most \(D<\tau\). Thus thresholding does not leave noise entries at locations where the true covariance is zero.

Proof. Work on the event \(\max_{j,k}|S_{jk}-\Sigma_{jk}|\le D\). At a nonzero off-diagonal location, if the sample entry is retained, the estimation error is at most \(D\). If it is removed, then \(|S_{jk}|\le\tau\), and therefore \[ |\Sigma_{jk}|\le|\Sigma_{jk}-S_{jk}|+|S_{jk}|\le D+\tau\le \frac{3}{2}\tau. \] The error at that location is consequently at most \(3\tau/2\), whether retained or removed. A zero off-diagonal location contributes no error because its sample entry is removed. Diagonal entries are not thresholded, and their errors are at most \(D\le\tau/2\). Each row of \(T_\tau(S)-\Sigma\) therefore has at most \(s\) potentially nonzero entries, each of absolute value at most \(3\tau/2\). Its maximum absolute row sum is at most \(3s\tau/2\).

For a symmetric matrix \(A\), \(\|A\|_{\mathrm{op}}\le\max_j\sum_k|A_{jk}|\). Indeed, for any unit vector \(v\), symmetry and \(2|v_jv_k|\le v_j^2+v_k^2\) imply \[ |v^\top Av|\le\sum_{j,k}|A_{jk}||v_jv_k| \le\sum_jv_j^2\sum_k|A_{jk}| \le\max_j\sum_k|A_{jk}|. \] The spectral theorem gives \(\|A\|_{\mathrm{op}}=\sup_{\|v\|_2=1}|v^\top Av|\) for symmetric \(A\). Applying this inequality to \(T_\tau(S)-\Sigma\) proves the theorem on the concentration event, which has probability at least \(1-\eta\). \(\square\)

Worked Examples

Interpretation and a Common Pitfall

The rate is not merely an entrywise concentration statement. It uses sparsity to limit how many entrywise errors can accumulate in any row. If \(s\) is large, even small errors can add up; if \(s\) is small, thresholding removes noise at zero locations and only a limited number of true locations contribute to each row sum. The sub-Gaussian condition supplies the \(\sqrt{\log p/n}\) scale for controlling all entries simultaneously.

• Pitfall: treating maximum entrywise error as operator-norm error. The incorrect argument is “every entry has error at most \(D\), so the operator error is at most \(D\).” A row with many errors can have a much larger row sum than \(D\). The correction is to count how many entries can contribute: under exact row sparsity and thresholding at least twice the entrywise error bound, the row sum is at most \(3s\tau/2\), which then controls the operator norm.
• Pitfall: thresholding below the noise level. A threshold smaller than the uniform entrywise error need not remove entries at true zero locations. The proof depends on choosing \(\tau\ge2D\), not merely on applying some positive threshold.
• Pitfall: reading the bound as an exact error value. It is a high-probability upper bound with conservative constants. A realized error can be much smaller, as the row-by-row calculation illustrates.