<s>[INST] 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?
 [/INST] 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}.
$$
</s>