American Institute of Mathematical Sciences

Advanced
January  2021, 17(1): 357-368. 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  January 2021 Early access  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 and Management Optimization, 2021, 17 (1) : 357-368. 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. 

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[16]

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

[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.

[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.

[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.

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. 

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[16]

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

[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.

[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.

[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.

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 and Continuous Dynamical Systems - B, 2017, 22 (1) : 187-198. doi: 10.3934/dcdsb.2017009
[2]

Jun He, Guangjun Xu, Yanmin Liu. New Z-eigenvalue localization sets for tensors with applications. Journal of Industrial and Management Optimization, 2022, 18 (3) : 2095-2108. doi: 10.3934/jimo.2021058
[3]

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

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033
[5]

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

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

Zaizheng Li, Qidi Zhang. Sub-solutions and a point-wise Hopf's lemma for fractional $ p $-Laplacian. Communications on Pure and Applied Analysis, 2021, 20 (2) : 835-865. doi: 10.3934/cpaa.2020293
[8]

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

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 and Applied Analysis, 2014, 13 (1) : 307-330. doi: 10.3934/cpaa.2014.13.307
[10]

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

Xiaojun Zheng, Zhongdan Huan, Jun Liu. On the solvability of a semilinear higher-order elliptic problem for the vector field method in image registration. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2022068
[12]

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

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
[14]

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

Kongzhi Li, Xiaoping Xue. The Łojasiewicz inequality for free energy functionals on a graph. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2022066
[16]

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
[17]

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
[18]

George J. Bautista, Ademir F. Pazoto. Decay of solutions for a dissipative higher-order Boussinesq system on a periodic domain. Communications on Pure and Applied Analysis, 2020, 19 (2) : 747-769. doi: 10.3934/cpaa.2020035
[19]

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
[20]

Clesh Deseskel Elion Ekohela, Daniel Moukoko. On higher-order anisotropic perturbed Caginalp phase field systems. Electronic Research Announcements, 2019, 26: 36-53. doi: 10.3934/era.2019.26.004

2020 Impact Factor: 1.801

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy