Estimation structurée de la matrice de covariance via décomposition tensor-train

Informations de base

• ID de l'article : 2510.08174
• Titre : Structured covariance estimation via tensor-train decomposition
• Auteurs : Artsiom Patarusau, Nikita Puchkin, Maxim Rakhuba, Fedor Noskov (Université HSE)
• Classification : math.ST (Théorie statistique)
• Date de publication : 15 octobre 2025
• Lien de l'article : https://arxiv.org/abs/2510.08174v2

Résumé

Cet article étudie le problème de l'estimation de la matrice de covariance à partir d'échantillons indépendants et identiquement distribués de vecteurs aléatoires de haute dimension. Pour éviter la malédiction de la dimensionnalité, les auteurs imposent des hypothèses structurelles supplémentaires sur la matrice de covariance Σ, en étudiant spécifiquement le cas où Σ peut être approximée par une somme de produits de Kronecker doubles de matrices plus petites au format tensor-train (TT). Ce cadre étend naturellement les modèles bien connus de somme de Kronecker et CANDECOMP/PARAFAC, tout en permettant des interactions plus riches entre les modalités. Les auteurs proposent des algorithmes itératifs en temps polynomial basés sur TT-SVD et sur l'itération orthogonale d'ordre supérieur (HOOI) adaptée à la structure mixte Tucker-2, et dérivant des bornes de convergence non asymptotiques et sans dimension qui tiennent compte de la structure cachée des produits de Kronecker et du tensor-train.

Contexte et motivation de la recherche

Définition du problème

Étant donné des vecteurs aléatoires centrés indépendants et identiquement distribués $X, X_1, \ldots, X_n \in \mathbb{R}^d$, il s'agit d'estimer leur matrice de covariance $\Sigma = \mathbb{E}[XX^T] \in \mathbb{R}^{d \times d}$.

Motivation de la recherche

1. Problème de la malédiction de la dimensionnalité : Dans le cas de haute dimension, l'estimateur classique de covariance empirique $\hat{\Sigma} = \frac{1}{n}\sum_{i=1}^n X_i X_i^T$ fait face à la malédiction de la dimensionnalité, avec une dégradation drastique des performances lorsque $d$ est grand.
2. Nécessité d'hypothèses structurelles : Pour surmonter ce problème, les statisticiens imposent généralement des hypothèses structurelles supplémentaires sur $\Sigma$ afin d'exploiter la structure des données et de réduire le nombre total de paramètres inconnus.
3. Limitations des méthodes existantes :
   • Le modèle de produit de Kronecker $\Sigma = \Phi \otimes \Psi$ est trop simple
   • Le modèle de somme de Kronecker $\Sigma = \sum_{k=1}^K \Phi_k \otimes \Psi_k$ manque de flexibilité suffisante
   • Le modèle CANDECOMP/PARAFAC fait face à des problèmes NP-difficiles sur le plan informatique

Innovation de cet article

Proposition d'un modèle de covariance au format tensor-train (TT) : $\Sigma = \sum_{j=1}^J \sum_{k=1}^K U_j \otimes V_{jk} \otimes W_k$ où $U_j \in \mathbb{R}^{p \times p}$, $V_{jk} \in \mathbb{R}^{q \times q}$, $W_k \in \mathbb{R}^{r \times r}$, et $pqr = d$.

Contributions principales

1. Nouveau modèle de covariance : Proposition d'une structure de covariance basée sur la décomposition tensor-train, qui étend naturellement les modèles de somme de Kronecker et CANDECOMP/PARAFAC, permettant des interactions plus riches entre les modalités.
2. Algorithme efficace : Conception de l'algorithme HardTTh (Hard Tensor Train Thresholding), basé sur TT-SVD et HOOI adapté à la structure mixte Tucker-2, avec une complexité de calcul de $O((J+K)Td_1d_2d_3)$.
3. Garanties théoriques : Établissement de bornes de convergence non asymptotiques et sans dimension, constituant le premier résultat théorique sans dimension pour l'estimation de tenseurs avec structure TT.
4. Validation pratique : Vérification de l'efficacité de la méthode par des expériences numériques, démontrant la nécessité de l'amélioration itérative.

Détails de la méthode

Définition de la tâche

Entrée : Échantillons indépendants et identiquement distribués $X_1, \ldots, X_n \in \mathbb{R}^{pqr}$Sortie : Estimation $\tilde{\Sigma}$ de la matrice de covariance $\Sigma$Contrainte : $\Sigma$ possède une structure TT, pouvant être exprimée comme $\Sigma = \sum_{j=1}^J \sum_{k=1}^K U_j \otimes V_{jk} \otimes W_k$

Architecture du modèle

Réarrangement tensoriel et décomposition

1. Opération de réarrangement : Réarrangement de la matrice de covariance $\Sigma \in \mathbb{R}^{pqr \times pqr}$ en tenseur d'ordre trois $\mathcal{R}(\Sigma) \in \mathbb{R}^{p^2 \times q^2 \times r^2}$
2. Représentation de décomposition TT : $\mathcal{R}(\Sigma) = \sum_{j=1}^J \sum_{k=1}^K \text{vec}(U_j) \otimes \text{vec}(V_{jk}) \otimes \text{vec}(W_k)$
3. Forme compacte : $\mathcal{R}(\Sigma) = U \times_1 V \times_3 W$ où $U \in O_{p^2,J}$, $V \in O_{r^2,K}$, $W \in \mathbb{R}^{J \times q^2 \times K}$

Algorithme HardTTh

Algorithme 1 : HardTTh

Entrée : Tenseur Y ∈ ℝ^{d₁×d₂×d₃}, rang TT (J,K), nombre d'itérations T
Sortie : Approximation TT T̂ = Û ×₁ V̂ ×₃ Ŵ

1. Calculer la SVD tronquée de m₁(Y) : Û₀, Σ₀,₁, Ũ₀ = SVD_J(m₁(Y))
2. Calculer la SVD tronquée de m₃(Û₀ᵀ ×₁ Y) : V̂₀, Σ₀,₂, Ṽ₀ = SVD_K(m₃(Û₀ᵀ ×₁ Y))

pour t = 1, ..., T faire :
3. Ût, Σt,₁, Ũt = SVD_J(m₁(V̂ₜ₋₁ᵀ ×₃ Y))
4. V̂t, Σt,₂, Ṽt = SVD_K(m₃(Ûtᵀ ×₁ Y))

5. Définir Û = ÛT, V̂ = V̂T, Ŵ = Ûᵀ ×₁ V̂ᵀ ×₃ Y

Points d'innovation technique

1. Structure mixte Tucker-2 : Contrairement à la décomposition Tucker standard qui nécessite trois facteurs orthogonaux, la structure TT ne nécessite que deux facteurs orthogonaux, réduisant ainsi la complexité de calcul.
2. Stratégie d'amélioration itérative : Amélioration progressive de la précision d'estimation par optimisation alternée des sous-espaces modaux.
3. Traitement par seuillage dur : Utilisation du seuillage dur plutôt que du seuillage doux, évitant le problème NP-difficile de l'approximation de la norme nucléaire tensorielle.

Configuration expérimentale

Modèle de génération de données

• Rang TT : $J = 7, K = 9$
• Dimensions : $p = q = r = 10$, dimension totale $d = 1000$
• Processus de génération :
  • Génération de matrices aléatoires symétriques $A_j \in \mathbb{R}^{p \times p}$, $B_{jk} \in \mathbb{R}^{q \times q}$, $C_k \in \mathbb{R}^{r \times r}$
  • Vecteur aléatoire défini comme : $\sum_{j=1}^J \sum_{k=1}^K A_j \times_1 B_{jk} \times_2 C_k \times_3 E_{ijk}$
  • où $E_{ijk}$ est un tenseur gaussien standard

Indicateurs d'évaluation

Erreur relative : $\|\hat{S} - \Sigma\|_F / \|\Sigma\|_F$

Méthodes de comparaison

1. Sample Mean : Estimateur de covariance empirique
2. TT-HOSVD : Version sans itération de l'algorithme HardTTh ($T=0$)
3. Tucker : Décomposition Tucker standard
4. Tucker+HOOI : Décomposition Tucker avec itération HOOI
5. PRLS : Version modifiée de la méthode des moindres carrés régularisés

Détails d'implémentation

• Nombre d'itérations : $T = 10$
• Paramètres PRLS : Optimisation de $\lambda_1, \lambda_2$ sur une grille à échelle logarithmique
• Répétitions d'expériences : 16-32 répétitions pour chaque configuration

Résultats expérimentaux

Résultats principaux

Découvertes clés

1. Nécessité de l'itération : HardTTh améliore significativement les résultats par rapport à TT-HOSVD, particulièrement pour n=2000, où l'erreur relative passe de 0.154 à 0.082.
2. Comportement de convergence :
   • Pour n=500 : $\sin\Theta(\text{Im}\hat{U}_0, \text{Im}U^*) \approx 1$, $\sin\Theta(\text{Im}\hat{U}_T, \text{Im}U^*) \approx 1$
   • Pour n=2000 : $\sin\Theta(\text{Im}\hat{U}_0, \text{Im}U^*) \approx 1$, $\sin\Theta(\text{Im}\hat{U}_T, \text{Im}U^*) = 0.33±0.08$
3. Efficacité de calcul : La complexité temporelle de HardTTh est modérée, plus rapide que la décomposition Tucker complète mais plus lente que TT-HOSVD.

Vérification théorique

Les expériences confirment la nécessité des conditions théoriques : lorsque la condition sur les valeurs singulières n'est pas satisfaite (par exemple, n=500), l'algorithme ne peut pas récupérer efficacement le sous-espace ; lorsque la condition est satisfaite (par exemple, n≥2000), l'itération améliore significativement les performances.

Travaux connexes

Modèles de produit de Kronecker

• Produit de Kronecker unique : Werner et al. (2008) proposent le modèle $\Sigma = \Phi \otimes \Psi$
• Somme de Kronecker : Tsiligkaridis & Hero (2013), Puchkin & Rakhuba (2024) étudient le modèle $\Sigma = \sum_k \Phi_k \otimes \Psi_k$

Méthodes de décomposition tensorielle

• Décomposition CP : Fait face à des problèmes de complexité informatique
• Décomposition Tucker : Zhang & Xia (2018) et autres établissent des bornes dépendantes de la dimension
• Décomposition TT : Oseledets (2011) la propose ; cet article l'applique pour la première fois à l'estimation de covariance

Progrès théoriques

• Bornes dépendantes de la dimension : La plupart des résultats existants dépendent de la dimension ambiante
• Bornes sans dimension : Limitées aux cas simples ; cet article les étend à la structure TT

Conclusions et discussion

Conclusions principales

1. Avantages du modèle : Le modèle de covariance au format TT fournit une structure plus riche que les modèles de Kronecker traditionnels tout en restant informatiquement réalisable.
2. Efficacité de l'algorithme : L'algorithme HardTTh réalise une complexité temporelle polynomiale et améliore significativement la qualité d'estimation par itération.
3. Garanties théoriques : Établissement de la première borne de convergence sans dimension pour la structure TT, avec le terme de variance : $\tilde{v} = 96\omega\|\Sigma\|\sqrt{\frac{Jr_1^2(\Sigma) + JKr_2^2(\Sigma) + Kr_3^2(\Sigma) + \log(48/\delta)}{n}}$

Limitations

1. Condition sur les valeurs singulières : L'algorithme nécessite $\sigma_J(m_1(\mathcal{R}(\Sigma))) \gtrsim \|\Sigma\|\sqrt{r_2^2(\Sigma)r_3^2(\Sigma)/n}$, plus forte que la condition théoriquement optimale.
2. Structure du bruit : L'analyse théorique suppose une structure de bruit spécifique, différente du bruit homogène.
3. Sélection des paramètres : Le choix du rang TT $(J,K)$ nécessite une connaissance préalable ou des méthodes pilotées par les données.

Directions futures

1. Méthodes de débiaisage : Développement de techniques de débiaisage pour traiter le bruit non homogène.
2. Sélection adaptative du rang : Établissement de méthodes de sélection du rang avec garanties théoriques.
3. Extensions d'applications : Extension de la méthode à d'autres problèmes d'estimation de matrices structurées.

Évaluation approfondie

Avantages

1. Innovation théorique : Première fourniture de bornes théoriques sans dimension pour l'estimation de covariance avec structure TT, comblant une lacune théorique importante.
2. Praticité de la méthode : L'algorithme HardTTh possède une complexité de calcul raisonnable et évite les problèmes NP-difficiles.
3. Expériences suffisantes : Vérification de l'efficacité de la méthode par plusieurs méthodes de comparaison et différentes tailles d'échantillon.
4. Analyse approfondie : Fourniture d'analyses théoriques détaillées et d'études de convergence d'algorithmes.

Insuffisances

1. Conditions plus fortes : Les conditions théoriques sont plus strictes que les bornes inférieures connues, avec un écart statistique-informatique.
2. Limitations du modèle : Applicable uniquement aux matrices de covariance pouvant être bien approximées au format TT.
3. Sensibilité aux paramètres : Les performances dépendent de la sélection correcte du paramètre de rang TT.

Impact

1. Contribution théorique : Fourniture de nouveaux outils théoriques pour les méthodes tensorielles en statistique de haute dimension.
2. Valeur pratique : Applications potentielles dans l'analyse de données multimodales, le traitement du signal, etc.
3. Signification méthodologique : Démonstration de l'application efficace des techniques de décomposition tensorielle aux problèmes d'estimation statistique.

Scénarios d'application

1. Données multimodales : Images, vidéos et autres données possédant une structure tensorielle naturelle
2. Données spatio-temporelles : Estimation de covariance avec structure temporelle-spatiale
3. Données financières de haute dimension : Modélisation structurée de covariance des rendements d'actifs
4. Réseaux de capteurs : Estimation de covariance de données multi-capteurs

Références

1. Werner, K., Jansson, M., & Stoica, P. (2008). On estimation of covariance matrices with Kronecker product structure.
2. Tsiligkaridis, T., & Hero, A. O. (2013). Covariance estimation in high dimensions via Kronecker product expansions.
3. Zhang, A., & Xia, D. (2018). Tensor SVD: Statistical and computational limits.
4. Puchkin, N., & Rakhuba, M. (2024). Dimension-free structured covariance estimation.
5. Oseledets, I. V. (2011). Tensor-train decomposition.