Convergence Properties of Kronecker Graphical Lasso Algorithms

Abstract

This paper studies iteration convergence of Kronecker graphical lasso (KGLasso) algorithms for estimating the covariance of an i.i.d. Gaussian random sample under a sparse Kronecker-product covariance model and MSE convergence rates. The KGlasso model, originally called the transposable regularized covariance model by Allen ["Transposable regularized covariance models with an application to missing data imputation," Ann. Appl. Statist., vol. 4, no. 2, pp. 764-790, 2010], implements a pair of ${\ell }_1$ penalties on each Kronecker factor to enforce sparsity in the covariance estimator. The KGlasso algorithm generalizes Glasso, introduced by Yuan and Lin ["Model selection and estimation in the Gaussian graphical model," Biometrika, vol. 94, pp. 19-35, 2007] and Banerjee ["Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data," J. Mach. Learn. Res., vol. 9, pp. 485-516, Mar. 2008], to estimate covariances having Kronecker product form. It also generalizes the unpenalized ML flip-flop (FF) algorithm of Dutilleul ["The MLE algorithm for the matrix normal distribution," J. Statist. Comput. Simul., vol. 64, pp. 105-123, 1999] and Werner ["On estimation of covariance matrices with Kronecker product structure," IEEE Trans. Signal Process., vol. 56, no. 2, pp. 478-491, Feb. 2008] to estimation of sparse Kronecker factors. We establish that the KGlasso iterates converge pointwise to a local maximum of the penalized likelihood function. We derive high dimensional rates of convergence to the true covariance as both the number of samples and the number of variables go to infinity. Our results establish that KGlasso has significantly faster asymptotic convergence than Glasso and FF. Simulations are presented that validate the results of our analysis.

47 pages, accepted to IEEE Transactions on Signal Processing

References in corpus (3)

• Sparse permutation invariant covariance estimation
• Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
• High-dimensional covariance estimation by minimizing ${\ell }_1$-penalized log-determinant divergence

Cited by in corpus (18)

• Covariance Estimation in High Dimensions via Kronecker Product Expansions
• Gemini: Graph estimation with matrix variate normal instances
• Robust Kronecker Product PCA for Spatio-Temporal Covariance Estimation
• Integrated Principal Components Analysis
• High dimensional errors-in-variables models with dependent measurements
• Detection of Anomalous Crowd Behavior Using Spatio-Temporal Multiresolution Model and Kronecker Sum Decompositions
• Learning High-Dimensional Differential Graphs From Multi-Attribute Data
• Tensor Graphical Model: Non-convex Optimization and Statistical Inference
• Classification and Representation via Separable Subspaces: Performance Limits and Algorithms
• Non-separable covariance models for spatio-temporal data, with applications to neural encoding analysis
• Kronecker PCA Based Robust SAR STAP
• Graph Estimation for Matrix-variate Gaussian Data
• SG-PALM: a Fast Physically Interpretable Tensor Graphical Model
• The Sylvester Graphical Lasso (SyGlasso)
• Gaussian and Robust Kronecker Product Covariance Estimation: Existence and Uniqueness
• Near optimal sample complexity for matrix and tensor normal models via geodesic convexity
• Learning Quasi-Kronecker Product Graphical Models
• Learning Gaussian DAGs from Network Data