[Linear Algebra] Normal Equation with Not Invertible Matrix

What if $C = A^T A$ is NOT Invertible?

• Given $A^T A \textbf{x} = A^T \textbf{b}$, what if $C = A^T A$ is NOT invertible?

• If matrix $C$ is not invertible, $A^T A \textbf{x} = A^T \textbf{b}$ will have either no solution or infinitely many solutions

• However, the solution always exist for normal equation, and thus infinitely many solutions exist

  • we can always make projection $A^T \textbf{b}$ to $\textrm{Col} C$

• When $C = A^T A$ is NOT invertible?

  • if and only if the $\textrm{Col} A$ are linearly dependent

• However, $C = A^T A$ is usually invertible

  • amount of data >> feature dimension