Randomized Iterative Methods for Matrix Approximation

Standard tools to update approximations to a matrix A (for example, Quasi-Newton Hessian approximations in optimization) incorporate computationally expensive one-sided samples AV. This article develops randomized algorithms to efficiently approximate A by iteratively incorporating cheaper two-sided samples U⊤AV. Theoretical convergence rates are proved and realized in numerical experiments. A heuristic accelerated variant is developed and shown to be competitive with existing methods based on one-sided samples