Introduction to Computational Linear Algebra

84 Introduction to Computational Linear Algebra

Since R

m

= Im(A) ⊕ Im(A)

⊥

, where Im(A)

⊥

is the orthogonal complement

of Im(A) in R

m

, we can express y = c + d where c ∈ Im(A) and d ∈ Im(A)

⊥

.

Therefore, for any x ∈ R

n

,

krk

2

= ky − Axk

2

,

= kc − Axk

2

+ kdk

2

,

since c ∈ Im(A). This sum of norms is minimum if and only if x is such

that Ax = c and therefore r = d, i.e., r ∈ (Im(A))

⊥

= Null(A

T

), implying

A

T

r = 0.

As a consequence, we obtain now existence of solutions to the linear least

squares problem (4.1).

Theorem 4.3 The set S(A, y) is non-empty.

Proof. The proof is constructive in obtaining S(A, y). By considering c, the

orthogonal projection of y = c + r ∈ R

m

on ...