Dimension-free Bounds for Covariance Estimation with Tensor-Train Structure

We consider a problem of covariance estimation from a sample of i.i.d. high-dimensional random vectors. We are particularly interested in the situation when the covariance matrix $\Sigma$ can be approximated by a sum of double Kronecker products of smaller matrices in a tensor train (TT) format. Despite the model expressiveness, we show that one can estimate $\Sigma$ in high dimensions via an iterative polynomial time algorithm based on TT-SVD and higher-order orthogonal iteration (HOOI) adapted to Tucker‑2 hybrid structure. Our result naturally yields the first dimension-free bound for a general CANDECOMP/PARAFAC covariance model. We also illustrate the efficiency of our approach with numerical experiments.