# Near optimal sample complexity for matrix and tensor normal models via geodesic convexity

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 43 references that are in the map.
- First posted on arXiv 14 Oct 2021.

## Builds on (most cited first, 4 of 4)

- [Rigorous Guarantees for Tyler's M-estimator via quantum expansion](https://mlsanity.com/paper/2002.00071/) (2020)
- [Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes](https://mlsanity.com/paper/1910.12375/) (2019)
- [Efficient algorithms for tensor scaling, quantum marginals and moment polytopes](https://mlsanity.com/paper/1804.04739/) (2018)
- [Spectral analysis of matrix scaling and operator scaling](https://mlsanity.com/paper/1904.03213/) (2019)

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

- [Optimal Bounds for Tyler's M-Estimator for Elliptical Distributions](https://mlsanity.com/paper/2510.13751/) (2025)
- [Sufficient dimension reduction for feature matrices](https://mlsanity.com/paper/2303.04286/) (2023)
- [Tensor-normal maximum likelihood estimation at the operator-norm sample threshold](https://mlsanity.com/paper/2608.10488/) (2026)

## Abstract (arXiv)

The matrix normal model, i.e., the family of Gaussian matrix-variate distributions whose covariance matrices are the Kronecker product of two lower dimensional factors, is frequently used to model matrix-variate data. The tensor normal model generalizes this family to Kronecker products of three or more factors. We study the estimation of the Kronecker factors of the covariance matrix in the matrix and tensor normal models. For the above models, we show that the maximum likelihood estimator (MLE) achieves nearly optimal nonasymptotic sample complexity and nearly tight error rates in the Fisher-Rao and Thompson metrics. In contrast to prior work, our results do not rely on the factors being well-conditioned or sparse, nor do we need to assume an accurate enough initial guess. For the matrix normal model, all our bounds are minimax optimal up to logarithmic factors, and for the tensor normal model our bounds for the largest factor and for overall covariance matrix are minimax optimal up to constant factors provided there are enough samples for any estimator to obtain constant Frobenius error. In the same regimes as our sample complexity bounds, we show that the flip-flop algorithm, a practical and widely used iterative procedure to compute the MLE, converges linearly with high probability. Our main technical insight is that, given enough samples, the negative log-likelihood function is strongly geodesically convex in the geometry on positive-definite matrices induced by the Fisher information metric. This strong convexity is determined by the expansion of certain random quantum channels.