# Approximately Optimal Core Shapes for Tensor Decompositions

arXiv: https://arxiv.org/abs/2302.03886 · HTML: https://mlsanity.com/paper/2302.03886/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 62 references that are in the map.
- First posted on arXiv 8 Feb 2023.

## Builds on (most cited first, 12 of 12)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applications](https://mlsanity.com/paper/1511.06530/) (2015)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Low-Rank Tucker Approximation of a Tensor From Streaming Data](https://mlsanity.com/paper/1904.10951/) (2019)
- [Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions](https://mlsanity.com/paper/2104.01101/) (2021)
- [Optimization Landscape of Tucker Decomposition](https://mlsanity.com/paper/2006.16297/) (2020)
- [Active Distance-Based Clustering using K-medoids](https://mlsanity.com/paper/1512.03953/) (2015)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Decomposition of Big Tensors With Low Multilinear Rank](https://mlsanity.com/paper/1412.1885/) (2014)
- [More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees](https://mlsanity.com/paper/2110.07631/) (2021)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decomposition](https://mlsanity.com/paper/2110.12564/) (2021)

## Built on by (most cited first, 8 of 8)

- [Alternating Local Enumeration (TnALE): Solving Tensor Network Structure Search with Fewer Evaluations](https://mlsanity.com/paper/2304.12875/) (2023)
- [Geometry-aware training of factorized layers in tensor Tucker format](https://mlsanity.com/paper/2305.19059/) (2023)
- [SVDinsTN: A Tensor Network Paradigm for Efficient Structure Search from Regularized Modeling Perspective](https://mlsanity.com/paper/2305.14912/) (2023)
- [GeoLoRA: Geometric integration for parameter efficient fine-tuning](https://mlsanity.com/paper/2410.18720/) (2024)
- [Fast Tensor Completion via Approximate Richardson Iteration](https://mlsanity.com/paper/2502.09534/) (2025)
- [A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition](https://mlsanity.com/paper/2508.06693/) (2025)
- [Renormalization Group Guided Tensor Network Structure Search](https://mlsanity.com/paper/2512.24663/) (2025)
- [Tensor Decomposition Structure Search Framework from an Interaction Perspective](https://mlsanity.com/paper/2603.02720/) (2026)

## Abstract (arXiv)

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.