Checking my understanding of projection onto subspace vs least square approximation

Question

I have trouble understanding the topic of projection vs. least square approximation in an Introductory Linear Algebra class. I know this question has already been asked (Difference between orthogonal projection and least squares solution), but I want to check my understanding.

PROJECTION ONTO SUBSPACE

In projection, the purpose is to find the point where the projection occurs onto a subspace. Subspace here must pass through the center of the origin. For simplicity, assume that we are talking about the case of $\mathbb{R}^2$. Assume that the subspace here is a line vector $a$, characterized by $2$ x $1$ in size. A point $b$ is projecting onto the subspace $a$ at $p$. Then the point $p$ can be calculated as follow:

$$ p = ax = \frac{aa^T}{a^Ta}b $$

(This is the part that I am very unsure of: What does $x$ actually represent?) In this equation, $x$ represents the multiplication factor of $a$. It tells you how much $a$ is needed in order to find the exact location of $p$.

The meaning of $x$ here can easily be generalized in $\mathbb{R}^n$. $A$ is a subspace where the point $b$ is projected onto. In $\mathbb{R}^n$, $x$ is a vector representing how much each of the columns in $A$ is needed in order to find the point $p$.

When there are multiple $b$'s, it is often useful to calculate the projection matrix $P$ for convenience.

$P = \frac{aa^T}{a^Ta}$

because $p = Pb$.

LEAST SQUARE APPROXIMATION

In $\mathbb{R}^2$, least square approximation is for finding a (regression) line that best fits multiple datapoints.

In the previous case of projection on subspace, the vector $a$ is a known subspace which $b$ is projected onto. However, in least square approximation, the regression line (which datapoints are projected onto) is unknown parameters instead. The regression line is also not necessarily a subspace (it usually does not pass through origin).

The role of $x$ is also different between projection onto subspace and least square approximation. In projection onto subspace, $x$ is a multiplication factor for the subspace $a$. However, in least square approximation, $x$ is the intercept and the slope of the regression line, which the datapoints are projected onto.

Projection matrix $P$ is useful in the previous topic (projection onto subspace) but not very useful in the current topic (least square approximation).

Even in $\mathbb{R}^2$, $A$ is a $m$ x 2 matrix, rather than a simple subspace vector in the previous topic. The goal of least square is to calculate $x$ (regression line):

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

b represents the the value of datapoints on the $y$-axis. The first column of $A$ represents intercept (usually with the value of $1$), while the second column of $A$ represents the value of datapoints on the $x$-axis.

I know that I am poor in terminology in the above discussion, but I would appreciate if anyone can point out any serious mistakes in my understanding. One thing I found extremely confusing is that the same method is used for both topics, while $a$ (or $A$), $b$, and $x$ mean totally different things in the two topics.

Answer 1

Notation is a culprit here. Regression line fitting is in fact a projection onto a linear subspace but perhaps not the one you would first think of. Even if you fit to a cubic polynomial you will be dealing with a projection onto a linear subspace! Let us stick to regression lines and let $Y=\left( \begin{matrix} y_1 & y_2& \cdots& y_n \end{matrix} \right)^T$, $M=\left( \begin{matrix} x_1 & x_2 & \cdots & x_n\\ 1 & 1 & \cdots & 1\end{matrix}\right)^T$ and $u=\left( \begin{matrix} a \\ b \end{matrix}\right)$. We want to estimate $u$ (i.e. $a$ and $b$) so as to minimize the sum $\sum_i (y_i - ax_i - b)^2$ or equivalently the square distance $\|Y-Mu\|^2=\langle Y-Mu,Y-Mu\rangle$ in ${\mathbb R}^n$ (note that this distance and scalar product is in $n$ dimensional space and not in two dimensions). A minimum is attained when $M^T M u = M^T Y$ which leads to a unique solution whenever $M^T M$ is invertible. You may in fact do a least square fit to any linear combination of (non-linear) functions, say $ae^x+b\sin(x)$. It is linearity w.r.t. $a$ and $b$ (the fitting constants), not $x$ (the variable), which is important.

Answer 2

It turns out that the roles of $A$, $\mathbf x$ and $\mathbf b$ are the same in both contexts, but I think I see the source of your confusion. Since we’re trying to find the “best” line, it appears that you’re trying to relate that process to the previous lesson on (orthogonal) projection onto a line—a one-dimensional space—but that’s not what’s going in least-squares fitting. In that, we’re projecting onto a two-dimensional subspace of an $N$-dimensional space, where $N$ is the size of the data set, so you need to relate it to the discussion of projection in higher dimensions instead.

To review the least-squares construction, suppose that all of the given data points were colinear. Then there would be some $C$ and $D$ such that $$\begin{align}C+Dx_1&=y_1\\C+Dx_2&=y_2\\\vdots\\C+Dx_N&=y_N.\end{align}$$ In matrix form, this system is $$A\mathbf x=\begin{bmatrix}1&x_1\\1&x_2\\\vdots&\vdots\\1&x_N\end{bmatrix}\begin{bmatrix}C\\D\end{bmatrix}=\begin{bmatrix}y_1\\y_2\\\vdots\\y_N\end{bmatrix}.$$ Note that the vector $\mathbf x=[C,D]^T$ in this equation lies in a different copy of $\mathbb R^2$ than the data points and the line that we’re trying to find, but there’s a one-to-one mapping between it and all non-vertical lines in the data space.

Recall that in a matrix-vector product $A\mathbf x$, the result is a linear combination of the columns of $A$, i.e., it lies in their span. Thus, for the data points to be colinear, the vector $\mathbf b=(y_1,y_2,\dots,y_N)^T$ must be an element of the space $W$ spanned by the columns of $A$, i.e., in the span of $\mathbf1$ (the vector of all ones) and $\mathbf w=(x_1,x_2,\dots,x_N)^T$. You can interpret the vectors in this space as sets of $y$-values that, when paired with the corresponding $x$-values from the points in the data set, produce a set of colinear points in the data space.

Unfortunately, $\mathbf b\notin W$, or we wouldn’t be doing this in the first place. We know that for all $\hat{\mathbf b}\in W$, $A\mathbf x=\hat{\mathbf b}$ does have a solution, so we look for the element $\hat{\mathbf b}$ of $W$ that’s closest to $\mathbf b$. The distance between them is $((\hat b_1-y_1)^2+(\hat b_2-y_2)^2+\cdots+(\hat b_N-y_N)^2)^{\frac12}$, so we’re really minimizing the sum of squares of differences in $y$-values in the data space. As we learned in previous lessons, the nearest element of $W$ to a vector $\mathbf b$ is its (orthogonal) projection onto $W$, so finding the parameters $C$ and $D$ of the best-fit line is equivalent to finding values such that $C\mathbf 1+D\mathbf w$ equals the projection of $\mathbf b$ onto $W$. This is exactly what the equation $A^TA\hat{\mathbf x}=A^T\mathbf b$ from the previous lesson on projection onto a multidimensional space does.

Least-squares fitting is an instance of a widely-applicable technique of solving problems via orthogonal projection. For instance, one can solve resistive electrical networks (which are really graph-flow problems) by projecting the vector of branch currents that would exist if there were no voltage drops onto the space of graph cycles. The technique is applicable in many other domains as well.