1
$\begingroup$

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!

$\endgroup$
1

3 Answers 3

1
$\begingroup$

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)$$

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – ShellRox
    Apr 29, 2018 at 8:20
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.