L.Vandenberghe ECE133A(Spring2021) 8. Least squares

L. Vandenberghe

8. Least squares

ECE133A (Fall 2021)

? least squares problem ? solution of a least squares problem ? solving least squares problems

8.1

Least squares problem

given R? and R, find vector R that minimizes

2

- 2 = -

=1 =1

? "least squares" because we minimize a sum of squares of affine functions:

- 2 = ()2,

=1

() = -

=1

? the problem is also called the linear least squares problem

Least squares

8.2

Example

1

2 0

1

=

-1

1

,

=

0

x2

0

0

2

-1

f (x^) + 2 f (x^) + 1

x^

-1-1

0

1

x1

? the least squares solution ^ minimizes

() = - 2 = (21 - 1)2 + (-1 + 2)2 + (22 + 1)2

? to find ^, set derivatives with respect to 1 and 2 equal to zero:

101 - 22 - 4 = 0, -21 + 102 + 4 = 0

solution is (^1, ^2) = (1/3, -1/3)

Least squares

8.3

Least squares and linear equations

minimize - 2

? solution of the least squares problem: any ^ that satisfies ^ - - for all

? ^ = ^ - is the residual vector ? if ^ = 0, then ^ solves the linear equation = ? if ^ 0, then ^ is a least squares approximate solution of the equation ? in most least squares applications, > and = has no solution

Least squares

8.4

Column interpretation

least squares problem in terms of columns 1, 2, . . . , of :

minimize

- 2 =

b

-

2

=1

r = Ax^ - b

Ax^ range(A) = span(a1, . . . , an)

? ^ is the vector in range( ) = span(1, 2, . . . , ) closest to ? geometric intuition suggests that ^ = ^ - is orthogonal to range( )

Least squares

8.5

Example: advertising purchases

? demographic groups; advertising channels ? is # impressions (views) in group per dollar spent on ads in channel ? is amount of advertising purchased in channel ? ( ) is number of impressions in group ? is target number of impressions in group

Example: = 10, = 3, = 1031

Columns of matrix A

Channel 1

2

Channel 2 Channel 3

Target b and least squares result Ax^ 1,500

1,000

Impressions Impressions

1 500

1 2 3 4 5 6 7 8 9 10

Least squares

Group

1 2 3 4 5 6 7 8 9 10

Group

8.6

Example: illumination

? lamps at given positions above an area divided in regions ? is illumination in region if lamp is on with power 1 and other lamps are off ? is power of lamp ? ( ) is illumination level at region ? is target illumination level at region

Example: = 252, = 10; figure shows position and height of each lamp

25m

1 (4.0m)

2 (3.5m)

3 (6.0m)

4 (4.0m)

6 (6.0m)

5 (4.0m)

7 (5.5m)

8 (5.0m)

9 (5.0m) 10 (4.5m)

00

Least squares

25m

8.7

Example: illumination

? left: illumination pattern for equal lamp powers ( = 1) ? right: illumination pattern for least squares solution ^, with = 1

(4.0m)

(3.5m)

(6.0m)

(6.0m) (4.0m)

(4.0m) (5.5m)

(5.0m) (5.0m) (4.5m)

(4.0m)

(3.5m)

1.4

(6.0m) 1.2

(6.0m)

(4.0m) (4.0m)

(5.5m)

1

0.8

(5.0m) (5.0m) (4.5m)

0.6

Number of regions

100

100

50

50

0

0

0

1

2

0

1

2

Intensity

Intensity

Least squares

8.8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download