{"ID":2884907,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.06693","arxiv_id":"2508.06693","title":"A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition","abstract":"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 \u003e 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 \u003e 0$.","short_abstract":"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 \u003e 0$. This matches the upper bound of De Lathauwer et al. (2000a) and shows that the...","url_abs":"https://arxiv.org/abs/2508.06693","url_pdf":"https://arxiv.org/pdf/2508.06693v1","authors":"[\"Matthew Fahrbach\",\"Mehrdad Ghadiri\"]","published":"2025-08-08T20:34:57Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}