A Variational Equation and Lower Bound for the Linear Least-Squares Backward Error

Résumé technique : Une équation variationnelle et une borne inférieure pour l'erreur arrière des moindres carrés linéaires

Énoncé du problème
L'article aborde le défi consistant à estimer efficacement l'erreur arrière, $\mu$, pour les problèmes de moindres carrés linéaires avec plusieurs vecteurs de droite :
$$\min_{X \in \mathbb{R}^{n \times d}} \|AX - B\|_F$$
où $A \in \mathbb{R}^{m \times n}$ et $B \in \mathbb{R}^{m \times d}$. L'erreur arrière $\mu$ est définie comme la norme minimale des perturbations $[E, \theta F]$ telles que la solution approchée $X$ devienne une solution exacte du système perturbé $(A+E)^T(A+E)X = (A+E)^T(B+F)$.

Le calcul direct de $\mu$ est prohibitivement coûteux pour les solveurs itératifs car il nécessite la résolution d'un grand problème de valeurs propres ou d'un problème de valeurs propres généralisé. Bien que des estimations existent (telles que l'estimation de Karlson-Waldén), elles sont souvent coûteuses à calculer exactement ou manquent de bornes garanties (c'est-à-dire qu'elles ne sont pas strictement des bornes supérieures ou inférieures). L'article cherche une méthode pour dériver des estimations fiables et peu coûteuses en calcul, se concentrant spécifiquement sur des bornes inférieures pouvant servir de critères d'arrêt pour des méthodes itératives comme LSQR et LSMR.

Méthodologie
La méthodologie centrale repose sur l'expression de l'erreur arrière en termes d'un problème de valeurs propres généralisé dans le cadre de l'algèbre linéaire indéfinie.

1. Formulation variationnelle : L'article établit d'abord une équation variationnelle pour l'erreur arrière $\mu(A, R_\theta)$, où $R_\theta$ est une matrice résiduelle transformée. Il exprime $\mu$ comme un problème de maximisation sur une variété indéfinie définie par la contrainte $X^T J_{n,d} X = -I_d$, où $J_{n,d} = \text{diag}(I_n, -I_d)$.
   $$\mu(A, R_\theta) = \sup_{X^T J_{n,d} X = -I_d} \left( \|R_\theta\|_F^2 - \|[A, R_\theta]X\|_F^2 \right)^{1/2}$$
2. Décomposition CS hyperbolique : Pour résoudre ce problème d'optimisation, les auteurs utilisent la décomposition CS hyperbolique (un analogue indéfini de la décomposition CS pour les matrices unitaires). Cette décomposition permet de découpler l'optimisation sur la matrice $X$ en des optimisations sur des matrices orthogonales et des matrices de mise à l'échelle diagonales.
3. Théorème de décomposition : En appliquant cette décomposition, l'article déduit un théorème montrant que l'erreur arrière pour un problème avec $d$ vecteurs de droite peut être décomposée en la somme de $d$ problèmes d'erreur arrière plus petits, chacun impliquant un seul vecteur de droite.
4. Construction d'une borne inférieure : Tirant parti de cette décomposition, les auteurs proposent une borne inférieure basée sur l'échantillonnage (sketching). En calculant un seul vecteur de test $p$ à l'aide d'une matrice échantillonnée $SA$(où$S$ est une matrice d'échantillonnage), ils peuvent évaluer la formule de l'erreur arrière pour un seul vecteur de droite. Cela fournit une borne inférieure prouvée de la vraie erreur arrière.

Contributions clés

• Théorème 1 (Décomposition) : La contribution théorique principale est la décomposition de l'erreur arrière $\mu(A, R_\theta)$ en une somme de termes plus petits :
  $$\mu(A, R_\theta) = \max_{P, Q} \left( \sum_{i=1}^k \mu^2(Ap_i, R_\theta q_i) \right)^{1/2}$$
  où $P$ et $Q$ sont des matrices à colonnes orthonormées. Cela réduit la complexité du problème à une série d'optimisations scalaires.
• Expression exacte pour un seul vecteur de droite : L'article fournit une expression stable et sous forme close pour l'erreur arrière dans le cas d'un seul vecteur de droite, $\mu(a, r)$, qui dépend des normes de la somme et de la différence des vecteurs :
  $$\mu(a, r) = \frac{2|a^T r|}{\|a+r\|_2 + \|a-r\|_2}$$
• Borne inférieure basée sur l'échantillonnage : Les auteurs proposent une nouvelle borne inférieure pour les méthodes itératives. En utilisant une matrice d'échantillonnage $S$ pour calculer une direction approchée $p$, ils peuvent évaluer la formule pour un seul vecteur de droite afin d'obtenir une valeur $\mu(Ap/\|p\|_2, r_\theta)$.
  • Cette valeur est prouvée être une borne inférieure de la vraie erreur arrière.
  • L'article démontre que cette borne inférieure est de qualité comparable à l'estimation échantillonnée de Karlson-Waldén, satisfaisant spécifiquement l'inégalité :
    $$\frac{1-\eta^2}{1+\eta^2} \nu(A, r_\theta) \leq \mu(Ap/\|p\|_2, r_\theta) \leq \mu(A, r_\theta)$$
    où $\eta$ représente la distorsion de l'échantillonnage et $\nu$ est l'estimation de Karlson-Waldén.
• Raffinement itératif et recyclage : L'article discute de méthodes pour améliorer cette estimation via un raffinement itératif du vecteur $p$ et le « recyclage » du vecteur calculé $Ap$ au cours des itérations pour réduire le coût computationnel.

Résultats
Des expériences numériques ont été menées en utilisant le solveur LSMR sur une matrice de la collection SuiteSparse avec un nombre de conditionnement élevé ($\approx 3.5 \times 10^{16}$). Les résultats indiquent :

• La borne inférieure proposée est constamment comparable en précision à l'estimation échantillonnée de Karlson-Waldén.
• Dans les cas avec des échantillonnages moins coûteux (plus petit $n_{sketch}$), la borne inférieure proposée était parfois plus précise que l'estimation échantillonnée de Karlson-Waldén.
• La borne inférieure « recyclée » (réutilisant $Ap$ au cours des itérations) est restée proche de la vraie erreur arrière pendant une partie significative de l'historique des itérations, suggérant son utilité comme moniteur d'erreur peu coûteux.
• Le raffinement itératif du vecteur $p$ n'a amélioré la précision que lorsque la taille de l'échantillon était très grande ($16n$), suggérant que pour des tailles d'échantillon standard, le coût computationnel ajouté pourrait ne pas être justifié.
• Les tentatives pour construire des bornes supérieures en utilisant des techniques similaires se sont révélées seulement marginalement meilleures que les bornes simples existantes (comme $\|A^T r\|_2 / \|r\|_2$) et ont toujours surestimé de manière significative la vraie erreur.

Signification et affirmations
L'article affirme que sa signification principale est théorique : il fournit une décomposition de l'erreur arrière qui conduit naturellement à des bornes inférieures calculables.

• Fiabilité : Contrairement à l'estimation échantillonnée de Karlson-Waldén, qui n'est pas garantie d'être une borne supérieure ou inférieure, la méthode proposée produit une borne inférieure stricte. Cela est précieux pour les critères d'arrêt, car il garantit que l'erreur vraie est au moins aussi grande que l'estimation.
• Efficacité : La méthode permet de convertir une estimation basée sur l'échantillonnage en une borne inférieure de qualité comparable, mais avec la garantie supplémentaire d'être une borne.
• Modestie : Les auteurs sont modestes concernant les bornes supérieures, notant que leurs tentatives pour produire des bornes supérieures de manière similaire ont été « généralement infructueuses ». Ils reconnaissent que la décomposition pour plusieurs vecteurs de droite implique une optimisation sur deux matrices ($P$ et $Q$), ce qui est plus complexe que l'optimisation d'un seul vecteur requise pour la borne inférieure. Des travaux futurs sont suggérés pour traiter le cas de plusieurs vecteurs de droite et pour investiguer pourquoi la recherche de bonnes bornes supérieures semble plus difficile que la recherche de bonnes bornes inférieures.