RCLUPPr: a new randomized CholeskyQR with LU preconditioning

In this work, we present the comprehensive rounding error analysis of RCLUPPr proposed in \cite{RCLUPP}, which is a novel randomized CholeskyQR-type algorithm performing LU decomposition with partial pivoting (LUPP decomposition) directly on the tall-skinny $X\in\mathbb{R}^{m\times n}$ with $m \ge n$ and $\mbox{rank}(X)=n$.

In contrast to the existing RCLUPP in \cite{RCLUPP}, which applies matrix sketching before LUPP decomposition, RCLUPPr places LUPP decomposition as a preconditioning step first, significantly reducing error propagation.

Our analysis rigorously proves that RCLUPPr enjoys markedly better applicability to the ill-conditioned matrices than the existing CholeskyQR-type algorithms and remains stable and accurate in the mixed-precision arithmetic.

We further propose practical acceleration strategies in the real implementations of RCLUPPr.

Extensive numerical experiments on the real-world problems confirm the theoretical results in this work, demonstrating the robustness and practicality of RCLUPPr in the single, double, and the mixed-precision architecture.