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  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, 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.   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]

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

Chaoqian Li, Yajun Liu, Yaotang Li. Note on $ Z $-eigenvalue inclusion theorems for tensors. Journal of Industrial & Management Optimization, 2021, 17 (2) : 687-693. doi: 10.3934/jimo.2019129
[3]

Tomasz Szostok. Inequalities of Hermite-Hadamard type for higher order convex functions, revisited. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020296
[4]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018
[5]

Toshiko Ogiwara, Danielle Hilhorst, Hiroshi Matano. Convergence and structure theorems for order-preserving dynamical systems with mass conservation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3883-3907. doi: 10.3934/dcds.2020129
[6]

Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020178
[7]

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

Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020355
[9]

Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089
[10]

Guo-Niu Han, Huan Xiong. Skew doubled shifted plane partitions: Calculus and asymptotics. Electronic Research Archive, 2021, 29 (1) : 1841-1857. doi: 10.3934/era.2020094
[11]

Honglei Lang, Yunhe Sheng. Linearization of the higher analogue of Courant algebroids. Journal of Geometric Mechanics, 2020, 12 (4) : 585-606. doi: 10.3934/jgm.2020025
[12]

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

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

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[15]

Shuang Liu, Yuan Lou. A functional approach towards eigenvalue problems associated with incompressible flow. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3715-3736. doi: 10.3934/dcds.2020028
[16]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404
[17]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[18]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
[19]

Puneet Pasricha, Anubha Goel. Pricing power exchange options with hawkes jump diffusion processes. Journal of Industrial & Management Optimization, 2021, 17 (1) : 133-149. doi: 10.3934/jimo.2019103
[20]

Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067

2019 Impact Factor: 1.366

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences