Convergence Properties of Kronecker Graphical Lasso Algorithms

Covariance estimation is a problem of great interest in many different disciplines, including machine learning, signal processing, economics and bioinformatics. In many applications the number of variables is very large, e.g., in the tens or hundreds of thousands, leading to a number of covariance parameters that greatly exceeds the number of observations. To address this problem constraints are frequently imposed on the covariance to reduce the number of parameters in the model. For example, the Glasso model of Yuan and Lin [2] and Banerjee et al [3] imposes sparsity constraints on the covariance. The Kronecker product model of Dutilleul [4] and Werner et al [5] assumes that the covariance can be represented as the Kronecker product of two lower dimensional covariance matrices. The transposable regularized covariance model of Allen et al [1] imposes a combination of sparsity and Kronecker product form on the covariance. When there is no missing data, an extension of the alternating optimization algorithm of [4], [5], called the flip flop (FF) algorithm, can be applied to estimate the parameters of this combined sparse and Kronecker product model. In this report we call this algorithm the Kronecker Glasso (KGlasso) and we thoroughly analyze convergence of the algorithm in the high dimensional setting.