Normal Equation and non-invertibility(CS229)

Normal Equation: $\mathbf\Theta=(\mathbf{X^\top}\mathbf{X})^{-1}\mathbf{X^\top}\mathbf{y}$

If $(\mathbf{X^\top}\mathbf{X})^{-1}$ is non-invertible(singular)

Reasons of singular matrix:

  • redundant features ($x^{(i)}$s are linearly dependent)

    • for example, $x_1$ is size in feet square, meanwhile, $x_2$ is size in meter square. For all data, $x_1 = (3.28)^2x_2$ will lead to a non-invertible $(\mathbf{X^\top}\mathbf{X})^{-1}$
  • Too many features, i.e. $m\lt n$

    • We have $m$ conditions(data) but if there were $n$ unknowns and $n$ is greater than $m$, the solution can not be solve.
    • To solve the problem, delete some features, or use regularization.