Lecture 4 Orthonormal sets of vectors and QR factorization PDF

6.3 Orthogonal and orthonormal vectors

6.3 Orthogonal and orthonormal vectors. Definition. We say that 2 vectors are orthogonal if they are perpendicular to each other.

5. Orthogonal matrices

R × has orthonormal columns if its Gram matrix is the identity matrix: a square real matrix with orthonormal columns is called orthogonal.

21. Orthonormal Bases

In addition to being orthogonal each vector has unit length. Suppose T = {u1

Orthogonal but not Orthonormal

https://empslocal.ex.ac.uk/people/staff/reverson/uploads/Site/procrustes.pdf

Lecture 4 Orthonormal sets of vectors and QR factorization

slang: we say 'u1

Orthogonal and orthonormal sets

24-Feb-2015 Note that if S is orthonormal then o ? S

Math 115A - Week 9 Textbook sections: 6.1-6.2 Topics covered

Orthonormal bases. • Gram-Schmidt orthogonalization. • Orthogonal complements. *****. Orthogonality. • From your lower-division vector calculus you know

Orthogonality

slang: we say 'u1;:::;uk are orthonormal vectors' but orthonormality (like I (you'd think such matrices would be called orthonormal not orthogonal).

Orthonormal Bases in Hilbert Space APPM 5440 Fall 2017 Applied

02-Dec-2017 Let (ek) be an orthonormal sequence in an inner product space X. Let x ? X. The quantities. ?ekx? are called the Fourier coefficients of x ...

Orthonormal Sets • Bessel Inequality • Total Orthonormal Sequences

EL3370 Orthogonal Expansions - 5. BESSEL INEQUALITY. Theorem (Bessel Inequality). If !! {e n. } is an orthonormal sequence in an inner product space V

EE263 Autumn 2007-08Stephen Boyd

Lecture 4

Orthonormal sets of vectors andQRfactorization

orthonormal sets of vectors

Gram-Schmidt procedure,QRfactorization

orthogonal decomposition induced by a matrix

4-1

Orthonormal set of vectors

set of vectorsu1,...,uk?Rnis

normalizedif?ui?= 1,i= 1,...,k

(uiare calledunit vectorsordirection vectors)

orthogonalifui?ujfori?=j

orthonormalif both

slang:we say 'u1,...,ukare orthonormal vectors" but orthonormality (like independence) is a property of a set of vectors, not vectors individually in terms ofU= [u1···uk], orthonormal means U TU=Ik

Orthonormal sets of vectors andQRfactorization4-2

orthonormal vectors are independent(multiplyα1u1+α2u2+···+αkuk= 0byuTi)

henceu1,...,ukis an orthonormal basis for

span(u1,...,uk) =R(U) warning: ifk < nthenUUT?=I(since its rank is at mostk) (more on this matrix later . . . )

Orthonormal sets of vectors andQRfactorization4-3

Geometric properties

suppose columns ofU= [u1···uk]are orthonormal ifw=Uz, then?w?=?z?

multiplication byUdoes not change norm

mappingw=Uzisisometric: it preserves distances

simple derivation using matrices:

?w?2=?Uz?2= (Uz)T(Uz) =zTUTUz=zTz=?z?2

Orthonormal sets of vectors andQRfactorization4-4

inner productsare also preserved:?Uz,U˜z?=?z,˜z?

ifw=Uzand˜w=U˜zthen

?w,˜w?=?Uz,U˜z?= (Uz)T(U˜z) =zTUTU˜z=?z,˜z? norms and inner products preserved, soanglesare preserved: (Uz,U˜z) =? (z,˜z) thus, multiplication byUpreserves inner products, angles, and distances

Orthonormal sets of vectors andQRfactorization4-5

Orthonormal basis for Rn

supposeu1,...,unis an orthonormalbasisforRn

thenU= [u1···un]is calledorthogonal: it is square and satisfies U TU=I (you"d think such matrices would be calledorthonormal, notorthogonal) it follows thatU-1=UT, and hence alsoUUT=I,i.e., n i=1u iuTi=I

Orthonormal sets of vectors andQRfactorization4-6

Expansion in orthonormal basis

supposeUis orthogonal, sox=UUTx,i.e., x=n? i=1(uTix)ui uTixis called thecomponentofxin the directionui a=UTxresolvesxinto the vector of itsuicomponents

x=Uareconstitutesxfrom itsuicomponents

x=Ua=n?

i=1a iuiis called the (ui-)expansionofx

Orthonormal sets of vectors andQRfactorization4-7

the identityI=UUT=?ni=1uiuTiis sometimes written (in physics) as I=n? i=1|ui??ui| since x=n? i=1|ui??ui|x? (but we won"t use this notation)

Orthonormal sets of vectors andQRfactorization4-8

Geometric interpretation

ifUis orthogonal, then transformationw=Uz

preservesnormof vectors,i.e.,?Uz?=?z?

preservesanglesbetween vectors,i.e.,?

(Uz,U˜z) =? (z,˜z) examples:

rotations (about some axis)

reflections (through some plane)

Orthonormal sets of vectors andQRfactorization4-9

Example:rotation byθinR2is given by

y=Uθx, Uθ=?cosθ-sinθ sinθcosθ? reflection across linex2=x1tan(θ/2)is given by y=Rθx, Rθ=?cosθsinθ sinθ-cosθ? Orthonormal sets of vectors andQRfactorization4-10 x 1x1x 2x2 e 1e1e

2e2rotation reflection

can check thatUθandRθare orthogonal Orthonormal sets of vectors andQRfactorization4-11

Gram-Schmidt procedure

given independent vectorsa1,...,ak?Rn, G-S procedure finds orthonormal vectorsq1,...,qks.t. thus,q1,...,qris an orthonormal basis forspan(a1,...,ar) rough idea of method: firstorthogonalizeeach vector w.r.t. previous ones; thennormalizeresult to have norm one Orthonormal sets of vectors andQRfactorization4-12

Gram-Schmidt procedure

step 1a.˜q1:=a1

step 1b.q1:= ˜q1/?˜q1?(normalize)

step 2a.˜q2:=a2-(qT1a2)q1(removeq1component froma2)

step 2b.q2:= ˜q2/?˜q2?(normalize)

step 3a.˜q3:=a3-(qT1a3)q1-(qT2a3)q2(removeq1,q2components)

step 3b.q3:= ˜q3/?˜q3?(normalize)

etc.

Orthonormal sets of vectors andQRfactorization4-13

˜q1=a1q1q

2˜q2=a2-(qT1a2)q1a2

fori= 1,2,...,kwe have a i= (qT1ai)q1+ (qT2ai)q2+···+ (qTi-1ai)qi-1+?˜qi?qi =r1iq1+r2iq2+···+riiqi (note that therij"s come right out of the G-S procedure, andrii?= 0) Orthonormal sets of vectors andQRfactorization4-14

QRdecomposition

written in matrix form:A=QR, whereA?Rn×k,Q?Rn×k,R?Rk×k: a1a2···ak?

A=?q1q2···qk?

Q???? r

11r12···r1k

0r22···r2k............

0 0···rkk????

QTQ=Ik, andRis upper triangular & invertible

calledQRdecomposition(or factorization) ofA

usually computed using a variation on Gram-Schmidt procedurewhich is less sensitive to numerical (rounding) errors

columns ofQare orthonormal basis forR(A)

Orthonormal sets of vectors andQRfactorization4-15

General Gram-Schmidt procedure

in basic G-S we assumea1,...,ak?Rnare independent ifa1,...,akare dependent, we find˜qj= 0for somej, which meansaj is linearly dependent ona1,...,aj-1 modified algorithm: when we encounter˜qj= 0, skip to next vectoraj+1 and continue: r= 0; fori= 1,...,k

˜a=ai-?rj=1qjqTjai;

if˜a?= 0{r=r+ 1;qr= ˜a/?˜a?;} Orthonormal sets of vectors andQRfactorization4-16 on exit, q1,...,qris an orthonormal basis forR(A)(hencer=Rank(A)) eachaiis linear combination of previously generatedqj"s in matrix notation we haveA=QRwithQTQ=IrandR?Rr×kin upper staircase form: zero entries possibly nonzero entries 'corner" entries (shown as×) are nonzero Orthonormal sets of vectors andQRfactorization4-17 can permute columns with×to front of matrix:

A=Q[˜R S]P

where:

QTQ=Ir

˜R?Rr×ris upper triangular and invertible

P?Rk×kis a permutation matrix

(which moves forward the columns ofawhich generated a newq) Orthonormal sets of vectors andQRfactorization4-18

Applications

directly yields orthonormal basis forR(A)

yields factorizationA=BCwithB?Rn×r,C?Rr×k,r=Rank(A) to check ifb?span(a1,...,ak): apply Gram-Schmidt to[a1···akb] staircase pattern inRshows which columns ofAare dependent on previous ones works incrementally: one G-S procedure yieldsQRfactorizations of [a1···ap]forp= 1,...,k: [a1···ap] = [q1···qs]Rp wheres=Rank([a1···ap])andRpis leadings×psubmatrix ofR Orthonormal sets of vectors andQRfactorization4-19 'Full"QRfactorization withA=Q1R1theQRfactorization as above, write

A=?Q1Q2??R1

0? where[Q1Q2]is orthogonal,i.e., columns ofQ2?Rn×(n-r)are orthonormal, orthogonal toQ1 to findQ2: find any matrix˜As.t.[A˜A]is full rank (e.g.,˜A=I)

apply general Gram-Schmidt to[A˜A]

Q1are orthonormal vectors obtained from columns ofA Q2are orthonormal vectors obtained from extra columns (˜A) Orthonormal sets of vectors andQRfactorization4-20 i.e., any set of orthonormal vectors can beextendedto an orthonormal basis forRn R(Q1)andR(Q2)are calledcomplementary subspacessince they are orthogonal (i.e., every vector in the first subspace is orthogonal to every vector in the second subspace) their sum isRn(i.e., every vector inRncan be expressed as a sum of two vectors, one from each subspace) this is written

R(Q1)?+R(Q2) =Rn

R(Q2) =R(Q1)?(andR(Q1) =R(Q2)?)

(each subspace is theorthogonal complementof the other) we knowR(Q1) =R(A); but what is its orthogonal complementR(Q2)? Orthonormal sets of vectors andQRfactorization4-21

Orthogonal decomposition induced byA

fromAT=?RT10??QT 1QT 2? we see that A

Tz= 0??QT

1z= 0??z? R(Q2)

soR(Q2) =N(AT) (in fact the columns ofQ2are an orthonormal basis forN(AT)) we conclude:R(A)andN(AT)arecomplementary subspaces:

R(A)?+N(AT) =Rn(recallA?Rn×k)

R(A)?=N(AT)(andN(AT)?=R(A))

calledothogonal decomposition (ofRn) induced byA?Rn×k Orthonormal sets of vectors andQRfactorization4-22 everyy?Rncan be written uniquely asy=z+w, withz? R(A), w? N(AT)(we"ll soon see what the vectorzis . . . ) can now prove most of the assertions from the linear algebra review lecture switchingA?Rn×ktoAT?Rk×ngives decomposition ofRk:

N(A)?+R(AT) =Rk

Orthonormal sets of vectors andQRfactorization4-23quotesdbs_dbs48.pdfusesText_48

[PDF] Lecture 4 Orthonormal sets of vectors and QR factorization

EE263 Autumn 2007-08Stephen Boyd

Lecture 4

Orthonormal sets of vectors andQRfactorization

orthonormal sets of vectors

Gram-Schmidt procedure,QRfactorization

orthogonal decomposition induced by a matrix

Orthonormal set of vectors

normalizedif?ui?= 1,i= 1,...,k

orthogonalifui?ujfori?=j

orthonormalif both

Orthonormal sets of vectors andQRfactorization4-2

henceu1,...,ukis an orthonormal basis for

Orthonormal sets of vectors andQRfactorization4-3

Geometric properties

multiplication byUdoes not change norm

simple derivation using matrices:

Orthonormal sets of vectors andQRfactorization4-4

ifw=Uzand˜w=U˜zthen

Orthonormal sets of vectors andQRfactorization4-5

Orthonormal basis for Rn

supposeu1,...,unis an orthonormalbasisforRn

Orthonormal sets of vectors andQRfactorization4-6

Expansion in orthonormal basis

x=Uareconstitutesxfrom itsuicomponents

x=Ua=n?

Orthonormal sets of vectors andQRfactorization4-7

Orthonormal sets of vectors andQRfactorization4-8

Geometric interpretation

preservesnormof vectors,i.e.,?Uz?=?z?

preservesanglesbetween vectors,i.e.,?

rotations (about some axis)

reflections (through some plane)

Orthonormal sets of vectors andQRfactorization4-9

Example:rotation byθinR2is given by

2e2rotation reflection

Gram-Schmidt procedure

Gram-Schmidt procedure

step 1a.˜q1:=a1

step 1b.q1:= ˜q1/?˜q1?(normalize)

step 2b.q2:= ˜q2/?˜q2?(normalize)

step 3b.q3:= ˜q3/?˜q3?(normalize)

etc.

˜q1=a1q1q

2˜q2=a2-(qT1a2)q1a2

QRdecomposition

A=?q1q2···qk?

11r12···r1k

0r22···r2k............

0 0···rkk????

QTQ=Ik, andRis upper triangular & invertible

calledQRdecomposition(or factorization) ofA

columns ofQare orthonormal basis forR(A)

General Gram-Schmidt procedure

˜a=ai-?rj=1qjqTjai;

A=Q[˜R S]P

QTQ=Ir

˜R?Rr×ris upper triangular and invertible

P?Rk×kis a permutation matrix

Applications

directly yields orthonormal basis forR(A)

A=?Q1Q2??R1

apply general Gram-Schmidt to[A˜A]

 R(Q1)?+R(Q2) =Rn

 R(Q2) =R(Q1)?(andR(Q1) =R(Q2)?)

Orthogonal decomposition induced byA

Tz= 0??QT

1z= 0??z? R(Q2)

 R(A)?+N(AT) =Rn(recallA?Rn×k)

 R(A)?=N(AT)(andN(AT)?=R(A))

N(A)?+R(AT) =Rk

orthonormal sets of vectors

Gram-Schmidt procedure,QRfactorization

orthogonal decomposition induced by a matrix

normalizedif?ui?= 1,i= 1,...,k

orthogonalifui?ujfori?=j

orthonormalif both

henceu1,...,ukis an orthonormal basis for

multiplication byUdoes not change norm

simple derivation using matrices:

ifw=Uzand˜w=U˜zthen

supposeu1,...,unis an orthonormalbasisforRn

x=Uareconstitutesxfrom itsuicomponents

x=Ua=n?

preservesnormof vectors,i.e.,?Uz?=?z?

preservesanglesbetween vectors,i.e.,?

rotations (about some axis)

reflections (through some plane)

step 1a.˜q1:=a1

step 1b.q1:= ˜q1/?˜q1?(normalize)

step 2b.q2:= ˜q2/?˜q2?(normalize)

step 3b.q3:= ˜q3/?˜q3?(normalize)

etc.

QTQ=Ik, andRis upper triangular & invertible

calledQRdecomposition(or factorization) ofA

columns ofQare orthonormal basis forR(A)

QTQ=Ir

P?Rk×kis a permutation matrix

directly yields orthonormal basis forR(A)

apply general Gram-Schmidt to[A˜A]

R(Q1)?+R(Q2) =Rn

R(Q2) =R(Q1)?(andR(Q1) =R(Q2)?)

R(A)?+N(AT) =Rn(recallA?Rn×k)

R(A)?=N(AT)(andN(AT)?=R(A))