Sparse inverse covariance matrix estimation via the ℓ0-norm with Tikhonov regularization*The research is supported by the Special Project on High-performance Computing under the National Key R&D Program (Grant No. 2016YFB0200602), by the Natural Science Foundation of China under Grant Nos. 11701189 and 11771464. (4th October 2019)

• Record Type: Journal Article
• Authors: Liu, Xinrui; Zhang, Na
• Is Part Of: Inverse problems. Volume 35:Number 11(2019)
• Publication Date: 2019-10-04
• Subjects: penalty methods -- ℓ0-norm regularization -- sparse inverse covariance matrix estimation -- Tikhonov regularization; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/1361-6420/ab1af3
• Languages: English
• ISSNs: 0266-5611

Abstract

Abstract: Sparse inverse covariance matrix estimation is a fundamental problem in a Gaussian network model and has attracted much attention in the last decade. A widely used approach for estimating the sparse inverse covariance matrix is the regularized negative log-likelihood minimization, where the regularization term promotes the sparsity of the inverse covariance matrix. Although the -norm is the most popular sparsity promoting function due to its convexity, it may not result in sufficiently satisfied estimations. The -norm is the most natural function to measure sparsity and the -norm regularized negative log-likelihood minimization has been demonstrated to produce favorable results. However, when the sample covariance matrix is singular, the -norm problem has no optimal solution. In this paper, we propose to estimate the sparse inverse covariance matrix via simultaneously using the -norm and the Tikhonov regularization. The resulting minimization problem is guaranteed to have optimal solutions. To overcome the numerical difficulty caused by the -norm, we utilize the penalty decomposition approach. We prove the asymptotic approximation and exact approximation to local (resp., global) minimizers of the original problem by those of the penalty decomposition problem. Then, local minimizers of the penalty decomposition problem are characterized as fixed-points of a system of fixed-point equations with the help of proximity operators. Based on these theoretical results, we design for solving the proposed minimization problem a penalty decomposition fixed-point proximity algorithm and provide the convergence analysis of the algorithm. Numerical results indicate that the proposed algorithm outperforms the compared state-of-the-art algorithms in terms of accuracy.