American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2019115

The point-wise convergence of shifted symmetric higher order power method

Gang Luo 1, and  Qingzhi Yang 1,2,,

1. 

School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China
2. 

School of Mathematics and Statistics, Kashi University, Kashi 844006, China

* Corresponding author: Qingzhi Yang

Received  January 2019 Revised  June 2019 Published  September 2019

Fund Project: The second author is supported by Natural Science Foundation of Xinjiang (Grant No. 2017D01A14)

Shifted symmetric higher-order power method (SS-HOPM) is an effective method of computing tensor eigenpairs. However the point-wise convergence of SS-HOPM has not been proven yet. In this paper, we provide a solid proof of the point-wise convergence of SS-HOPM via Łojasiewicz inequality. In particular, we establish a mapping from the sequence generated by the algorithm to a specially defined sequence. Using Łojasiewicz inequality, we prove the convergence of the new sequence, then the original sequence is convergent based on the relation of two sequences.

Keywords: Z-eigenvalue, shifted symmetric higher-order power method, point-wise convergence, Łojasiewicz inequality.
Mathematics Subject Classification: Primary: 15A18, 90C26; Secondary: 15A69.
Citation: Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019115
References:
[1]

A. Uschmajew, A new convergence proof for the higher-order power method and generalizations, Pac. J. Optim., 11 (2015), 309-321.   Google Scholar

[2]

A. T. Erdogan, On the convergence of ICA algorithms with symmetric orthogonalization, IEEE Trans. Signal Process., 57 (2009), 2209-2221.  doi: 10.1109/TSP.2009.2015114.  Google Scholar

[3]

D. Cartwright and B. Sturmfels, The number of eigenvalues of a tensor, Linear Alg. Appl., 438 (2013), 942-952.  doi: 10.1016/j.laa.2011.05.040.  Google Scholar

[4]

E. Kofidis and P. A. Regalia, On the best rank-1 approximation of higher-order supersymmetric tensors, SIAM J. Matrix Anal. Appl., 23 (2001), 863-884.  doi: 10.1137/S0895479801387413.  Google Scholar

[5]

G. H. Golub and C. F. Van Loan, Matrix Computations, Fourth edition, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013.  Google Scholar

[6]

L. De Lathauwer, B. De Moor and J. Vandewalle, On the best rank-1 and rank-($r_1$, $r_2$, ..., $r_N$) approximation of higher-order tensors, SIAM J. Matrix Anal. Appl., 21 (2000), 1324-1342.  doi: 10.1137/S0895479898346995.  Google Scholar

[7]

L. Lim, Singular values and eigenvalues of tensors: A variational approach, 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2005., IEEE, (2005), 129-132. Google Scholar

[8]

L. Q. Qi, Eigenvalues of a real supersymmetric tensor, J. Symb. Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[9]

L. Q. Qi and K. L. Teo, Multivariate polynomial minimization and its application in signal processing, J. Glob. Optim., 26 (2013), 419-433.  doi: 10.1023/A:1024778309049.  Google Scholar

[10]

L. Q. Qi, W. Y. Sun and Y. J. Wang, Numerical multilinear algebra and its applications, Front. Math. China, 2 (2007), 501-526.  doi: 10.1007/s11464-007-0031-4.  Google Scholar

[11]

M. Ng, L. Q. Qi and G. L. Zhou, Finding the largest eigenvalue of a nonnegative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), 1090-1099.  doi: 10.1137/09074838X.  Google Scholar

[12]

P.-A. Absil, R. Manhony and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim., 16 (2005), 531-547.  doi: 10.1137/040605266.  Google Scholar

[13]

P. A. Regalia and E. Kofidis, Monotonic convergence of fixed-point algorithms for ICA, IEEE Trans. Neural Netw., 14 (2003), 943-949.  doi: 10.1109/TNN.2003.813843.  Google Scholar

[14]

Q. Ni, L. Q. Qi and F. Wang, An eigenvalue method for testing positive definiteness of a multivariate form, IEEE Trans. Automat. Contr., 53 (2008), 1096-1107.  doi: 10.1109/TAC.2008.923679.  Google Scholar

[15]

R. Schneider and A. Uschmajew, Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality, SIAM J. Optim., 25 (2015), 622-646.  doi: 10.1137/140957822.  Google Scholar

[16]

S. Łojasiewicz, Ensembles semi-analytiques, Lectures Notes, IHES Bures-sur-Yvette, (1965). Google Scholar

[17]

T. G. Kolda and J. R. Mayo, Shifted power method for computing tensor eigenpairs, SIAM J. Matrix Anal. Appl., 32 (2011), 1095-1124.  doi: 10.1137/100801482.  Google Scholar

[18]

Y. J. Wang, L. Q. Qi and X. Z. Zhang, A practical method for computing the largest $m$-eigenvalue of a fourth-order partially symmetric tensor, Numer. Linear Algebra Appl., 16 (2009), 589-601.  doi: 10.1002/nla.633.  Google Scholar

[19]

Y. Y. Xu and W. T. Yin, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., 6 (2013), 1758-1789.  doi: 10.1137/120887795.  Google Scholar

show all references

References:
[1]

A. Uschmajew, A new convergence proof for the higher-order power method and generalizations, Pac. J. Optim., 11 (2015), 309-321.   Google Scholar

[2]

A. T. Erdogan, On the convergence of ICA algorithms with symmetric orthogonalization, IEEE Trans. Signal Process., 57 (2009), 2209-2221.  doi: 10.1109/TSP.2009.2015114.  Google Scholar

[3]

D. Cartwright and B. Sturmfels, The number of eigenvalues of a tensor, Linear Alg. Appl., 438 (2013), 942-952.  doi: 10.1016/j.laa.2011.05.040.  Google Scholar

[4]

E. Kofidis and P. A. Regalia, On the best rank-1 approximation of higher-order supersymmetric tensors, SIAM J. Matrix Anal. Appl., 23 (2001), 863-884.  doi: 10.1137/S0895479801387413.  Google Scholar

[5]

G. H. Golub and C. F. Van Loan, Matrix Computations, Fourth edition, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013.  Google Scholar

[6]

L. De Lathauwer, B. De Moor and J. Vandewalle, On the best rank-1 and rank-($r_1$, $r_2$, ..., $r_N$) approximation of higher-order tensors, SIAM J. Matrix Anal. Appl., 21 (2000), 1324-1342.  doi: 10.1137/S0895479898346995.  Google Scholar

[7]

L. Lim, Singular values and eigenvalues of tensors: A variational approach, 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2005., IEEE, (2005), 129-132. Google Scholar

[8]

L. Q. Qi, Eigenvalues of a real supersymmetric tensor, J. Symb. Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[9]

L. Q. Qi and K. L. Teo, Multivariate polynomial minimization and its application in signal processing, J. Glob. Optim., 26 (2013), 419-433.  doi: 10.1023/A:1024778309049.  Google Scholar

[10]

L. Q. Qi, W. Y. Sun and Y. J. Wang, Numerical multilinear algebra and its applications, Front. Math. China, 2 (2007), 501-526.  doi: 10.1007/s11464-007-0031-4.  Google Scholar

[11]

M. Ng, L. Q. Qi and G. L. Zhou, Finding the largest eigenvalue of a nonnegative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), 1090-1099.  doi: 10.1137/09074838X.  Google Scholar

[12]

P.-A. Absil, R. Manhony and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim., 16 (2005), 531-547.  doi: 10.1137/040605266.  Google Scholar

[13]

P. A. Regalia and E. Kofidis, Monotonic convergence of fixed-point algorithms for ICA, IEEE Trans. Neural Netw., 14 (2003), 943-949.  doi: 10.1109/TNN.2003.813843.  Google Scholar

[14]

Q. Ni, L. Q. Qi and F. Wang, An eigenvalue method for testing positive definiteness of a multivariate form, IEEE Trans. Automat. Contr., 53 (2008), 1096-1107.  doi: 10.1109/TAC.2008.923679.  Google Scholar

[15]

R. Schneider and A. Uschmajew, Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality, SIAM J. Optim., 25 (2015), 622-646.  doi: 10.1137/140957822.  Google Scholar

[16]

S. Łojasiewicz, Ensembles semi-analytiques, Lectures Notes, IHES Bures-sur-Yvette, (1965). Google Scholar

[17]

T. G. Kolda and J. R. Mayo, Shifted power method for computing tensor eigenpairs, SIAM J. Matrix Anal. Appl., 32 (2011), 1095-1124.  doi: 10.1137/100801482.  Google Scholar

[18]

Y. J. Wang, L. Q. Qi and X. Z. Zhang, A practical method for computing the largest $m$-eigenvalue of a fourth-order partially symmetric tensor, Numer. Linear Algebra Appl., 16 (2009), 589-601.  doi: 10.1002/nla.633.  Google Scholar

[19]

Y. Y. Xu and W. T. Yin, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., 6 (2013), 1758-1789.  doi: 10.1137/120887795.  Google Scholar

Figure 1.  Trajectories of sequences $ \{x_k\} $, $ \{y_k\} $ generated by SS-HOPM
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Gang Wang, Guanglu Zhou, Louis Caccetta. Z-Eigenvalue Inclusion Theorems for Tensors. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 187-198. doi: 10.3934/dcdsb.2017009
[2]

Xinmin Yang, Xiaoqi Yang, Kok Lay Teo. Higher-order symmetric duality in multiobjective programming with invexity. Journal of Industrial & Management Optimization, 2008, 4 (2) : 385-391. doi: 10.3934/jimo.2008.4.385
[3]

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033
[4]

Weisheng Niu, Yao Xu. Convergence rates in homogenization of higher-order parabolic systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (8) : 4203-4229. doi: 10.3934/dcds.2018183
[5]

Yongqin Liu. The point-wise estimates of solutions for semi-linear dissipative wave equation. Communications on Pure & Applied Analysis, 2013, 12 (1) : 237-252. doi: 10.3934/cpaa.2013.12.237
[6]

Petteri Harjulehto, Peter Hästö, Juha Tiirola. Point-wise behavior of the Geman--McClure and the Hebert--Leahy image restoration models. Inverse Problems & Imaging, 2015, 9 (3) : 835-851. doi: 10.3934/ipi.2015.9.835
[7]

Jiao Chen, Weike Wang. The point-wise estimates for the solution of damped wave equation with nonlinear convection in multi-dimensional space. Communications on Pure & Applied Analysis, 2014, 13 (1) : 307-330. doi: 10.3934/cpaa.2014.13.307
[8]

Kazuyuki Yagasaki. Higher-order Melnikov method and chaos for two-degree-of-freedom Hamiltonian systems with saddle-centers. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 387-402. doi: 10.3934/dcds.2011.29.387
[9]

Zhuchun Li, Yi Liu, Xiaoping Xue. Convergence and stability of generalized gradient systems by Łojasiewicz inequality with application in continuum Kuramoto model. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 345-367. doi: 10.3934/dcds.2019014
[10]

Eduardo Martínez. Higher-order variational calculus on Lie algebroids. Journal of Geometric Mechanics, 2015, 7 (1) : 81-108. doi: 10.3934/jgm.2015.7.81
[11]

Alain Haraux. Some applications of the Łojasiewicz gradient inequality. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2417-2427. doi: 10.3934/cpaa.2012.11.2417
[12]

Simão P. S. Santos, Natália Martins, Delfim F. M. Torres. Noether's theorem for higher-order variational problems of Herglotz type. Conference Publications, 2015, 2015 (special) : 990-999. doi: 10.3934/proc.2015.990
[13]

Pedro D. Prieto-Martínez, Narciso Román-Roy. Higher-order mechanics: Variational principles and other topics. Journal of Geometric Mechanics, 2013, 5 (4) : 493-510. doi: 10.3934/jgm.2013.5.493
[14]

Feliz Minhós, Hugo Carrasco. Solvability of higher-order BVPs in the half-line with unbounded nonlinearities. Conference Publications, 2015, 2015 (special) : 841-850. doi: 10.3934/proc.2015.0841
[15]

Robert Jankowski, Barbara Łupińska, Magdalena Nockowska-Rosiak, Ewa Schmeidel. Monotonic solutions of a higher-order neutral difference system. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 253-261. doi: 10.3934/dcdsb.2018017
[16]

Feng Wang, Fengquan Li, Zhijun Qiao. On the Cauchy problem for a higher-order μ-Camassa-Holm equation. Discrete & Continuous Dynamical Systems - A, 2018, 38 (8) : 4163-4187. doi: 10.3934/dcds.2018181
[17]

Qilin Wang, S. J. Li. Higher-order sensitivity analysis in nonconvex vector optimization. Journal of Industrial & Management Optimization, 2010, 6 (2) : 381-392. doi: 10.3934/jimo.2010.6.381
[18]

David F. Parker. Higher-order shallow water equations and the Camassa-Holm equation. Discrete & Continuous Dynamical Systems - B, 2007, 7 (3) : 629-641. doi: 10.3934/dcdsb.2007.7.629
[19]

Min Zhu. On the higher-order b-family equation and Euler equations on the circle. Discrete & Continuous Dynamical Systems - A, 2014, 34 (7) : 3013-3024. doi: 10.3934/dcds.2014.34.3013
[20]

Michał Jóźwikowski, Mikołaj Rotkiewicz. Bundle-theoretic methods for higher-order variational calculus. Journal of Geometric Mechanics, 2014, 6 (1) : 99-120. doi: 10.3934/jgm.2014.6.99

2018 Impact Factor: 1.025

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences