Positive Definite Sparse Covariance Estimation via Dual Space Optimization

Covariance matrix estimation in high-dimensional settings is a fundamental problem in machine learning and data science. To mitigate the challenges posed by high dimensionality, a common structural assumption is the sparsity, which posits that most variable pairs exhibit negligible correlations. We revisit the seminal positive definite sparse covariance estimation (PDSCE) formulation proposed by Rothman (2012). In contrast to many earlier approaches, this formulation guarantees that the estimator is positive definite, thereby ensuring the well-posedness of the problem. However, the incorporation of a log-determinant barrier also introduces significant optimization challenges. Existing algorithms for solving the PDSCE problem suffer from several limitations, such as high computational complexity, poor scalability, and the need for explicit mechanisms to maintain positive definiteness. To address these issues, we propose a dual proximal gradient method (DPGM) that, unlike existing primal-space approaches, operates in the dual space. This dual method offers several key advantages. First, DPGM inherently preserves positive definiteness, eliminating the need for complex mechanisms to enforce it. Second, DPGM achieves improved iteration complexity over primal-space methods. Third, the worst-case step size for DPGM is a constant independent of the ambient dimension, making the method particularly suitable for high-dimensional applications. Extensive numerical experiments demonstrate that DPGM consistently outperforms existing algorithms, validating its effectiveness and scalability for high-dimensional sparse covariance estimation.