Solving a problem using Householder's method

Question

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?

Answer 1

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.