Cholesky QR Algorithm

Posted June 21, 2024

Idea of Cholesky QR

Let $X \in \mathbb{R}^{ m \times n }$ with $m \ge n$ of full column rank. The Cholesky QR (CholQR) algorithm computes a QR factorization of $X$ by

forming the Gram matrix $A = X^{T} X$,
computing its Cholesky factorization $A = R^{T} R$, and
finally finding the $Q$ factor by $Q = XR^{-1}$.

Here, the requirement of full column rank ensure the Cholesky factorization
succeed. Let $X=U\varSigma V^{T}$ be a singular value decomposition, where $U\in\mathbb{R}^{m\times n}$, $\Sigma\in\mathbb{R}^{n\times n}$ and $V\in\mathbb{R}^{n\times n}$. Full column rank implies $\sigma_{ii} > 0$, which is equivalent as $\sigma_{i}(X^{T} X) > 0$ since $X^{T} X = V \varSigma^{2} V^{T}$.

This algorithm is ideal in high performance computing.

Its complexity is $2mn^{2}$, which is the same as the MGS.
The first and third steps can be done in parallel BLAS 3 way, which makes it very efficient.
The second step, which can only perform sequentially, requires only $O(n^{3})$ flops compare to $O(mn^{2})$ flops for the other two steps.

Drawback and solutions to the instability

However, CholQR is NOT stable. We can provide several heuristic observations. Suppose $\kappa_{2}(X) > u^{-1/2}$, then $\kappa_{2}(X^{T} X) > u^{-1}$ which can result in loss of positive definiteness.

Even though we are lucky enough to be able to form $R$, ill conditioned $R$ and $X$ can still result in a large deviation from orthogonality. Stathopoulos and Wu proved that $|| Q^{T} Q-I || \le O(\kappa_{2}(X)^{2})$.

To overcome the lack of orthogonality

Yamamoto, Nakatsukasa, Yanagisawa and Fukaya suggested that appling the CholQR algorithm twice will make the deviation from orthgonality reduces to $O(mnu)$, which drops the dependence on $\kappa_{2}(X)$.
Yamazaki, Tomov and Dongarra suggested that performing the first two steps at high precision $u_{h}$, and the last step at working precision $u$. Then the deviation from orthogonality can then be written as $O(u_{h} \kappa_{2}(X)^{2} + u \kappa_{2}(X))$, which can drop the dependency on $\kappa_{2}(X)^{2}$ for $u_{h}$ sufficiently small.

To overcome the instability,

Fukaya Kannan Nakatsukasa Yamamoto And Yanagisawa suggested using a shift $s$ to ensure the success of the Cholesky factorization $R^T R = X^T X + sI$. Then, instead of working with $\kappa_2(X) < u^{-1/2}$, the shifted CholQR works well on matrices with $\kappa_2(X) < u^{-1}$.