 Linear Transformation Linear Transformation

 Projections and least squares approximations  What a matrix transformation cannot possibly do:

Transformation Matrix A (i) It is impossible to move the origin since A0=0

 Transformation: x Ax (RnRm if A is m by n) (ii) If A transforms x to x’, then cx can be only transformed to cx’ since

 Stretch: A=cI expands or contracts the vectors. A(cx)=c(Ax)

c 0  (iii) If A transforms x to x’ and y to y’, then their sum x+y

Ex. A   
0 c 
can only be transformed to x’+y’ since A(x+y)=Ax+Ay
 Rotation: turns the space around the origin.
 Any matrix transformation follows these three rules.
0  1
Ex. A   o
 turns all vectors through 90 .
1 0   Three rules can be combined into:

 Reflection: transforms every vector into its mirror image. For all numbers c and d and all vectors x and y, matrix multiplication

0 1  satisfies the rule of linearity:

Ex. A   o
 the mirror is the 45 line (x=y)
1 0 
A(cx+dy)=c(Ax)+d(Ay)
 Projection: project a space onto a lower-dimensional subspace.
Any transformation that meets this requirement is a linear transformation
(projection matrix must not be invertible)
 Every matrix is a linear transformation. Question: Does every linear
1 0
Ex. A    transforms vector (x, y) in the plane to the nearest point
 0 0 transformation lead to a matrix? That is, can we express any

(x, 0) on the horizontal axis. transformation in matrix form?

1 2
 Linear Transformation Example - Polynomials Basis and Linear Transformation

 Let x1, x2,…,xn be the basis, then any other vector in the space is a
combination of the vectors in the basis:
 Polynomial space Pn: p=a0+a1t+…+antn with space dimension = n+1
if x  c1 x1    cn xn then Ax  c1 ( Ax1 )    cn ( Axn )
 Example: is differentiation operation on a polynomial: A=d/dt
 Crucial property:
d
Ap  (a0  a1t    ant n )  a1    nant n 1 a linear transformation?
dt Once Axi’s are determined, Ax of any x is known

Nullspace: one-dimensional space of constant polynomial

 A vector x=(c1, c2,…, cn) is actually defined to be the linear combination
Column space: n-dimensional space Pn-1 of the basis x  c1 x1    cn xn and c1, c2,…, cn are coefficients of the linear
combination.
 Example: is integration from 0 to t
 Example: differentiation for the polynomials of degree 3. What is the
an n 1 basis? The natural choice of basis vector: p1=1, p2=t, p3=t2, p4=t3
Ap  0t (a0    ant n )dt  a0t    t a linear transformation?
n 1  Any polynomials of degree 3, p, can be then expressed as
nullspace: none (except for the zero vector as always) p=c1p1+c2p2+c3p3+c4p4
column space: Pn+1 without constant term  All we need to know is how the transformation performs on the basis:
 Example: Multiplication by a fixed polynomial, say 2+3t Ap1=0, Ap2=1= p1, Ap3=2t=2p2, Ap4=3t2=3p3
Ap  (2  3t )(a0    ant n )  2a0    3ant n1
 Then, the transformation of any p becomes:
It transforms Pn to Pn+1 and no nullspace except for p=0 dp/dt=Ap= c1Ap1+c2Ap2+c3Ap3+c4Ap4=0+ c2+2c3p2+3c4p3
 Are square of polynomials (Ap=p2), adding 1 (Ap=p+1) or keeping the
 Differentiate the polynomials of degree 3: p=2+tt2t3 becomes
positive terms (A(t-t2)=t) linear transformation? 0+ 1+2(-1)p2+3(-1)p3=1-2t-3t2

3 4
 Linear Transformation in Matrix Form Differentiation/Integration of Polynomials in Matrix Form
 Question: how to find matrix A?  Example: Differentiation for the polynomials of degree 3: Ap1=0=(0, 0, 0,

 Suppose the vectors x1, …, xn are a basis for the space V and y1, …, ym are a 0)T, Ap2=1= p1=(1, 0, 0, 0)T, Ap3=2t=2p2=(0, 2, 0, 0)T, Ap4=3t2=(0, 0, 3, 0)T

basis for W. Then each linear transformation from V to W is represented by 0 1 0 0

0 0 2 0
a matrix A:  A  found by the basis transformations.
0 0 0 3
0 0 0 0
Apply transformation to the jth basis vector of V, xj, and then express the 

transformation result as a combination of the W

 This matrix can be then used to differentiate any polynomials of degree
basis :Axj=A(0x1+0x2++1xj++0xn)=a1jy1+a2jy2+…+amjym i.e. 3: say, p=2+tt2t3
0 1 0 0  2   1 
0 1st  a1 j  0 0 2 0  1   2
  dp

  a2 j   Ap          1  2t  3t 3
A   . dt 0 0 0 3  1   3
1 j th    0 0 0 0  1  0 
   
   amj 
 Example: find the transformation matrix for integration on a polynomial
Then, a1 j , a2 j ,, amj form the jth column of A. (Why?)
of degree 3. Basis: x: 1, t, t2, t3 ; y: 1, t, t2, t3, t4
 Example: Differentiation for the polynomials of degree 3 with basis: p1=1,
t t 1 1
p2=t, p3=t , p4=t  any p=c1p1+c2p2+c3p3+c4p4
2 3  1dt  Ax
0 1  t  y2 ,  tdt  Ax2  t 2  y3 ,
0 2 2
t 1 3 1 t 1 4 1
0 t dt  Ax3  3 t  3 y4 , 0 t dt  Ax4  4 t  4 y5
2 3
 in vector form p=(c1, c2, c3, c4)T

 basis: p1=(1, 0, 0, 0)T, p2=(0, 1, 0, 0)T, p3=(0, 0, 1, 0)T, p4=(0, 0, 0, 1)T 0 0 0 0 

1 0 0 0 
Transformation performed on the basis:  
 Aint  0 1 / 2 0 0  AdiffAint = I
0 0 1 / 3 0 
Ap1=0=(0, 0, 0, 0)T, Ap2=1= p1=(1, 0, 0, 0)T, Ap3=2t=2p2=(0, 2, 0, 0)T,  
0 0 0 1 / 4
Ap4=3t2=(0, 0, 3, 0)T
BUT AintAdiff  I !!

5 6
 Rotation Matrix Q Projection Matrix P

 Rotation through an angle   Projection of (1, 0) onto the -line:

 c -s  c  cos
Q   
 s c  s  sin 

 Does the inverse of Q equal Q-?

c -s   c s  1 0  The transformation can not be reversed  The matrix has no inverse!!

Q Q     
 s c    s c   0 1  Points, like (-s, c), on the perpendicular line are projected onto the origin
 Does the product of Q and Q equal Q ?
(zero vector)  perpendicular line is the nullspace of P
cos  cos   sin  sin   cos(   )  sin(   )
Q Q     Points on the -line are projected to themselves  P2=P
sin  cos   cos  sin    sin(   ) cos(   )   the
2
 Q  c 2 cs  c 2 ( c 2  s 2 ) cs( c 2  s 2 )
P 
2
2
  2 
P
 cs( c  s ) s ( c  s )
2 2 2 2
 cs s 
product of the matrices corresponds to the product of the transformations

A: VW and B: U V  AB: UW

 To construct A and B, we need bases for V & W and U & V. If the basis

for V is kept the same, then the product matrix goes directly from the

basis in U to basis in W.

7 8
 Reflection Matrix H Basis for Constructing Transformation Matrix A

 Reflection of (1, 0) in the -line:

Let the basis be (c, s) and (-s, c): one is on the -line and the other is on -

line’s perpendicular line.

1 0
 Projection matrix: P   
 0 0
1 0 
 Reflection matrix: H   
0  1
 Check H=2PI
 Two reflections bring back the original: H2=I  H-1=H
c  s 
-1  Rotation matrix: Q   
Can you guess H simply from the matrix form? But it’s easy if you know s c 
the meaning of the what transformation the matrix represents.

 The sum of a vector and its mirror image equals twice the projection of
Choosing the best basis is very important!!
the vector  Hx+x=2Px  H=2PI
 Idea: make the transformation matrix diagonal, as P and H here using (c,
 H =(2PI) =4P 4P+I=I since P =P
2 2 2 2

s) and (-s, c) as basis.

 By changing basis, transformation matrix A  S-1AS

where S account for the change of basis.

 We come back later to this subject of choosing the best basis.

9 10
 Projection of b onto Vector a Schwarz Inequality
 The projection point p must be some multiple of a ( p  x̂a )

 The line from b to the closest point p  x̂a is perpendicular to the vector a  Schwarz Inequality: any two vectors satisfy

| a T b |  || a || || b ||
2
2 aT b (bT b)( a T a )  ( a T b) 2
Reason 1: || b  p ||  b  a  0
aT a aT a

 (bT b)( a T a )  ( a T b) 2  0  | a T b |  || a || || b ||

aT b
T Reason 2:  1  cos   1  | cos  | 1   1  | a T b |  || a || || b ||
a b || a || || b ||
(b  xˆa )  a , or aT (b-xˆa )  0 , or xˆ 
aT a
 Equality holds if and only if b is a multiple of a  =0o or 180o and
 The projection of b onto the line through O and a is
cosine=1 or –1  b=p
aT b
p  xˆa  T a
a a  Example: Project b=(1, 2, 3) onto the line through

aT b 6
a=(1, 1, 1): xˆ   2
aT a 3
|| p || 12
The projection point p=2a=(2, 2, 2)  cos  
|| b || 14

Schwarz inequality: 6 | aT b |  || a || ||b||  3 14

11 12
 Projections of Rank One New Definition of Transpose
aT b aaT
 p  xˆa  p  axˆ  a T  T b  Pb
a a a a
 Old definition: ( AT )ij  ( A) ji
T
aa
 Projection matrix P  T to project b onto a
a a  New definition: The inner product of Ax with y equals the inner product

Example: The matrix that projects any vector onto the line through a=(1, 1, of x with ATy: (Ax)T y = xT(ATy)

1) is  Inner product of x, transformed by A, with y equals the inner product of

1 1 / 3 1 / 3 1 / 3 x with y transformed by AT
aa T 1  
P  T  1 1 1 1  1 / 3 1 / 3 1 / 3
a a 3   
 Proof for (AB)T=BTAT:
1 1 / 3 1 / 3 1 / 3
Two properties for P: (ABx)Ty = [A(Bx)]Ty = (Bx)TATy = xT(BTATy)

1. A symmetric matrix  An important reminder: (A-1)T=(AT)-1

2. P2=P  transpose of the inverse = inverse of the transpose

 Rank=1; column space: spanned by a=(1, 1, 1); left-null space is formed

by vectors that satisfy aTb=0.

 P remains the same if a is multiplied by a scalar.

 Projection onto the “-direction” line, i.e. the line through a=(cos , sin

c 
 s c s  c 2 cs 
): P     
c   cs s2 
c s 
 s

13 14
 Least Squares Approximate of Solution Projection onto Column Space
 Ax=b is solvable  b is in the column space  This is a problem analogy to find an approximate solution for an

 When there are more equations than unknowns, b is hardly in the column unsolvable Ax=b system, especially when the no. (n) of unknowns is less

space  Find x such that Ax is as close as possible to b  least square than the no. (m) of equations

approximation  To find x̂ that minimizes E2  to find a point p on the column space of A

2 x  b1 that is closest to b
Example: 3 x  b2
4 x  b3

If (b1, b2, b3) is not on the same line as (2, 3, 4)  find x that minimizes the

sum of squared errors:

E 2  ( 2 x  b1 ) 2  (3 x  b2 ) 2  ( 4 x  b3 ) 2

2b1  3b2  4b3 a T b

Set dE /dx=0 to find xˆ 
2  T
2 2  32  4 2 a a
 Sum of squared errors for general cases:
 error e= b  Axˆ must be perpendicular to the column space
E 2  ( a1 x  b1 ) 2    (a m x  bm ) 2 || ax  b ||2
1. The vectors perpendicular to the column space must lie in the left
 Set the derivative to zero 
nullspace: AT (b  Axˆ )  0 or AT Axˆ  AT b
(a1 xˆ  b1 )a1    (am xˆ  bm )am  a (axˆ  b)  0
T

2. The error vector must be perpendicular to every column in A:

aT b
 The least squares solution to ax=b is xˆ  T
a a  a1T 
 
   b  Axˆ   0
 anT 
 

15 16
 Normal Equations, Least Squares Approximation and Projection Matrix P
Projection onto a Subspace  p  A( AT A) 1 AT b  Pb  P= A( AT A) 1 AT = Projection Matrix to

 The normal equations for an inconsistent system Ax=b of m equations and project b onto the column space of A

n unknowns: AT Axˆ  AT b which is always solvable.  b is split into Pb component (in the column space) and bPb component in

 The least squares approximation of x exists uniquely: the orthogonal complement (left nullspace)

xˆ  ( AT A) 1 AT b  IP is also a projection matrix that project b to the left null space:

if ATA is invertible, i.e., the columns of A are linearly independent (r=n). (IP)b=bPb

 The projection of b onto the column space is:  Two properties for P

p  Axˆ  A( AT A) 1 AT b 1. P2=P

 If b is actually in the column space of A (b=Ax), then: 2. PT=P (symmetric property)

p  A( AT A) 1 AT b  A( AT A) 1 AT Ax  AIx  Ax  b Proof:

 If b is perpendicular to the column space (ATb=0), then: P 2  A( AT A) 1[ AT A( AT A) 1 ] AT  A( AT A) 1 IAT  P

p  A( AT A) 1 AT b  0 PT  ( AT )T [( AT A) 1 ]T AT  ( A)[( AT A)T ]1 AT  P

 When A is square and invertible:

p  A( AT A) 1 AT b  AA1 ( AT ) 1 AT b  IIb  b

 (ATA)-1 can be only taken apart when A is square and invertible.

17 18
 More on Projection Matrix ATA and Left-Inverse of A
 It is known now if P is a projection matrix then P2=P and PT=P  (ATA)T=ATATT=ATA  ATA is symmetric

 Is any symmetric matrix with P2=P a projection matrix? YES!  ATA has the same nullspace as A since if Ax=0 then ATAx=0 and if ATAx=0

Proof: then xTATAx=||Ax||2=0=Ax.

To prove P is a projection matrix, we have to prove that the error vector  Normal equation AT Axˆ  AT b is always solvable but may have many

bPb is perpendicular to the component of any vector c projected onto that solutions when A has linearly dependent columns, i.e., A or ATA has non-

space (Pc): trivial nullspace solutions.

(b  Pb)T Pc  bT ( I  P )T Pc  bT ( I  P ) Pc  bT ( P  P 2 )c  0  If A has linearly independent columns(r=n) with zero dimension of null

A Projection matrix P  P2=P and PT=P space, then ATA is an nn square with zero dimension of null space, i.e.,

ATA is square and invertible  x̂ is unique as A has full column rank

Example:  Recall r=n (nm) a left-inverse exist  Bn  m Am  n  I n  n

If A is square and invertible, any vector b projects to itself  r=n (nm)  A has linearly independent columns

 P must be an identity matrix: Pb=Ib=b  ATA is square, symmetric, and invertible

How?  (ATA)-1 exists

P  A( AT A)  1 AT  AA 1 ( AT )  1 AT  I  (ATA)-1 ATA=I [ (ATA)-1 AT]A=I

Note: I is symmetric and I2=I  (ATA)-1 AT is the left-inverse of A

 If columns of A are not linearly independent (r<n), the normal equation

AT Axˆ  AT b is still solvable with many solutions (+xnull). A new matrix, say

A’, has to be formed by only independent columns of A to ensure existence

of (A’TA’)-1

19 20
 Projection onto Row Space and AAT AAT and Pseudo-inverse
 Row space of A=column space of AT  Recall pseudoinverse A+ is to invert Ax back to the row-space part of x:

 Projection onto row space of A A+Ax=xr

= Projection onto column space of AT  xr is the component of x in the row space

 Recall projection matrix to project onto A column space = xr is projection of x onto the row space

= A( AT A) 1 AT = AT ( AAT ) 1 Ax  A Ax

 Projection matrix to project onto row space of A  A  AT ( AAT ) 1

= Projection matrix to project onto AT column space  A+Ax=xr

= AT [( AT )T AT ]1 ( AT )T  AT ( AAT ) 1 A  A+A is a projection matrix to project onto row space

if AAT is invertible.  AA+= AAT ( AAT ) 1  I

 If A has linearly independent rows(r=m), then AAT is square, symmetric,  A+ is a right inverse of A when A has independent rows

and invertible  What if AAT is not invertible? Removing zero rows in U and deal with

 Recall r=m (mn) a right-inverse exist  Am nCn m  I m m UUT…

 r=m (mn)  A has linearly independent rows

 AAT is square, symmetric, and invertible

 (AAT)-1 exists

 AAT (AAT)-1 =I  A[AT (AAT)-1] =I

 AT (AAT)-1 is the right-inverse (pseudo-inverse) of A

21 22
 Least Squares Fitting of Data Two Explanations of Least Squares
C  Dt1  b1
C  Dt 2  b2

C  Dt m  bm
We obtain observations (t1, b1), …, (tm, bm) from experiments.

We would like to estimate C, and D:

1 t1   b1  Right: b=(1, 1, 3) is not on the plane spanned by (1, 1, 1) and (1, 1, 2); least
1 t  C  
 2     b2 
  Ax=b squares replace b by p which lies on the plane.
     D    
1 t  b 
 m  m Left: (1, 1), (1, 1) and (2, 3) are not one a line. Least squares replace them

by points on a line: (-1, p1) (1, p2) (2, p3)

 Unable to solve Ax=b, we solve Axˆ  p

5 13 17 2 6 4
 e  b  Axˆ  b  p  (1, 1, 3)  ( , , )  ( , , ) is orthogonal to the
7 7 7 7 7 7

both columns (1, 1, 1) and (-1, 1, 2)

Example: b=1 at t=-1, b=1 at t=1, b=3 at t=2 2 6 4

 If b  ( , , )  xˆ  0 , the best fitted line y=0 (x-axis)
7 7 7
1  1 1
1 1   C 
 1  For m pairs of observations:
   D   
1 2  3
 Cˆ  m  ti   Cˆ    bi 
3 2   C   5  AT A   AT b   2     
Dˆ   ti  ti   Dˆ   ti bi 
 AT Axˆ  AT b is    
 2 6   D  6 
 b  Ce  t  De  t : to estimate C and D is a linear problem. But to
9 4
 Cˆ  and Dˆ 
7 7 estimate  and  is a nonlinear problem.

23 24
 Multiple Regression Weighted Least Square

Values  Sometimes observations are not trusted to the same degree because they
Observatio Y X1 X2 … Xp
n are obtained from different accurate scales. Then, different weights can
1 y1 x11 x12 x1p
2 y2 x21 x22 x2p be applied to different observations when calculating the sum of squared
    … 
n yn xn1 xn2 xnp
errors:
Values
Weight Observation Y X1 X2 … Xp
 Model: Y   0   1 X 1   2 X 2     p X p  e W1 1 y1 x11 x12 x1p
W2 2 y2 x21 x22 x2p
 Goal: given n sets of observation, estimate  0,  1, …, p      … 
Wn N yn xn1 xn2 xnp
 This is a problem of Ax=b, where  Weighted sum of squared errors:

1 x11 x 21  x1 p   0   y1  E 2  w12 (  0   1 x11    p x1 p  y1 ) 2    wn2 (  0   1 xn1    p xnp  y n ) 2

1 x x 22 x2 p      
A
21  , x   1  , b   y2  0 
1          w1 0
 0
 x    y  w2   
1 n1 xn 2 xnp   p   n Let W=    E 2  WAx  Wb 2
   0
 ˆ  xˆ  ( AT A) 1 AT b 0  0 wn 

 The notation may confuse you but the problem is exactly the same. And That is, we would like to find a least square solution ( x̂ ) that makes WAˆx as

this is again how mathematics can help you to solve problems that no closed as possible to Wb .

longer can be pictured.  Least square solution to WAx=Wb :

( AT W T WA) xˆW  AT W T Wb

 In practice, choice of W is the most important question!

More accurate more weight  wi  1 /  yi (accuracy ~ 1/)

25 26