04/12/2022, 23:09
E' dato il problema ai minimi quadrati :
$min_(X inRR^(mxxs))||B − AX||_F$ tale che $AinRR^(nxxm)$, $BinRR^(nxxs)$
con $A$ di rango massimo.
a) Descrivi in dettaglio un algoritmo per determinare $X$, che lavori su tutte le colonne di $B $contemporaneamente, illustrandone anche il costo computazionale.
b)Modifica l’algoritmo proposto nel caso $B = B_1B_2^T$ con $B_1inRR^(nxxr)$, $B_2 ∈RR^(sxxr)$, $r < s$, spiegando la procedura usata.
a) Usiamo le matrici di Householder (fattorizzazione $QR$ di $A$) per trovare $R_1$ e $B_1$: abbiamo che $Q^T[A,B]=[R,\hat B]$ (con $Q=[Q_1,Q_2]$) in cui $R=[(R_1),(0)]$ e $\hat B=[(Q_1^TB),(Q_2^TB)]$ e poniamo $B_1=Q_1^TB$. Il costo computazionale di questo processo è di $2nm^2-2/3m^3+4nms-2m^2s$ flops (sperando di aver fatto bene i calcoli). Ora abbiamo che $||B − AX||_F^2=||Q Q^TB − QRX||_F^2=||Q(Q^TB − RX)||_F^2=||Q^TB − RX||_F^2=||[(Q_1^TB-R_1X),(Q_2^TB)]||_F^2=||Q_1^TB-R_1X||_F^2+||Q_2^TB||_F^2$
Per cui deve valere che $Q_1^TB-R_1X=0$ da cui $R_1X=Q_1^TB=B_1$. Poichè $R_1$ triangolare superiore risolvo il sistema così (riporto a destra i costi di ogni commando):
$x_{m,j}=b_{m,j}/r_{m,m}$ con $j=1,...,s$ ($s$ flops)
$x_{i,j}=(b_{i,j}-\sum_{k=i+1}^m r_{i,k}x_{k,j})/r_{i,i}$ con $i=m-1,...,1$ e $j=1,...,s$ ($s(2(m-i)+1)$ flops).
In totale abbiamo $sm^2-s$ flops.
ll costo complessivo di tutto l'algoritmo è di $ 2nm^2-2/3m^3+4nms-m^2s $ flops.
Per la parte b) non ho ben capito come la decomposizione $B = B_1B_2^T$ dovrebbe in qualche modo modificare l'algoritmo che ho fatto, qualcuno mi può dare un aiuto, grazie.