iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10589-016-9846-9
An adaptive gradient method for computing generalized tensor eigenpairs | Computational Optimization and Applications Skip to main content
Springer Nature Link
Log in

An adaptive gradient method for computing generalized tensor eigenpairs

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

High order tensor arises more and more often in signal processing, data analysis, higher-order statistics, as well as imaging sciences. In this paper, an adaptive gradient (AG) method is presented for generalized tensor eigenpairs. Global convergence and linear convergence rate are established under some suitable conditions. Numerical results are reported to illustrate the efficiency of the proposed method. Comparing with the GEAP method, an adaptive shifted power method proposed by Kolda and Mayo (SIAM J Matrix Anal Appl 35:1563–1581, 2014) the AG method is much faster and could reach the largest eigenpair with a higher probability.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Bader, B.W., Kolda, T.G. et al.: MATLAB Tensor Toolbox Version 2.6, Available online, February 2015. http://www.sandia.gov/~tgkolda/TensorToolbox/

  2. Bloy, L., Verma, R.: On computing the underlying fiber directions from the diffusion orientation distribution function. Medical Image Computing and Computer-Assisted Intervention MICCAI, pp. 1–8. Springer, Berlin (2008)

    Google Scholar 

  3. Cetin, S., Unal, G.: A higher-order tensor vessel tractography for segmentation of vascular structures. IEEE Trans. Med. Imaging 34, 2172–2185 (2015)

    Article  Google Scholar 

  4. Chang, K.C., Pearson, K.J., Zhang, T.: Perron–Frobenius Theorem for nonnegative tensors. Commun. Math. Sci. 6, 507–520 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chang, K.C., Pearson, K.J., Zhang, T.: On eigenvalue problems of real symmetric tensors. J. Math. Anal. Appl. 350, 416–422 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chang, K., Pearson, K., Zhang, T.: Primitivity, the convergence of the NQZ method, and the largest eigenvalue for nonnegative tensors. SIAM J. Matrix Anal. Appl. 32, 806–819 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chang, K., Qi, L., Zhang, T.: A survey on the spectral theory of nonnegative tensors. Numer. Linear Algebra Appl. 20, 891–912 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chang, K., Zhang, T.: On the uniqueness and nonuniqueness of the Z-eigenvector for transition probability tensors. J. Math. Anal. Appl. 408, 525–540 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  9. Chen, Y., Dai, Y., Han, D., Sun, W.: Positive semidefinite generalized diffusion tensor imaging via quadratic semidefinite programming. SIAM J. Imaging Sci. 6, 1531–1552 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chen Y., Qi L., Wang Q.: Computing eigenvalues of large scale Hankel tensors. J Sci Comput. doi:10.1007/s10915-015-0155-8

  11. Chu M., Wu S.: On the second dominant eigenvalue affecting the Power method for transition probability tensors, Manuscript (2014)

  12. Cui, C., Dai, Y., Nie, J.: All real eigenvalues of symmetric tensors. SIAM J. Matrix Anal. Appl. 35, 1582–1601 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  13. Ding, W., Wei, Y.: Generalized tensor eigenvalue problems. SIAM J. Matrix Anal. Appl. 36, 1073–1099 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  14. Han, L.: An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors. Numer. Algebr. Control Optim. 3, 583–599 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hao, C., Cui, C., Dai, Y.: A sequential subspace projection method for extreme Z-eigenvalues of supersymmetric tensors. Numer. Linear Algebra Appl. 22, 283–298 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  16. Hao, C., Cui, C., Dai, Y.: A feasible trust-region method for calculating extreme Z-eigenvalues of symmetric tensors. Pac. J. Optim. 11, 291–307 (2015)

    MathSciNet  MATH  Google Scholar 

  17. Hillar, C., Lim, L.: Most tensor problems are NP-hard. J. ACM 45, 1–39 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  18. Hu, S., Li, G., Qi, L., Song, Y.: Finding the maximum eigenvalue of essentially nonnegative symmetric tensors via sum of squares programming on the largest eigenvalue of a symmetric nonnegative tensor. J. Optim. Theory Appl. 158(3), 717–738 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  19. Hu, S., Huang, Z., Qi, L.: Finding the extreme Z-eigenvalues of tensors via a sequential SDPs method. Numer. Linear Algebr. Appl. 20, 972–984 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kofidis, E., Regalia, P.: On the best rank-1 approximation of higher-order supersymmetric tensors. SIAM J. Matrix Anal. Appl. 23, 863–884 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kolda, T.G., Mayo, J.R.: An adaptive shifted power methods for computing generalized tensor eigenpairs. SIAM J. Matrix Anal. Appl. 35, 1563–1581 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kolda, T.G., Mayo, J.R.: Shifted power method for computing tensor eigenpairs. SIAM J. Matrix Anal. Appl. 32, 1095–1124 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  23. De Lathauwer, L., De Moor, B., Vandewalle, J.: On the best rank-1 and rank-(R1, R2, RN) approximation of higher-order tensors. SIAM J. Matrix Anal. Appl. 21, 1324–1342 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  24. Li, G., Qi, L., Yu, G.: The Z-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory. Numer. Linear Algebra Appl. 20, 1001–1029 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  25. Li, G., Qi, L., Yu, G.: Semismoothness of the maximum eigenvalue function of a symmetric tensor and its application. Linear Algebra Appl. 438, 813–833 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Li, W., Ng, M.: On the limiting probability distribution of a transition probability tensor. Linear Multilinear Algebra 62, 362–385 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  27. Lim L.H.: Singular values and eigenvalues of tensors, a variational approach, proceedings of 1st IEEE international workshop on computational advances of multi-tensor adaptive processing, 129–132 (2005)

  28. Ng, M., Qi, L., Zhou, G.: Finding the largest eigenvalue of a nonnegative tensor. SIAM J. Matrix Anal. Appl. 31, 1090–1099 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  29. Ni, Q., Qi, L., Wang, F.: An eigenvalue method for testing positive definiteness of a multivariate form. IEEE Trans. Autom. Control 53, 1096–1107 (2008)

    Article  MathSciNet  Google Scholar 

  30. Ni, Q., Qi, L.: A quadratically convergent algorithm for finding the largest eigenvalue of a nonnegative homogeneous polynomial map. J. Glob. Optim. 61, 627–641 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  31. Ni, G., Qi, L., Bai, M.: Geometric measure of entanglement and U-eigenvalues of tensors. SIAM J. Matrix Anal. Appl. 35, 73–87 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  32. Nie, J., Wang, L.: Semidefinite relaxations for best rank-1 tensor approximations. SIAM J. Matrix Anal. Appl. 35, 1155–1179 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  33. Papy, J.M., De Lathauwer, L., Van Huffel, S.: Exponential data fitting using multilinear algebra: the single-channel and multi-channel case. Numer. Linear Algebra Appl. 12, 809–826 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  34. Papy, J.M., De Lathauwer, L., Van Huffel, S.: Exponential data fitting using multilinear algebra: the decimative case. J. Chemom. 23, 341–351 (2009)

    Article  Google Scholar 

  35. Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40, 1302–1324 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  36. Qi, L.: Eigenvalues and invariants of tensor. J. Math. Anal. Appl. 325, 1363–1377 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  37. Qi, L., Han, D., Wu, E.X.: Principal invariants and inherent parameters of diffusion kurtosis tensors. J. Math. Anal. Appl. 349, 165–180 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  38. Qi, L., Wang, F., Wang, Y.: Z-eigenvalue methods for a global polynomial optimization problem. Math. Program. 118, 301–316 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  39. Qi, L., Wang, Y., Wu, E.X.: D-eigenvalues of diffusion kurtosis tensors. J. Comput. Appl. Math. 221, 150–157 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  40. Qi, L., Yu, G., Wu, E.X.: Higher order positive semi-definite diffusion tensor imaging. SIAM J. Imaging Sci. 3, 416–433 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  41. Qi, L., Yu, G., Xu, Y.: Nonnegative diffusion orientation distribution function. J. Math. Imaging Vis. 45, 103–113 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  42. Schultz, T., Seidel, H.-P.: Estimating crossing fibers: a tensor decomposition approach. IEEE Trans. Vis. Comput. Graph. 14, 1635–1642 (2008)

    Article  Google Scholar 

  43. Song, Y., Qi, L.: Tensor complementarity problem and semi-positive tensors. J. Optim. Theory Appl. 165(3), 854–873 (2015)

    Article  MathSciNet  Google Scholar 

  44. Song, Y., Yu, G.: Properties of solution set of tensor complementarity problem. J. Optim. Theory Appl. doi:10.1007/s10957-016-0907-0

  45. Sun, L., Ji, S., Ye, J.: Hypergraph spectral learning for multi-label classification. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, ACM, pp. 668–676 (2008)

  46. Yang, L., Yang, Q., Zhao, X.: Quadratic third-order tensor optimization problem with quadratic constraints. Stat Optim Inf Comput 2, 130–146 (2014)

    Article  MathSciNet  Google Scholar 

  47. Yang, Q., Yang, Y.: Further results for Perron–Frobenius theorem for nonnegative tensors II. SIAM J. Matrix Anal. Appl. 32, 1236–1250 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  48. Yang, Y., Yang, Q.: Further results for Perron–Frobenius theorem for nonnegative tensors. SIAM J. Matrix Anal. Appl. 31, 2517–2530 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  49. Xie, J., Chang, A.: H-eigenvalues of the signless Laplacian tensor for an even uniform hypergraph. Front. Math. China 8, 107–127 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  50. Zeng, M., Ni, Q.: Quasi-Newton method for computing Z-eigenpairs of a symmetric tensor. Pac. J. Optim. 11, 279–290 (2015)

    MathSciNet  MATH  Google Scholar 

  51. Zhang, F., Zhou, B., Peng, L.: Gradient skewness tensors and local illumination detection for images. J. Comput. Appl. Math. 237, 663–671 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  52. Zhang, L., Qi, L.: Linear convergence of an algorithm for computing the largest eigenvalue of a nonnegative tensor. Numer. Linear Algebra Appl. 19, 830–841 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  53. Zhang, L., Qi, L., Xu, Y.: Finding the largest eigenvalue of an irreducible nonnegative tensor and linear convergence for weakly positive tensors. J. Comput. Math. 30, 24–33 (2012)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (Nos. 61262026, 61263011, 11571095, 11501100), NCET Programm of the Ministry of Education (NCET 13-0738), JGZX programm of Jiangxi Province (20112BCB23027), Natural Science Foundation of Jiangxi Province (20132BAB201026), science and technology programm of Jiangxi Education Committee (LDJH12088), Program for Innovative Research Team in University of Henan Province (14IRTSTHN023), the frontier and key technology innovation project of Guangdong Province (No. 2014B010118003, 2015B010106008).

Author information

Author notes

    Authors and Affiliations

    1. School of Mathematics and Computer Sciences, Gannan Normal University, Ganzhou, 341000, China

      Gaohang Yu & Zefeng Yu

    2. Department of Mathematics, Southeast University, Nanjing, China

      Yi Xu

    3. School of Mathematics and Information Science and Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang, China

      Yisheng Song

    4. Department of Biomedical Engineering, Zhongshan School of Medicine, Sun Yat-Sen University, Guangzhou, China

      Yi Zhou

    Authors
    1. Gaohang Yu
      View author publications

      You can also search for this author in PubMed Google Scholar

    2. Zefeng Yu
      View author publications

      You can also search for this author in PubMed Google Scholar

    3. Yi Xu
      View author publications

      You can also search for this author in PubMed Google Scholar

    4. Yisheng Song
      View author publications

      You can also search for this author in PubMed Google Scholar

    5. Yi Zhou
      View author publications

      You can also search for this author in PubMed Google Scholar

    Corresponding author

    Correspondence to Gaohang Yu.

    Additional information

    Gaohang Yu, Zefeng Yu, Yi Xu, Yisheng Song, Yi Zhou have contributed equally to the paper.

    Rights and permissions

    Reprints and permissions

    About this article

    Check for updates. Verify currency and authenticity via CrossMark

    Cite this article

    Yu, G., Yu, Z., Xu, Y. et al. An adaptive gradient method for computing generalized tensor eigenpairs. Comput Optim Appl 65, 781–797 (2016). https://doi.org/10.1007/s10589-016-9846-9

    Download citation

    • Received:

    • Published:

    • Issue Date:

    • DOI: https://doi.org/10.1007/s10589-016-9846-9

    Keywords

    Search

    Navigation