Regression using Linear Algebra (for univariate inputs)

Regression aims to find the best fit of a function from a set of given data points. Suppose we want to fit $n$ data points to $y$ , where $y$ is a function of $x$ .

y = a_{0} + a_{1} x + a_{2} x^{2} \dots a_{d} x^{d}

We have $n$ data points

X = (\begin{matrix} x_{0} \\ x_{1} \\ ⋮ \\ x_{n} \end{matrix}) Y = (\begin{matrix} y_{0} \\ y_{1} \\ ⋮ \\ y_{n} \end{matrix})

Vandermonde Matrix

A Vandermonde Matrix is defined as such. It describes a polynomial function of degree $d$ . #Vandermonde_Matrix

\tilde{X} = V (x_{0}, x_{1}, x_{2}, \dots x_{n}) = (\begin{matrix} 1 & x_{0} & x_{0}^{2} & \dots & x_{0}^{d} \\ 1 & x_{1} & x_{1}^{2} & \dots & x_{1}^{d} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & x_{n} & x_{n}^{2} & \dots & x_{n}^{d} \end{matrix})

$y$ can be re-expressed as

Y = \tilde{X} A

where

A = (\begin{matrix} a_{0} \\ a_{1} \\ a_{2} \\ ⋮ \\ a_{d} \end{matrix})

To solve for $A$ , $\hat{X}$ typically does not have an inverse as $d \neq n + 1$ . However, we can multiply the Vandermonde matrix by its transpose, thus "squaring" it, which allows us to solve for its inverse.

\begin{aligned} {\tilde{X}}^{T} Y & = ({\tilde{X}}^{T} \tilde{X}) A \\ A & = ({\tilde{X}}^{T} \tilde{X})^{- 1} {\tilde{X}}^{T} Y \end{aligned}