Chapter5-Least Squares

In this Chapter we will introduction two main algorithms for fitting problem, the least squares and QR decomposition.

The Fitting Problem

Like what we talk in Chapter4-Interpolation, we always want to find a proper function $P(X)$ that go through all the given points. But it may be too costly sometimes. So does there any way to fit the given points? That’s where least squares works.

Suppose there are $n+1$ points

$$(x_0,y_0),(x_1,y_1),\cdots ,(x_n,y_n)$$

To fit with given function:

$$\phi (x)=a_0{\phi }_0\left(x\right)+\cdots +a_m{\phi }_m\left(x\right),$$

Given the weight matrix, label matrix and coefficient matrix: $X=\left[\begin{array}{c}{a}_0\\ a_1\\ ⋮\\ a_m\end{array}\right],b=\left[\begin{array}{c}{y}_0\\ y_1\\ ⋮\\ y_n\end{array}\right],A=\left[\begin{array}{cccc}1& {\phi }_0(x_0)& \cdots & {\phi }_m(x_0)\\ 1& {\phi }_0(x_1)& \cdots & {\phi }_m(x_1)\\ ⋮& \ddots & \ddots & ⋮\\ 1& {\phi }_0(x_n)& \cdots & {\phi }_m(x_n)\end{array}\right]$

Our goal is to let the loss function

$$L(X)=\Vert r{\Vert }_2=\Vert AX-b{\Vert }_2=\frac{1}{2}(AX-b{)}^{\top }(AX-b)$$

To be least. Namely:

$$\frac{\partial L(X)}{\partial X}=A^{\top }(AX-b)=0$$

Rewrite it:

$$X^{\ast }=(A^{\top }A{)}^{-1}{A}^{\top }b$$

The problem turn out to be solve the equation above.

Least Squares

text title here...

example of least squares

example of least squares

QR Decomposition

If we Let

$$A=QR$$

Then:

$$X^{\ast }=R^{-1}{Q}^{\top }b$$

Connection Between Least Squares and QR Decomposition

Least squares and QR decompostion