证明了高阶奇异值分解的近似率上限无法改进，是理论极限。
A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
- 构造反例证明HOSVD近似率下界为N/(1+ε)
- 首次严格验证三种算法最坏情况下的近似率不可优化
- 适合关注张量分解理论极限的研究者
我们证明了经典高阶奇异值分解（HOSVD）的近似保证是紧的，通过构造一个张量，使得HOSVD的近似比达到 $N/(1+ε)$（对任意 $ε > 0$）。该结果与De Lathauwer等（2000a）的上界一致，表明HOSVD的近似比无法进一步提升。通过更复杂的构造，我们还证明了Vannieuwenhoven等（2012）提出的ST-HOSVD以及De Lathauwer等（2000b）的HOOI算法的近似保证也是紧的，它们在最坏情况下可实现 $N / (1 + ε)$ 的近似比。这说明这些算法的性能已达到理论极限。
原文摘要 · Abstract (English)
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$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。