Tensor Deli: Tensor Completion for Low CP-Rank Tensors via Random Sampling
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916160174292992 |
|---|---|
| author | Haselby, Cullen Iwen, Mark Karnik, Santhosh Wang, Rongrong |
| author_facet | Haselby, Cullen Iwen, Mark Karnik, Santhosh Wang, Rongrong |
| contents | We propose two provably accurate methods for low CP-rank tensor completion - one using adaptive sampling and one using nonadaptive sampling. Both of our algorithms combine matrix completion techniques for a small number of slices along with Jennrich's algorithm to learn the factors corresponding to the first two modes, and then solve systems of linear equations to learn the factors corresponding to the remaining modes. For order-$3$ tensors, our algorithms follow a "sandwich" sampling strategy that more densely samples a few outer slices (the bread), and then more sparsely samples additional inner slices (the bbq-braised tofu) for the final completion. For an order-$d$, CP-rank $r$ tensor of size $n \times \cdots \times n$ that satisfies mild assumptions, our adaptive sampling algorithm recovers the CP-decomposition with high probability while using at most $O(nr\log r + dnr)$ samples and $O(n^2r^2+dnr^2)$ operations. Our nonadaptive sampling algorithm recovers the CP-decomposition with high probability while using at most $O(dnr^2\log n + nr\log^2 n)$ samples and runs in polynomial time. Numerical experiments demonstrate that both of our methods work well on noisy synthetic data as well as on real world data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_09932 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tensor Deli: Tensor Completion for Low CP-Rank Tensors via Random Sampling Haselby, Cullen Iwen, Mark Karnik, Santhosh Wang, Rongrong Numerical Analysis 65F55, 15A83, 15A69 We propose two provably accurate methods for low CP-rank tensor completion - one using adaptive sampling and one using nonadaptive sampling. Both of our algorithms combine matrix completion techniques for a small number of slices along with Jennrich's algorithm to learn the factors corresponding to the first two modes, and then solve systems of linear equations to learn the factors corresponding to the remaining modes. For order-$3$ tensors, our algorithms follow a "sandwich" sampling strategy that more densely samples a few outer slices (the bread), and then more sparsely samples additional inner slices (the bbq-braised tofu) for the final completion. For an order-$d$, CP-rank $r$ tensor of size $n \times \cdots \times n$ that satisfies mild assumptions, our adaptive sampling algorithm recovers the CP-decomposition with high probability while using at most $O(nr\log r + dnr)$ samples and $O(n^2r^2+dnr^2)$ operations. Our nonadaptive sampling algorithm recovers the CP-decomposition with high probability while using at most $O(dnr^2\log n + nr\log^2 n)$ samples and runs in polynomial time. Numerical experiments demonstrate that both of our methods work well on noisy synthetic data as well as on real world data. |
| title | Tensor Deli: Tensor Completion for Low CP-Rank Tensors via Random Sampling |
| topic | Numerical Analysis 65F55, 15A83, 15A69 |
| url | https://arxiv.org/abs/2403.09932 |