Convex Banding of the Covariance Matrix

Abstract

We introduce a new sparse estimator of the covariance matrix for high-dimensional models in which the variables have a known ordering. Our estimator, which is the solution to a convex optimization problem, is equivalently expressed as an estimator which tapers the sample covariance matrix by a Toeplitz, sparsely-banded, data-adaptive matrix. As a result of this adaptivity, the convex banding estimator enjoys theoretical optimality properties not attained by previous banding or tapered estimators. In particular, our convex banding estimator is minimax rate adaptive in Frobenius and operator norms, up to log factors, over commonly-studied classes of covariance matrices, and over more general classes. Furthermore, it correctly recovers the bandwidth when the true covariance is exactly banded. Our convex formulation admits a simple and efficient algorithm. Empirical studies demonstrate its practical effectiveness and illustrate that our exactly-banded estimator works well even when the true covariance matrix is only close to a banded matrix, confirming our theoretical results. Our method compares favorably with all existing methods, in terms of accuracy and speed. We illustrate the practical merits of the convex banding estimator by showing that it can be used to improve the performance of discriminant analysis for classifying sound recordings.

Keywords: High-dimensional; adaptive; hierarchical group lasso; structured sparsity.

Figure 1

(Left) The group g₃; (Middle) the nested groups in the penalty (2.1); (Right) a K-banded matrix where K = 2 and p = 6. Note that L = p − K − 1 = 2 counts the number of subdiagonals that are zero. This can be expressed as ${\sum }_{g_L}=0$ or ${\sum }_{s_{\ell }}=0$ for 1 ≤ ℓ ≤ L.

Figure 2

Convergence in Frobenius norm. Monte Carlo estimate of (Left) $E\Vert \widehat{\sum }-{\sum }^{\ast }{\Vert }_F^2/p$ and (Right) $E\Vert \widehat{\sum }-{\sum }^{\ast }{\Vert }_F^2/(p\log p)$ as a function of K, the bandwidth of Σ*

Figure 3

Comparison of our procedure with simple and general weights.

Figure 4

(Left:) For large n, expected $E\Vert \widehat{\sum }-{\sum }^{\ast }{\Vert }_F^2/p$ is seen to decay like n⁻¹ as can be seen from −1 slope of log-log plot (gray lines are of slope −1). (Right:) Scaling this quantity by log p aligns the curves for large n. Both of these phenomena are suggested by Corollary 2.

Figure 5

Comparison of methods in three settings in terms of (Top) squared Frobenius norm, relative to $\Vert S-{\sum }^{\ast }{\Vert }_F^2$ and (Bottom) operator norm relative to ‖S − Σ^∗‖_op.

Figure 6

Comparison of methods in terms of (Left) squared Frobenius norm and (Right) operator norm in a setting where ‖Σ^∗‖_op is increasing.

Figure 7

Test set misclassification error rates of discriminant analysis of phoneme data. For both QDA and LDA, using a regularized covariance matrix improves the misclassification error rate.