This entire homework will take the full rank least squares problem LS  = arg miny∈R亢 ,b − Xy,2(2)

and compare it to the perturbed solution

LS  = arg miny∈R亢 ,b + δb − (X + δX)y,2(2)

You are going to prove a bound on ,LS  − LS ,2  and ,LS  − LS ,2  where

LS     =   b − X LS

LS     =   b + δb − (X + δX)LS

1. Inverse of Augmented Matrix. We know that LS  and LS  satisfy   \ ╱   \ = ╱ 0n(b)  \

If X has full column rank, show that

(a) The matrix

M =  \

is nonsingular.

(b) The inverse is given by

M-l  = ╱ X(P)十     − (十)-l  \ ,

where X十 is the Moore–Penrose pseudoinverse and P = Im − XX十 .

2. Perturbation of ,X十 ,2 . Show the following. (a) If X has full column rank then

,X十 ,2  = σn (X)-l

where σn (X) is the smallest singular value of X .

(b) Using the result in the notes that

σn (X) =  min  ,Xw,2

|w|2 =l

show that if

ηX  = ,(δX)X十 ,2  < 1

then

σn (X + δX) ≥ (1 − ηX )σn (X) > 0.

Thus X + δX has full column rank and

,(X + δX)十 ,2  ≤ ,X十 ,2 /(1 − ηX ).

3. Perturbation Bound on the Solution. Assume that ηX  = ,(δX)X十 ,2  < 1. Let

fLS  =  \ ,    gLS  =  \

and let

M˜ =  \ .

(a) Noting the fLS  solves

MfLS  = ╱ 0(b) \

and

M˜ gLS  = ╱ b δb \

show that

LS  − LS     =   P [(δb) − (δX)LS ] − (X十 )T (δX)T LS

LS  − LS     =   X十 [(δb) − (δX)LS ] + (XT X)-l (δX)T LS where P = Im − XX十 .

(b) Using norm bound and some identities, show that

,LS  − LS ,2     ≤   ζ

,LS  − LS ,2     ≤   ,X十 ,2 ζ

where

ζ ≤ ,δb,2 + ,(δX ),2 ,LS ,2 + ηX ,LS ,2 .

4. Meaning for Q–R factorization.  Let D be a nonsingular diagonal matrix and let

X = XS D

(a)  Show that if X has the Q–R factorization

X = Q ╱ 0(R) \

then XS  has the Q–R factorization

XS  = Q ╱ 0(R)S  \ ,    RS  = RD-l

and

XS(十)  = DX十 .

(b)  Show that if X + δX = (XS + δXS )D then

ηX  = ,(δXS )XS(十) ,2 .

and thus

ηX  ≤ min{,(δX)D-l ,2 ,(XD-l )十 ,2 : D diagonal and nonsingular }.

(c) In floating point arithmetic, Householder Q–R decomposition yields a computed Qˆ and Rˆ such that

X + δX = Qˆ ╱ 0(Rˆ) \

where

,δXej ,2  = ξ,Xej ,2 ,    ξ = O(mnεM ).

Let D = diag(dl , . . . , dn ), dj  = ,Xej ,2 . Show that

ηX  ≤ √nξ,XS(十) ,2 .