Least Squares Estimation

Systems and Control Theory Lecture Notes

Laura Giarr´ e

Lesson 2: Least Squares Estimation

 Least Squares Estimation

 Computing the LS

 Projection Theorem

Least Squares Estimation

 Consider a system of m equations in n unknown, with m > n, of the form

y = Ax.

 Assume that the system is inconsistent: more equations than unknowns, equations not linear combinations of one another.

 In these conditions, there is no x such that y − Ax = 0.

However, one can write e = y − Ax, and find x that minimizes e.

 This is a least squares problem min x e = min

x y − Ax ² ₂ .

The optimal x is the least squares estimate.

Computing the Least Square Estimate (LS)

 The set M : {z ∈ R ^m : z = Ax, x ∈ R ⁿ } is a subspace of R ^m , called the range of A, R(A), i.e., the set of all vectors

obtained by linear combinations of the columns of A.

 Now we are looking for the element of M that is closest to y, in 2-norm. The solution is:

e = (y − Aˆx)⊥R(A).

 In particular, if a _i is the i-th column of A, then

(y − Aˆx)⊥R(A) ⇔a ^ _i (y − Aˆx) = 0, for i = 1, ..., n A ^ (y − Aˆx) = 0

A ^ Aˆx = A ^ y.

 Then the LS solution is

ˆx = (A ^ A) ⁻¹ A ^ y.

The Gram product

 Let us take a more abstract look at this problem, e.g., to

address the case that the data vector y is infinite-dimensional.

 Given an array of n _A vectors A = [a ₁ |...|a _n

], and an array of n _B vectors B = [b 1 |...|b n

], both from an inner vector space V , define the Gram Product ≺ A, B  as a n _A × n _B matrix such that its (i, j) entry is a i , b j .

 For the usual Euclidean inner product in an m-dimensional space,

≺ A, B = A ^ B.

 Symmetry and linearity of the inner product imply symmetry

and linearity of the Gram product.

The Least Squares Estimation Problem

 Consider again the problem of computing

x∈R min

y − Ax = min

y∈R(A) y − ˆy ₂

 y can be an infinite-dimensional vector, as long as n is finite.

 We assume that the columns of A = [a 1 , a 2 , ..., a n ] are independent.

Lemma (Gram matrix) The columns of a matrix A are independent

⇔ ≺ A, A  is invertible.

Proof of Lemma

 If the columns are dependent, then there is η = 0 such that Aη = 

j a j η j = 0. But then j a i , a j η j = 0 by the linearity of inner product.

That is, ≺ A, A  η = 0, and hence ≺ A, A  is not invertible.

 Conversely, if ≺ A, A  is not invertible, then ≺ A, A  η = 0 for some η = 0.

In other words η ^ ≺ A, A  η = 0, and hence Aη = 0.

The Projection Theorem and Least Squares Estimation 1

 y has a unique decomposition y = y 1 + y 2 , where y 1 ∈ R(A), and y ₂ ∈ R ^⊥ (A).

 To find this decomposition, let y 1 = Aα, for some α ∈ R ⁿ . Then, ensure that y ₂ = y − y ₁ ∈ R ^⊥ (A). For this to be true,

a _i , y − Aα = 0, i = 1, ..., n, i.e.,

≺ A, y − Aα = 0.

 Rearranging, we get ≺ A, A  α =≺ A, y 

 If the columns of A are independent,

α =≺ A, A  ⁻¹ ≺ A, y 

The Projection Theorem and Least Squares Estimation 2

 Decompose e = e ₁ + e ₂ ( e ₁ ∈ R(A), and e ₂ ∈ R ^⊥ (A)).

 Note that e = e ₁  + e ₂ .

 Rewrite e = y − Ax as

e ₁ + e ₂ = y ₁ + y ₂ − Ax, i.e.,

e ₂ − y ₂ = y ₁ − e ₁ − Ax.

 Each side must be 0, since they are on orthogonal subspaces!

 e 2 = y 2 – can’t do anything about it.

 e ₁ = y ₁ − Ax = A(α − x) - minimize by choosing x = α.

ˆx =≺ A, A  ⁻¹ ≺ A, y 

Examples

 If y, e ∈ R ^m , and it is desired to minimize

e ² = e ^ e =  _m

i=1 |e _i | ² , then ˆx = (A ^ A) ⁻¹ A ^ y.

(If the columns of A are mutually orthogonal, A ^ A is diagonal, and inversion is easy)

 If y, e ∈ R ^m , and it is desired to minimize e ^ Se, where S is a Hermitian, positive-definite matrix, then ˆx = (A ^ SA) ⁻¹ A ^ Sy.

 Note that if S is diagonal, then e ^ Se =  _m

i=1 s _ii |e _i | ² , i.e., we are minimizing a weighted least square criterion. A large s _ii penalizes the i _th component of the error more.

 In a stochastic setting, the weight matrix S should be related to the noise covariance, i.e.,

S = (E[ee ^ ]) ⁻¹

Thanks

DIEF- laura.giarre@unimore.it