Finding the least square line passing through the origin

Question

So, I am trying to solve a least square problem. I have the matrix $$ A= \begin{bmatrix} \ 1&-1 \\ 1 & 1 \\ 1&2 \end{bmatrix}. $$

and the matrix

$$ b = \begin{bmatrix} 7 \\ 7 \\ 21 \end{bmatrix} $$

Now, I have found the least square line normally with the equation being $$y(t) = 4x + 9$$. However, I know am trying to find a straight line through the origin that best fits the data in a least square sense. So, my thinking is $y(0) = m \cdot 0 + b = 0$. So I know b, must equal to zero, I wanna say that $m = \frac{21}{2}$ since both the 7's would be on either side. I got y(t) by using $A^t Ax = A^Tb$. Thanks.

Answer 1

@Algebraic Pavel provides an elegant solution. A less rigorous solution follows.

The function which forces the solution through the origin has the form $y(x) = ax$ where $a$ is the slope. With these data the sum of the squares of the residuals is $$ r^2(a) = \Bigg\Vert \left[ \begin{array}{r} -1 \\ 1 \\ 2 \end{array} \right] \left[ \begin{array}{r} a \end{array} \right] - \left[ \begin{array}{r} 7 \\ 7 \\ 21 \end{array} \right] \Bigg\Vert^{2} $$

The problem reduces to finding the minimum of $r^2(a) = 6a^2 - 84 a + 539$, that is, solve $$ \frac{\partial}{\partial a} r^2 = 12 a - 84 = 0 $$

As shown earlier, the solution is that the slope $a = 7$.

Answer 2

So you want to solve a linear least squares problem with linear constraints. The solution can be found by using Lagrange multipliers. Assume you want to solve $Ax=b$ (where $A$ has full column rank) in the least squares sense such that $Cx=d$ (where $C$ has full row rank). The Lagrange function of the problem is $$ \mathcal{L}(x,\lambda)=\frac{1}{2}\|Ax-b\|_2^2+\lambda^T(Cx-d). $$ Now compute the gradient w.r.t. $x$ and $\lambda$: $$ \nabla_x\mathcal{L}(x,\lambda)=A^T(Ax-b)+C^T\lambda, \quad \nabla_{\lambda}\mathcal{L}(x,\lambda)=Cx-d. $$ Hence the first order optimality conditions give you the system $$ \begin{bmatrix} A^TA&C^T\\ C&0 \end{bmatrix} \begin{bmatrix} x\\\lambda \end{bmatrix} = \begin{bmatrix} A^Tb\\ d \end{bmatrix}. $$

---

Now plug in your $A$ and $b$, the linear constraint is $[1,0]x=0$ (you want the constant term of the line, which is the first component of $x$, to be zero), so $C=[1,0]$ and $d=0$. Solving the system leads to $$ x=\begin{bmatrix} 0\\7 \end{bmatrix} $$ and thus $$ y(t)=7t. $$

---

Yet another, less general but more straightforward, approach is to directly consider the line to have the form $y(t)=xt$. With $$ A=\begin{bmatrix}-1\\1\\2\end{bmatrix} $$ you get the least squares problem $Ax=b$ (with the same $b$ as before). Hence $x=(A^TA)^{-1}A^Tb=7$.