0
$\begingroup$

(Sorry I had to post the images as links. I don't have enough cred to post pictures directly yet)

I'm trying to understand what the least squares solution to an overdetermined system means geometrically in the case of the following system:

$$ y = -2x-1\\ y = 3x -2\\ y = x+1\\ $$

rewritten in matrix form:

$$ \overbrace{\begin{bmatrix} 2 & 1\\ -3 & 1\\ -1 & 1 \end{bmatrix}}^A \underbrace{\begin{bmatrix} x\\ y \end{bmatrix}}_x = \overbrace{\begin{bmatrix} -1\\ -2\\ 1 \end{bmatrix}}^b $$

Using A\b in MATLAB, you get the solution $\begin{bmatrix}0.1316 & -0.5789\end{bmatrix}^T$. I know that MATLAB returns the lowest norm solution of a least squares problem. I have plotted the system here and the green dot in the middle is this least squares solution.

Now, correct me if I'm wrong, but (in this 2D case) the least squares solution minimizes the "distance" from the solution to each line. I can geometrically calculate the distance of a point $(x_0,y_0)$ from a line $ax + by + c = 0$ as follows:

$$\mathrm{distance} = \frac{|ax_0 + by_0 + c|}{\sqrt{a^2 + b^2}}$$

and doing that for each line produces the following sum of squared distances function

dfun = @(x,y) ((y+2*x+1).^2)/(1^2 + 2^2) + ((y+3*x+2).^2)/(1^2 + 3^2) + ((y+x-1).^2)/(1^2 + 1^2);

If I generate a surface using this function over a range of $x$ and $y$ values, I get this surface with this top-down view (looking down the z-axis on the xy plane). You can download the MATLAB .fig file here if you want to zoom and pan (requires MATLAB, link expires in 30 days).

Here is an image showing the least squares solution with the sum of squares of distances of the solution and its norm. As can be seen, the norm is $0.5937$ and the distance is $1.4704$. But clearly, there is a contour that has a lower sun of squared distance in the image, as shown here for $(x_0, y_0) = (-0.3,0)$, where the norm and the sum of squared distances are both smaller. Shouldn't this (or another point) be a better least squares solution? Do I have the wrong intuition about what least squares is doing here?

$\endgroup$

2 Answers 2

0
$\begingroup$

First of all : Welcome to the site !

When you face an overdetermined system of $m$ linear or nonlinear (even implicit) equations $$f_i(x_1,x_2,\cdots,x_n)=0 \quad\text{for}\quad i=1,2,\cdots,m\qquad \quad\text{and}\quad m >n$$ it reduces to the minimization of a norm.

The simplest is $$\Phi(x_1,x_2,\cdots,x_n)=\sum_{i=1}^n w_i \Big[f_i(x_1,x_2,\cdots,x_n)\Big]^2$$ which shows the analogy with weighted least-square method.

For the problem you gave, using equal weights, $$\Phi(x,y)=(y+2x+1)^2+(y-3x+2)^2+(y-x-1)^2$$ Computing the partial derivetives $$\frac{\partial \Phi(x,y)}{\partial x}=28 x-4 y-6 \qquad\text{and}\qquad \frac{\partial \Phi(x,y)}{\partial y}=-4 x+6 y+4$$ which gives $x=\frac{5}{38}$ and $y=-\frac{11}{19}$. At this point, $\Phi=\frac{169}{38}$ is the absolute minimum for this specific norm.

If you change the definition of the norm or even the weights, different results.

I think that this approach would be simpler than the one based on distance (but, for sure, I may be wrong) since it is totally general and not limited to linear equations.

$\endgroup$
1
  • $\begingroup$ Thank you! I think I had the right understanding of what least squares is doing in this case. After reading your answer I realizes that my dfun was wrong - I got a couple of the signs wrong and that's why I was getting the wrong surface. I will post an answer with the right images. Not sure if I should accept my own answer or yours... $\endgroup$
    – vyb
    Sep 6, 2021 at 17:40
0
$\begingroup$

After reading Claude Leibovici's answer above, I realized that my dfun had typos in it -- I messed up a couple of minus signs in the function.

Additionally, the norm typically used for least squares calculations (also used by MATLAB) is the $l^2$-norm (a.k.a Euclidean norm):

$$ x = \begin{bmatrix}x_1\\ x_2\\ \vdots\\ x_n\end{bmatrix}, ||x|| = \sqrt{x_1^2 + x_2^2 + \dots + x_n^2}$$

Note that there is no scaling of the "distance" like there is in my dfun. Therefore correct function should be:

dfun = @(x,y) ((y+2*x+1).^2) + ((y-3*x+2).^2) + ((y-x-1).^2);

After fixing these mistakes, here is the surface that is generated, with this top-down view. As can be seen here, the solution of $\begin{bmatrix}0.1316 & -0.5789\end{bmatrix}^T$ is, in fact, correct and confirms the original intuition I was trying to confirm.

$\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.