New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Camryn Rogahn


Camryn Rogahn
GPA 3.61


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Mathematics (M)

This 18 page Class Notes was uploaded by Camryn Rogahn on Tuesday October 20, 2015. The Class Notes belongs to MATH543 at San Diego State University taught by P.Blomgren in Fall. Since its upload, it has received 24 views. For similar materials see /class/225266/math543-san-diego-state-university in Mathematics (M) at San Diego State University.




Report this Material


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: 10/20/15
Peter Blom in V9 M Peter Blomgren blomgren peter gmail com Department of Mathematics and Statistics San Diego CA 9218277720 httpterminussdsuedu Spring 2010 5 Mayan a nu Pml ms 0 Solution 0 Recap 9 Least Squares Problems 0 Problem Language 0 Problem Setup the Vandermonde Matrix 0 Formal Statement 9 LSQ The Solution 0 Pseudoilnverse 0 The MoorePenrose Matrix lnverse 0 3 5 Algorithms for the LSQ Problem Peter Blom Previously Computing the QR factorization 3 ways Gram Schmidt Orthogonalization Modified vs Classical Householder Triangularization Modified Gram Schmidt Householder Numerically stable Even better stability Useful for iterative methods Not as useful for iterative methods Triangular Orthogonalizationquot Orthogonal Triangularizationquot ARlerHRnQ QnHAQZQlAR Work N 2mn2 flops Work N 2mn2 7 27 73 flops Note No Q at this lower cost quot 5quot Peter Blomgren Least Squares Problems 1 Least Squares Problems Q quot ol Iluo S Iitiun Least Squares Least squares datamodel fitting is used everywhere social sciences engineering statistics mathematics In our language the problem is expressed as an overdetermined system Aiamp AECm mgtm Since A is tall and skinny we have more equations than unknowns The least squares solution is defined by EiAi is arg min SEEC Least Squares Some Language The quantity F b 7 A is known as the residual and since our problem is overdetermined we cannot in general hope to find an 52 such that F0 0 Minimizing some norm of F6 is a close second best The choice of the 2 norm leads to a problem that is easy to work with and it is usually the correct choice for statistical reasons computing the least squares solution yields the Maximum Likelihood estimate under certain conditions independent identically distributed variables etc Peter Blomgren Least Squares Problems Recap Least Squares Prohle s be Solution Example Polynomial Data Fitting Figure Illustrating the leastisquares polynomial fit of degrees 1 2 3 6 12 and 18 o d t containing 38 points The top panel of each figure shows the dataset and the fitted polynomial the bottom panel shows the residual as a function of thm polynomial degree r Least Squares Problems Problem Set the Vandermonde Matrix quot y I r v LSQ Iluo Solution Least Squares Problem Set Up So How do we achieve this miracle of data fitting7l We flip back to lecture 2 and express our system using the Vandermonde matrix c b 1 X1 x12 de 0 0 1 2 d C1 b1 xz x2 x2 A 7 c 62 7 b b2 7 1 X x2 Xd 39 39 where the fitting polynomial is described using the coefficients E px Co clx czx2 cdxdi Given the locations of the points i and a particular set of coefficients E the matrixvector product Iquot AE evaluates the polynomial in those points ie T px17 p097 i i i pXm Peter Blon ren quares Problems Recap Least Squares Problems Problem See 19 Vandermonde Matrix r LSQ The Sollitiul Least Squares Thinking About Projectors We can think of the least squares problem in as the problem of finding the vector in rangeA which is closest to b df Since we are measuring using the 2 norm closest e closest In the sense of Euclidean distance We look to minimize the residual F b7 A52 The minimum residual must be orthogonal to rangeA Peter Blomgren 39 Least Squares Problems Recap Least Squares Problems LSQ Tho Solmion 22mm Banana Thetawem may 9mm Let A 6 CW m 2 n and l E Cm he given A vector 6 C minimizes the residual norm Hsz Mb 7 Ail 2 thereby solving the least squares problem if and only if L rangeA that is AF 0 gt AAquotlt Al gt Ai PE Where the orthogonal projector P E Cm maps Cm onto rangeA The n x n system AA Z Ab the normal equations is non singular if and only ifA has full rank ltgt The solution 52 is unique if and only ifA has full rank Peter Blomgren Language The Pseudo Inverse Hence if A has full rank the least squaressolution is is uniquely determined by as AA 1A E The matrix Al 2 AA 1A is known as the pseudo inverse of A With this notation and language the least squares problem comes down to computing one or both of We will look at 3 algorithms for accomplishing this 5351 Peter Blomgren Least Squares Problems The MoorePenrose Matrix Inverse Pseudo Inverse Given B 6 CW the Moore Penrose generalized matrix inverse is a unique pseudo inverse Bi satisfying i BBTB B ii BTBBT Bi iii BBT 88 iv BTB BTB The MoorePenrose inverse is often referred to in the literature so it is a good thing to know what it is Peter Blomgren Least Squares Problems Leasrsmrares Pro 7 r LSQ The Solution iurms for are LSQ Problem Take1 The Normal Equations Ian l flops The classical straight forward boneheaded way to solve the least squares problem is to solve the normal equations AAS Ab The preferred way of doing this is by computing the Cholesky factorization details to follow at a later date AA CE RR where R is an upper triangular matrix Hence the equivalent system RR lt AE Al RR 1A can be solved by a forward and a backward substitution sweep m Peter Blomgren Least Squares Problems est vi ir new he Solution idnns for die LSQ Problem Take2 The SVD 2mn2 lln3 flops If when we can compute the reduced SVD A Bi V we can use 7 to express the projector P and end up with the linear system of equations Di w 70 and we get is by is Vf lU S Here the pseudo inverse is AT Vi lUf 535 Peter Blomgren Least Squares Problems Leasrsmrares Pro 7 r LSQ The Solution iurms for are LSQ Problem Take3 The QR Factorization With the reduced QR factorization the game unfolds like this GivenAAA we can project I to the range of A using P 6262 then the system an ears has a unique solution given by is R 1Qb Al R 1Q Note that we do not need Q explicitly only the action QE which we can get cheaply from the Q less version of Householder triangularization Peter Blomgren Least Squares Problems Say we computed P using the Householder Q less QR factorization but forgot to compute Qb is everything lost No we can still compute is using the following sequence 2 R lR AE F 57A R lR AF i i The first step solves the semi normal equationsquot RR lt AE The remaining three steps takes one step of iterative refinement to reduce roundofF error Peter Blomgren Least Squares Problems 1 Least 51 wres PrulIIen Iquot 5h 4 L5 The Solution 35 Algorithms for the LSQ Problem Algorithms for Least Squares Comments Method Work flops Comment 3 39 39 Normal Equations N mng n7 Fastest sensitive to rdoundofT er rors Not recommen e Your everyday choice Can break 3 QReFaCtorization N Zmn2 7 2L I I when A Is close to rankedeflclent 3 The Big HammerTM more stable SVD N 2mn2 11n3 than the QR approach but requires more computational wor Additional Comment If rn gt n then the work for QR and SVD are both dominated by the first term Zmng and the computational cost of the SVD is not excessive However when rn z n the cost of the SVD is roughly 10 times that of the QRefaCtorization p Pralinequot Iquot 5h 4 The Solution 35 Algorithms for die LSQ Problem Looking Forward We can now compute and use one of the big important tools of numerical linear algebra the QR factorization Next we finally formalize the discussion on numerical stability and then we take another look at some of our algorithms in the light of stability considerations LsQ Problem HW4 Due Friday March 5 2010 HW4 Exploratory Implement modified Gram Schmidt QR factorization Work through experiment 1 and 2 in lecture 9 of Trefethen amp Bau Make sure your versions of classical and modified GS can reproduce figure 91 Do exercises 91ab and 92ab For additional non mandatory fun do exercises 91c and 92c Peter Blomgrel Least Squares Problems


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Bentley McCaw University of Florida

"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!"

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.