5.

Inner Product Spaces, Orthogonality

5.1 Inner Product Spaces - Introduction

Applications of Inner Product Spaces QR factorization - Singular Value Decomposition - relations
of fundamental subspaces - Least square solutions.

5.2 Singular Value Decomposition (SVD)

Let A be an m × n real matrix. Then the Singular Value Decomposition (SVD) of A is given by:

A = UΣV T

where:
• U is an m × m orthogonal matrix (columns are left singular vectors),
• Σ is an m × n diagonal matrix with non-negative real numbers on the diagonal (singular
values),
• V is an n × n orthogonal matrix (columns are right singular vectors).
■ Example 5.1 Let A be the matrix given by
 
3 1
A=
1 3

Find the singular value of A. ■

Solution. Let us consider the matrix

 
3 1
A=
1 3

Step 1: Compute AT A and AAT

 T    
T 3 1 3 1 10 6
A A= =
1 3 1 3 6 10
182 Chapter 5. Inner Product Spaces, Orthogonality

Step 2: Find eigenvalues and eigenvectors of AT A

Solve det(AT A − λ I) = 0:

10 − λ 6
= (10 − λ )2 − 36 = λ 2 − 20λ + 64 = 0
6 10 − λ

√ λ1 = 16, λ2 =
Solving, we get eigenvalues √4.
Singular values are σ1 = 16 = 4, σ2 = 4 = 2.
Step 3: Compute V from eigenvectors of AT A
Corresponding normalized eigenvectors:
" 1 #
√ − √12
   
1 1 1 −1
v1 = √ , v2 = √ ⇒ V = √12 √1
2 1 2 1 2 2

Step 4: Compute U

U = AV Σ−1
 
4 0
Σ= , U = AV Σ−1 = A ·V · Σ−1
0 2
 " √1 √1
#   " √1 √1
#
− 1

3 1 0
Compute U : U= · √12 √1
2 · 4
1 = √1
2 2
1 3 2 2
0 2 2
− √12

Final Decomposition A = UΣV T

" # " #
√1 √1 √1 √1
 
2 2 4 0 T 2 2
where U= √1
, Σ= , V =
2
− √12 0 2 − √12 √1
2

Problem 5.1 Let A be the matrix given by

 
1 1
A = 0 1
1 0

Find the singular value if A.

Solution. Step 1: Compute AT A

 
  1 1  
T 1 0 1  2 1
A A= 0 1 =
1 1 0 1 2
1 0

Step 2: Find the Eigenvalues of AT A

Compute the characteristic polynomial:

2−λ 1
det(AT A − λ I) = = (2 − λ )2 − 1 = λ 2 − 4λ + 3
1 2−λ

Solve:

λ 2 − 4λ + 3 = 0 ⇒ λ = 1, 3
5.2 Singular Value Decomposition (SVD) 183

Step 3: Compute Singular Values

Singular values are the square roots of eigenvalues of AT A:
√ √
σ1 = 3, σ2 = 1 = 1

Step 4: Compute V from AT A

We find orthonormal eigenvectors of AT A:
For λ = 3:
    
T −1 1 v1 1 1
(A A − 3I)v = 0 ⇒ = 0 ⇒ v1 = v2 ⇒ v1 = √
1 −1 v2 2 1

For λ = 1:
    
T 1 1 v1 1 1
(A A − I)v = 0 ⇒ = 0 ⇒ v1 = −v2 ⇒ v2 = √
1 1 v2 2 −1
Hence,
" # " #
√1 √1 √1 √1
V= √1
2 2 , VT = 2 2
2
− √12 √1
2
− √12

1
Step 5: Compute U via U = σi Avi
Compute u1 :
 
  2
1 1 1 1  
u1 = √ A · √ =√ 1
3 2 1 6 1

Compute u2 :
 
 0 
1 1 1 1
u2 = A · √ = √ −1
1 2 −1 2 1

Now orthonormalize (they already are):

   
2 0
1   1  
u1 = √ 1 , u2 = √ −1
6 1 2 1

Complete U to an orthonormal basis (choose any orthonormal vector orthogonal to both u1 and u2 ,
e.g. by Gram-Schmidt). One such vector is:
 
1
1
u3 = √ −1
3 −1

Then:
√2 √1
 
6
0 3
 √1 − √12 − √13 
U=  6 
√1 √1 − √13
6 2
184 Chapter 5. Inner Product Spaces, Orthogonality

Step 6: Construct Σ
As A is 3 × 2, Σ is:
√ 
3 0
Σ =  0 1
0 0

Final SVD

A = UΣV T
 2
√ 0 √1
 √ 
6 3 3 0 "
√1 √1
#
 √1 − √12 − √13 
U= , Σ =  0 1 , VT = √1
2 2
− √12
 6
√1 √1 − 3
√ 1 0 0 2
6 2

Application of Singular value decomposition

eigenvectors can be written as
A = PDP−1
where D is a diagonal matrix of eigenvalues of A. As a special case, if A is then A has the
factorization
A = QDQt
where Q is an orthogonal matrix.
In this section we consider a generalization of this last result for m× i Specifically, we introduce
the singular value decomposition, abbreviate which enables us to write any m × n matrix as

A = UΣV t

where U is an m × m orthogonal matrix, V is an n × n orthogonal matrix an m × n matrix with

numbers, called singular values, on its diagonal.
Definition 5.2.1 Singular Values Let A be an m × n matrix. The singular values of A, denoted
by σi for 1 ≤ i ≤ n, are the positive square roots of the eigenvalues λ1 , . . . , λn of At A. That is,
p
σi = λi for 1 ≤ i ≤ n

■ Example 5.2 Let A be the matrix given by

 
1 1
A= 0 1 
1 0

. Find the singular values of A. ■

Solution. ■

The singular values of A are found by first computing the eigenvalues of the square matrix
 
  1 1  
t 1 0 1  2 1
AA= 0 1 =
1 1 0 1 2
1 0
5.2 Singular Value Decomposition (SVD) 185

The characteristic equation, in this case, is given by

det At A − λ I = (λ − 3)(λ − 1) = 0

√
The eigenvalues of At A are then λ1 = 3 and λ2 = 1, so that the singular values are σ1 = 3 and
σ2 = 1.
Problem 5.2 Find a singular value decomposition of the matrix
 
−1 1
A =  −1 1 
2 −2

Solution. A procedure for finding an SVD of A is included in the proof of Theorem 18. We present
the solution as a sequence of steps.
Step 1. Find the eigenvalues and corresponding orthonormal eigenvectors of Ai A and define the
matrix V .
The eigenvalues of the matrix  
t 6 −6
AA=
−6 6
in decreasing order are given by λ1 = 12 and λ2 = 0. The corresponding orthonormal eigenvectors
are  √   √ 
−1/√2 1/√2
v1 = and v2 =
1/ 2 1/ 2
Since the column vectors of V are given by the orthonormal eigenvectors of At A, the matrix V is
given by √ √ 

−1/√2 1/√2
V=
1/ 2 1/ 2
Step 2. Find the singular values of A and define the matrix Σ.
The singular values of A are the square roots of the eigenvalues of At A, so that
p √ p
σ1 = λ1 = 2 3 and σ2 = λ2 = 0

Since Σ has the same dimensions as A, then Σ is 3 × 2. In this case,

 √ 
2 3 0
Σ= 0 0 
0 0

Step 3. Define the matrix U.

The matrix A has one nonzero singular value, so by Theorem 17 the rank of A is 1 . Therefore,
the first column of U is  √ 
1/√6
1
u1 = Av1 =  1/√6 
σ1
−2/ 6
Next we extend the set {u1 } to an orthonormal basis for R3 by adding to it the vectors
 √   √ 
2/ 5 −1/√2
u2 =  √0  and u3 =  1/ 2 
1/ 5 0
186 Chapter 5. Inner Product Spaces, Orthogonality

so that  √ √ √ 
1/√6 2/ 5 −1/√2
U =  1/√6 0√ 1/ 2 
−2/ 6 1/ 5 0
The singular value decomposition of A is then given by
√ √ √  √
√ √ 
 
1/√6 2/ 5 −1/√ 2 2 3 0 
t −1/√2 1/ √2
A = UΣV =  1/ √6 0√ 1/ 2   0 0 
1/ 2 1/ 2
−2/ 6 1/ 5 0 0 0
 
−1 1
= −1
 1 
2 −2
■
■ Example 5.3 Find a singular value decomposition of the matrix
 
1 1
A=
3 −3
■

Solution. ■
First observe that
    
t 1 3 1 1 10 −8
AA= =
1 −3 3 −3 −8 10
 
1
By inspection we see that v1 = √12 is a unit eigenvector of At A with corresponding eigen-
−1
 
1
value λ1 = 18, and v2 = √12 is a unit eigenvector of At A with corresponding eigenvalue
1
λ2 = 2. Hence,  
1 1 1
V=√
2 −1 1
√ √
The singular values of A are σ1 = 3 2 and σ2 = 2 so that
 √ 
3 2 √0
Σ=
0 2
To find U, we compute
    
t 1 1 1 3 2 0
AA = =
3 −3 1 −3 0 18
 
0
Observe that a unit eigenvector corresponding to λ1 = 18 is u1 = and a unit eigenvector
1
 
1
corresponding to λ2 = 2 is u2 = . Thus,
0
 
0 1
U=
1 0
A singular value decomposition of A is then given by
  √ " √1 −1
√
#  
t 0 1 3 2 √0 2 2 1 1
A = UΣV = √1 √1
=
1 0 0 2 2 2
3 −3
 5.3 11.5 Application: Least squares approximations and curve fitting 187

5.3 11.5 Application: Least squares approximations and curve fitting

5.3.1 Find least squares approximations for a system of equations
In this section, we will consider the problem of finding approximate solutions to a system of linear
equations Av = b. This can be useful when the system is inconsistent, but we would still like to
find a "best" answer. For example, consider the following system of equations.

0.1x + 0.2y = 0.3

0.2x + 0.5y = 0.7
0.7x + 0.2y = 0.9

This system has the solution (x, y) = (1, 1), so it is clearly consistent. Now imagine that we
introduce some small inaccuracies into the equations. The inaccuracies might perhaps be due to
round-off errors, or due to measurement errors if the coefficients are obtained from experimental
data. We might end up with the following system of equations:

0.1000001x + 0.2y = 0.3

0.2x + 0.5y = 0.7
0.7x + 0.2y = 0.9

Except for a tiny error in one of the coefficients, this is the same system of equations as before. We
would expect that such a small error does not affect the result much. However, this last system of
equations is inconsistent; it has no solutions at all. You can see this by observing that (x, y) = (1, 1)
is still the unique solution to the last two equations; substituting this into the first equation, we get
0.3000001 = 0.3, which almost, but not exactly, true. What we would like to find in a situation
like this is an "approximate solution", i.e., numbers x and y such that each of the three equations
"almost" holds. We can formulate the problem more precisely as follows:
Problem 5.3 — Least squares approximation problem. ?? Given a (possibly inconsistent)
system of equations Av = b, find v such that

∥Av − b∥

is as small as possible. We call such a vector v a least squares approximation for the system of
equations.
To see why this is called a "least squares" approximation, consider a system of equations

a11 x1 + · · · + a1n xn = b1 ,
a21 x1 + · · · + a2n xn = b2 ,
···
am1 x1 + · · · + amn xn = bm .

We can write this in matrix form Av = b, where

     
a11 · · · a1n b1 x1
A =  ... .. ..  , b =  ..  , and v =  ...  .
  
. .   . 
am1 · · · amn bm xn

Then  
a11 x1 + · · · + a1n xn − b1
Av − b =  ··· ,
am1 x1 + · · · + amn xn − bm
188 Chapter 5. Inner Product Spaces, Orthogonality

and therefore

∥Av − b∥2 = (a11 x1 + · · · + a1n xn − b1 )2 + . . . + (am1 x1 + · · · + amn xn − bm )2 .

Therefore, minimizing ∥Av − b∥ is the same as minimizing the sum of the squares of the errors
of all the equations, where the error of each equation is defined to be the difference between its
left-hand side and right-hand side.
We note that ∥Av − b∥ = 0 if and only if Av = b. Therefore, if the system of equations Av = b is
consistent, then its least squares approximations are exactly the solutions of the system of equations
in the usual sense.
The least squares approximation problem has a very elegant solution, provided by the following
proposition.
Proposition 5.3.1 — Solution of the least squares approximation problem. A vector v is a
least squares approximation of the system of equations Av = b if and only if

AT Av = AT b

Proof. Let a1 , . . . an be the columns of the matrix A. Recall that span {a1 , . . . an } is called the
column space of A, which we write as col(A). If
 
x1
v =  ... 
 

xn

is any vector, then by the definition of matrix multiplication, we have

Av = x1 a1 + . . . + xn an .

Therefore, a vector is of the form Av if and only if it is an element of col(A). In particular, the
equation Av = b has a solution if and only if b is an element of the column space of A. For v to be
a least squares approximation, we want ∥Av − b∥ to be as small as possible. This means that we are
looking for the element of col(A) that is closest to b.

Figure 5.1

We know that this happens when Av − b is orthogonal to col(A). Since col(A) = span
{a1 , . . . an }, this is equivalent to saying that Av − b is orthogonal to each of the vectors a1 , . . . an .
Therefore,
aTi (Av − b) = 0
for i = 1, . . . , n. Since aT1 , . . . aTn are the rows of the matrix AT , this system of n equations is
equivalent to the single equation
AT (Av − b) = 0
5.3 11.5 Application: Least squares approximations and curve fitting 189

or equivalently,
AT Av = AT b

■ Example 5.4 — Least squares approximation. Find the least squares approximation for the
system of equations
2x + 2y + 2z = 1
x − y − z = −2
−x − y + 2z = 4
2x + 2y − z = −8
■

Solution. We first write the system in matrix form Av = b, where

   
2 2 2 1
 1 −1 −1   −2 
A=
 −1 −1
 and b= 
2   4 
2 2 −1 −8

By Proposition 11.49, the least squares approximation is given by the solution of the system of
equations AT Av = AT b. We calculate:
 
  2 2 2  
2 1 −1 2  10 8 −1
1 −1 −1
AT A =  2 −1 −1

2   =  8 10 1 
 −1 −1 2 
2 −1 2 −1 −1 1 10
2 2 −1
 
  1  
2 1 −1 2  −20
T −2  

A b= 2
 −1 −1 2  4  = −16 .

2 −1 2 −1 20
−8

Therefore, we must solve the system of equations

    
10 8 −1 x −20
 8 10 1   y  =  −16 
−1 1 10 z 20

After some row operations, we find that the unique solution is (x, y, z) = (−1, −1, 2). We can
double-check this answer as follows. We calculate
         
2 2 2   1 0 1 −1
 1 −1 −1  −1
  −1  −  −2  =  −2  −  −2  =  0 
       
Av − b = 
 −1 −1 2   4   6   4   2 
2
2 2 −1 −8 −6 −8 2

and check that this vector is orthogonal to every column of A. Since this is the case, our answer is
correct. ■
 190 Chapter 5. Inner Product Spaces, Orthogonality

5.3.2 Find best fit lines and parabolas for a set of data points
An important application of least squares approximations is curve fitting: finding the "best" function
of a given type (for example, linear, quadratic) to fit a given series of data points. The next two
examples show how to use least square approximations to solve curve fitting problems.
■ Example 5.5 — Least squares line. A company has collected daily data on temperature and ice
cream sales over a period of one week. The data is as follows:

Date Peak temperature Sales

July 1 17◦ C $320
July 2 22◦ C $570
July 3 26◦ C $850
July 4 20◦ C $470
July 5 24◦ C $750
July 6 23◦ C $620
July 7 23◦ C $680

The company is interested in predicting how temperature will affect future sales. Find a function
of the form y = a + bx that best fits the data, where x is temperature in degrees Celsius and y is
sales in dollars. By "best fit", we mean that the sum of the square of the errors should be as small
as possible (where each error is the difference between the dollar amount predicted by the formula
y = a + bx and the actual dollar amount). Such a function is called a least squares line or a linear
regression for the data. ■

Solution. We first write down a system of equations that expresses the relationship y = a + bx for
each of the seven data points (x, y) :
a + 17b = 320,
a + 22b = 570,
a + 26b = 850,
a + 20b = 470,
a + 24b = 750,
a + 23b = 620,
a + 23b = 680.
This is a system of seven equations in two variables (the variables are a and b ). This system is
likely inconsistent, because there are more equations than variables, and also because it is unlikely
that the relationship between temperature and sales is exactly (as opposed to approximately) linear.
Instead, we find the least squares approximation for the system of equations. We let
   
1 17 320
 1 22   570 
   
 1 26   850 
   
A=  1 20  and b =  470 
  
 1 24   750 
   
 1 23   620 
1 23 680

By Proposition 11.49, we must solve the equation AT Av = AT b. We calculate

   
T 7 155 T 4260
A A= and A b =
155 3483 97380
5.3 11.5 Application: Least squares approximations and curve fitting 191

So the system of equations we must solve is

    
7 155 a 4260
= .
155 3483 b 97380

After some row operations, we find the unique solutions (a, b) = (−720, 60). This means that the
desired linear approximation is y = −720 + 60x. The following plot shows this function along with
the original data points.

Figure 5.2

The following table compares the observed data to the computed linear regression (sorted by
increasing temperature). It also shows the error for each data point.

Temperature Actual sales Best linear fit Error

17 320 300 -20
20 470 480 +10
22 570 600 +30
23 620 660 +40
23 680 660 -20
24 750 720 -30
26 850 840 -10

The sum of the squares of the errors is 202 + 102 + 302 + 402 + 202 + 302 + 102 = 4400. ■

■ Example 5.6 — Least squares parabola. Find a quadratic polynomial that is the best fit for
the following data points:
(x1 , y1 ) = (3, 23.5),
(x2 , y2 ) = (4, 13.5),
(x3 , y3 ) = (5, 12.5),
(x4 , y4 ) = (6, 5.5),
(x5 , y5 ) = (7, 9.0),
(x6 , y6 ) = (8, 8.0),
(x7 , y7 ) = (9, 19.0).
■

Solution. We are looking for an equation of the form y = a + bx + cx2 . Substituting each of the
192 Chapter 5. Inner Product Spaces, Orthogonality

seven data points into the equation, we obtain 7 equations in the unknowns a, b, and c :

a + 3b + 9c = 23.5,
a + 4b + 16c = 13.5,
a + 5b + 25c = 12.5,
a + 6b + 36c = 5.5,
a + 7b + 49c = 9.0,
a + 8b + 64c = 8.0,
a + 9b + 81c = 19.0.

We write this in matrix form at Av = b, where

   
1 3 9 23.5

 1 4 16 


 13.5 


 1 5 25 


 12.5 

A=
 1 6 36 
 and b=
 5.5 


 1 7 49 


 9.0 

 1 8 64   8.0 
1 9 81 19.0

To find the least squares approximation, we calculate

   
7 42 280 91
AT A =  42 280 2016  and AT b =  518 
280 2016 15316 3430

and solve the system of equations AT Av = AT b, i.e.,

    
7 42 280 a 91
 42 280 2016   b  =  518 
280 2016 15316 c 3430

After doing some row operations, we find that the unique solution is (a, b, c) = (67, −19, 1.5).
Therefore, the desired quadratic approximation is y = 67 − 19x + 1.5x2 . The following plot shows
this function along with the original data points.

Figure 5.3

The following table shows the original data, the values of the best fit parabola, and the error for
each data point.
 5.3 11.5 Application: Least squares approximations and curve fitting 193

x Actual y Best fit parabola Error

3 23.5 23.5 0.0
4 13.5 15.0 +1.5
5 12.5 9.5 -3.0
6 5.5 7.0 +1.5
7 9.0 7.5 -1.5
8 8.0 11.0 +3.0
9 19.0 17.5 -1.5

The sum of the squares of the errors is 02 + 1.52 + 32 + 1.52 + 1.52 + 32 + 1.52 = 27. ■

5.3.3 Exercises
Problem 5.4 Find the least squares approximation for the system of equations

x + 2y + 2z =5,
x + y − z =11,
x + 2y − z = − 18,
2x − y + 2z =0.

Problem 5.5 Find the least squares approximation for the system of equations
   
−1 2 1   1

 −1 0 −1 
 x  1



 y = 3
 2 0 2     .
 
 0 0 2  z  −2 
1 2 2 4

Problem 5.6 Consider the points (x1 , y1 ) = (−1, 0), (x2 , y2 ) = (0, 3), (x3 , y3 ) = (1, 3), (x4 , y4 ) =
(2, 5), (x5 , y5 ) = (3, 9). Find the least squares line for these points.
Problem 5.7 Consider the points (x1 , y1 ) = (−1, 4), (x2 , y2 ) = (0, −2), (x3 , y3 ) = (1, 4), (x4 , y4 ) =
(2, 2). Find the least squares parabola for these points.