Tensor Completion with Nearly Linear Samples Given Weak Side Information
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908468716240896 |
|---|---|
| author | Yu, Christina Lee Xi, Xumei |
| author_facet | Yu, Christina Lee Xi, Xumei |
| contents | Tensor completion exhibits an interesting computational-statistical gap in terms of the number of samples needed to perform tensor estimation. While there are only $Θ(tn)$ degrees of freedom in a $t$-order tensor with $n^t$ entries, the best known polynomial time algorithm requires $O(n^{t/2})$ samples in order to guarantee consistent estimation. In this paper, we show that weak side information is sufficient to reduce the sample complexity to $O(n)$. The side information consists of a weight vector for each of the modes which is not orthogonal to any of the latent factors along that mode; this is significantly weaker than assuming noisy knowledge of the subspaces. We provide an algorithm that utilizes this side information to produce a consistent estimator with $O(n^{1+κ})$ samples for any small constant $κ> 0$. We also provide experiments on both synthetic and real-world datasets that validate our theoretical insights. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_00736 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Tensor Completion with Nearly Linear Samples Given Weak Side Information Yu, Christina Lee Xi, Xumei Machine Learning Numerical Analysis Tensor completion exhibits an interesting computational-statistical gap in terms of the number of samples needed to perform tensor estimation. While there are only $Θ(tn)$ degrees of freedom in a $t$-order tensor with $n^t$ entries, the best known polynomial time algorithm requires $O(n^{t/2})$ samples in order to guarantee consistent estimation. In this paper, we show that weak side information is sufficient to reduce the sample complexity to $O(n)$. The side information consists of a weight vector for each of the modes which is not orthogonal to any of the latent factors along that mode; this is significantly weaker than assuming noisy knowledge of the subspaces. We provide an algorithm that utilizes this side information to produce a consistent estimator with $O(n^{1+κ})$ samples for any small constant $κ> 0$. We also provide experiments on both synthetic and real-world datasets that validate our theoretical insights. |
| title | Tensor Completion with Nearly Linear Samples Given Weak Side Information |
| topic | Machine Learning Numerical Analysis |
| url | https://arxiv.org/abs/2007.00736 |