Single-pass Nyström approximation in mixed precision

Low rank matrix approximations appear in a number of scientific computing applications. We consider the Nystr\"{o}m method for approximating a positive semidefinite matrix $A$. The computational cost of its single-pass version can be decreased by running it in mixed precision, where the expensive products with $A$ are computed in a precision lower than the working precision. We bound the extra finite precision error which is compared to the error of the Nystr\"{o}m approximation in exact arithmetic and develop a heuristic to identify when the approximation quality is not affected by the low precision computation. Further, the mixed precision Nystr\"{o}m method can be used to inexpensively construct a limited memory preconditioner for the conjugate gradient method. We bound the condition number of the resulting preconditioned coefficient matrix, and experimentally show that such a preconditioner can be effective.