Vector Spaces and Singular Value Decomposition

Lecture 11 Vector Spaces and Singular Value Decomposition

Syllabus Lecture 01 Lecture 02 Lecture 03 Lecture 04 Lecture 05 Lecture 06 Lecture 07 Lecture 08 Lecture 09 Lecture 10 Lecture 11 Lecture 12 Lecture 13 Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Describing Inverse Problems Probability and Measurement Error, Part 1 Probability and Measurement Error, Part 2 The L2 Norm and Simple Least Squares A Priori Information and Weighted Least Squared Resolution and Generalized Inverses Backus-Gilbert Inverse and the Trade Off of Resolution and Variance The Principle of Maximum Likelihood Inexact Theories Nonuniqueness and Localized Averages Vector Spaces and Singular Value Decomposition Equality and Inequality Constraints L1 , L Norm Problems and Linear Programming Nonlinear Problems: Grid and Monte Carlo Searches Nonlinear Problems: Newton s Method Nonlinear Problems: Simulated Annealing and Bootstrap Confidence Intervals Factor Analysis Varimax Factors, Empirical Orthogonal Functions Backus-Gilbert Theory for Continuous Problems; Radon s Problem Linear Operators and Their Adjoints Fr chet Derivatives Exemplary Inverse Problems, incl. Filter Design Exemplary Inverse Problems, incl. Earthquake Location Exemplary Inverse Problems, incl. Vibrational Problems

Purpose of the Lecture View m m and d d as points in the space of model parameters and data Develop the idea of transformations of coordinate axes Show how transformations can be used to convert a weighted problem into an unweighted one Introduce the Natural Solution and the Singular Value Decomposition

Part 1 the spaces of model parameters and data

what is a vector? algebraic viewpoint a vector is a quantity that is manipulated (especially, multiplied) via a specific set of rules geometric viewpoint a vector is a direction and length in space

what is a vector? algebraic viewpoint column- a vector is a quantity that is manipulated (especially, multiplied) via a specific set of rules geometric viewpoint a vector is a direction and length in space in our case, a space of very high dimension

S(d d) S(m m) d d m m m3 d3

forward problem d d = Gm Gm maps an m onto a d maps a point in S(m m) to a point in S(d d)

Forward Problem: Maps S(m m) onto S(d d) d d m m m3 d3

inverse problem m m = G G-gd d maps a d onto an m maps a point in S(m m) to a point in S(d d)

Inverse Problem: Maps S(d d) onto S(m m) d d m m m3 d3

Part 2 Transformations of coordinate axes

coordinate axes are arbitrary given M linearly-independent basis vectors m m(i) we can write any vector m m* as ...

span space don t span space d d m3 m3

... as a linear combination of these basis vectors

... as a linear combination of these basis vectors components of m m* in new coordinate system m mi* = i

might it be fair to say that the components of a vector are a column-vector ?

matrix formed from basis vectors Mij = vj(i)

transformation matrix T T

transformation matrix T T same vector different components

Q: does T T preserve length ? (in the sense that m mTm m = m Tm ) A: only when T TT= T-1

transformation of the model space axes GTm-1] [T Tmm m] = G G m m d d = Gm Gm = GIm GIm = [GT d d = Gm d d = G G m m Gm same equation different coordinate system for m

transformation of the data space axes d d = T Tdd d = [T TdG] m G] m = G m G m d d = Gm d d = G G m m Gm same equation different coordinate system for d

transformation of both data space and model space axes d d = T Tdd d = [T TdG GT Tm-1] [ ] [T Tmm] m] = G m G m same equation different coordinate systems for d and m d d = Gm d d = G G m m Gm

Part 3 how transformations can be used to convert a weighted problem into an unweighted one

when are transformations useful ? remember this?

when are transformations useful ? remember this? massage this into a pair of transformations

m mTW Wmm m W Wm=D DTD D or W Wm W Wm =W Wm TW Wm Wm=W OK since W symmetric Wm m mTW = m mTD DTDm = [Dm Dm] T[Dm Wmm m = Dm = Dm] Tm

when are transformations useful ? remember this? massage this into a pair of transformations

e eTW Wee e We W We =W We TW We W We=W We OK since W symmetric e eTW = eTW We TW We e = We m m] T[W We m m] Td Wee e = e e = [W

we have converted weighted least-squares into unweighted least-squares minimize: E + L = e e Te e +m m Tm m

steps 1: Compute Transformations T Tm=D D=W Wm and T Te=W We 2: Transform data kernel and data to new coordinate system G G =[T [TeGT GTm-1] ] and d d =T Ted d 3: solve G G m m = d d for m m using unweighted method 4: Transform m m back to original coordinate system m m=T Tm-1m m

steps extra work 1: Compute Transformations T Tm=D D=W Wm and T Te=W We 2: Transform data kernel and data to new coordinate system G G =[T [TeGT GTm-1] ] and d d =T Ted d 3: solve G G m m = d d for m m using unweighted method 4: Transform m m back to original coordinate system m m=T Tm-1m m

steps to allow simpler solution method 1: Compute Transformations T Tm=D D=W Wm and T Te=W We 2: Transform data kernel and data to new coordinate system G G =[T [TeGT GTm-1] ] and d d =T Ted d 3: solve G G m m = d d for m m using unweighted method 4: Transform m m back to original coordinate system m m=T Tm-1m m

Part 4 The Natural Solution and the Singular Value Decomposition (SVD)

Gm Gm = d d suppose that we could divide up the problem like this ...

Gm Gm = d d only m mp pcan affect d d since Gm Gm0 0=0

Gm Gm = d d Gm Gmp pcan only affect d dp since no m m can lead to a d d0 0

determined by a priori information determined by data determined by m mp not possible to reduce

natural solution determine m mp by solving d dp-Gm Gmp=0 set m m0=0

what we need is a way to do Gm Gm = d d

Singular Value Decomposition (SVD)

singular value decomposition U UTU U=I I and V VTV V=I I

suppose only ps are non-zero

suppose only ps are non-zero only first p columns of U U only first p columns of V V

UpTUp=I and VpTVp=I since vectors mutually pependicular and of unit length UpUpT I and VpVpT I since vectors do not span entire space

The part of m m that lies in V V0 cannot effect d d since V VpTV V0=0 so V V0 is the model null space

The part of d d that lies in U U0 cannot be affected by m m since pV VpTm m is multiplied by U Up and U U0U UpT =0 so U U0 is the data null space

The Natural Solution