Numerical Methods & Scientific Computing: lecture notes
Data fitting
The matrix 2-norm
If
k r k2) =) can no longer avoid the matrix 2-norm :
Itis Sym(AtIA), HAIK= Hmm,CA)! The 2-norm is the natural norm for LSQ problems (minimizing
Example:
for a square matrix A (see ‘MatrixNorms’ for proof) kAk2 = q max(AT A)
max(AT A) is the largest eigenvalue of AT A
(all eigenvalues are positive since AT A is positive definite).
Numerical Methods & Scientific Computing: lecture notes
Data fitting
Singular value decomposition SVD
It is easier to characterize the condition number in the 2-norm in terms of the singular values of A. To do that we need the
Definition
A m ⇥ n real matrix A has the singular value decomposition A = U⌃VT
where
1 U is m ⇥ m orthogonal matrix
2 ⌃ is a diagonal m⇥n real matrix
3 V is n ⇥ n orthogonal matrix
The non-negative diagonal entries { k 0} in ⌃ are called the singular values of A.
In our case, where m > n, there are n positive singular values
1 2… n >0,ifAisoffullrank.
“” I
“” j:” “”
I ;.gl]
TT
f. A=
V
E
ie. OT = OUT = Iman ,,
&-V are
. Example.
=
orthogonal
I = OT V T V = V- V T = I n x n ⇐ V – I = – V ?
Y;:]
orthogonal matrix
⇐ rotation transformation
Msn
–
I 6h Z O
value of matrix
.
G I 627 63 Z – i .
”
singular
A
If It is full rank, bn ,
so
If it
Lemma: IfOE1km’MandVElk””” are orthogonal, thenIt AlkaHAVIk=HAH
Proof:
Lemma: Proof:
is a n orthogonal matrix ,
H-UxIl}= (0×51ox=XT TUX= XTX= Hill!
mmMr AE1kWh
noAlk- Yayot= Y: ”
T” iti
=
It Alk .
Intuiting:
HYE #
‘t
un
112=11×112
-“- —
in:
: “÷Y
NHI
we
II
then 110×112=11×112
ng
,. –
.
.
Numerical Methods & Scientific Computing: lecture notes
Data fitting
The matrix 2-norm
Then from the definition above, we get kAk2 = 1(A)
Proof:
B
kill EV’ll, =H-21k.
VE l’t
E–
C- Hymn
[”
“” TixZamani Kittu-1658 EG
6.
q
)
k=mx¥o ttlkh
,
*
,
A
HIM of
s-GFEE.FR f-
0ft – utxph
HEIIs= 7 mxax “÷Y!
61
*
Etf all
= T- ”
= 6,
Numerical Methods & Scientific Computing: lecture notes
Data fitting
The pseudoinverse
The pseudoinverse A† = (AT A) 1AT can be expressed in terms of the SVD of A:
A† = V⌃†UT
where ⌃† is the n ⇥ m diagonal matrix, with entries {1/ k }. Proof:
At = CATAN AT MFT
EATA I V IT -UT
= TV312ft = tf FT
Z ET
A= V-2 =/” ” ;q )
+Angular value decomposition
a. Ez- =
(HAH = II’
)”
(“‘
– diag big . g.)
(VII.VT)’ ‘ =
=L””
y,;]
the largest singular value of ATA :
G’
.
.
,
-i.
.
smallest –
=L
‘I’LI’ V” = AT
of
f
ATA
. .
‘
.
( H AYAT
=
VK.t-VT-u-z-V-JT-VI-vi-ET-u.si
2=1″” ) jon
⇐ ‘i”” I””:
=L””
in
= EATIT T ”
Ii Z’=Li. 0] .↳
“.tl” ” .no) – iii.not
Numerical Methods & Scientific Computing: lecture notes
Data fitting
The condition number of a rectangular matrix
ItOT HATHa 11It112 By the same argument, we get
kA†k2 = 1/ n(A)
By the same argument as before, the condition number of a-rectangular
matrix is given by
KRAI HIAHa HA- Ilk 2(A) = ||A||2||A†||2 = 1(A)/ n(A)
wun
+ the ratio of the largest singular value
Proof:
Htt= V
to
the
smallest
singular
value
.
Numerical Methods & Scientific Computing: lecture notes
Data fitting
Sensitivity of the normal equations
The normal equations
are a linear system, so the sensitivity is given by the condition number of
AT A. But Proof:
ATAx = ATb 2(AT A) = 2(A)2
If
KCATAt =
nuns ATI make i t of
= (Tn)
= kz CA) ”
the largest singular value
TA
=
‘
Numerical Methods & Scientific Computing: lecture notes
Data fitting
Sensitivity of the LSQ problem
It turns out : condition number of LSQ problem is
⇡ 2(A) if the fit to the data is good (not much scatter)
[-n2
⇡ 2(A) me
fit is good)
‘ 1
!’
.
O
μ
to
if the fit to the data is poor (a lot of scatter)
i=) using normal equations worsens conditioning of problem (if the
,
www.nnmw
1 o
o
a
° a
Numerical Methods & Scientific Computing: lecture notes
Data fitting
Better ways to solve the LSQ problem
A# IRM’M’
th > n =⇒ full rank
if tankette. .
Vanklfttch ⇒ tank
If A is of full rank, use another matrix factorization — the QR
factorization
For rank-deficient matrices, use the QR factorization with column pivoting (MATLAB) aka Rank-revealing QR
or the singular value decomposition SVD
We’ll assume A is of full rank. ummm
deficient
Numerical Methods & Scientific Computing: lecture notes
Data fitting
QR factorization
–
The idea of (‘economy-size’) QR factorization is:
form a factorization
A = QR mm
where Q is orthogonal m ⇥ n matrix, R is upper triangular n ⇥ n matrix i.e. QT Q = In
matrix
–
to solve Ax = b, mm
triangular
+ upper QRx = b ) QT QRx = QT b ) Rx = QT b
ummm un mmmm
so solve a triangular system for x in O(n2) ops! un
Numerical Methods & Scientific Computing: lecture notes
Data fitting
Gram-Schmidt process
Ymou’ve seen a QRmfactorization befmore (in disguise) min Gram-Schmidt orthogonalization:
given a s
forming an n-D subspace of Rm, Gram-Schmidt orthogonaliza-
et of linearly in
dependent vecto
mum
tion produces a set of orthonormal vectors {q1,q2···qn}, an orthonormal basis of the same subspace.
.”
A = QR
i.e. use triangular transformations to produce an orthogonal matrix. We don’t do it this way because it’s numerically unstable; instead we use orthogonal transformations to turn A into R.
my
Given’s transform Household afro
,
transform
rs {a ,a ···a } 12n
iHi” AH, 1
!
Ay= binf-it.”
⇒
l l l
l
=bhottbak t ,
t blatk
bbk
ah- KiAh
ay= kithtrash
Gtramkhmidtproass
{ ay. . . . . aan} linearly independent ay,
I, = brain 12=11129 than
in 1km E.ooh, = I ⇒ by
E.I,so, E.o;f’t ⇒ b12, 622.
It
.
; Gua , 9th auto
gig tbint,nfy.itbanana
–
m=p- -mfun. fun Inoff
Io ⇒ bln 12h ” but h bnn
t t'” tthtn ,then ,
ay= mmr
ring Katy fun Ann
..”
Ii:/ AQK
HMM 1μmx n
-a= . L a n a i ; ] ‘L E E .
m ” m
– ,. ,,,.
HI” “r:”
lamb
Numerical Methods & Scientific Computing: lecture notes
Data fitting
Orthogonal transformations
xu — avg min Kruk = It bn- AYY Ayy → QAy=Qk I → QE
Orthogonal transformations are good because:
they involve perfectly-conditioned matrices
✓ 1101112=11412
they don’t change the conditioning of the problem
Proofs:
they don’t change the solution of the LSQ problem
mmmm
Ktv) =/.
I t H E I ⇒ H u l k – m y T” i f f ! = 7 ¥ :
4 At ATT
KzCQA) = HQAlk II AttHz CQATT = A’ Q’t = = HAIK11AtQT112
= HAIKHAT112 = KsCA) .
Numerical Methods & Scientific Computing: lecture notes
Data fitting
Complexity of QR
The QR factorization takes n2(m n/3) ops
war- but allows us to handle a larger class of matrices.
i.e. for m n, ⇡ twice as expensive as Cholesky factorization of normal
Example
our
equations
For square systems, can use QR (normwise backward stable) ! takes 3-~w
2n /3 ops Man
twice as expensive as GEPP but no issues re growth factor etc.
ummm
Numerical Methods & Scientific Computing: lecture notes
Data fitting
QR in MATLAB
mm.
I have described what MATLAB calls ‘economy-size QR’ factorization. A = QR
where Q is orthogonal m ⇥ n matrix, R is upper triangular n ⇥ n matrix.
This is all we need for the LSQ problem.
–
–
MATLAB by default produces the ‘full QR’ factorization
̄ ̄ A = QR
–
where Q ̄ is orthogonal m ⇥ m matrix, R ̄ is upper triangular m ⇥ n matrix
–
Q ̄ = [Q | extra orthog. cols]; R ̄ =
o R
0
–
–
so that Q ̄ T Q ̄ = Im . The extra columns are never used in the LSQ problem.
Numerical Methods & Scientific Computing: lecture notes
Data fitting
Using QR
-TTTT T SinceA A=R Q QR=R R,RistheCholeskyfactorofA A.
Hence to solve LSQ problem, we could:
ummm
1
2 → 3
[q,r]=qr(A,0);x=r\(q’*b);
mmmm
easiest to understand
– 9-‘ fr x –
t
Ax z b
‘ 9-‘ Axs 9- b
in
rt
–mm
G’d if’ b
r=triu(qr(A));x=r\(r’\(A’*b));
better since never need to form Q x=A\b;
⇒
. -T
\ acting on overdetermined system does the same as 2 (unless A A is rank-deficient)
A has full tank
Numerical Methods & Scientific Computing: lecture notes
Data fitting
The rank-deficient case
Suppose the matrix A has rank k < n i.e. is rank-deficient or not of full rank. This means the columns of A are not linearly independent. In this case, there is no unique solution, and we usually use the solution with minimum 2-norm. This solution can be found by either of:
1 QR factorization with column pivoting aka Rank revealing QR (RR-QR), based on
AE = QR -
A=U⌃VT =[U1 U2] ⌃1 0 [V1 V2] 00
xLS = A†b = V1⌃ 1UT b 11
obtained in MATLAB by a 3-output call to qr
2 the SVD
In the latter case, let v μ .
-
then
Numerical Methods & Scientific Computing: lecture notes
Data fitting
End of Week 8