Fast algorithms for sparse inverse covariance estimation

ABSTRACT

Sparse precision matrix (i.e. inverse covariance matrix in statistic term) estimation is an important problem in many applications of multivariate analysis. The problem becomes very challenging when the dimension of data is much larger than the number of samples. In this paper, we propose a convex relaxation model for the sparse covariance selection problem, which is solved by the well-known alternating direction method of multipliers (ADMM). Furthermore, a new model with positive semi-definite constraint is proposed. Numerical results show that the ADMM-based methods perform favourably compared with the column-wise manner on both synthetic and real data.

KEYWORDS:

• The precision matrix
• sparse inverse covariance estimation
• sparse covariance selection problem
• alternating direction method of multipliers
• positive semi-definite programming

2000 AMS SUBJECT CLASSIFICATIONS:

• 15A83
• 93C41
• 62H12

Acknowledgements

We would like to thank Prof. Zaiwen Wen for the discussions on sparse inverse covariance estimation. We also thank Prof. Weidong Liu for discussing the detail of the numerical experiment, and thank Dr Jingwei Liang for helpful discussions. The authors are grateful to editor and anonymous referees for their detailed and valuable comments and suggestions.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The work was supported in part by National Natural Science Foundation of China grant 11626143, the National Social Science Fundation of China grant 16CGL016, and Shandong Provincial Natural Science Foundation grant ZR2018MG001.