# Find optimal least square solution to the normal equation

What is the optimal solution for $\beta_1$ and $\beta_2$ in the following normal equation:

$$\beta _{ 1 }\sum _{ i=1 }^{ n }{ { x }_{ i } } +\beta _{ 0 }=\sum _{ i=1 }^{ n }{ { y }_{ i } }$$

EDIT

Suppose you are given a set of data $(x_i,y_i)$ with y = $\beta_1x+\beta_0$ and $\beta_1,\beta_0 \in \Bbb R$ are the parameters we want to determine.
A good criteria to find parameter values is to find $\beta_1$ and $\beta_0$ such that the residual sum of squares is minimum. In other words, we find the values $\beta_0$, $\beta_1$ that minimize:

$$\sum _{ i=1 }^{ n }{ ({ \beta }_{ 1 }{ x }_{ i }+{ \beta }_{ 0 }-y_{ i })^{ 2 } }$$ which I wrote as $$\left \|\ A\begin{pmatrix} \beta _{ 1 } \\ \beta _{ 0 } \end{pmatrix}-b\ \right \|^2$$ with $A=\begin{pmatrix} { x }_{ 1 } & 1 \\ { x }_{ 2 } & 1 \\ ... & ... \\ { x }_{ n } & 1 \end{pmatrix}$ and $b = \begin{pmatrix} y_{ 1 } \\ { y }_{ 2 } \\ ... \\ y_{ n } \end{pmatrix}$

From there, you can extract the normal equation
$$\beta _{ 1 }\sum _{ i=1 }^{ n }{ { x }_{ i } } +\beta _{ 0 }=\sum _{ i=1 }^{ n }{ { y }_{ i } }$$

Now equation is, how do you find the optimal solution for $\beta_1$ and $\beta_0$?

• Optimal with regards to what? (Which is to say, state your least squares condition in your question.) What have you tried so far? Commented Jul 23, 2014 at 1:17
• You are right. Edited the question.
– Joe
Commented Jul 23, 2014 at 1:29

The normal equation $(A^TA)\vec{\beta} = A^T\vec{y}$ actually gives you two equations:

$\displaystyle\underbrace{\begin{pmatrix}\sum_{i=1}^{n}x_i^2 & \sum_{i=1}^{n}x_i \\ \sum_{i=1}^{n}x_i & n\end{pmatrix}}_{A^TA} \underbrace{\begin{pmatrix} \beta_1 \\ \beta_0 \end{pmatrix}}_{\vec{\beta}} = \underbrace{\begin{pmatrix} \sum_{i=1}^{n}x_iy_i \\ \sum_{i=1}^{n}y_i \end{pmatrix}}_{A^T\vec{y}}$

$\displaystyle\beta_1\sum_{i = 1}^{n}x_i^2 + \beta_0\sum_{i=1}^{n}x_i = \sum_{i=1}^{n}x_iy_i$ (1)

$\displaystyle\beta_1\sum_{i = 1}^{n}x_i + \beta_0n = \sum_{i=1}^{n}y_i$ (2)

Now, you have a two variable, two unknown system. You should be able to solve this.

• As an extra note, would the same method work if say, the relation between x and y was not well approximated by a line, but rather a quadratic approximation with $y = \beta_2x^2+\beta_1x+\beta_0$. So we would want to minimize $\sum _{ i=1 }^{ n }{ (\beta _{ 2 }x^{ 2 }_{ i }+\beta _{ 1 }x_{ i }+\beta _{ 0 }-y_{ i })^{ 2 } }$. Would I still be able to write this problem as a least squares problem?
– Joe
Commented Jul 23, 2014 at 1:51
• Yes you would. Of course, you would get a $3 \times 3$ system to solve. Commented Jul 23, 2014 at 1:53

Given a sequence of measurements, $\left\{ x_{k}, y_{k} \right\}_{k=1}^{m}$, and a trial function $$y(x) = \beta_{0} + \beta_{1} x,$$ the linear system is \begin{align} \mathbf{A} \beta &= y \\ \left[ \begin{array}{cc} 1 & x_{1} \\ 1 & x_{2} \\ \vdots & \vdots \\ 1 & x_{m} \end{array} \right] % \left[ \begin{array}{c} \beta_{0} \\ \beta_{1} \end{array} \right] % &= % \left[ \begin{array}{c} y_{1} \\ y_{2} \\ \vdots \\ y_{m} \end{array} \right]. % \end{align} %

Here are the normal equations expressed in terms of column vectors: \begin{align} \mathbf{A}^{*} \mathbf{A} \beta &= \mathbf{A}^{*} y \\ \left[ \begin{array}{cc} \mathbf{1} \cdot \mathbf{1} & \mathbf{1} \cdot x \\ x \cdot \mathbf{1} & x \cdot x \end{array} \right] % \left[ \begin{array}{c} \beta_{0} \\ \beta_{1} \end{array} \right] % &= % \left[ \begin{array}{c} \mathbf{1} \cdot y \\ x \cdot y \end{array} \right]. % \end{align} % The solution is $$\beta = \left( \mathbf{A}^{*}\mathbf{A} \right)^{-1} \mathbf{A}^{*} b = \frac{1}{ \left( \mathbf{1} \cdot \mathbf{1} \right) \left( x \cdot x \right) - \left( \mathbf{1} \cdot x \right)^{2}} % \left[ \begin{array}{rr} x \cdot x & -\mathbf{1} \cdot x \\ -\mathbf{1} \cdot x & \mathbf{1} \cdot \mathbf{1} \end{array} \right] % \left[ \begin{array}{c} \mathbf{1} \cdot y \\ x \cdot y \end{array} \right].$$