{"ID":2858142,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.08174","arxiv_id":"2510.08174","title":"Dimension-free Bounds for Covariance Estimation with Tensor-Train Structure","abstract":"We consider a problem of covariance estimation from a sample of i.i.d. high-dimensional random vectors. To avoid the curse of dimensionality, we impose an additional assumption on the structure of the covariance matrix $Σ$. To be more precise, we study the case when $Σ$ can be approximated by a sum of double Kronecker products of smaller matrices in a tensor train (TT) format. Our setup naturally extends widely known Kronecker sum and CANDECOMP/PARAFAC models but admits richer interaction across modes. We suggest an iterative polynomial time algorithm based on TT-SVD and higher-order orthogonal iteration (HOOI) adapted to Tucker-2 hybrid structure. We derive non-asymptotic dimension-free bounds on the accuracy of covariance estimation taking into account hidden Kronecker product and tensor train structures. The efficiency of our approach is illustrated with numerical experiments.","short_abstract":"We consider a problem of covariance estimation from a sample of i.i.d. high-dimensional random vectors. To avoid the curse of dimensionality, we impose an additional assumption on the structure of the covariance matrix $Σ$. To be more precise, we study the case when $Σ$ can be approximated by a sum of double Kronecker...","url_abs":"https://arxiv.org/abs/2510.08174","url_pdf":"https://arxiv.org/pdf/2510.08174v3","authors":"[\"Artsiom Patarusau\",\"Nikita Puchkin\",\"Maxim Rakhuba\",\"Fedor Noskov\"]","published":"2025-10-09T12:59:39Z","proceeding":"math.ST","tasks":"[\"math.ST\"]","methods":"[]","has_code":false}