# Relationship between projections and least squares

To preface, this is a fairly basic linear algebra question, but I've been unsuccessful in finding a similar question on this site.

In the method of least squares for linear regression that is discussed in linear algebra, where the line is in the form of $$y=Cx+D$$ with $$m$$ data points, we set up an $$m$$ x 2 matrix ($$A$$) with the first column being the recorded x values and the second column being 1s multiplied by the vector with $$C$$ and $$D$$ as components ($$X$$) to get a column vector of the recorded y values ($$b$$). So $$AX=b$$.

In general, to solve these systems, since it is unlikely that all of the y values are in the column space of $$A$$, we typically solve the system $$A^TAX=A^Tb$$ instead, which is guaranteed to have a solution. This is where I am a bit confused. In the $$A^TAX=A^Tb$$ system, $$AX$$ is the projection, because the vector $$AX$$ minimizes the orthogonal distance between $$AX$$ and $$b$$. However, in linear regression, the squared vertical distance is minimized, not the orthogonal distance. Yet, linear regression still uses the $$A^TAX=A^Tb$$ method of solving the equations and clearly relies on the notion of projections. What accounts for the difference where projections minimize orthogonal distance and linear regression minimizes (squared) vertical distances?

Thanks.

Actually, there isn't any difference. The problem is set up so that minimizing the (sum of the) squared vertical distance is the same as minimizing the (Euclidean, what I guess you call "orthogonal") distance between two vectors. Let's say we are given $$m$$ points $$(x_1,y_1), \dots, (x_m,y_m)$$ and we want to find $$C,D$$ such that $$y = Cx + D$$ is the "best fit" for those points in terms of squared vertical distance. That is, we want to find $$C,D$$ such that the expression

$$\sum_{i=1}^m \left( Cx_i + D - y_i \right)^2$$

is minimal. If you set up a matrix and column vectors

$$A = \begin{pmatrix} x_1 & 1 \\ \vdots & \vdots \\ x_m & 1 \end{pmatrix}, \,\,\, b = \begin{pmatrix} y_1 \\ \vdots \\ y_m \end{pmatrix},\,\,X = \begin{pmatrix} C \\ D \end{pmatrix}$$

then

$$AX - b = \begin{pmatrix} Cx_1 + D \\ \vdots \\ Cx_m + D \end{pmatrix} - \begin{pmatrix} y_1 \\ \vdots \\ y_m \end{pmatrix} = \begin{pmatrix} Cx_1 + D - y_1 \\ \vdots \\ Cx_m + D - y_m \end{pmatrix}.$$

In terms of $$A,X,b$$, you want to find $$X$$ that minimizes $$\| AX - b \|^2$$. In other words, the vector $$AX$$ should minimize the distance to $$b$$ among all vectors of the form $$Ax$$. This implies that $$AX$$ is the orthogonal projection of $$b$$ onto the column space of $$A$$, so you can solve this problem using orthogonal projections.

• That's correct. And an orthogonal projection of the datapoints $a_i$ onto a subspace is simply PCA. The mathematical difference however is striking. While least squares is an easy convex program that can be solved explicitly, PCA is non-convex and can be solved relatively easily using SVD only in the very native model. Trying to change anything there such as adding an intercept to the model or penalties excludes the option to use SVD and we are left with a hard non-convex problem. Aug 6, 2020 at 10:17