CS323 LECTURE NOTES - LECTURE 15

1 Least squares

The approximations that we have talked about before nd a poly- nomial that goes exactly through the given points. A least squares approximation can be used to nd a polynomial with degree much smaller than the given number of points, such that it passes as close as possible to the points but is not required to go through them.

First we have to dene what we mean by ”passes as close as possible”, to do this we need a measure of error, as well as a formal

denition of the problem that we want to solve.

Problem.

Given a set of m points (x1,y1), (x2,y2), . . . , (xm,ym) and a n- degree polynomial

n

P(x) = a0 + a1x + a2x2 + . . . + anxn = Xajxj

i=0

We can compute the approximation error for a point (xi,yi) as the vertical distance from the point to the polynomial when x = xi:

errori = |P(xi) − yi|

so the total error when all the points have been taken in to ac-

count is:

E1(a0,a1, . . .,an) = X |P(xi) − yi|

i=1

This error is a function of the coecients a0,a1, . . .,am since all other values are constant.

Our problem consists in nding the coecients a0,a1, . . . ,am that minimize the total error. For this purpose, we would like to compute the derivatives ofE1 an make them equal to 0, but the absolute value function is not dierentiable in 0, so we prefer to use the function x2 instead of |x|, so the error is:

m

E(a0,a1, . . . ,an) = X(P(xi) − yi)2

i=1

or

m   n

E(a0,a1, . . . ,an) = X(Xajxj − yi)2

i=1 i=0

Using this formula we can nd its minimum using all of its partial derivatives with respect to ak and making each one equal to 0.

∂E = X2(Xajxi(j) − yj)(xi(k)) = 0

 = 

and xi, yi are constants. The factor of 2 can be placed outside of the summation where it will be cancelled out by the 0, and the term xi(k) can enter the summation since it is constant:

m   n

X(Xajx xi(k)yi) = 0

i=1 j=0

therefore,

m  n            m

XXajx Xxi(k)yi = 0

i=1 j=0           i=1

We can now swap the summations:

n     m          m

Xaj Xxi(k)+j = Xxi(k)yi  ∀k = 0, . . . ,n

j=0   i=1         i=1

recall that we have one equation for each value of k:

k = 0:

m           m                 m           m

ma0 + (Xxi)a1 + (Xx )a 2 + . . . + (Xxi(n))an = Xyi

k = 1: m

i=1          i=1                i=1          i=1

m            m                 m              m

(Xxi)a0 + (Xx )a 1 + (Xx )a 2 + . . . + (Xxi(n)+1)an = Xxiyi

i=1          i=1          i=1                i=1            i=1

..

..

..

k = n:

m           m             m                  m            m

(Xxi(n))a0+(Xxi(n)+1)a1+(Xxi(n)+2)a2+. . .+(Xxn)an = Xxi(n)yi

i=1          i=1            i=1                 i=1           i=1

These equations represent a linear system with n + 1 equations and n + 1 unknowns which can be written in matrix form:

 P xi

    .

 P1 xi(n)

Example:

P xi P x

.

.

.

P xi(n)+1

P x P x

.

.

.

P xi(n)+2

 1 

.     

· · · P..1 xn 

a0 a1

.

.

.

an

P yi  

.    

In the case nding a linear approximation n = 1, to a collection of points, the system of equations is:

  a(a)  =  

This system has 2 equations and 2 unknowns and can easily be solved by Cramer’s Rule.

a0  =

a1  =

Pyi Pxi2 − Pxi Pxiyi mPx − (Pxi)2

mPxiyi − Pxi Pyi mPx − (Pxi)2

Analysis

1. The algorithm computes xi, x, . . .,xn, that can be placed in a 2n ×m matrix, and requires time O(nm) time to be computed.

2. To compute all summations we need time in O(nm)

3. The solution of the linear system by Gaussian Elimination re- quires O(n3) time.

Therefore, the time complexity of the least squares polynomial approximation algorithm is O(nm + n3), and since n ≪ m, the algorithm is in O(nm)