Convergence of the alternating least squares algorithm for CP tensor decompositions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909617078927360 |
|---|---|
| author | Hu, Nicholas Iwen, Mark A. Needell, Deanna Wang, Rongrong |
| author_facet | Hu, Nicholas Iwen, Mark A. Needell, Deanna Wang, Rongrong |
| contents | The alternating least squares (ALS/AltLS) method is a widely used algorithm for computing the CP decomposition of a tensor. However, its convergence theory is still incompletely understood.
In this paper, we prove explicit quantitative local convergence theorems for CP-AltLS applied to orthogonally decomposable and incoherently decomposable tensors. Specifically, we show that CP-AltLS converges polynomially with order $N-1$ for $N$th-order orthogonally decomposable tensors and linearly for incoherently decomposable tensors, with convergence being measured in terms of the angles between the factors of the exact tensor and those of the approximate tensor. Unlike existing results, our analysis is both quantitative and constructive, applying to standard CP-AltLS and accommodating factor matrices with small but nonzero mutual coherence, while remaining applicable to tensors of arbitrary rank.
We also confirm these rates of convergence numerically and investigate accelerating the convergence of CP-AltLS using an SVD-based coherence reduction scheme. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_14037 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence of the alternating least squares algorithm for CP tensor decompositions Hu, Nicholas Iwen, Mark A. Needell, Deanna Wang, Rongrong Numerical Analysis 15A69, 65F99, 65F45 The alternating least squares (ALS/AltLS) method is a widely used algorithm for computing the CP decomposition of a tensor. However, its convergence theory is still incompletely understood. In this paper, we prove explicit quantitative local convergence theorems for CP-AltLS applied to orthogonally decomposable and incoherently decomposable tensors. Specifically, we show that CP-AltLS converges polynomially with order $N-1$ for $N$th-order orthogonally decomposable tensors and linearly for incoherently decomposable tensors, with convergence being measured in terms of the angles between the factors of the exact tensor and those of the approximate tensor. Unlike existing results, our analysis is both quantitative and constructive, applying to standard CP-AltLS and accommodating factor matrices with small but nonzero mutual coherence, while remaining applicable to tensors of arbitrary rank. We also confirm these rates of convergence numerically and investigate accelerating the convergence of CP-AltLS using an SVD-based coherence reduction scheme. |
| title | Convergence of the alternating least squares algorithm for CP tensor decompositions |
| topic | Numerical Analysis 15A69, 65F99, 65F45 |
| url | https://arxiv.org/abs/2505.14037 |