Covariance Estimation in High Dimensions via Kronecker Product Expansions

Abstract

This paper presents a new method for estimating high dimensional covariance matrices. The method, permuted rank-penalized least-squares (PRLS), is based on a Kronecker product series expansion of the true covariance matrix. Assuming an i.i.d. Gaussian random sample, we establish high dimensional rates of convergence to the true covariance as both the number of samples and the number of variables go to infinity. For covariance matrices of low separation rank, our results establish that PRLS has significantly faster convergence than the standard sample covariance matrix (SCM) estimator. The convergence rate captures a fundamental tradeoff between estimation error and approximation error, thus providing a scalable covariance estimation framework in terms of separation rank, similar to low rank approximation of covariance matrices. The MSE convergence rates generalize the high dimensional rates recently obtained for the ML Flip-flop algorithm for Kronecker product covariance estimation. We show that a class of block Toeplitz covariance matrices is approximatable by low separation rank and give bounds on the minimal separation rank $r$ that ensures a given level of bias. Simulations are presented to validate the theoretical bounds. As a real world application, we illustrate the utility of the proposed Kronecker covariance estimator for spatio-temporal linear least squares prediction of multivariate wind speed measurements.

47 pages, accepted to IEEE Transactions on Signal Processing

References in corpus (7)

• Regularized estimation of large covariance matrices
• Sparse permutation invariant covariance estimation
• Optimal rates of convergence for covariance matrix estimation
• Covariance Estimation in High Dimensions via Kronecker Product Expansions
• Convergence and prediction of principal component scores in high-dimensional settings
• Statistical eigen-inference from large Wishart matrices
• High-dimensional covariance estimation by minimizing ${\ell }_1$-penalized log-determinant divergence

Cited by in corpus (20)

• GPz: Non-stationary sparse Gaussian processes for heteroscedastic uncertainty estimation in photometric redshifts
• Covariance Estimation in High Dimensions via Kronecker Product Expansions
• A Sparse Gaussian Process Framework for Photometric Redshift Estimation
• Robust Kronecker Product PCA for Spatio-Temporal Covariance Estimation
• Learning Mixtures of Separable Dictionaries for Tensor Data: Analysis and Algorithms
• Time-dependent spatially varying graphical models, with application to brain fMRI data analysis
• Degradation analysis in the estimation of photometric redshifts from non-representative training sets
• Detection of Anomalous Crowd Behavior Using Spatio-Temporal Multiresolution Model and Kronecker Sum Decompositions
• Learning Product Graphs Underlying Smooth Graph Signals
• Multi-linear Tensor Autoregressive Models
• Classification and Representation via Separable Subspaces: Performance Limits and Algorithms
• Efficient Hierarchical Bayesian Inference for Spatio-temporal Regression Models in Neuroimaging
• Kronecker PCA Based Spatio-Temporal Modeling of Video for Dismount Classification
• Regularized Block Toeplitz Covariance Matrix Estimation via Kronecker Product Expansions
• Kronecker PCA Based Robust SAR STAP
• EiGLasso for Scalable Sparse Kronecker-Sum Inverse Covariance Estimation
• Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory
• Kronecker STAP and SAR GMTI
• Learning Quasi-Kronecker Product Graphical Models
• Channel Covariance Matrix Estimation via Dimension Reduction for Hybrid MIMO MmWave Communication Systems