arrow
Volume 36, Issue 3
A Trust-Region-Based Alternating Least-Squares Algorithm for Tensor Decompositions

Fan Jiang, Deren Han & Xiaofei Zhang

J. Comp. Math., 36 (2018), pp. 351-373.

Published online: 2018-06

Export citation
  • Abstract

Tensor canonical decomposition (shorted as CANDECOMP/PARAFAC or CP) decomposes a tensor as a sum of rank-one tensors, which finds numerous applications in signal processing, hypergraph analysis, data analysis, etc. Alternating least-squares (ALS) is one of the most popular numerical algorithms for solving it. While there have been lots of efforts for enhancing its efficiency, in general its convergence can not been guaranteed.
In this paper, we cooperate the ALS and the trust-region technique from optimization field to generate a trust-region-based alternating least-squares (TRALS) method for CP. Under mild assumptions, we prove that the whole iterative sequence generated by TRALS converges to a stationary point of CP. This thus provides a reasonable way to alleviate the swamps, the notorious phenomena of ALS that slow down the speed of the algorithm. Moreover, the trust region itself, in contrast to the regularization alternating least-squares (RALS) method, provides a self-adaptive way in choosing the parameter, which is essential for the efficiency of the algorithm. Our theoretical result is thus stronger than that of RALS in [26], which only proved the cluster point of the iterative sequence generated by RALS is a stationary point. In order to accelerate the new algorithm, we adopt an extrapolation scheme. We apply our algorithm to the amino acid fluorescence data decomposition from chemometrics, BCM decomposition and rank-($L_r$, $L_r$, 1) decomposition arising from signal processing, and compare it with ALS and RALS. The numerical results show that TRALS is superior to ALS and RALS, both from the number of iterations and CPU time perspectives.

  • Keywords

tensor decompositions, trust region method, alternating least-squares, extrapolation scheme, global convergence, regularization.

  • AMS Subject Headings

90C06, 90C53, 65K05

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

15905154902@163.com (Fan Jiang)

handeren@njnu.edu.cn (Deren Han)

879734743@qq.com (Xiaofei Zhang)

  • BibTex
  • RIS
  • TXT
@Article{JCM-36-351, author = {Fan and Jiang and 15905154902@163.com and 6793 and Jiangsu Key Laboratory of NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, China and Fan Jiang and Deren and Han and handeren@njnu.edu.cn and 6794 and Jiangsu Key Laboratory of NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, China and Deren Han and Xiaofei and Zhang and 879734743@qq.com and 6795 and Information Technology Department, Chinascope, Nanjing 210023, China and Xiaofei Zhang}, title = {A Trust-Region-Based Alternating Least-Squares Algorithm for Tensor Decompositions}, journal = {Journal of Computational Mathematics}, year = {2018}, volume = {36}, number = {3}, pages = {351--373}, abstract = {

Tensor canonical decomposition (shorted as CANDECOMP/PARAFAC or CP) decomposes a tensor as a sum of rank-one tensors, which finds numerous applications in signal processing, hypergraph analysis, data analysis, etc. Alternating least-squares (ALS) is one of the most popular numerical algorithms for solving it. While there have been lots of efforts for enhancing its efficiency, in general its convergence can not been guaranteed.
In this paper, we cooperate the ALS and the trust-region technique from optimization field to generate a trust-region-based alternating least-squares (TRALS) method for CP. Under mild assumptions, we prove that the whole iterative sequence generated by TRALS converges to a stationary point of CP. This thus provides a reasonable way to alleviate the swamps, the notorious phenomena of ALS that slow down the speed of the algorithm. Moreover, the trust region itself, in contrast to the regularization alternating least-squares (RALS) method, provides a self-adaptive way in choosing the parameter, which is essential for the efficiency of the algorithm. Our theoretical result is thus stronger than that of RALS in [26], which only proved the cluster point of the iterative sequence generated by RALS is a stationary point. In order to accelerate the new algorithm, we adopt an extrapolation scheme. We apply our algorithm to the amino acid fluorescence data decomposition from chemometrics, BCM decomposition and rank-($L_r$, $L_r$, 1) decomposition arising from signal processing, and compare it with ALS and RALS. The numerical results show that TRALS is superior to ALS and RALS, both from the number of iterations and CPU time perspectives.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1605-m2016-0828}, url = {http://global-sci.org/intro/article_detail/jcm/12265.html} }
TY - JOUR T1 - A Trust-Region-Based Alternating Least-Squares Algorithm for Tensor Decompositions AU - Jiang , Fan AU - Han , Deren AU - Zhang , Xiaofei JO - Journal of Computational Mathematics VL - 3 SP - 351 EP - 373 PY - 2018 DA - 2018/06 SN - 36 DO - http://doi.org/10.4208/jcm.1605-m2016-0828 UR - https://global-sci.org/intro/article_detail/jcm/12265.html KW - tensor decompositions, trust region method, alternating least-squares, extrapolation scheme, global convergence, regularization. AB -

Tensor canonical decomposition (shorted as CANDECOMP/PARAFAC or CP) decomposes a tensor as a sum of rank-one tensors, which finds numerous applications in signal processing, hypergraph analysis, data analysis, etc. Alternating least-squares (ALS) is one of the most popular numerical algorithms for solving it. While there have been lots of efforts for enhancing its efficiency, in general its convergence can not been guaranteed.
In this paper, we cooperate the ALS and the trust-region technique from optimization field to generate a trust-region-based alternating least-squares (TRALS) method for CP. Under mild assumptions, we prove that the whole iterative sequence generated by TRALS converges to a stationary point of CP. This thus provides a reasonable way to alleviate the swamps, the notorious phenomena of ALS that slow down the speed of the algorithm. Moreover, the trust region itself, in contrast to the regularization alternating least-squares (RALS) method, provides a self-adaptive way in choosing the parameter, which is essential for the efficiency of the algorithm. Our theoretical result is thus stronger than that of RALS in [26], which only proved the cluster point of the iterative sequence generated by RALS is a stationary point. In order to accelerate the new algorithm, we adopt an extrapolation scheme. We apply our algorithm to the amino acid fluorescence data decomposition from chemometrics, BCM decomposition and rank-($L_r$, $L_r$, 1) decomposition arising from signal processing, and compare it with ALS and RALS. The numerical results show that TRALS is superior to ALS and RALS, both from the number of iterations and CPU time perspectives.

Fan Jiang, Deren Han & Xiaofei Zhang. (2020). A Trust-Region-Based Alternating Least-Squares Algorithm for Tensor Decompositions. Journal of Computational Mathematics. 36 (3). 351-373. doi:10.4208/jcm.1605-m2016-0828
Copy to clipboard
The citation has been copied to your clipboard