Randomized Householder QR

Abstract. This paper introduces a randomized Householder QR factorization (RHQR). This factorization can be used to obtain a well-conditioned basis of a linear subspace and thus can be employed in a variety of applications. The RHQR factorization of the input matrix [Formula: see text] is equivalent to the standard Householder QR factorization of the matrix [Formula: see text], where [Formula: see text] is a sketching matrix that can be obtained from any subspace embedding technique. For this reason, the RHQR factorization can also be reconstructed from the Householder QR factorization of the sketched problem, yielding a single-synchronization randomized QR factorization. In most contexts, left-looking RHQR requires a single synchronization per iteration, with half the computational cost of Householder QR and a similar cost to randomized Gram–Schmidt overall. A finite-precision analysis shows that, under mild probabilistic assumptions, the RHQR factorization of the input matrix [Formula: see text] inherits the stability of the Householder QR factorization, producing a well-conditioned basis and a columnwise backward stable factorization, all independently of the condition number of the input [Formula: see text] and with the accuracy of the sketching step. We study the subsampled randomized Hadamard transform as a numerically accurate sketching technique. We discuss the usage of RHQR in the Arnoldi process and then in GMRES, showing thus how it can be used in Krylov subspace methods to solve systems of linear equations. Numerical experiments show that RHQR produces both a well-conditioned basis whose sketch is numerically orthogonal even for the most difficult inputs and an accurate factorization. The same results were observed with the high-dimensional operations made in half precision. The RHQR factorization reconstructed from the Householder factorization of the sketch was more stable than the standard randomized Cholesky QR.