Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor Decomposition
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911785890611200 |
|---|---|
| author | Bharadwaj, Vivek Malik, Osman Asif Murray, Riley Grigori, Laura Buluc, Aydin Demmel, James |
| author_facet | Bharadwaj, Vivek Malik, Osman Asif Murray, Riley Grigori, Laura Buluc, Aydin Demmel, James |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_12584 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor Decomposition Bharadwaj, Vivek Malik, Osman Asif Murray, Riley Grigori, Laura Buluc, Aydin Demmel, James Numerical Analysis 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. |
| title | Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor Decomposition |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2301.12584 |