A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918120719908864 |
|---|---|
| author | Fahrbach, Matthew Ghadiri, Mehrdad |
| author_facet | Fahrbach, Matthew Ghadiri, Mehrdad |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06693 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition Fahrbach, Matthew Ghadiri, Mehrdad Data Structures and Algorithms Machine Learning 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$. |
| title | A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2508.06693 |