A Sketched Generalized Krylov Subspace Method for Large-Scale Regularization

Résumé Technique : Une méthode de sous-espace de Krylov généralisée esquissée pour la régularisation à grande échelle

Énoncé du problème
L'article traite des problèmes de moindres carrés mal posés à grande échelle de la forme $\min_{x} \|Ax - b\|_2^2$, où la matrice $A$ est sévèrement mal conditionnée et $b$ est contaminé par du bruit. Pour stabiliser la solution, une régularisation de Tikhonov est employée, menant au problème pénalisé :
$$\min_{x \in \mathbb{R}^n} \left\{ \|Ax - b\|_2^2 + \lambda \|Lx\|_2^2 \right\},$$
où $L$ est une matrice de régularisation générale codant des informations a priori. Bien que des méthodes efficaces existent pour la forme standard de Tikhonov ($L=I$), la gestion d'un $L$ général est un défi computationnel. La méthode du Sous-espace de Krylov Généralisé (GKS) [28] a été proposée pour traiter un $L$ général en élargissant un espace de recherche à l'aide du gradient du fonctionnel de Tikhonov. Cependant, à mesure que la dimension du sous-espace croît, la GKS fait face à deux goulots d'étranglement computationnels prohibitifs :

1. Factorisations QR minces : La mise à jour des factorisations QR des matrices projetées $AV_k$ et $LV_k$ à chaque itération.
2. Réorthogonalisation : La réorthogonalisation explicite des nouveaux vecteurs de base par rapport à toutes les colonnes précédentes pour maintenir la stabilité numérique, ce qui nécessite des calculs complets de produits scalaires.

Ces opérations augmentent de manière défavorable avec le nombre d'itérations et la taille du problème, limitant la scalabilité de la GKS pour les problèmes inverses à grande échelle.

Méthodologie : sGKS (Sketched GKS)
Les auteurs proposent la sGKS, une variante randomisée de la méthode GKS qui utilise l'esquisse (sketching ou réduction de dimensionnalité randomisée) pour accélérer les étapes les plus coûteuses tout en préservant la qualité de l'approximation. La méthodologie repose sur deux observations principales :

1. Élimination de la réorthogonalisation explicite : Les auteurs observent que l'algorithme GKS ne repose pas intrinsèquement sur l'orthogonalité des vecteurs de base pour ses étapes de base (contrairement aux méthodes de Krylov classiques pour les systèmes linéaires qui reposent sur les relations d'Arnoldi/Lanczos). Par conséquent, la sGKS omet la réorthogonalisation explicite de la base entière. Au lieu de maintenir une base orthonormée $V_k$, la sGKS maintient une base non orthonormée $W_k$ formée en concaténant les vecteurs de gradient bruts. Cela supprime le coût de $O(d_k^2 n)$ de la réorthogonalisation (où $d_k$ est la dimension du sous-espace).

2. Résolution par esquisse (Sketch-and-Solve) pour les problèmes projetés : Pour réduire le coût de la résolution du problème de Tikhonov projeté et la mise à jour des factorisations QR, la sGKS emploie des opérateurs d'esquisse $S_A$ et $S_L$.

   • Le problème de moindres carrés projeté est résolu sur des matrices compressées $S_A A W_k$ et $S_L L W_k$ plutôt que sur les matrices complètes $A W_k$ et $L W_k$.
   • Les factorisations QR sont effectuées sur ces matrices esquissées de taille $s \times d_k$ (où $s \ll m, p$) et mises à jour de manière incrémentale via des extensions de rang un.
   • Les opérateurs d'esquisse utilisés sont des plongements de sous-espaces oblitérants (spécifiquement des transformations trigonométriques sous-échantillonnées et randomisées, SRTT), qui dépendent uniquement de la dimension du sous-espace, et non du sous-espace lui-même.

Contributions clés

• Conception algorithmique : Le développement de la sGKS, qui intègre l'esquisse randomisée dans le cadre GKS pour la régularisation de forme générale de Tikhonov.
• Analyse théorique :
  • Équivalence : Les auteurs prouvent que si l'esquisse est omise dans la résolution projetée, la sGKS produit des itérés mathématiquement identiques à la GKS standard (Proposition 1).
  • Quasi-optimalité : Ils démontrent que lorsque l'esquisse est appliquée, la méthode produit des normes de résidu quasi-optimales, l'erreur étant contrôlée par la qualité d'immersion ($\epsilon$) des opérateurs d'esquisse (Proposition 2).
  • Raffinement itératif : Pour les cas où la perte d'orthogonalité de la base devient significative (menant à une déficience de rang numérique), l'article montre qu'incorporer un petit nombre d'étapes de raffinement itératif (IR) dans la résolution projetée restaure les propriétés spectrales de la base et récupère la pleine précision de la méthode non esquissée.
• Efficacité computationnelle : La méthode réduit les coûts par itération en remplaçant les mises à jour QR de plein rang et la réorthogonalisation coûteuses par des opérations plus légères sur des matrices compressées.

Résultats numériques
L'article évalue la sGKS sur quatre problèmes inverses à grande échelle :

1. Débruitage d'image : La sGKS avec diverses dimensions d'esquisse ($s$) atteint une qualité de reconstruction comparable à la GKS standard. Un $s$ plus grand produit des trajectoires de convergence presque indiscernables de la GKS, tandis qu'un $s$ plus petit entraîne des erreurs finales légèrement plus élevées mais une convergence plus rapide.
2. Reconstruction CT (Tomographie Computée) à rayons X : Sur un problème avec $n=250\,000$ inconnues et un opérateur de régularisation important ($p \approx 500\,000$), la sGKS égale la précision de reconstruction de la GKS (RRE $\approx 0,183$) tout en réduisant considérablement le temps d'exécution (wall-clock time). L'accélération est pilotée par l'élimination de la réorthogonalisation et la réduction des coûts de mise à jour QR de $O(p)$ à $O(s)$.
3. Tomographie de temps de trajet sismique : Sur un système creux et surestimaté, la sGKS surpasse les méthodes hybrides LSQR en précision et en vitesse. Bien que l'accélération par rapport à la GKS standard soit modeste ici (car le calcul du gradient domine), la sGKS offre tout de même une réduction de temps de 10 % tout en maintenant une qualité de reconstruction supérieure aux variantes de LSQR.
4. CT Dynamique : Dans une formulation espace-temps avec un opérateur de régularisation massif, les coûts de QR et de réorthogonalisation dominent le temps d'exécution de la GKS standard. Ici, la sGKS atteint une accélération de 3$\times$ par rapport à la GKS standard. L'inclusion du raffinement itératif (IR) permet à la sGKS de récupérer la trajectoire de convergence exacte et le paramètre de régularisation optimal de la GKS non esquissée, là où la sGKS sans IR stagne à une erreur légèrement plus élevée.

Signification et affirmations
L'article affirme que la sGKS est une alternative évolutive à la GKS standard pour la régularisation à grande échelle avec des matrices générales. Sa signification réside dans :

• Scalabilité : Elle élimine les goulots d'étranglement computationnels (réorthogonalisation et mises à jour QR de plein rang) qui limitaient auparavant l'applicabilité de la GKS à des problèmes très vastes.
• Préservation de la précision : Elle maintient la qualité de reconstruction de la méthode originale, avec des garanties théoriques sur les normes de résidu et des preuves empiriques montrant que le raffinement itératif peut restaurer la pleine précision même lorsque l'orthogonalité de la base est perdue.
• Généralité : L'approche est indépendante du choix spécifique de l'opérateur d'esquisse et s'applique à des matrices de régularisation générales $L$, et non seulement aux problèmes de forme standard.

Les auteurs concluent que bien que la méthode introduise un paramètre d'esquisse ($s$) pour ajuster le compromis entre vitesse et précision, elle offre un cadre robuste pour résoudre les problèmes inverses à grande échelle où les méthodes de projection standard sont computationnellement prohibitives. Les travaux futurs suggérés incluent la sélection adaptative de la dimension d'esquisse et des extensions aux problèmes inverses non linéaires.