Is there a nice way to interpret this matrix equation that comes up in the context of least squares So I am working on this problem with fitting a second degree polynomial of the form $y=a_1x^2+a_2x+a_3$ to four points using least squares. One of the parts of the problem is to write out the matrix equation that describes the least squares problem. Basically we have the equation
$$\begin{bmatrix}
x_1^2 & x_1 & 1 \\
x_2^2 & x_2 & 1 \\
x_3^2 & x_3 & 1 \\
x_4^2 & x_4 & 1
\end{bmatrix}
\begin{bmatrix}
a_1 \\
a_2 \\
a_3
\end{bmatrix}
=
\begin{bmatrix}
y_1 \\
y_2 \\
y_3 \\
y_4
\end{bmatrix}$$
Let's call the matrix $A$ so that the problem is $A\mathbf{a}=\mathbf{y}$. Then the least squares equation is $A^TA\mathbf{a}=A^T\mathbf{y}$. If we write that out explicitly we get
$$\begin{bmatrix}
\sum_{i=1}^4x_i^4 & \sum_{i=1}^4x_i^3 & \sum_{i=1}^4x_i^2 \\
\sum_{i=1}^4x_i^3 & \sum_{i=1}^4x_i^2 & \sum_{i=1}^4x_i \\
\sum_{i=1}^4x_i^2 & \sum_{i=1}^4x_i & 4
\end{bmatrix}
\begin{bmatrix}
a_1 \\
a_2 \\
a_3
\end{bmatrix}
=
\begin{bmatrix}
\sum_{i=1}^4x_i^2y_i \\
\sum_{i=1}^4x_iy_i \\
\sum_{i=1}^4y_i
\end{bmatrix}
$$
This new matrix makes no intuitive sense to me whatsoever but is striking. Why do we care about, for instance, the sum of the 4th powers of $x_i$? Is there a way to interpret why this is the way it is, maybe in terms of calculus or something else?
 A: The normal equations for the least squares problem $Ax = b$ is given by $A^T Ax = A^T b$, as you clearly already know. It's not really the fourth powers of $x_i$ that are significant, but rather the matrix $A^T A$ that is significant, from a purely linear algebra point of view. One way to look at the matrix $A^T A$ is that it reduces the overdetermined problem $Ax = b$ (notice that you have three variables but four equations) down to an invertible problem, by taking each output $Ax$ and then dotting it by the columns of $A$, giving you precisely $A^T Ax$. Ultimately the least squares problem can be phrased as:

Given $Ax = b$, find $\hat{b}$ in the column space of $A$ closest to $b$, and then find $\hat{x}$ such that $A\hat{x} = \hat{b}$. We call $\hat{x}$ a least squares solution.

There is, however, a calculus way of looking at it. From an optimization point of view, we can say that $\hat{x}$ is a least squares solution if $\|Ax - b\|_2^2 = (Ax - b)^T (Ax - b)$ is minimized. We can calculate when this is minimized by taking the derivative in $x$. Let $f(x) = \|Ax - b\|_2^2$. Then
\begin{align}
Df_x(y) & = \lim_{h \rightarrow 0} \frac{1}{h} (f(x+hy) - f(x)) \\
& = \lim_{h \rightarrow 0} \frac{1}{h} \left( \|Ax - b\|_2^2 + h(Ay)^T (Ax - b) + h(Ax - b)^T Ay - \|Ax - b\|_2^2 \right) \\
& = (Ay)^T (Ax - b) + (Ax - b)^T Ay \\
& = y^T (A^T Ax - A^T b) + (A^T Ax - A^T b)^T y
\end{align}
We set this derivative to zero to solve for the minimum; this can only be zero for every choice of $y$ if $A^T Ax - A^T b = 0$. Thus we have derived the normal equations.
A: To augment the insightful post of @Christopher A. Wong, we offer two other perspectives.
First, why do we form the normal equations? To form a consistent linear system. Typically a linear algebra course begins with problems like
$$
\mathbf{A} a - y = 0.
$$
We learn Gaussian elimination, $\mathbf{L}\mathbf{U}$ decomposition, etc. Then the course presents problem where the above equation has no solution. We generalize the concept of a solution and ask that $r(x) = \mathbf{A} a - y$ be made a small as possible. To discuss the size of a vector, we need a norm. The $2-$norm is the overwhelming favorite and this leads to the method of least squares to minimize $\lVert r\rVert_{2}^{2}.$
Rewrite the problem as
$$
\mathbf{A} a = y.
$$
There is no solution; the vector $y$ is not in the range space of $\mathbf{A}$. The first solution attempt is to craft a consistent problem with the same solution. Multiply both sides of the equality by $\mathbf{A}^{*}$ to create the normal equations:
$$
  \mathbf{A}^{*} \left( \mathbf{A}a \right) =  \mathbf{A}^{*}\left( y \right).
$$
The parentheses emphasize the fact that we have a consistent linear system because the data vector $\mathbf{A}^{*}\left( y \right)$ in certainly in the column space of $\mathbf{A}^{*}$.
Second, look at the problem in terms of column vectors.
$$
\begin{align}
  \mathbf{A} a &= y \\
  \left[
    \begin{array}{cccc}
      \mathbf{1} & x & x^{2} & \dots & x^{d}
    \end{array}
  \right]
  \left[
    \begin{array}{cccc}
      a_{0} \\
      a_{1} \\
      \vdots \\
      a_{d} 
    \end{array}
  \right]
&=
  \left[
    \begin{array}{c}
      y
    \end{array}
  \right]
\end{align}
$$
The normal equations take the form
$$
\begin{align}
  \mathbf{A}^{*}\mathbf{A} a &= \mathbf{A}^{*}y \\
  \left[
    \begin{array}{cccc}
      \mathbf{1} \cdot \mathbf{1} & \mathbf{1} \cdot x & \mathbf{1} \cdot x^{2} & \dots & \mathbf{1} \cdot x^{d} \\
      x \cdot \mathbf{1} & x \cdot x & x \cdot x^{2} & \dots & x \cdot x^{d} \\
      \vdots & \vdots & \vdots && \vdots \\
      x^{d} \cdot \mathbf{1} & x^{d} \cdot x & x^{d} \cdot x^{2} & \dots & x^{d} \cdot x^{d} \\
    \end{array}
  \right]
  \left[
    \begin{array}{c}
      a_{0} \\
      a_{1} \\
      \vdots \\
      a_{d} 
    \end{array}
  \right]
&=
  \left[
    \begin{array}{r}
      \mathbf{1} \cdot y \\
        x     \cdot y \\
        x^{2} \cdot y \\
      \vdots\quad \\
       x^{d} \cdot y
    \end{array}
  \right]
\end{align}.
$$
