Riley Murray

Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor Decomposition

We present a data structure to randomly sample rows from the Khatri-Rao product of several matrices according to the exact distribution of its leverage scores. Our proposed sampler draws each row in time logarithmic in the height of the Khatri-Rao product and quadratic in its column count, with pers…