### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Applied Linear Algebra MAT 167

UCD

GPA 3.88

### View Full Document

## 10

## 0

## Popular in Course

## Popular in Mathematics (M)

This 6 page Class Notes was uploaded by Otilia Murray I on Tuesday September 8, 2015. The Class Notes belongs to MAT 167 at University of California - Davis taught by J. Temple in Fall. Since its upload, it has received 10 views. For similar materials see /class/187380/mat-167-university-of-california-davis in Mathematics (M) at University of California - Davis.

## Reviews for Applied Linear Algebra

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/08/15

Lecture 4 The Singular Value Decomposition The singular value decomposition SVD is a matrix factorization whose com putation is a step in many algorithms Equally important is the use of the SVD for conceptual purposes Many problems of linear algebra can be better understood if we rst ask the question what if we take the SVD A Geometric Observation The SVD is motivated by the following geometric fact The image of the unit sphere under any m X n matrix is a hyperellipse The SVD is applicable to both real and complex matrices However in de scribing the geometric interpretation we assume as usual that the matrix is real The term hyperellipse may be unfamiliar but this is just the m dimen sional generalization of an ellipse We may de ne a hyperellipse in IR as the surface obtained by stretching the unit sphere in IR by some factors 01am possibly zero in some orthogonal directions ulum 6 IR For convenience let us take the u to be unit vectors The vectors 021 are the principal semiaxes of the hyperellipse with lengths 01 am If A has rank 7 exactly 7 of the lengths a will turn out to be nonzero and in particular if m 2 n at most n of them will be nonzero 25 26 PART I FUNDAMENTALS The italicized statement above has the following meaning By the unit sphere we mean the usual Euclidean sphere in n space ie the unit sphere in the 2 norm let us denote it by S Then AS the image of S under the mapping A is a hyperellipse as just de ned This geometric fact is not obvious we shall restate it in the language of linear algebra and prove it later For the moment assume it is true Figure 41 SVD of a 2 X 2 matrix Let S be the unit sphere in IR and take any A 6 Tim with m 2 n For simplicity suppose for the moment that A has full rank n The image AS is a hyperellipse in IR we now de ne some properties of A in terms of the shape of AS The key ideas are indicated in Figure 41 First we de ne the n singular ualues of A These are the lengths of the n principal semiaxes of AS written 0102 0 It is conventional to assume that the singular values are numbered in descending order 01 2 02 2 2 0 gt 0 Next we de ne the n left singular uectors of A These are the unit vectors u1u2 uu oriented in the directions of the principal semiaxes of AS numbered to correspond with the singular values Thus the vector 021 is the ith largest principal semiaxis of AS Finally we de ne the n right singular uectors of A These are the unit vectors 121122 vu E S that are the preimages of the principal semiaxes of AS numbered so that Avj ajuj The terms left and right in the de nitions above are decidedly awk ward They come from the positions of the factors U and V in and 43 below What is awkward is that in a sketch like Figure 41 the left singular vectors correspond to the space on the right and the right singular vectors correspond to the space on the left One could resolve this problem by interchanging the two halves of the gure with the map A pointing from right to left but that would go against deeply ingrained habits LECTURE 4 THE SINGL LAR VALUE DECOMPOSITION 27 Reduced SVD we have just mentioned that the equations relating right singular vectors and left singular vectors can be written Av ajuj 13339 E n This collection of vector equations can be expressed as a matrix equation 01 02 vi A 7 212 u or more compactly AV LATE In this matrix equation 3 is an n X n diagonal matrix with positive real entries since A was assumed to have full rank n L7 is an m X n matrix with orthonormal columns and V is an n X n matrix with orthonormal columns Thus V is unitary and we can multiply on the right by its inverse V to obtain A E ilV 42 This factorization of A is called a reduced singular udlue decomposition or reduced S VD of A Schematically it looks like this Reduced SVD m 2 n A if is Vt Full SVD In most applications the SVD is used in exactly the form just described However this is not the standard way in which the idea of an SVD is usu ally formulated we have introduced the awkward term reduced and the unsightly hats on U and E in order to distinguish the factorization from the more standard full SVD This reduced vs full terminology and hatted notation will be maintained throughout the book and we shall make a similar distinction between reduced and full QR factorizations The idea is as follows The columns of L7 are n orthonormal vectors in the m dimensional space 0quot Unless m n they do not form a basis of 28 PART I FUNDAMENTALS 0quot nor is U a unitary matrix However by adjoining an additional m n orthonormal columns U can be extended to a unitary matrix Let us do this in an arbitrary fashion and call the result U If U is replaced by U in 42 then B will have to change too For the product to remain unaltered the last m n columns of U should be multiplied by zero Accordingly let X be the m X n matrix consisting of 3 in the upper n X n block together with m n rows of zeros below we now have a new factorization the full SVD of A A UBV 43 Here U is m X m and unitary V is n X n and unitary and E is m X n and diagonal with positive real entries Schematically Full SVD m 2 n m i A U E V The dashed lines indicate the silent columns of U and rows of E that are discarded in passing from to Having described the full SVD we can now discard the simplifying as sumption that A has full rank If A is rank de cient the factorization is still appropriate All that changes is that now not n but only iquot of the left singular vectors of A are determined by the geometry of the hyperellipse To construct the unitary matrix U we introduce m 7 instead of just m n additional arbitrary orthonormal columns The matrix V will also need n r arbitrary orthonormal columns to extend the 7 columns determined by the geometry The matrix B will now have 7 positive diagonal entries with the remaining n 7 equal to zero By the same token the reduced SVD also makes sense for matrices A of less than full rank One can take U to be m X n with 3 of dimensions n X n with some zeros on the diagonal or further compress the representation so that U is m X r and 3 is r X r and strictly positive on the diagonal Formal De nition Let m and n be arbitrary we do not require m 2 n Given A E Cm not necessarily of full rank a singular value decomposition SVD of A is a factorization A UBV 44 LECTURE 4 THE SINGL LAR VALUE DECOMPOSITION 29 where U E 07 is unitary V 6 CM is unitary E E IR M is diagonal In addition 23 is assumed to have its diagonal entries a nonnegative and in nonincreasing order that is 01 2 02 2 2 0p 2 0 where p minm Note that the diagonal matrix B has the same shape as A even when A is not square but U and V are always square unitary matrices It is clear that the image of the unit sphere in IR under a map A UBV must be a hyperellipse in IR The unitary map V preserves the sphere the diagonal matrix B stretches the sphere into a hyperellipse aligned with the canonical basis and the nal unitary map U rotates or re ects the hyperellipse without changing its shape Thus if we can prove that every matrix has an SVD we shall have proved that the image of the unit sphere under any linear map is a hyperellipse as claimed at the outset of this lecture Existence and Uniqueness Theorem 41 Euery matria A E Cm has a singular ualue decomposition Furthermore the singular ualues 0 are uniquely determined and if A is square and the a are distinct the left and right singular uectors and L3 are uniquely determined up to complea signs ie complea scalar factors of absolute ualue 1 Proof To prove existence of the SVD we isolate the direction of the largest action of A and then proceed by induction on the dimension of A Set 01 By a compactness argument there must be a vector 121 E C with 1 and 01 where 21 A0 Consider any extensions of 121 to an orthonormal basis of C and of 211 to an orthonormal basis of C and let U1 and V1 denote the unitary matrices with columns u and 11 respectively Then we have 01 w U AVS 45 1 1 0 B lt gt where 0 is a column vector of dimension m 1 w is a row vector of dimension n 1 and B has dimensions m 1 X n 1 Furthermore 01 w 01 01 0 B U 2 w 1312 2 of w w12 Since U1 and V1 are unitary we know that 12 1A12 01 so this implies in 0 9 2 gt of w w of w w1 392 implying 13 3 30 PART I FUNDAMENTALS If n 1 or m 1 we are done Otherwise the submatrix B describes the action of A on the subspace orthogonal to 121 By the induction hypothesis B has an SVD B U2 32V Now it is easily veri ed that f 1 0 01 0 1 0 AL1i0 U2ii0 B2i i0 V2i V1 is an SVD of A completing the proof of existence For the uniqueness claim the geometric justi cation is straightforward if the semiaxis lengths of a hyperellipse are distinct then the semiaxes them selves are determined by the geometry up to signs Algebraically we can argue as follows First we note that 01 is uniquely determined by the condition that it is equal to 1A12 as follows from Now suppose that in addition to 121 there is another linearly independent vector in with 1 and 1Aw12 01 De ne a unit vector v2 orthogonal to 121 as a linear combination of 121 and w w ltvxwgtv1 2 1w vfwlvlllg 39 Since 1A12 01 1Av212 g 01 but this must be an equality for otherwise since in 1216 1225 for some constants c and s with C2 s2 1 we would have 1Aw12 lt 01 This vector 122 is a second right singular vector of A corresponding to the singular value 01 it will lead to the appearance of a vector 3 equal to the last at 1 components of va2 with 1 and 1By12 01 we conclude that if the singular vector 121 is not unique then the corresponding singular value 01 is not simple To complete the uniqueness proof we note that as indicated above once 01 and v1 and U1 are determined the remainder of the SVD is determined by the action of A on the space orthogonal to 121 Since 121 is unique up to sign this orthogonal space is uniquely de ned and the uniqueness of the remaining singular values and vectors now follows by induction El Exercises Determine SVDs of the following matrices by hand calculation 3 0 2 0 1 1 1 1 ltagt02ltbgt03ltcgt ltdgt00ltegt Suppose A is an m X n matrix and B is the n X m matrix obtained by rotating A ninety degrees clockwise on paper not exactly a standard mathematical 02 00 00

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.