pipette
ESEspañol

Approximate Matrix Multiplication through Joint Leverage Score Sampling

Neophytos Charalambides, Mert Pilanci, Alfred O. Hero III

Preprint

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.