Approximately Optimal Core Shapes for Tensor Decompositions

Mehrdad Ghadiri, Matthew Fahrbach, Gang Fu, Vahab Mirrokni
2/8/2023
cs.DScs.LGmath.CO

No official code found. Best implementation: fahrbach/approximately-optimal-core-shapes (0 stars, MIT, last commit 2025-09-08).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

fahrbach/approximately-optimal-core-shapesCommunity65%
MIT

Approximately optimal core shapes for tensor decompositions (ICML 2023)

00PythonDec 10, 20221 years agoMIT

Similar Papers

Revisiting Trace Norm Minimization for Tensor Tucker Completion: A Direct Multilinear Rank Learning Approach

81% match2024

Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints

79% match1 repo52024

Riemannian Optimization on Tree Tensor Networks with Application in Machine Learning

78% match2025

Tensor Completion via Integer Optimization

78% match2024

Fast Tensor Completion via Approximate Richardson Iteration

78% match1 repo32026

Structured Low-Rank Tensor Learning

78% match2023

Cite this paper

@article{ghadiri2023approximately,
  title  = {Approximately Optimal Core Shapes for Tensor Decompositions},
  author = {Mehrdad Ghadiri and Matthew Fahrbach and Gang Fu and Vahab Mirrokni},
  year   = {2023},
  eprint = {2302.03886},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2302.03886v1},
  journal = {ICML 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2302.03886.svg)](https://codeofpaper.com/paper/2302.03886)

Discussion