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]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[2]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[3]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075
[4]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[5]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320
[6]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014
[7]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[8]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[9]

Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020264
[10]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378
[11]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[12]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045
[13]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377
[14]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[15]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[16]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[17]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[18]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[19]

Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247
[20]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (118)
  • HTML views (444)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences