Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor Decomposition
| Autor: | Bharadwaj, Vivek, Malik, Osman Asif, Murray, Riley, Grigori, Laura, Buluc, Aydin, Demmel, James |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 persistent space overhead at most the size of the input matrices. As a result, it tractably draws samples even when the matrices forming the Khatri-Rao product have tens of millions of rows each. When used to sketch the linear least squares problems arising in CANDECOMP / PARAFAC tensor decomposition, our method achieves lower asymptotic complexity per solve than recent state-of-the-art methods. Experiments on billion-scale sparse tensors validate our claims, with our algorithm achieving higher accuracy than competing methods as the decomposition rank grows. Comment: The 37th Conference on Neural Information Processing Systems (Neurips'23). 28 pages, 10 figures, 6 tables |
| Databáze: | arXiv |
| Externí odkaz: |
|