Approximate Matrix Multiplication through Joint Leverage Score Sampling
In the authors' words
In this paper, we investigate approximate matrix multiplication through random sampling. Specifically, we propose using a non-uniform sampling distribution constructed from the leverage scores of the two matrices, and characterize the associated approximation error in terms of the matrix spectral norm; which is well-known to better characterize the downstream error when the matrix product operator is applied to an input vector. We provide the probability error bounds for the proposed algorithm are also given, and discuss connections to data-oblivious approximate matrix multiplication, and graph sparsification algorithms.
Main resultThe abstract does not state a limitation.
Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.