Before revision:  Instead, we perform sketching through leverage score sampling, crucially relying on the fact that the structure of the Khatri-Rao product allows sampling from overestimates of the leverage scores without forming the full product or the corresponding probabilities. Naive application of leverage score sampling is ineffective because we often have cases where a few scores are quite large, leading to repeatedly sampling the few entries with large scores. We improve the speed by combining repeated rows. Additionally, we propose a novel hybrid of deterministic and random leverage-score sampling which consistently yields improved fits . Numerical results on real-world large-scale tensors show the method is significantly faster than competing methods without sacrificing accuracy.
After revision:  Instead, we perform sketching through leverage score sampling, crucially relying on the fact that the structure of the Khatri-Rao product allows sampling from overestimates of the number of rows in the sketched system is independent of the number of nonzeros in the full tensor and the number of rows in the full system. Along the way, we provide a practical solution to the generic matrix sketching problem of sampling overabundance for high-leverage-score rows, proposing to include such rows deterministically and combine repeated samples in the sketched system; we conjecture that this can lead to improved theoretical bounds . Numerical results on real-world large-scale tensors show the method is significantly faster than competing methods without sacrificing accuracy.