# A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 18 references that are in the map.
- First posted on arXiv 8 Aug 2025.

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

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Introduction to Tensor Decompositions and their Applications in Machine Learning](https://mlsanity.com/paper/1711.10781/) (2017)
- [Optimization Landscape of Tucker Decomposition](https://mlsanity.com/paper/2006.16297/) (2020)
- [Approximately Optimal Core Shapes for Tensor Decompositions](https://mlsanity.com/paper/2302.03886/) (2023)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)

## Abstract (arXiv)

We prove that the classic approximation guarantee for the higher-order singular value decomposition (HOSVD) is tight by constructing a tensor for which HOSVD achieves an approximation ratio of N/(1+varepsilon), for any varepsilon > 0. This matches the upper bound of De Lathauwer et al. (2000a) and shows that the approximation ratio of HOSVD cannot be improved. Using a more advanced construction, we also prove that the approximation guarantees for the ST-HOSVD algorithm of Vannieuwenhoven et al. (2012) and higher-order orthogonal iteration (HOOI) of De Lathauwer et al. (2000b) are tight by showing that they can achieve their worst-case approximation ratio of N / (1 + varepsilon), for any varepsilon > 0.