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 esti-mation 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 stan-dard Glasso, KGlasso has low computational complexity as the dimension of the covariance matrix increases. We de-rive a tight MSE convergence rate for KGlasso and show it strictly outperforms standard Glasso and FF. Simulations val-idate these results and shows that KGlasso outperforms the maximum-likelihood solution (FF), in the high-dimensional small-sample regime. Index Terms — sparsity, structured covariance estima-tion, penalized maximum likelihood, graphical lasso 1