Solving a problem using Householder's method For the following points on a plane: $(-1,1),(0,0),(1,1),(1,-1)$, we look for a polynomial $p(x)=a+bx$ such that:
$$
\sum_{i=1}^4{(p(x_i)-y_i)^2} = min 
$$
How do I formulate this as problem as a linear least squares problem and then solve it using Householder's method?
 A: Solution 1: Least Squares
You would write out the Linear Least Squares problem as:
$$A = \left(
\begin{array}{cc}
 1 & -1 \\
 1 & 0 \\
 1 & 1 \\
 1 & 1 \\
\end{array}
\right), y = \left(
\begin{array}{c}
 1 \\
 0 \\
 1 \\
 -1 \\
\end{array}
\right)$$
$$||Ax-y||_2^2 = \sum_{i=1}^m (x_1 + x_2t_i - y_i)^2, p(t) = x_1 + x_2 t$$
To solve this, we have:
$$A^TA x = A^Ty \implies x_1 = 0.363636, x_2= -0.454545$$
Solution 2: QR Factorization (use your favorite tool)
$$A = QR = \left(
\begin{array}{cccc}
 \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\
 -\frac{5}{2 \sqrt{11}} & -\frac{1}{2 \sqrt{11}} & \frac{3}{2 \sqrt{11}} & \frac{3}{2 \sqrt{11}} \\
\end{array}
\right)\left(
\begin{array}{cc}
 2 & \frac{1}{2} \\
 0 & \frac{\sqrt{11}}{2} \\
\end{array}
\right)$$
$$c = Q^Ty = \left(
\begin{array}{c}
 0.5 \\
 -0.753778 \\
\end{array}
\right)$$
We would solve $Rx = c$, which yields (compare to Solution 1):
$$x_1 = 0.363636, x_2 = -0.454546$$
Solution 3:  QR Factorization by Householder Matrices
The general algorithm is:


*

*$ u = w \pm \sigma~ e_1, |\sigma| = ||w||$

*Sign ($\pm$) above is equal to the sign of $w_1$

*$\rho = \dfrac{2}{||u||^2}$

*$H = I - \rho u u^T$

*Solve $H_nH_{n-1} \ldots H_1 Ax = H_nH_{n-1} \ldots H_1y$


We have:
$$H_1 = \left(
\begin{array}{cccc}
 -\frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \\
 -\frac{1}{2} & \frac{5}{6} & -\frac{1}{6} & -\frac{1}{6} \\
 -\frac{1}{2} & -\frac{1}{6} & \frac{5}{6} & -\frac{1}{6} \\
 -\frac{1}{2} & -\frac{1}{6} & -\frac{1}{6} & \frac{5}{6} \\
\end{array}
\right)$$
$$H_2 = \left(
\begin{array}{cccc}
 1 & 0 & 0 & 0 \\
 0 & 0.1 & 0.7 & 0.7 \\
 0 & 0.7 & 0.45 & -0.55 \\
 0 & 0.7 & -0.55 & 0.45 \\
\end{array}
\right)$$
$$H_2H_1Ax = \left(
\begin{array}{cc}
 -2. & -0.5 \\
 0. & 1.65 \\
\end{array}
\right)x = H_2H_1y = \left(
\begin{array}{c}
 -0.5 \\
 -0.75 \\
\end{array}
\right)$$
Solving this yields:
$$x_1 = 0.363636 , x_2 = -0.454545$$
Compare this to both solutions above.
Note This takes some time and work to get your hands around and I left out some details, but there is more than enough for you to work through it.
