This is a technique for computing coefficients for Multivariate Linear Regression. The problem is also called Ordinary Least Square Regression, and Normal Equation is an approach for solving it.

This was discovered by Carl Friedrich Gauss in 1809. It finds the regression coefficients analytically. It's a one-step learning algorithm as opposed to Gradient Descent.

In Multivariate Linear Regression Problem suppose we have m training examples (x_i, y_i) each with n features, x_i = [x_i1, ..., x_in] ∈ Rⁿ. We can put all such x_i as rows of a matrix X, sometimes called the Design Matrix, and the observed values y = [y₁, …, y_m] ∈ R^m. Thus, we expressed our multivariate linear regression problem in the matrix form Xw = y. Note that there's usually additional feature x_i0 = 1 to incorporate the intercept term, so x_i∈Rⁿ⁺¹ .

Thus, we have a system Xw = y. Now, how do we solve w, and if there's no solution, how do we find the best possible w?

Let w be the best fit solution to Xw ≈ y. We will try to minimize the error e = y−Xw also called residuals. We take the square of this error, so the objective is to minimize J(w)=∥e∥²=∥y−Xw∥² over w. So, our problem is to find w = arg min J(w) = arg min ∥y−Xw∥². Let's expand J(w) = y^Ty − 2w^TX^Ty + w^TX^TXw. Now to minimize J(w) with respect to w we set:

∂J(w)/∂w = −2X^Ty + 2X^TXw = 0

Or, X^TXw = X^Ty

Or, w = (X^TX)⁻¹X^Ty

The equation, X^TXw = X^Ty, is known as the Normal Equation that is used to solve the regression coefficients w in Multivariate Linear Regression.

QUESTION I: How to compute the Normal Equations for Polynomial Regression?

QUESTION II: Could we apply Iterative Method to solve the Normal Equations?