Cholesky Decomposition for Least Squares Method
Algorithm
Given $A \in \mathbb{C}^{m \times n}$ and vector $\mathbf{b} \in \mathbb{C}^{m}$ such that $\text{rank} A = n$ and the least-squares solution of $A \mathbf{x} = \mathbf{b}$ is denoted as $\mathbf{x}_{\ast}$.
Step 1.
Multiply both sides of the given equation by $A^{\ast}$ to form the normal equation $A^{\ast} A \mathbf{x} = A^{\ast} \mathbf{b}$.
The solution of the normal equation is the least-squares solution of the original equation, hence, solving for $\mathbf{x}$ fulfills our requirement.
Step 2.
Calculate $\mathbf{y} := A^{\ast} \mathbf{b}$ to obtain $A^{\ast} A \mathbf{x} = \mathbf{y}$.
Step 3. Cholesky Decomposition
Find a lower triangular matrix $L$ that satisfies $A^{\ast} A = L L^{\ast}$ to derive $L L^{\ast} \mathbf{x} = \mathbf{y}$.
Step 4. Forward Substitution
Given $L L^{\ast} \mathbf{x} = \mathbf{y}$, assume $L^{\ast} \mathbf{x} : = \mathbf{w}$ then $L \mathbf{w} = \mathbf{y}$
Since $L$ is a lower triangular matrix, the solution of the equation for $\mathbf{w}$ is found using the forward substitution method.
Step 5. Backward Substitution
Having found $\mathbf{w}$ and with $L^{\ast}$ being an upper triangular matrix, the solution of the equation $L^{\ast} \mathbf{x} = \mathbf{w}$ for $\mathbf{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 $\mathbf{v} \ne \mathbb{0}$,
$$ \mathbf{v}^{\ast} A^{\ast} A \mathbf{v} = (A \mathbf{v})^{\ast} A \mathbf{v} = | A \mathbf{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 $\mathbf{v} \ne \mathbb{0}$ satisfying $A^{\ast} A \mathbf{v} = \mathbb{0}$. Multiplying both sides of the equation by $\mathbf{v}^{\ast}$ on the left yields $| A \mathbf{v} |^2 = 0$, and from the definition of norm, $A \mathbf{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 $\mathbf{v} \ne \mathbb{0}$ satisfying $A \mathbf{v} = \mathbb{0}$.
Multiplying both sides of the equation by $A^{\ast}$ on the left yields $A^{\ast} A \mathbf{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 $$
■