Approximately Optimal Core Shapes for Tensor Decompositions
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914836854603776 |
|---|---|
| author | Ghadiri, Mehrdad Fahrbach, Matthew Fu, Gang Mirrokni, Vahab |
| author_facet | Ghadiri, Mehrdad Fahrbach, Matthew Fu, Gang Mirrokni, Vahab |
| contents | This work studies the combinatorial optimization problem of finding an optimal core tensor shape, also called multilinear rank, for a size-constrained Tucker decomposition. We give an algorithm with provable approximation guarantees for its reconstruction error via connections to higher-order singular values. Specifically, we introduce a novel Tucker packing problem, which we prove is NP-hard, and give a polynomial-time approximation scheme based on a reduction to the 2-dimensional knapsack problem with a matroid constraint. We also generalize our techniques to tree tensor network decompositions. We implement our algorithm using an integer programming solver, and show that its solution quality is competitive with (and sometimes better than) the greedy algorithm that uses the true Tucker decomposition loss at each step, while also running up to 1000x faster. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_03886 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Approximately Optimal Core Shapes for Tensor Decompositions Ghadiri, Mehrdad Fahrbach, Matthew Fu, Gang Mirrokni, Vahab Data Structures and Algorithms Machine Learning Combinatorics This work studies the combinatorial optimization problem of finding an optimal core tensor shape, also called multilinear rank, for a size-constrained Tucker decomposition. We give an algorithm with provable approximation guarantees for its reconstruction error via connections to higher-order singular values. Specifically, we introduce a novel Tucker packing problem, which we prove is NP-hard, and give a polynomial-time approximation scheme based on a reduction to the 2-dimensional knapsack problem with a matroid constraint. We also generalize our techniques to tree tensor network decompositions. We implement our algorithm using an integer programming solver, and show that its solution quality is competitive with (and sometimes better than) the greedy algorithm that uses the true Tucker decomposition loss at each step, while also running up to 1000x faster. |
| title | Approximately Optimal Core Shapes for Tensor Decompositions |
| topic | Data Structures and Algorithms Machine Learning Combinatorics |
| url | https://arxiv.org/abs/2302.03886 |