A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
This provides a fundamental theoretical limit for tensor approximation methods, which is important for researchers in numerical linear algebra and machine learning, though it is incremental as it confirms existing bounds rather than introducing new methods.
The paper proves that the approximation guarantees for higher-order singular value decomposition (HOSVD) and related algorithms are tight by constructing tensors where they achieve worst-case ratios of N/(1+ε), matching known upper bounds and showing these ratios cannot be improved.
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$.