# Covariance Estimation in High Dimensions via Kronecker Product Expansions

arXiv: https://arxiv.org/abs/1302.2686 · HTML: https://mlsanity.com/paper/1302.2686/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2013.

## Built on by (most cited first, 16 of 16)

- [Learning Product Graphs from Spectral Templates](https://mlsanity.com/paper/2211.02893/) (2022)
- [Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory](https://mlsanity.com/paper/2102.11822/) (2021)
- [EiGLasso for Scalable Sparse Kronecker-Sum Inverse Covariance Estimation](https://mlsanity.com/paper/2105.09872/) (2021)
- [Efficient Hierarchical Bayesian Inference for Spatio-temporal Regression Models in Neuroimaging](https://mlsanity.com/paper/2111.01692/) (2021)
- [Scalable Bigraphical Lasso: Two-way Sparse Network Inference for Count Data](https://mlsanity.com/paper/2203.07912/) (2022)
- [Multi-Fidelity Covariance Estimation in the Log-Euclidean Geometry](https://mlsanity.com/paper/2301.13749/) (2023)
- [Multiway Ensemble Kalman Filter](https://mlsanity.com/paper/2112.04322/) (2021)
- [Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model](https://mlsanity.com/paper/2307.00575/) (2023)
- [Structured Low-Rank Tensors for Generalized Linear Models](https://mlsanity.com/paper/2308.02922/) (2023)
- [DNNLasso: Scalable Graph Learning for Matrix-Variate Data](https://mlsanity.com/paper/2403.02608/) (2024)
- [Higher-Order Transformers With Kronecker-Structured Attention](https://mlsanity.com/paper/2412.02919/) (2024)
- [Weaver: Kronecker Product Approximations of Spatiotemporal Attention for Traffic Network Forecasting](https://mlsanity.com/paper/2511.08888/) (2025)
- [Dictionary-based Low-Rank Approximations and the Mixed Sparse Coding problem](https://mlsanity.com/paper/2111.12399/) (2021)
- [A Muon-Accelerated Algorithm for Low Separation Rank Tensor Generalized Linear Models](https://mlsanity.com/paper/2604.04726/) (2026)
- [Precise sample covariance spectral norm error -- an RDT view](https://mlsanity.com/paper/2607.14460/) (2026)
- [Spatiotemporal Kronecker Covariance Neural Networks](https://mlsanity.com/paper/2609.25326/) (2026)

## Abstract (arXiv)

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.