Cholesky QR Algorithm
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\Sigma 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_{i} > 0\), which is equivalent as \(\sigma_{i}(X^{T} X) > 0\) since \(X^{T} X = V \Sigma^{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(u\,\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}\).