A randomized preconditioned Cholesky-QR algorithm
<|reference_start|>A randomized preconditioned Cholesky-QR algorithm: We a present and analyze rpCholesky-QR, a randomized preconditioned Cholesky-QR algorithm for computing the thin QR factorization of real mxn matrices with rank n. rpCholesky-QR has a low orthogonalization error, a residual on the order of machine precision, and does not break down for highly singular matrices. We derive rigorous and interpretable two-norm perturbation bounds for rpCholesky-QR that require a minimum of assumptions. Numerical experiments corroborate the accuracy of rpCholesky-QR for preconditioners sampled from as few as 3n rows, and illustrate that the two-norm deviation from orthonormality increases with only the condition number of the preconditioned matrix, rather than its square -- even if the original matrix is numerically singular.<|reference_end|>
@article{garrison2024a,
    title={A randomized preconditioned Cholesky-QR algorithm},
    author={James E. Garrison and Ilse C. F. Ipsen},
    journal={arXiv preprint arXiv:2406.11751},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.11751},
    primaryClass={math.NA cs.NA}
}