Supposons maintenant disposer d’une matrice initiale $A$ de dimension $n\times m$ censée représenter une image. Nous allons commencer par transformer cette matrice en la mettant sous forme bidiagonale :
Rappelons que la factorisation $QR$ est une méthode permettant de mettre une matrice donnée sous la forme d’un produit d’une matrice orthogonale et d’une matrice triangulaire supérieure. Ici, nous allons nous autoriser à multiplier à gauche et à droite par des matrices orthogonales pour obtenir cette forme bidiagonale. Considérons l’algorithme suivant (dans lequel les indices des tableaux commencent à $0$) :
Qleft = Id; Qright = Id; BD = A;
For i from 0 to (n-1)
# Let Q1 be a HH matrix mapping BD[i:n,i] on a vector with a single non-zero element
Qleft = Qleft * Q1;
BD = Q1 * BD,
If (not(i==(m-2)))
# Let Q2 be a HH matrix mapping BD[i,(i+1):m] on a vector with a single non-zero element
Qright = Q2 * Qright
BD = BD * Q2
End if
End for
Return (Qleft, BD, Qright)
Concrètement, on place les zéros nécessaires sur la première colonne, puis sur la première ligne, puis sur la seconde colonne … À chaque tour de boucle de l’algorithme, on peut vérifier que : $ Q_{left} \times BD \times Q_{right} = A $