Cholesky Decomposition for Least Squares Method
Algorithm
Given $A \in \mathbb{C}^{m \times n}$ and vector $\mathbb{b} \in \mathbb{C}^{m}$ such that $\text{rank} A = n$ and the least-squares solution of $A \mathbb{x} = \mathbb{b}$ is denoted as $\mathbb{x}_{\ast}$.
Step 1.
Multiply both sides of the given equation by $A^{\ast}$ to form the normal equation $A^{\ast} A \mathbb{x} = A^{\ast} \mathbb{b}$.
The solution of the normal equation is the least-squares solution of the original equation, hence, solving for $\mathbb{x}$ fulfills our requirement.
Step 2.
Calculate $\mathbb{y} := A^{\ast} \mathbb{b}$ to obtain $A^{\ast} A \mathbb{x} = \mathbb{y}$.
Step 3. Cholesky Decomposition
Find a lower triangular matrix $L$ that satisfies $A^{\ast} A = L L^{\ast}$ to derive $L L^{\ast} \mathbb{x} = \mathbb{y}$.
Step 4. Forward Substitution
Given $L L^{\ast} \mathbb{x} = \mathbb{y}$, assume $L^{\ast} \mathbb{x} : = \mathbb{w}$ then $L \mathbb{w} = \mathbb{y}$
Since $L$ is a lower triangular matrix, the solution of the equation for $\mathbb{w}$ is found using the forward substitution method.
Step 5. Backward Substitution
Having found $\mathbb{w}$ and with $L^{\ast}$ being an upper triangular matrix, the solution of the equation $L^{\ast} \mathbb{x} = \mathbb{w}$ for $\mathbb{x}$ is found using the backward substitution method.
Explanation
The Cholesky decomposition originally had a strong precondition that the matrix to be decomposed must be a positive definite matrix. The key in this method lies in the trick of constructing the normal equation, which forcibly satisfies that stringent condition. Of course, this trick requires a guarantee that $A^{\ast} A$ is positive definite, and proving this is not too difficult.
Theorem
For the matrix $A \in \mathbb{C}^{m \times n} (m \ge n)$, $A^{\ast} A > 0 \iff \text{rank} A = n$
Proof
For any vector $\mathbb{v} \ne \mathbb{0}$,
$$ \mathbb{v}^{\ast} A^{\ast} A \mathbb{v} = (A \mathbb{v})^{\ast} A \mathbb{v} = | A \mathbb{v} |^{2} \ge 0 $$
thus, $A^{\ast} A \ge 0$. Assuming that the inverse of $A^{\ast} A$ does not exist implies the existence of $\mathbb{v} \ne \mathbb{0}$ satisfying $A^{\ast} A \mathbb{v} = \mathbb{0}$. Multiplying both sides of the equation by $\mathbb{v}^{\ast}$ on the left yields $| A \mathbb{v} |^2 = 0$, and from the definition of norm, $A \mathbb{v} = 0$. This means that the column vectors of $A$ are linearly dependent, thus $\text{rank} A < n$.
Conversely, assuming $\text{rank} A < n$ implies the existence of $\mathbb{v} \ne \mathbb{0}$ satisfying $A \mathbb{v} = \mathbb{0}$.
Multiplying both sides of the equation by $A^{\ast}$ on the left yields $A^{\ast} A \mathbb{v} = \mathbb{0}$, and $A^{\ast} A$ does not have an inverse. Since $A^{\ast}A \ge 0$,
$$ A^{\ast} A \ne 0 \iff \text{rank} A = n $$
therefore,
$$ A^{\ast} A > 0 \iff \text{rank} A = n $$
■