# Proof of correctness of normal equation

I was taking an online course and saw linear regression being by gradient descent The intuition behind why the method would work seemed plausible.

I tried understanding normal equation as to why setting individual partial derivates to 0 and solving the equations give the optimal values of theta, but that didn't ring a bell.

1. Why setting partial derivatives to zero, and solving the equations gives optimal value of theta.
The minimum is determined by calculating the partial derivatives of S(β1,β2) with respect to β1 and β2 and setting them to zero
is still dicey to me.
Why would it work. Why would it give the values of β1 and β2 for minimized cost function.
2. If we have multiple local optima, would the normal equation method give the global optima? If so, why?

This is really just a matter of using standard results in multivariate calculus. In the ordinary least-squares (OLS) problem, the objective function being minimised is:

$$F(\boldsymbol{\beta}) = ||\mathbf{y} - \mathbf{x} \boldsymbol{\beta} ||^2.$$

The first and second derivatives (gradiant and Hessian) are:

\begin{equation} \begin{aligned} \nabla F(\boldsymbol{\beta}) &= 2 [ (\mathbf{x}^\text{T} \mathbf{x}) \boldsymbol{\beta} - (\mathbf{x}^\text{T} \mathbf{y}) ], \\[6pt] \nabla^2 F(\boldsymbol{\beta}) &= 2 (\mathbf{x}^\text{T} \mathbf{x}). \\[6pt] \end{aligned} \end{equation}

The Gramian matrix $$\mathbf{x}^\text{T} \mathbf{x}$$ is non-negative definite. So long as the columns of the design matrix $$\mathbb{x}$$ are linearly independent (which is generally the case in regression problems) it is positive definite. In the latter case the objective function $$F$$ is strictly convex, which means that it has a global minimising value at its unique critical point, which is found by solving:

$$\nabla F(\hat{\boldsymbol{\beta}}) = \mathbf{0} \quad \quad \implies \quad \quad \hat{\boldsymbol{\beta}} = (\mathbf{x}^\text{T} \mathbf{x})^{-1} (\mathbf{x}^\text{T} \mathbf{y}).$$

In the least-squares problem, linear independence of the columns of the design matrix $$\mathbb{x}$$ ensures that we do not have multiple optima. In the case where we have linearly dependence in the design matrix, this means that there are excess variables that give "ridges" of minimising values, and the parameters are not identified. This is usually dealt with by removing columns of the design matrix until linear independence is obtained.

Why setting partial derivatives to zero, and solving the equations gives optimal value of theta. I also went through the following link. The part about The minimum is determined by calculating the partial derivatives of S(β1,β2) with respect to β1 and β2 and setting them to zero is still dicey to me. Why would it work. Why would it give the values of β1 and β2 for minimized cost function.

From calculus, if we set the gradient to zero we arrive at an extremum (see, e.g, here). Hence, setting the partial derivatives to zero w.r.t. the $\beta_i$'s is generally a good approach to optimise over some objective function.

If we have multiple local optima, would the normal equation method give the global optima? If so, why?

We do not have multiple local optima. The loss function for the linear regression problem is quadratic and (strictly) convex, so there exists only one, unique, global optimum. Hence, by the properties of the objective function the normal equations will yield that global optimum.

• Multivariate linear regression would "always" have a convex plot?(i.e. only one global minima) Not only for 2 variables, and no matter what the data set is. For any variables, for any data points, if we use linear regression, then the cost function will have only global minima? Jun 23, 2017 at 5:08
• Why are you so surprised? The cost function is a quadratic polynomial with a positive sign on the highest term, so it is strictly convex and admits only one global extremum (by convexity, that will be a minimum). This holds both in the multivariate and scalar case, and, assuming the matrix $X$ is of full column rank, for all data. Jun 24, 2017 at 8:38

I just want to complement and integrate the very good answers provided above, just to provide a different point of view and provide a different intuitive understanding of the mathematical nature of the solution.

Given an OLS problem like the typical $$y=X \beta + \epsilon$$ where y is a $$Tx1$$ vector, $$X$$ is a $$TxN$$ matrix where the number of samples is T and the number of regressors is N, $$\beta$$ and $$\epsilon$$ are $$Nx1$$ vectors, you want to minimize the sum of squared errors. The problem can be seen as the resolution of an overdetermined set of T equations (each corresponding to a row of the precious representation): each equation is $$y_{t}=x_{t} \beta$$ for each row t (notice that $$x_{t}$$ is now a vector representing the t-th row of the matrix $$X$$, $$y_{t}$$ is a scalar). Since the system is overdetermined for most real-world applications where $$y$$ is not a linear combination of the columns of $$X$$, then there exists no exact solutions to this set of equations. However the best proxy for a solution for an overdetermined system is to choose the minimum norm solution, which is obtained by setting $$\beta$$ equal to the product of the pseudoinverse of the matrix $$X$$ and the vector of dependent variable $$y$$, where the pseudoinverse of $$X$$ is indeed $$(X^{T}X)^{-1}X^{T}$$. This is indeed the solution to the system that minimizes the squared norm of the vector $$\epsilon = y-X\beta$$. This is why you have that formula for the OLS estimator.

This is a just different way of interpreting the OLS estimator compared to the usual minimization of squared error or maximization of the corresponding likelihood. Just a different way of looking at the same mathematical problem.

I also add this concise source

• This is a very confusing post because it switches between using "underdetermined" and "overdetermined" inexplicably. Taken literally, the set of $T$ equations "$y_t=X_t\beta+\epsilon_t$" (notice there should be no subscripts on the $\beta$) involves $T+N$ variables $\beta_i$ and $\epsilon_t$ and therefore is underdetermined, not overdetermined. The set of equations $y_t=X_t\beta_t$ involves just $N$ variables and therefore, provided $T\gt N,$ indeed is overdetermined: but the relevance of this point of view to the original problem is unclear.
– whuber
Aug 29, 2019 at 12:58
• @whuber oh my god just a typo, sorry for this, it was 4 am European time.. I think it may be an explanation for the typo. It was evident it was a typo..
– Fr1
Aug 29, 2019 at 13:02
• OK, but now it seems you are consistently using "overdetermined" to mean underdetermined. If not, then some explanation of your meaning is required. Indeed, there always exists at least one exact solution to your system of equations: set $\beta$ to be any $N$-vector and for each $t$ between $1$ and $T,$ define $\epsilon_t = y_t - x_t\beta.$
– whuber
Aug 29, 2019 at 13:10
• I apologize for the edited typo and thank @whuber for noticing it. I also provided more clarity on the system of equations, that however to me is very trivial to see. I remember everyone that you are free to edit my answers, if you see evident typos.
– Fr1
Aug 29, 2019 at 13:14
• I would have no idea how to fix your post because it doesn't seem to be a matter of typos, but of some kind of miscommunication about what you really mean by "$y_t=x_t\beta+\epsilon_t.$" I have explained my interpretation, but your edits don't address that.
– whuber
Aug 29, 2019 at 13:16