Machine Learning: Closed form of Linear Regression

A follow up from the previous Machine Learning Post: Machine Learning: Linear Regression

(Credit: Thanks to Stanford University for their online course and Prof. Andrew Ng for great materials and discussions. All credit goes to them. I am merely posting my thoughts for future references)

In linear regressions, we want to find \(\theta\) such that the least squares function \(J(\theta) = \frac{1}{2} \sum_i (h_{\theta}(x_i) - y_i)^2) \) is minimized. One of the way to go is by implementing the gradient descent algorithm:
for each j:
     update \(\theta_j = \theta - \alpha \frac{\partial}{\partial \theta_j} J(\theta) \)

a bit of matrix: LUP Decomposition

Scratch note:

Given system of linear equation \(Ax = b\), solve for \(x\).

One of the method to solve this classic linear algebra is described here called "LUP decomposition". LUP is itself an abbreviation for Lower, Upper, and Permutation Matrixes. The idea is that in a Gauss Elimination process, we are actually trying to transform a matrix into its row equivalent upper or lower triangular matrix. The method here owes to the insight from Gauss Elimination.

Recursively:

1. We swap the first row in \(A\) with another row such that the first element in \(A\) is not zero. Call this permutation \(Q\), and hence the resulting matrix \(QA\).
2. Rewrite QA as
\( \left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)

3. Let \(P =
\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)
Q
\)
Where \(P'(A-vw^T/a_{k1})=L'U'\)
Hence we have
\(PA =

\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)

\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)

which simplifies to
\(PA =
\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & L'
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & U'
\end{array}
\right)
\)
Or \(PA = LU\)