Please enable JavaScript.
Coggle requires JavaScript to display documents.
Approssimazione Minimi Quadrati - Coggle Diagram
Approssimazione Minimi Quadrati
QR
Teorema
Data A € R^(mxn), esistono Q € R^(mxm) ortogonale e R° € R^(nxn) triangolare superiore (e non singolare se rank(A) =n ) tali che
A=QR=Q(R° 0)^T
A=QR prende il nome di fattorizzazione QR di A
come si ottiene?
Matrici elementari di householder
se rank(A)=n
H= I- (2/v^T v)vv^T
v != 0
per soddisfare Hz=alpha e1
alpha € R, z!=0 ,
H ortogonale, e1=(1 0 ... 0)^T
||z||^2 2 =z^T z= ...= alpha^2
scegliendo v=z- alpha e1
Hz=alpha e1
si passa da A(0) a A(1)=H1A(0)
fino ad A(n)=Hn...H1A=R
A=(Hn...H1)^-1 R
sappiamo cosa sia Q adesso
soluzione problema minimi quadrati
ponendo x° uguale alla soluzione del sistema R°x=g1
||Ax°-b||2 =||R°x°-g1||2+||g2||2=||g2||2=min||Ax-b||2
essendo R° triangolare superiore, il sistema è facilmente risolvibile
SVD
richiamo:
autovalori e autovettori
Ax=lambda x
x autovettore
lambda autovalore
sigma(A)=spettro di A
(A-lambda I)x=0
se e solo se
det(A-lambda I)=0
equazione caratteristica polinomiale
Teorema di Gershgorin
A matrice nxn
Ri := {z € C: |z-a_ij|<=SUM |a_ij|}
sigma(A) contenuto uguale U Ri
Se esistono k cerchi tali che (U Ri con i da 1 a k) intersezione (U Ri con i da k+1 a n) sia vuota,allora (U Ri con i da 1 a k) contiene esattamente k autovalori
Matrici simili
A,B matrici nxn sono (unitariamente) simili se esiste T invertibile (T unitaria, cioé T^-1 =T°) tale che B=T^-1 A T
A,B sono simili --> hanno gli stessi autovalori
Teorema di Schar
A matrice nxn, esiste T tale che U= T^-1 A T, dove U matrice triangolare superiore
altri teoremi
A simile ad una matrice diagonale D se e solo se esiste base di autovettori per R^n
Allora D=S^-1 A S
D matrice diagonale con gli autovalori sulla diagonale
matrice le cui colonne sono autovettori
A simmetrica se e solo se esiste D diagonale, Q ortogonale tale che A=QDQ^T (D=Q^T AQ)
corollario: A€R^(nxn) simmetrica --> esiste v1,...,vn autovettori ortonormali e gli autovalori € R
decomposizione a valori singolari
A€C^(mxn)
allora
esistono U€C^(mxm) V€C^(nxn)
matrici unitarie
A=UEV°
E=matrice con tutti 0 tranne nella diagonale principale dove abbiamo i sigma
sigmaij=0 se i!=j
sigmaii=sigmai
sigma1>sigma2>...>sigmap>0
(son tutti maggiore uguale)
matrice A composta come prima,
sigma k strettamente maggiore di sigma k+1=...=
sigma p=0
Im(A)=<u1,...,uk>
sigma_i^2 sono gli autovalori di A°A e quindi ||A||2=sigma1 ||A||^2 F =SUM sigmai^2
ker(A)=<vk+1,vn>
se A simmetrica(m=n) --> sigma i=|lambdai| dove lambda_i sono gli autovalori di A (vettori sing coincidono con gli autovettori)
A=UkEkVk
solo le prime k colonne
come ottenerla?
calcolo auotovalori
e autovettori di A°A
osservo che A°A
è hermitiana
A°A=QDQ°
Q autovettori sulle colonne
D matrice diagonali con autovalori
considero C=AQ e calcolo
fatt QR di CTT=UR
TT matrice di permutazione
(binaria e ortogonale)
A=CQ°
C=URTT°
A=URTT°Q°
R è E
TT°Q° è V°
per A(m>=n)
approssimazione a
basso rango di matrici
abbiamo A con rank(A)=r
voglio approssimare con B con rank(B)=k<r
teorema:
A=UEV° rank(A)=r
sigma1>=...>=sigma(r+1)=...=sigmap=0
per ogni k<r k€N min||A-B||2=||A-Ak||2=sigma(k+1)
rank(B)=k Ak=SUM sigmai ui vi°
ui i esima col di U
vi iesima col di V
se k=0 otteniamo il numero di condizionamento della matrice
problema lineare dei minimi quadrati
approssimare dati (xi,ji) con y(x)=SUM aj zj(x)
dove zj: R-->R (j=1,...,n) e z1,...,zn son lin indie
scelgo a1,...,an tali che sia minimizzata
sum(yi-y(xi))^2
il problema si riduce a minimizzare ||Za-y||2
Z matrice di collocazione y=[y1 ... ym]^T
a=[a1 ... an]^T
risolvere nel senso dei minimi quadrati
Ax=b con A=Z x=a b=y
possiamo limitarci a considerare il problema
A€R^(mxn) m>=n b€R^m
p_LS:=min||Ax-b||2
X={x€R^n : ||Ax-b||2=p_LS}
x_LS: ||x_LS||2<= ||x||2 per ogni x€X
x€X se e solo se A^T A x= A^T b
X convesso
x_LS esiste ed è unico
X={x_LS} se e solo se A ha rango massimo
teorema:
A=UEV° rank(A)=k A=sum sigmai ui vi°
allora si ha x_LS = SUM (ui°b / sigma i vi) e p_LS^2= SUM (ui° b)^2
Matrice pseudo inversa
(moore - penrose)
A^+ matrice che soddisfa x_LS=A^+ b
dove x_LS è la soluzione di min. norma dal problema dei minimi quadrati
A^+ =V E^+ U°
E^+ al posto di avere i sigma ha gli 1/sigma (0 per i=k,...,p)
permette di estendere il concetto di condizionamento di matrice
mu(A):=||A|| ||A^+||
PCA
dato un insieme di m punti Pi €R^3
vogliamo determinare la direzione w, ||w||2=1
tale che i dati siano maggiormente allineati lungo essa
direzione principale normalizzata
che massimizzi S(w)= SUM((Pi-M)*w)^2
M=(sum Pi)/m
(Pi-m)*w è la proiezione del vettore Pi-M lungo la direzione w
possiamo sempre traslare il sistema di coordinate in modo da far coincidere M con l'origine
individuare direzione principale in cui i punti sono disposti
corrisponde a fare la decomposizione a valori singolari e prendere la prima colonna della Matrice V
dati (xi,yi) € R2 voglio approssimare con una funzione
y(x) = SUM(alpha j z j(x)
zj(x) sono funzioni linearmente indipendenti e gli alpha j sono opportuni coefficienti
scelgo gli alpha j tali che sia minimizzato lo scarto
S:= SUM (yi - y(xi))^2
||y-Zalpha||^2 2
Zalpha=(sum alphaj zj(x1) ... sum alpha j zj(xm))^T
y=(y1 ... ym)^T
il problema si riduce a determinare alpha° tale che
||Zalpha° - y||2 = min ||Zalpha - y||2...
Zalpha=y in generale non ha soluzione
si cerca di minimizzare la norma del residuo ||Zalpha-y||2
Problema Minimi Quadrati
dati A €R ^(mxn) (m>=n), b€R^m, determinare x° tale che ||Ax°-b||2=min||Ax-b||2
pLS
soluziione unica se e solo se il rank(A) =n
si dimostra che rank(A) =n --> x° è la soluzone di A^T Ax =A^T b
risolvere tale sistema non è consigliabile
fattorizzazione QR di A
decomposizione a valori singolari di A