linear least squares regression

Least Squares Regression

For an overdetermined system $Ax=b$ where $A\in {\mathbb{R}}^{m\times n}$ with $m>n$, least squares finds the solution $\tilde{x}$ that minimizes the squared error:

$$\underset{x}{\min }\Vert Ax-b{\Vert }_2^2$$

One issue with this approach are outliers (i.e. when the distribution is not gaussian, which can significantly skew the solution → robust regression techniques.

Solution via SVD

Using the SVD $A=U\Sigma V^T$, the solution is given by:

$$\begin{array}{rl}\tilde{x}& =A^{+}b\\ & =V{\Sigma }^{-1}{U}^{T}b\end{array}$$

where $A^{+}$ is the pseudo inverse.

Geometric Interpretation

The solution $\tilde{x}$ gives us coefficients that define a hyperplane which:
Minimizes the sum of squared vertical distances to the data points
Projects $b$ onto the column space of $A$
Makes the residual $r=b-A\tilde{x}$ orthogonal to the column space of $A$

Normal Equations

The normal equations for a least squares problem $Ax\approx b$ are:

$$\begin{array}{rl}{A}^{T}Ax& =A^{T}b\\ \bar{x}& =(A^{T}A{)}^{-1}{A}^{T}b\end{array}$$

where $A\in {\mathbb{R}}^{m\times n}$ is the data matrix, $b\in {\mathbb{R}}^m$ is the target vector, and $x\in {\mathbb{R}}^n$ is the solution vector we seek.

The name “normal” comes from the fact that $A^T(b-Ax)=0$ implies the residual $(b-Ax)$ is orthogonal (or normal) to the column space of $A$.

Simple Linear Regression

For fitting a line through the origin $y=mx$ to points $(x_i,y_i)$, we have:

$$A=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_m\end{array}\right],\beta =[m],y=\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_m\end{array}\right]$$

Applying the normal equations to this simplified case:

$$\begin{array}{rl}\tilde{m}& =(A^{T}A{)}^{-1}{A}^{T}y\\ & =\frac{A^{T}y}{A^{T}A}=\frac{A^{T}y}{\Vert A{\Vert }_2^2}\end{array}$$

where $A^{T}y$ is the dot product – the sum of coordinate-wise products (correlation matrix) – and $\Vert A{\Vert }_2^2$ normalizes by the squared magnitudes of the input.
To add an offset, we can append a column of ones to $A$ and solve for $[m,c]$.