mlsanityData to 7 Oct 2026

Approximately Optimal Core Shapes for Tensor Decompositions

arXiv 2302.03886 ↗First posted 8 Feb 2023cs.DS cs.LG math.COcited by 8

Not on the map. Why?

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.

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

Builds on

12 of 62 references.

References · 12

  1. 2016Tensor Decomposition for Signal Processing and Machine Learningcited by 223
  2. 2015Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applicationscited by 161
  3. 2017Relative Error Tensor Low Rank Approximationcited by 45
  4. 2019Low-Rank Tucker Approximation of a Tensor From Streaming Datacited by 15
  5. 2021Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositionscited by 11
  6. 2020Optimization Landscape of Tucker Decompositioncited by 10
  7. 2015Active Distance-Based Clustering using K-medoidscited by 8
  8. 2022Constant-Factor Approximation Algorithms for Socially Fair k-Clusteringcited by 8
  9. 2014Decomposition of Big Tensors With Low Multilinear Rankcited by 7
  10. 2021More Efficient Sampling for Tensor Decomposition With Worst-Case Guaranteescited by 7
  11. 2022Subquadratic Kronecker Regression with Applications to Tensor Decompositioncited by 6
  12. 2021A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decompositioncited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 1; 2025: 3; 2026: 1.

8 papers.

  1. 2023Alternating Local Enumeration (TnALE): Solving Tensor Network Structure Search with Fewer Evaluationscited by 12
  2. 2023Geometry-aware training of factorized layers in tensor Tucker formatcited by 12
  3. 2023SVDinsTN: A Tensor Network Paradigm for Efficient Structure Search from Regularized Modeling Perspectivecited by 9
  4. 2024GeoLoRA: Geometric integration for parameter efficient fine-tuningcited by 5
  5. 2025Fast Tensor Completion via Approximate Richardson Iterationcited by 0
  6. 2025A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decompositioncited by 0
  7. 2025Renormalization Group Guided Tensor Network Structure Searchcited by 0
  8. 2026Tensor Decomposition Structure Search Framework from an Interaction Perspectivecited by 0