Fast Tensor Completion via Approximate Richardson Iteration
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912533810511872 |
|---|---|
| author | Ghadiri, Mehrdad Fahrbach, Matthew Kook, Yunbum Jadbabaie, Ali |
| author_facet | Ghadiri, Mehrdad Fahrbach, Matthew Kook, Yunbum Jadbabaie, Ali |
| contents | We study tensor completion (TC) through the lens of low-rank tensor decomposition (TD). Many TD algorithms use fast alternating minimization methods to solve highly structured linear regression problems at each step (e.g., for CP, Tucker, and tensor-train decompositions). However, such algebraic structure is often lost in TC regression problems, making direct extensions unclear. This work proposes a novel lifting method for approximately solving TC regression problems using structured TD regression algorithms as blackbox subroutines, enabling sublinear-time methods. We analyze the convergence rate of our approximate Richardson iteration-based algorithm, and our empirical study shows that it can be 100x faster than direct methods for CP completion on real-world tensors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09534 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast Tensor Completion via Approximate Richardson Iteration Ghadiri, Mehrdad Fahrbach, Matthew Kook, Yunbum Jadbabaie, Ali Data Structures and Algorithms Machine Learning Statistics Theory We study tensor completion (TC) through the lens of low-rank tensor decomposition (TD). Many TD algorithms use fast alternating minimization methods to solve highly structured linear regression problems at each step (e.g., for CP, Tucker, and tensor-train decompositions). However, such algebraic structure is often lost in TC regression problems, making direct extensions unclear. This work proposes a novel lifting method for approximately solving TC regression problems using structured TD regression algorithms as blackbox subroutines, enabling sublinear-time methods. We analyze the convergence rate of our approximate Richardson iteration-based algorithm, and our empirical study shows that it can be 100x faster than direct methods for CP completion on real-world tensors. |
| title | Fast Tensor Completion via Approximate Richardson Iteration |
| topic | Data Structures and Algorithms Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2502.09534 |