2025/08/08 by Matthew Fahrbach, Fahrbach, Matthew, Mehrdad Ghadiri +1
Engineering · Mathematics · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Model Reduction and Neural Networks #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2508.06693
openalex publication_date 2025/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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+ε), for any ε > 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 + ε), for any ε > 0.