Statistically and Computationally Optimal Estimation and Inference of Common Subspaces

Résumé technique : Estimation et inférence statistiquement et computationnellement optimales de sous-espaces communs

Formulation du problème
Cet article étudie les limites statistiques et computationnelles de l'estimation d'un sous-espace commun $U \in \mathbb{R}^{n \times r}$ à partir d'une collection de $L$ matrices symétriques observées $\{A^{(l)}\}_{l=1}^L$. Les données suivent le modèle COSIE (Common Subspace Independent Edge) :
$$A^{(l)} = S^{(l)} + N^{(l)}, \quad S^{(l)} = U R^{(l)} U^\top,$$
où $S^{(l)}$ est une matrice de signal de faible rang partageant le sous-espace commun $U$, $R^{(l)} \in \mathbb{R}^{r \times r}$ est une matrice symétrique de plein rang spécifique à chaque couche, et $N^{(l)}$ est une matrice de bruit symétrique à entrées subgaussiennes indépendantes (spécifiquement modélisée comme des matrices de l'ensemble de Wigner ou de l'ensemble orthogonal gaussien avec une variance $\sigma^2$). L'objectif est de récupérer $U$ (à un isométrie orthogonale près) et de réaliser l'inférence statistique sur l'erreur d'estimation $\|\sin \Theta(\hat{U}, U)\|_F^2$.

Méthodologie
Les auteurs proposent une procédure d'estimation en deux étapes :

1. Initialisation spectrale par somme de carrés : Pour initialiser l'algorithme, ils calculent la décomposition spectrale de la somme des carrés des matrices observées : $\hat{U}_0 = \text{SVDr}(\sum_{l=1}^L (A^{(l)})^2)$. Cette initialisation est cruciale car la simple moyenne de $A^{(l)}$ peut conduire à une annulation du signal si les matrices $R^{(l)}$ présentent des signes mixtes ou des structures variables. Le fait de mettre les matrices au carré garantit que le signal s'accumule de manière constructive dans l'espace propre principal.
2. Descente de gradient projetée (PGD) : Partant de $\hat{U}_0$, les auteurs optimisent la fonction de perte $h(\hat{U}; \{\hat{R}^{(l)}\}) = \frac{1}{4L} \sum_{l=1}^L \|A^{(l)} - \hat{U}\hat{R}^{(l)}\hat{U}^\top\|_F^2$ en utilisant la descente de gradient projetée. À chaque itération, l'étape de gradient est suivie d'une projection sur la variété de Stiefel (via la SVD) pour maintenir l'orthonormalité. Les termes $\hat{R}^{(l)}$ sont mis à jour de manière fermée par $\hat{R}^{(l)}_t = \hat{U}_t^\top A^{(l)} \hat{U}_t$.

Pour l'inférence statistique, les auteurs dérivent un résultat de normalité asymptotique pour l'erreur de Frobenius au carré $\|\sin \Theta(\hat{U}, U)\|_F^2$ dans le régime de rapport signal sur bruit (SNR) élevé. Sur la base de ce théorème limite, ils construisent des intervalles de confiance par substitution (plug-in) pour l'erreur sans nécessiter la connaissance préalable de l'intensité du signal.

Contributions clés et résultats

1. Taux d'estimation optimaux :
   L'article établit que l'algorithme PGD proposé atteint le taux d'erreur minimax-optimal après un nombre logarithmique d'itérations, à condition que le SNR ($\lambda/\sigma$, où $\lambda$ caractérise l'intensité du signal) satisfasse une condition de « SNR d'estimation forte » : $\lambda/\sigma \gtrsim \sqrt{n}/L^{1/4}$.

   • SNR d'estimation faible ($\lambda/\sigma \ll \sqrt{n/L}$) : L'estimation est informationnellement impossible.
   • SNR d'estimation modérée ($\sqrt{n/L} \lesssim \lambda/\sigma \ll \sqrt{n}/L^{1/4}$) : Aucun estimateur en temps polynomial n'existe sur la base de tests de rapport de vraisemblance de degré faible, indiquant une barrière computationnelle.
   • SNR d'estimation forte : L'algorithme proposé est à la fois statistiquement et computationnellement optimal.

2. Inférence statistique et adaptativité :
   Une contribution novatrice est l'analyse de l'inférence statistique adaptative. Les auteurs montrent que, bien que l'estimation puisse être réalisable en temps polynomial, l'inférence adaptative (construction d'intervalles de confiance sans connaître le SNR) fait face à un seuil plus élevé.

   • SNR d'inférence faible ($\sqrt{n}/L^{1/4} \ll \lambda/\sigma \ll n/\sqrt{L}$) : L'inférence adaptative est informationnellement impossible.
   • SNR d'inférence forte ($\lambda/\sigma \gg n/\sqrt{L}$) : Les intervalles de confiance proposés sont adaptativement minimax-optimaux.
   • Normalité asymptotique : L'article prouve que $\|\sin \Theta(\hat{U}, U)\|_F^2$ est asymptotiquement gaussien dans le régime d'inférence forte, permettant la construction d'intervalles de confiance valides.

3. Écarts computationnels et statistiques :
   Les résultats révèlent un phénomène nouveau : un écart « computationnel-statistique » d'inférence. Le seuil computationnel pour l'estimation ($\lambda/\sigma \sim \sqrt{n}/L^{1/4}$) est strictement inférieur au seuil statistique pour l'inférence adaptative ($\lambda/\sigma \sim n/\sqrt{L}$). Par conséquent, il existe un régime où l'estimation optimale est computationnellement réalisable, tandis que l'inférence statistique adaptative reste informationnellement impossible. Cela contraste avec de nombreux modèles existants (par exemple, l'analyse de données tensorielles) où l'inférence est souvent « gratuite » dès lors que l'estimation est computationnellement réalisable.

Signification
Cet article fournit une caractérisation complète des transitions de phase dans le modèle de sous-espace commun. Il comble le fossé entre l'estimation et l'inférence en démontrant que les exigences pour l'inférence adaptative sont nettement plus strictes que celles pour l'estimation. Ce travail étend la portée de l'analyse de sous-espace commun au-delà des données de réseaux (où elle était précédemment appliquée) aux matrices symétriques de faible rang générales avec un bruit homoscédastique. L'algorithme proposé s'avère robuste et optimal sans nécessiter d'optimisation globale ou d'étapes de correction de biais supplémentaires, qui sont souvent nécessaires dans les contextes hétéroscédastiques. Les conclusions soulignent que dans les contextes de haute dimension avec de multiples sources de données, la capacité à quantifier l'incertitude de manière adaptative est un problème statistique distinct et plus difficile que la simple estimation ponctuelle.