  A randomized Gram-Schmidt algorithm is developed for orthonormalization of
high-dimensional vectors or QR factorization. The proposed process can be less
computationally expensive than the classical Gram-Schmidt process while being
at least as numerically stable as the modified Gram-Schmidt process. Our
approach is based on random sketching, which is a dimension reduction technique
consisting in estimation of inner products of high-dimensional vectors by inner
products of their small efficiently-computable random images, so-called
sketches. In this way, an approximate orthogonality of the full vectors can be
obtained by orthogonalization of their sketches. The proposed Gram-Schmidt
algorithm can provide computational cost reduction in any architecture. The
benefit of random sketching can be amplified by performing the non-dominant
operations in higher precision. In this case the numerical stability can be
guaranteed with a working unit roundoff independent of the dimension of the
problem. The proposed Gram-Schmidt process can be applied to Arnoldi iteration
and result in new Krylov subspace methods for solving high-dimensional systems
of equations or eigenvalue problems. Among them we chose randomized GMRES
method as a practical application of the methodology.
