Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910570900357120 |
|---|---|
| author | Gomez-Leos, Alejandro López, Oscar |
| author_facet | Gomez-Leos, Alejandro López, Oscar |
| contents | We revisit the sample and computational complexity of completing a rank-1 tensor in $\otimes_{i=1}^{N} \mathbb{R}^{d}$, given a uniformly sampled subset of its entries. We present a characterization of the problem (i.e. nonzero entries) which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems. For example, when $N = Θ(1)$, we prove it uses no more than $m = O(d^2 \log d)$ samples and runs in $O(md^2)$ time. Moreover, we show any algorithm requires $Ω(d\log d)$ samples.
By contrast, existing upper bounds on the sample complexity are at least as large as $d^{1.5} μ^{Ω(1)} \log^{Ω(1)} d$, where $μ$ can be $Θ(d)$ in the worst case. Prior work obtained these looser guarantees in higher rank versions of our problem, and tend to involve more complicated algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_05431 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan Gomez-Leos, Alejandro López, Oscar Data Structures and Algorithms Machine Learning Statistics Theory We revisit the sample and computational complexity of completing a rank-1 tensor in $\otimes_{i=1}^{N} \mathbb{R}^{d}$, given a uniformly sampled subset of its entries. We present a characterization of the problem (i.e. nonzero entries) which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems. For example, when $N = Θ(1)$, we prove it uses no more than $m = O(d^2 \log d)$ samples and runs in $O(md^2)$ time. Moreover, we show any algorithm requires $Ω(d\log d)$ samples. By contrast, existing upper bounds on the sample complexity are at least as large as $d^{1.5} μ^{Ω(1)} \log^{Ω(1)} d$, where $μ$ can be $Θ(d)$ in the worst case. Prior work obtained these looser guarantees in higher rank versions of our problem, and tend to involve more complicated algorithms. |
| title | Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan |
| topic | Data Structures and Algorithms Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2408.05431 |