Previous Articles     Next Articles

A TRUST-REGION-BASED ALTERNATING LEAST-SQUARES ALGORITHM FOR TENSOR DECOMPOSITIONS

Fan Jiang1, Deren Han1, Xiaofei Zhang2   

  1. 1. Jiangsu Key Laboratory of NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, China;
    2. Information Technology Department, Chinascope, Nanjing 210023, China
  • Received:2017-01-05 Revised:2017-03-20 Online:2018-05-15 Published:2018-05-15
  • Supported by:

    This research is supported by a project funded by PAPD of Jiangsu Higher Education Institutions and the NSFC grants 11625105, 11371197, 11431002, 11571178.

Fan Jiang, Deren Han, Xiaofei Zhang. A TRUST-REGION-BASED ALTERNATING LEAST-SQUARES ALGORITHM FOR TENSOR DECOMPOSITIONS[J]. Journal of Computational Mathematics, 2018, 36(3): 351-373.

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-(Lr, Lr, 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.

CLC Number: 

[1] E. Acar, C. Aykut-Bingol, H. Bingol, R. Bro and B. Yener, Multiway analysis of epilepsy tensors, Bioinformatics, 23(2007), i10-i18.

[2] E. Acar and B. Yener, Unsupervied multiway data analysis:A literature survey, IEEE T. Knowl. Data En., 21(2009), 6-20.

[3] A.L.F. De Almeida, G. Favier and J.C.M. Mota, Generalized PARAFAC model for multidimensional wireless communications with application to blind multiuser equalization, Conference Record of the 39th Asilomar Conference on Signals, Systems and Computers, 11(2005), 1429-1433.

[4] A.L.F. De Almeida, G. Favier and J.C.M. Mota, Constrained tensor modeling approach to blind multiple-antenna CDMA schemes, IEEE T. Signal Proces., 56(2008), 2417-2428.

[5] G. Beylkin and M.J. Mohlenkamp, Algorithms for numerical analysis in high dimensions, SIAM J. Sci. Comput. 26(2005), 2133-2159.

[6] R. Bro, Multi-way analysis in the food industry:Models, algorithms, and applications, Ph.D. dissertation, University of Amsterdam, Amsterdam, 1998.

[7] J.D. Carol and J.J. Chang, Analysis of individual differences in multidimensional scaling via an N-way generalization of "Eckart-Young" decomposition, Psychometrika, 35(1970), 283-319.

[8] Y. Chen, D. Han and L. Qi, New ALS methods with extrapolating search directions and optimal step size for complex-valued tensor decompositions, IEEE T. Signal Proces., 59(2011), 5888-5898.

[9] J. Coloigner, A. Karfoul, L. Albera and P. Comon, Line search and trust region strategies for canonical decomposition of semi-nonnegative semi-symmetric 3rd order tensors, Linear Algebra Appl., 450(2014), 334-374.

[10] P. Comon, X. Luciani and A.L.F. De Almeida, Tensor decompositions, alternating least squares and other tales, J. Chemometr., 23(2009), 393-405.

[11] A.R. Conn, N.I. Gould and P.L. Toint, Trust region methods, SIAM, 2000.

[12] D.A. Cox, J. Little and D. O'Shea, Using Algebraic Geometry, Springer Science & Business Media, 2006.

[13] E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91(2002), 201-213.

[14] I. Domanov and L.D. Lathauwer, Canonical polyadic decomposition of third-order tensors:reduction to generalized eigenvalue decomposition, SIAM J. Matrix Anal. A., 35(2014), 636-660.

[15] J. Fan and Y. Yuan, On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74(2005), 23-39.

[16] J. Fan, The modified Levenberg-Marquardt method for nonlinear equations with cubic convergenc, Math. Comput., 81(2012), 447-466.

[17] J. Fan, Accelerating the modified Levenberg-Marquardt method for nonlinear equation, Math. Comput., 83(2014), 1173-1187.

[18] L. Grippo and M. Sciandrone, On the convergence of the block nonlinear Gauss-Seidel method under convex constraints, Oper. Res. Lett., 26(2000), 127-136.

[19] R.A. Harshman, Foundations of the PARAFAC procedure:model and conditions for an "explanatory" multi-code factor analysis, UCLA Working Papers, 1970.

[20] F.L. Hitchcock, The expression of a tensor or a polyadic as a sum of products, J. Math. Phys., 6(1927), 164-189.

[21] F.L. Hitchcock, Multiple invariants and generalized rank of a p-way matrix or tensor, J. Math. Phys., 7(1928), 39-79.

[22] W. Hackbush, B.N. Khoromskij and E.E. Tyrtyshnikov, Hierarchical Kronecker Tensor-Product Approximations, J. Numer. Math., 13(2005), 119-156.

[23] A.R. Hoy, C.G. Koay, S.R. Kecskemeti and A.L. Alexander, Optimization of a free water elimination two-compartment model for diffusion tensor imaging, NeuroImage, 103(2014), 323-333.

[24] T.G. Kolda and B.W. Bader, Tensor decompositions and applications, SIAM Rev., 51(2009), 455-500.

[25] B. Khoromskij and V. Khoromskaia, Low rank tucker type tensor approximation to classical potentials, Open Math., 5(2007), 523-550.

[26] N. Li, S. Kindermann and C. Navasca, Some convergence results on the regularized alternating least-squares method for tensor decomposition, Linear Algebra Appl., 2(2013), 796-812.

[27] C. Navasca, L. De Lathauwer and S. Kindermann, Swamp reducing technique for tensor decomposition, IEEE 16th European Signal Processing Conference, (2008), 1-5.

[28] D. Nion and L. De Lathauwer, A block factor analysis based receiver for blind multi-user access in wireless communications, IEEE International Conference on Acoustics, Speech and Signal Processing Proceedings, 5(2006), 825-828.

[29] D. Nion and L. De Lathauwer, Line search computation of the block factor model for blind multi-user access in wireless communications, IEEE Workshop on Signal Processing Advances in Wireless Communications (SPAWC), (2006), 1-5.

[30] D. Nion and L. De Lathauwer, An enhanced line search scheme for complex-valued tensor decompositions. Application in DS-CDMA, Signal Process., 88(2008), 749-755.

[31] J. Nocedal and S. Wright, Numerical optimization, Springer Science & Business Media, 2006.

[32] L. Qi, W. Sun and Y. Wang, Numerical multilinear algebra and its applications, Front. Math. China, 2(2004), 501-526.

[33] M. Rajih, P. Comon and R.A. Harshman, Enhanced line search:A novel method to accelerate PARAFAC, SIAM J. Matrix Anal. A., 30(2008), 1128-1147.

[34] M. Razaviyayn, M. Hong and Z. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization, SIAM J. Optimiz., 23(2013), 1126-1153.

[35] M. Signoretto, Q.T. Dinh, L. De Lathauwer and J.A.K. Suykens, Learning with tensors:a framework based on convex optimization and spectral regularization, Mach. Learn., 94(2014), 303-351.

[36] A. Smilde, R. Bro and P. Geladi, Multi-way analysis:applications in the chemical sciences, John Wiley & Sons, 2005.

[37] L. Sorber, M. van Barel and L. De Lathauwer, Optimization-based algorithms for tensor decompositions:Canonical polyadic decomposition, decomposition in rank-(Lr, Lr, 1) terms, and a new generalization, SIAM J. Optimiz., 23(2013), 695-720.

[38] L.R. Tucker, Some mathematical notes on three-mode factor analysis, Psychometrika, 31(1966), 279-311.

[39] M. De Vos, A. Vergult, L. De Lathauwer, W. De Clercq, S. Van Huffel, P. Dupont, A. Palmini and W. Van Paesschen, Canonical decomposition of ictal scalp EEG reliably detects the seizure onset zone, NeuroImage, 37(2007), 844-854.
[1] Xiaoyu Wang, Ya-xiang Yuan. STOCHASTIC TRUST-REGION METHODS WITH TRUST-REGION RADIUS DEPENDING ON PROBABILISTIC MODELS [J]. Journal of Computational Mathematics, 2022, 40(2): 294-334.
[2] Yuting Chen, Mingyuan Cao, Yueting Yang, Qingdao Huang. AN ADAPTIVE TRUST-REGION METHOD FOR GENERALIZED EIGENVALUES OF SYMMETRIC TENSORS [J]. Journal of Computational Mathematics, 2021, 39(3): 358-374.
[3] Keke Zhang, Hongwei Liu, Zexian Liu. A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION [J]. Journal of Computational Mathematics, 2021, 39(2): 159-177.
[4] Wenjuan Xue, Weiai Liu. A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING [J]. Journal of Computational Mathematics, 2020, 38(5): 683-704.
[5] Yuanping Zhang, Yanfei Wang. THREE-DIMENSIONAL GRAVITY-MAGNETIC CROSS-GRADIENT JOINT INVERSION BASED ON STRUCTURAL COUPLING AND A FAST GRADIENT METHOD [J]. Journal of Computational Mathematics, 2019, 37(6): 758-777.
[6] Bothina El-Sobky, Abdallah Abotahoun. A TRUST-REGION ALGORITHM FOR SOLVING MINI-MAX PROBLEM [J]. Journal of Computational Mathematics, 2018, 36(6): 776-791.
[7] Caixia Kou, Zhongwen Chen, Yuhong Dai, Haifei Han. AN AUGMENTED LAGRANGIAN TRUST REGION METHOD WITH A BI-OBJECT STRATEGY [J]. Journal of Computational Mathematics, 2018, 36(3): 331-350.
[8] Yangyang Xu. FAST ALGORITHMS FOR HIGHER-ORDER SINGULAR VALUE DECOMPOSITION FROM INCOMPLETE DATA [J]. Journal of Computational Mathematics, 2017, 35(4): 397-422.
[9] Lingsheng Meng, Bing Zheng. STRUCTURED CONDITION NUMBERS FOR THE TIKHONOV REGULARIZATION OF DISCRETE ILL-POSED PROBLEMS [J]. Journal of Computational Mathematics, 2017, 35(2): 169-186.
[10] Zhifeng Wu, Si Li, Xueying Zeng, Yuesheng Xu, Andrzej Krol. REDUCING STAIRCASING ARTIFACTS IN SPECT RECONSTRUCTION BY AN INFIMAL CONVOLUTION REGULARIZATION [J]. Journal of Computational Mathematics, 2016, 34(6): 626-647.
[11] Rongfang Gong, Joseph Eichholz, Xiaoliang Cheng, Weimin Han. ANALYSIS OF A NUMERICAL METHOD FOR RADIATIVE TRANSFER EQUATION BASED BIOLUMINESCENCE TOMOGRAPHY [J]. Journal of Computational Mathematics, 2016, 34(6): 648-670.
[12] Jinkui Liu, Shengjie Li. SPECTRAL DY-TYPE PROJECTION METHOD FOR NONLINEAR MONOTONE SYSTEM OF EQUATIONS [J]. Journal of Computational Mathematics, 2015, 33(4): 341-355.
[13] Heng Mao. ADAPTIVE CHOICE OF THE REGULARIZATION PARAMETER IN NUMERICAL DIFFERENTIATION [J]. Journal of Computational Mathematics, 2015, 33(4): 415-427.
[14] Jinghui Liu, Changfeng Ma. A NEW NONMONOTONE TRUST REGION ALGORITHM FOR SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(4): 476-490.
[15] Guofeng Zhang, Zhong Zheng. BLOCK-SYMMETRIC AND BLOCK-LOWER-TRIANGULAR PRECONDITIONERS FOR PDE-CONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2013, 31(4): 370-381.
Viewed
Full text


Abstract