5
$\begingroup$

I have always been confused about whether the approximate solution to $Ax=b$ is equivalent to minimizing the average distance of all of the $b$ vectors to $Ax$, or whether it is minimizing the distance projected along the $b$ axis?

(where $A$ is full rank and skinny and the system is overdetermined).

Consider these two pictures: minimizing the distance projected along the $b$ axis from http://www.statisticshowto.com/least-squares-regression-line/

and another figure on the same page:

projection onto the line $Ax$ also from from http://www.statisticshowto.com/least-squares-regression-line/.

Notice these are two figures on the same page! I do not understand how these are both being minimized at the same time. can someone please explain? thanks.

this is a related question Least squares solutions and orthogonal projection?

$\endgroup$
0

4 Answers 4

3
$\begingroup$

The least squares value is the $x$ that minimizes $(Ax-b)^2.$ However, least squares is more often thought of as a curve fitting method where you want to fit a line to the points $(x_1,y_1),$ $\ldots,(x_n,y_n) $ and you want a best fit line. In this case we take $$ A = \pmatrix{1& x_1\\ 1& x_2\\\vdots& \vdots\\ 1 & x_n}$$ and $$b = \pmatrix{y_1\\\vdots \\y_n}$$ and parametrize $x$ as $x=\pmatrix{a\\b}$ and then when we minimize $(b-Ax)^2,$ we get a fit line $y_i\approx bx_i + a.$ The picture of the fit line matches your first diagram above. And the quantity you have minimized is the sum of the squares of the quantities depicted.

(Sorry about the potentially confusing double use of $x.$ Usually in regression it's written $y=X\beta$ rather than $b=Ax$.)

However, when we look at it as an approximate solution to an overdetermined system of equations, you can view it as finding an orthogonal projection onto the column space of $A$ that minimizes the Euclidean distance in $n$-dimensional space between the point $b$ and the point $Ax$ that it's projected to.

$\endgroup$
6
  • $\begingroup$ At first you say "The pictures of the fit line matches your [my] first diagram above", but this doesn't seem to be consistent with what you say later about "view it as finding an orthogonal projection onto the column space of A" (that seems to align with my second figure more closely). $\endgroup$
    – makansij
    Jul 1, 2018 at 5:05
  • 1
    $\begingroup$ @Candic3 Viewing the link in context the second picture just seems out and out wrong. In the view as an orthogonal projection (where these figures would be schematic representations of things in high-dimensional spaces) the plane you're projecting on is a fixed thing (it is the column space of $A$)... not something you move around to minimize some distance. The distance that is being minimized is that between the point and the point on the plane it is being projected onto. In other words we're choosing the projection that moves points orthogonally rather than any other direction. $\endgroup$ Jul 1, 2018 at 5:11
  • 1
    $\begingroup$ @Candic3 When we're viewing this as a trend-line fitting procedure as I outlined above, it's best for one's sanity to write it as $y =X\beta$ rather than $b=Ax$ where $X$ is a $n\times 2$ matrix as I wrote down above with the first column all ones and $\beta$ is $2\times 1$ where the first component is an 'intercept' and the second is a \slope' of the regression line. Then we view $X\beta$ as an estimate of $y$ by a trend line and the components of $y-X\beta$ are the errors drawn on the first diagram. So minimizing $(y-X\beta)^2$ over $\beta$ is minimizing the sum of squares of those errors. $\endgroup$ Jul 1, 2018 at 5:22
  • 1
    $\begingroup$ @Candic3 Choosing $\beta$ to minimize the sum of squared residuals between $y_i$ and $(X\beta)_i = bx_i+a$ (where the residuals are depicted in your first diagram) and choosing $\beta$ so that $X\beta$ is the orthogonal projection of $y\in \mathbb R^n$ onto the column space of $X$ (as depicted in the slides you sent) are the exact same thing. These diagrams refer to superficially very different concepts that happen to be different depictions of the same thing. $\endgroup$ Jul 1, 2018 at 5:42
  • 1
    $\begingroup$ @Candic3 If it helps, orthogonal projection is a much more general thing than trend-line fitting by least squares. Trend-line fitting is orthogonal projection applied to the situation $y = X\beta$ where $X$ takes that form with the first column ones and the second column the $x$ data and $y$ is the y data. $\endgroup$ Jul 1, 2018 at 5:58
2
$\begingroup$

The "standard" least squares method assumes that the $x$ values are precise and the "error" is only in the $y$ data. Therefore it minimize the vertical ($y$) distance.

When both the $x$ and $y$ data are subject to error (of course under the assumption that they are normally distributed, independent, etc..), the distance to be minimized shall be along segments inclined of $\sigma_y/\sigma_x$.

That's called Total Least Squares.

$\endgroup$
2
  • $\begingroup$ Interesting, so from what I'm gather then, principal component analysis is moreclosely related to total least squares. all my life I've thought PCA was just multiple least squares regression, but you're telling me that it is more closesly related to total least squares, which isdifferent. is that true? $\endgroup$
    – makansij
    Jul 1, 2018 at 4:35
  • $\begingroup$ @Candic3: what it is true, in all statistical field, is that everything depends on a) what is known b) what is presumed to be known c) what is assumed to be demonstrated. PCA starts from certain assumptions about the data, Total Least Squares from others. $\endgroup$
    – G Cab
    Jul 1, 2018 at 14:43
2
$\begingroup$

Any kind of regression that you perform should describe the model that is used and the way that $\|\hat x - x\|$, the "distance" between the estimated value and the measured value is defined.

Given the equation $Ax = y$ where $A \in \mathbb R^{m \times n}, x \in \mathbb R^{n \times 1},$ and $y \in \mathbb R^{n \times 1}$, the most common model is $$Ax = y + \epsilon.$$ The best fit estimator, $\hat x$, will minimize $$\epsilon^T \epsilon = \sum_{i=1}^n \epsilon_i^2$$ and the formula is $$\hat x = (A^TA)^{-1}A^Ty$$ which requires that the columns of $A$ are linearly independent.

There are other models. You might want to minimize the absolute error, $$\max_{i=1}^n |\epsilon_i|$$ or you might want to calculate the line $\ell$ that minimizes $$\sum_{i=1}^n d((x_i, y_i), \ell )^2$$ the sum of the squares of the distances from the points $(x_i, y_i)$ to the line $\ell$. If the line $\ell$ is described by $ax+by=c$, then $d((x_i, y_i), \ell )^2 = \dfrac{(ax_i+by_i-c)^2}{a^2+b^2}$.

There are many other models.

$\endgroup$
2
  • $\begingroup$ So, when you say "the sum of squares distances" does that mean point-to-set distance of each $y_i$ to the set of points $\in R(A)$? I'm having trouble extrapolating an answer to my question from your post. $\endgroup$
    – makansij
    Jul 1, 2018 at 4:57
  • 1
    $\begingroup$ I edited my post. I hope it makes a bit more sense. I am not happy with what he calls "ordinary" least squares regression as it is very far from the most popular form of linear regression. $\endgroup$ Jul 1, 2018 at 6:00
1
$\begingroup$

In the first picture, we want the line of best fit. We want to solve $A\bf{x}=b$ in a way that makes $ \| A\bf{x}-b\|$ minimum. We cannot have $A\bf{x}=\bf{b}$, but will find $\bf{\overline{b}}$ such that $A\bf{x}=\bf{\overline{b}}\in$ $R(A)$ (orhogonal proj of $\bf{b} $ onto $R (A) $), with $\bf{x}$ $=(a,b)$ say, and the line of best fit $y=ax+b$ (A as in one of the other answers above).

So in the actual data plot we have the point $(x_i,y_i)$ and its corresponding 'best fit' point $(x_i,ax_i+b)$. The distance between the actual and 'estimated' point is the distance between these two points and is indicated in the graph by the red arrow (measured on the $y$-axis if you wish). The sum of these terms (each squared) is also said to be sum of squared errors of this 'approximation', and it has been minimised by using the 'least squares' method.

Note also that we can talk about $\overline {b} $ as being 'closest' vector in range of $A $ to vector $b $ (it is its ortogonal projection onto range of $A $. It is via this orthogonal projection that we obtain the (least squares) solution above.

$\endgroup$
5
  • $\begingroup$ Okay, so from what I understand of your answer, we are minimizing what is shown in the first figure (with the red lines) - NOT the second figure. So, is the 2nd figure relevant to least squares at all? Or does it not matter whether we optimize for the minimal orthogonal distance (figure two with blue lines) versus the minimal residual distance (figure 1 with red lines)? $\endgroup$
    – makansij
    Jul 1, 2018 at 5:15
  • 1
    $\begingroup$ @Candic3 I would not give the second picture much thought. It seems misleading (it is not clear what 'distance' one is supposed to think of here) and it is not properly labeled or referenced. $\endgroup$
    – AnyAD
    Jul 1, 2018 at 5:29
  • $\begingroup$ Check out see.stanford.edu/materials/lsoeldsee263/05-ls.pdf on slide 3. Are you telling me that's wrong? $\endgroup$
    – makansij
    Jul 1, 2018 at 5:30
  • 1
    $\begingroup$ @Candic3 No, that is not what I am telling you at all. What is on that slide is what I have described in my answer above and it is correct. You can take that picture, then, as a schematic representation of the projection of vector $b$ onto $R(A)$, which as I have already said, is an orthogonal projection. $\endgroup$
    – AnyAD
    Jul 1, 2018 at 5:37
  • 1
    $\begingroup$ And the error vector is given by $\bf {b-\overline {b}}$. This is orthogonal to range of $A $ (plane/line in schematuc representation of this, eg the slide you mention. $\endgroup$
    – AnyAD
    Jul 1, 2018 at 6:46

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.