Basics of the least squares method最小二乗法さいしょうにじょうほう

1Introduction

The key point of this lecture is that the least squares method最小二乗法さいしょうにじょうほう is not a way to force an inconsistent equation to have an exact solution. It is the method of projecting the right-hand side右辺うへん onto the column space列空間れつくうかん.

The equation $Ax=b$Ax=b has a solution exactly when $b$b lies in $\mathrm{Col}\left(A\right)$\operatorname{Col}(A). In applications, measured data often put $b$b slightly outside the column space列空間れつくうかん. Then the correct problem is to choose $Ax$Ax as the point of $\mathrm{Col}\left(A\right)$\operatorname{Col}(A) closest to $b$b.

2Terms and definitions

Least squares最小二乗法さいしょうにじょうほう means minimizing

over $x$x.

The residual残差ざんさ is

For real matrices, the normal equations正規方程式せいきほうていしき are

In the complex case, $A^T$A^T is replaced by the conjugate transpose共役転置きょうやくてんち $A^{*}$A^*:

3Plan

Since $Ax$Ax always lies in $\mathrm{Col}\left(A\right)$\operatorname{Col}(A), minimizing $\parallel Ax-b\parallel$\|Ax-b\| means projecting $b$b onto that column space列空間れつくうかん. The best approximation $Ax$Ax and the error $b-Ax$b-Ax are orthogonal, and that orthogonality gives the normal equations正規方程式せいきほうていしき.

4Intuitive explanation

Think of the column space列空間れつくうかん as a plane. If $b$b is not on the plane, $Ax=b$Ax=b cannot hold. But there is a closest point on the plane. That point is $Ax$Ax, and the perpendicular error is the residual.

The reason we project onto the column space列空間れつくうかん is built into the expression $Ax$Ax: no matter how $x$x is chosen, $Ax$Ax is a linear combination線型結合せんけいけつごう of the columns of $A$A. Therefore the reachable right-hand sides are exactly $\mathrm{Col}\left(A\right)$\operatorname{Col}(A).

At the closest point $\hat{b}$\hat b, the residual $r=b-\hat{b}$r=b-\hat b has no component along the column space列空間れつくうかん. Otherwise one could move within the column space列空間れつくうかん and reduce the distance. Hence

5Precise explanation

5.11. Projection onto the column space列空間れつくうかん

For a least squares solution, $Ax$Ax is the orthogonal projection直交射影ちょっこうしゃえい of $b$b onto $\mathrm{Col}\left(A\right)$\operatorname{Col}(A). Therefore

is orthogonal to every column of $A$A.

5.22. From orthogonality to normal equations正規方程式せいきほうていしき

Let the columns of $A$A be $a_1,\dots ,a_n$a_1,\ldots,a_n. The condition

is written in matrix form as

in the real case. Substituting $r=b-Ax$r=b-Ax gives

so

In the complex case, the same orthogonality condition is written as $A^{*}r=0$A^*r=0, hence

5.33. Uniqueness

If the columns of $A$A are linearly independent, then $A^{T}A$A^TA is invertible可逆かぎゃく and the least squares solution is unique:

If the columns are linearly dependent, the projection $\hat{b}$\hat b is still unique, but the coefficient vector $x$x may not be unique. The pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ selects the least-norm solution最小さいしょうノルム解かい.

5.44. Projection matrix

If $A$A has full column rank階数かいすう, the orthogonal projection直交射影ちょっこうしゃえい onto $\mathrm{Col}\left(A\right)$\operatorname{Col}(A) is

Then

The matrix $P$P satisfies

In the complex case,

6Concrete examples

For

the vector $Ax$Ax has all entries equal to $x$x. The normal equation is

so $x=7/3$x=7/3. This is the average of $1,2,4$1,2,4 and is the best constant approximation.

For a line fit through $(0,1),(1,2),(2,2)$(0,1),(1,2),(2,2) using $y=\alpha +\beta t$y=\alpha+\beta t, write

Then

Solving gives

The best-fit line is

and the residual is orthogonal to both columns of $A$A.

7Another viewpoint

Geometrically, the least squares method最小二乗法さいしょうにじょうほう projects a point onto a subspace部分空間ぶぶんくうかん. Statistically, it minimizes the sum of squared differences between observed values and predicted values.

8Theorem: existence and projection characterization

For every $A\in R^{m\times n}$A\in\mathbb R^{m\times n} and $b\in R^m$b\in\mathbb R^m, a minimizer of $\parallel Ax-b\parallel$\|Ax-b\| exists. The minimizing vector $x$x may not be unique, but the best approximation $\hat{b}=Ax$\hat b=Ax is unique and equals the orthogonal projection直交射影ちょっこうしゃえい of $b$b onto $\mathrm{Col}\left(A\right)$\operatorname{Col}(A).

Indeed, since $\mathrm{Col}\left(A\right)$\operatorname{Col}(A) is finite-dimensional, we can decompose

Choose $x$x such that $Ax=\hat{b}$Ax=\hat b. For any $y$y,

This proof shows that least squares is fundamentally an orthogonal-decomposition argument.

9rank階数かいすう-deficient case and least-norm solutions

If the columns of $A$A are dependent, $A^{T}A$A^TA is not invertible可逆かぎゃく. The normal equations正規方程式せいきほうていしき may have multiple solutions. All such solutions give the same projection $\hat{b}$\hat b, and their differences lie in $\ker A$\ker A. To choose a unique representative, one selects the solution with no component in the nullspace direction, namely the least-norm solution最小さいしょうノルム解かい. This is what the pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ provides.

10Numerical warning

The normal equations正規方程式せいきほうていしき are theoretically important, but forming $A^{T}A$A^TA can roughly square the condition number. A mildly ill-conditioned matrix can therefore become much more unstable. In numerical computation, QR decomposition or singular value decomposition特異値分解とくいちぶんかいSVD is usually safer.

11Criteria

• Use least squares when $Ax=b$Ax=b is overdetermined or inconsistent.
• The residual must be orthogonal to the column space列空間れつくうかん.
• If the columns of $A$A are independent, use the invertibility of $A^{T}A$A^TA.
• If the columns are dependent, distinguish the unique projection from nonunique coefficient vectors.

12Scope and limitations

In real standard inner products, use $A^T$A^T. In complex spaces, use $A^{*}$A^*. When the columns are dependent, the projection $\hat{b}$\hat b is unique but the coefficients $x$x need not be. Numerical algorithms often avoid explicitly forming $A^{T}A$A^TA.

13Theorem: existence of least-squares solutions and orthogonal projection

For $A\in R^{m\times n}$A\in\mathbb R^{m\times n} and $b\in R^m$b\in\mathbb R^m, a vector $x$x minimizing $\parallel Ax-b\parallel$\|Ax-b\| always exists. However, $x$x need not be unique. The unique object is the best approximation $\hat{b}=Ax$\hat b=Ax, namely the orthogonal projection直交射影ちょっこうしゃえい of $b$b onto $\mathrm{Col}\left(A\right)$\operatorname{Col}(A).

The reason is that $\mathrm{Col}\left(A\right)$\operatorname{Col}(A) is a finite-dimensional subspace部分空間ぶぶんくうかん, so

Choose $x$x with $Ax=\hat{b}$Ax=\hat b. For any $y$y,

Here $Ay-\hat{b}\in \mathrm{Col}\left(A\right)$Ay-\hat b\in\operatorname{Col}(A) and $r\perp \mathrm{Col}\left(A\right)$r\perp\operatorname{Col}(A) are used. This proof shows that least squares is based on orthogonal decomposition直交分解ちょっこうぶんかい, not merely on differentiation.

14rank階数かいすう-deficient case and least-norm solutions

If the columns of $A$A are linearly dependent一次従属いちじじゅうぞく, then $A^{T}A$A^TA is not invertible. The normal equations正規方程式せいきほうていしき

may have multiple solutions. Those solutions give the same $Ax=\hat{b}$Ax=\hat b, and their differences lie in $\ker A$\ker A. To select a unique representative, choose the least-norm solution with no component in the $\ker A$\ker A direction. The pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ realizes this choice.

15Calculation example: fitting a line with two variables

Approximate the points $(0,1),(1,2),(2,2)$(0,1),(1,2),(2,2) by $y=\alpha +\beta t$y=\alpha+\beta t. In matrix form,

The normal equations are

so

Solving gives

Thus the best-fitting line is

The residual $b-Ax$b-Ax is orthogonal直交ちょっこう to the two columns of $A$A.

16Practical numerical warning

Forming $A^{T}A$A^TA roughly squares the condition number. Thus even if $A$A is only moderately ill-conditioned, $A^{T}A$A^TA can become much more unstable. Normal equations show the theoretical structure, but in numerical computation QR decomposition or singular value decompositionSVD特異値分解とくいちぶんかい is safer.

17Final forms

18In one sentence

The least squares method最小二乗法さいしょうにじょうほう projects $b$b onto the column space列空間れつくうかん and makes the residual orthogonal to that column space列空間れつくうかん.

19Exercise links

20Related links