Result: Randomized algorithms with rank-one random vectors

Randomized algorithms in numerical linear algebra typically generate random vectors from standard distributions, such as Gaussian. However, in certain applications it may be advantageous to run computations with vectors compatible with the underlying structure of the problem. In this talk we discuss algorithms that use "rank-one" vectors, i.e., Kronecker products of two random vectors, which may allow for faster operations with matrices represented as short sums of Kronecker products. Possible applications include trace estimation and large-scale eigenvalue computation; we provide theoretical and numerical evidence that the use of rank-one instead of unstructured random vectors still leads to good estimates.