# Solving least squares problem using partial derivatives

Let's say we want to solve a linear regression problem by choosing the best slope and bias with the least squared errors. As example, let the points be $$x=[1, 2, 3]$$ and $$y=[1,2,2]$$.

This quadratic minimization problem can also be represented as:

$$||Ax-b||^2=||e||^2=e^2_1+e^2_2+e^2_3$$

# Linear Algebra

We could solve this problem by utilizing linear algebraic methods. We could use projections. For projecting on the $$0+$$ dimensional subspaces. Projection equation $$p = Ax = A(A^TA)^{-1}A^Tb$$ could be utilized:

$$A^T(b-Ax)=0$$

$$A^TAx = A^Tb$$

$$x = (A^TA)^{-1} A^Tb$$

We know the inner product of $$A^T$$ and $$e=b-p=b-Ax$$ is $$0$$ since they are orthogonal (or since $$e$$ is in the null space of $$A^T$$). Which is the reason why we got the equation above.

Now we need to present the quadratic minimization problem in linear algebra $$Ax=b$$:

$$\begin{bmatrix}1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}\begin{bmatrix}c \\m\end{bmatrix} = \begin{bmatrix}1 \\ 2 \\ 2 \end{bmatrix}$$

where $$c$$ is bias and $$m$$ is slope. We can see that matrix $$A$$ is a basis for the column space, $$c$$ and $$m$$ are linear coefficients and $$b$$ represents range of the function. Considering that this equation doesn't have direct solution, then we are looking for projection of the vector $$b$$ on the column space of matrix $$A$$.

Solution:

Let $$Proj(x)$$ be the projection function (where $$x$$ contains unknown coefficients that we are trying to find, in this case $$[c, m]^T$$):

$$Proj(x) = Proj\left(\begin{bmatrix}c \\ m \end{bmatrix}\right) = (A^TA)^{-1}A^Tb = \left(\begin{bmatrix}1 & 1 & 1 \\ 1 & 2 & 3\end{bmatrix}\begin{bmatrix}1 & 1 \\ 1 & 2 \\ 1 & 3\\ \end{bmatrix}\right)^{-1} \begin{bmatrix}1 & 1 & 1 \\ 1 & 2 & 3\end{bmatrix}\begin{bmatrix}1 \\ 2 \\ 2\\ \end{bmatrix} = \left(\begin{bmatrix}3 & 6 \\ 6 & 14 \end{bmatrix}\right)^{-1}\begin{bmatrix}5 \\ 11 \end{bmatrix}=\left(\frac{1}{3(14)-6(6)}\begin{bmatrix}14 & -6 \\ -6 & 3 \end{bmatrix}\right)\begin{bmatrix}5 \\ 11 \end{bmatrix}=\begin{bmatrix}2.33333333 & -1 \\ -1 & 0.5 \end{bmatrix}\begin{bmatrix}5 \\ 11 \end{bmatrix} = \begin{bmatrix}0.66666667 \\ 0.5 \end{bmatrix}$$

# Multivariable Calculus

At this point of the lecture Professor Strang presents the minimization problem as $$A^TAx=A^Tb$$ and shows the normal equations. Then he proceeds solving minimization problem using partial derivatives, although I couldn't quite understand how could partial differentiation be used to solve this problem.

From what I know, partial derivatives can be used to find derivatives for the structures that are in higher dimensions. Since for example finding full derivative at certain point of a 3 dimensional object may not be possible since it can have infinite tangent lines. Although, by treating one variable as a constant can be utilized to solve the differentiation problem, and this process is called partial differentiation from my knowledge.

# Question

How does partial differentiation solution exactly work? How can it be compared to the linear algebraic orthogonal projection solution?

Thank you!

• Apr 29, 2018 at 4:46

To try to answer your question about the connection between the partial derivatives method and the method using linear algebra, note that for the linear algebra solution, we want $$(Ax-b)\cdot Ax = 0$$. For the partial derivatives, we want $\frac{\partial}{\partial x_1}||Ax-b||^2 = 0$ and $\frac{\partial}{\partial x_2}||Ax-b||^2 = 0$. Suppose we have $n$ data points and $n$ inputs $a_1,a_2,\cdots a_n$. Then, with $x_1$ representing the slope of the least squares, and $x_2$ representing the intercept, we have that $$\frac{\partial}{\partial x_1}||Ax-b||^2 = 2\sum_{i=1}^{n}a_i(x_1a_i+x_2-b_i) = 0$$ and $$\frac{\partial}{\partial x_2}||Ax-b||^2 = 2\sum_{i=1}^{n}(x_1a_i+x_2-b_i) = 0$$. This implies that $$x_1\sum_{i=1}^{n}a_i(x_1a_i+x_2-b_i)+x_2\sum_{i=1}^{n}(x_1a_i+x_2-b_i) = 0$$ $$\implies \sum_{i=1}^{n} (x_1a_i+x_2)(x_1a_i+x_2-b_i)=0=Ax\cdot (Ax-b)$$

• Hello, thanks for the question! So as I understand the goal here is to find local minimum? Therefore the partial derivative of quadratic error function with respect to $x$ is equal to the sum of squared error that our matrix can span as well. But apologies for my confusion, why are there two partial derivatives? Apr 29, 2018 at 8:20

You can solve the least squares minimization problem $$\min_{x} ||Ax-b||$$ by setting the partial derivatives of the cost function (wrt each element of x) $$f(x) = ||Ax-b||$$ equal to zero. You will get $n$ equations in $n$ unknowns, where $n$ is the dimension of the least squares solution vector $x$. It can be shown that the solution x is a local minimum.

By using least squares to fit data to a model, you are assuming that any errors in your data are additive and Gaussian.

You have a matrix $$A$$ with 2 columns -- one column of ones, and one column the vector $$x$$ (in your case $$x=[1, 2, 3]^T$$. You are looking for vector of parameters $$p=[c, m]^T$$. For given parameters $$p$$ the vector $$Ap$$ is the vector of values $$c+mx_i$$, and the vector $$e=Ap-y^T$$ is the vector of errors of you model $$(c+mx_i)-y_i$$. Now the sum of squares of errors is $$f(p)=|Ap-y|^2$$, and this is what you want to minimize, by varying $$p$$. The basic idea is to find extrema of $$f(p)$$ by setting $$f$$s derivative (with respect to $$p$$) to zero. It will turn out that if not all $$x_i$$ are equal, this local extremum is unique, and is in fact a global minimum. Leaving that aside for a moment, we focus on finding the local extremum.

We can do it in at least two ways. The higher-brow way is to say that for $$g(z)= |z|^2$$ one has $$Dg(z)=2z^T$$ (since $$\frac{\partial}{\partial z_i} \sum z_i^2=2 z_i$$), and so, since $$D (Ap)=A$$ at every point $$p$$, by chain rule $$D(|Ap-y|^2)=2(Ap-y)^T A$$. Thus the optimality equation is $$(Ap-y)^T A=0$$, as in the linear algebra approach.

The lower-tech method is to just compute the partials with respect to $$c$$ and $$m$$.

For partial in $$c$$:

$$\frac{\partial}{\partial c} \sum_i [(c+mx_i)-y_i]^2=\sum_i 2[(c+mx_i)-y_i]=2(Ap-y)\cdot [1, \ldots, 1]^T=0$$

For partial in $$m$$:

$$\frac{\partial}{\partial m} \sum_i [(c+mx_i)-y_i]^2=\sum_i 2 [(c+mx_i)-y_i] x_i =2(Ap-y)\cdot x=0$$

Setting both to zero we get two equations expressing the fact that the two columns of $$A$$ are orthogonal to $$(Ap-y)$$, which is again the same as $$(Ap-y)^TA=0$$.

Thus the optimization approach is equivalent to the linear algebra one.

Now about the nature of local optimum.

From general theory: The function $$f(p)$$ is quadratic in $$p$$ with positive-semidefinite leading term $$A^TA$$ If $$x$$ is not proportional to the vector of 1s, this leading term is positive definite, and so the function is strictly convex and hence has a unique global minimum.

Alternatively: If $$x$$ is not proportional to the vector of 1s, then rank of $$A$$ is 2, and $$A$$ has no null space. Then $$|Ap|$$ is never zero, and so attains a minimum on the unit circle. Then for $$p$$ with large $$|p|$$ we have that $$|Ap|$$ is large, hence so is $$|Ap-y|$$. On the other hand, the set of solutions of $$(Ap-y)^TA=0$$ aka of $$A^T(Ap-y)=0$$ aka $$A^TAp=A^Ty$$ is an affine subspace on which the value of $$f(p)$$ is therefore constant. This can work only if this space is of dimension 0 - otherwise as we go to infinity inside this subspace the value $$f(p)$$ would have to grow unbounded while staying constant. So in fact there is precisely one solution, and hence (since the function grows to positive infinity at infinity) it is a global minimum, just as expected.