Mise sous forme bidiagonale

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 :

Bidiag

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 $

Implémentation

  • Question : Mettre en place l’algorithme de mise sous forme bidiagonale, de manière à renvoyer la matrice transformée, ainsi que les changements de base à gauche et à droite.

Analyse

  • Question : Vérifier que l’invariant est conservé à chaque étape de votre algorithme.