Kronecker graphical lasso

We consider high-dimensional estimation of a (possibly sparse) Kronecker-decomposable covariance matrix given i.i.d. Gaussian samples. We propose a sparse covariance estimation algorithm, Kronecker Graphical Lasso (KGlasso), for the high dimensional setting that takes advantage of structure and sparsity. Convergence and limit point characterization of this iterative algorithm is established. Compared to standard Glasso, KGlasso has low computational complexity as the dimension of the covariance matrix increases. We derive a tight MSE convergence rate for KGlasso and show it strictly outperforms standard Glasso and FF. Simulations validate these results and shows that KGlasso outperforms the maximum-likelihood solution (FF), in the high-dimensional small-sample regime.