SpringerLink
Log in

On the tensor spectral \({\textbf{p}}\)-norm and its higher order power method

  • Published:
Calcolo Aims and scope Submit manuscript

Abstract

Tensor spectral \({\textbf{p}}\)-norms are generalizations of matrix induced norms. Matrix induced norms are an important type of matrix norms, and tensor spectral \({\textbf{p}}\)-norms are also important in applications. We discuss some basic properties of tensor spectral \({\textbf{p}}\)-norms. We extend the submultiplicativity of the matrix spectral 2-norm to the tensor case, based on which we give a bound of the tensor spectral 2-norm and provide a fast method for computing spectral 2-norms of sum-of-squares tensors. To compute tensor spectral \({\textbf{p}}\)-norms, we propose a higher order power method. Experiments show the high efficiency of the proposed methods and numerical results on spectral \({\textbf{p}}\)-norms of random tensors are also given.

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
EUR 32.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 includes VAT (Thailand)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Fig. 2

Similar content being viewed by others

Data availability

The datasets analysed during the current study are synthetic and generated randomly.

References

  1. Allen-Zhu, Z., Gelashvili, R., Razenshteyn, I.: Restricted isometry property for general p-norms. IEEE Trans. Inf. Theory 62(10), 5839–5854 (2016)

    Article  MathSciNet  Google Scholar 

  2. Bader, B.W., Kolda, T.G., et al.: MATLAB Tensor Toolbox Version 3.0-dev. https://www.tensortoolbox.org (2017)

  3. Banach, S.: Über homogene Polynome in (\(L^2\)). Stud. Math. 7(1), 36–44 (1938)

    Article  Google Scholar 

  4. Boyd, D.W.: The power method for lp norms. Linear Algebra Appl. 9, 95–101 (1974)

    Article  MathSciNet  Google Scholar 

  5. Cao, S., He, S., Li, Z., Wang, Z.: Extreme ratio between spectral and Frobenius norms of nonnegative tensors. SIAM J. Matrix Anal. Appl. 44(2), 919–944 (2023)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  7. Chen, B., Li, Z.: On the tensor spectral \(p\)-norm and its dual norm via partitions. Comput. Optim. Appl. 75(3), 609–628 (2020)

    Article  MathSciNet  Google Scholar 

  8. Cobos, F., Kühn, T., Peetre, J.: On \({\mathfrak{G}}_p\)-classes of trilinear forms. J. Lond. Math. Soc. 59(3), 1003–1022 (1999)

    Article  Google Scholar 

  9. De Lathauwer, L., De Moor, B., Vandewalle, J.: On the best rank-1 and rank-\((R_1, R_2,\ldots , R_N)\) approximation of higher-order tensors. SIAM J. Matrix Anal. Appl. 21(4), 1324–1342 (2000)

    Article  MathSciNet  Google Scholar 

  10. Fasino, D., Tudisco, F.: Ergodicity coefficients for higher-order stochastic processes. SIAM J. Math. Data Sci. 2(3), 740–769 (2020)

    Article  MathSciNet  Google Scholar 

  11. Friedland, S.: Best rank one approximation of real symmetric tensors can be chosen symmetric. Front. Math. China 8(1), 19–40 (2013)

    Article  MathSciNet  Google Scholar 

  12. Friedland, S., Lim, L.-H.: Nuclear norm of higher-order tensors. Math. Comput. 87(311), 1255–1281 (2018)

    Article  MathSciNet  Google Scholar 

  13. Friedland, S., Lim, L.-H., Zhang, J.: Grothendieck constant is norm of Strassen matrix multiplication tensor. Numer. Math. 143(4), 905–922 (2019)

    Article  MathSciNet  Google Scholar 

  14. Friedland, S., Wang, L.: Spectral norm of a symmetric tensor and its computation. Math. Comput. 89(325), 2175–2215 (2020)

    Article  MathSciNet  Google Scholar 

  15. Gautier, A., Hein, M., Tudisco, F.: The global convergence of the nonlinear power method for mixed-subordinate matrix norms. J. Sci. Comput. 88(1), 1–28 (2021)

    Article  MathSciNet  Google Scholar 

  16. Gautier, A., Tudisco, F.: The contractivity of cone-preserving multilinear map**s. Nonlinearity 32(12), 4713 (2019)

    Article  MathSciNet  Google Scholar 

  17. Gautier, A., Tudisco, F., Hein, M.: The Perron–Frobenius theorem for multihomogeneous map**s. SIAM J. Matrix Anal. Appl. 40(3), 1179–1205 (2019)

    Article  MathSciNet  Google Scholar 

  18. Gautier, A., Tudisco, F., Hein, M.: A unifying Perron–Frobenius theorem for nonnegative tensors via multihomogeneous maps. SIAM J. Matrix Anal. Appl. 40(3), 1206–1231 (2019)

    Article  MathSciNet  Google Scholar 

  19. Gautier, A., Tudisco, F., Hein, M.: Nonlinear Perron–Frobenius theorems for nonnegative tensors. SIAM Rev. 65(2), 495–536 (2023)

    Article  MathSciNet  Google Scholar 

  20. Golub, G.H., Van Loan, C.F.: Matrix Computations. JHU Press, Baltimore, Maryland. (2013)

  21. Hendrickx, J.M., Olshevsky, A.: Matrix \(p\)-norms are NP-hard to approximate if \(p\ne 1,2,\infty \). SIAM J. Matrix Anal. Appl. 31(5), 2802–2812 (2010)

    Article  MathSciNet  Google Scholar 

  22. Higham, N.J.: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia (2002)

    Book  Google Scholar 

  23. Higham, N.J., Relton, S.D.: Estimating the largest elements of a matrix. SIAM J. Sci. Comput. 38(5), C584–C601 (2016)

    Article  MathSciNet  Google Scholar 

  24. Hillar, C.J., Lim, L.-H.: Most tensor problems are NP-hard. J. ACM (JACM) 60(6), 45 (2013)

    Article  MathSciNet  Google Scholar 

  25. Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (2012)

    Book  Google Scholar 

  26. Hou, K., So, A.M.-C.: Hardness and approximation results for \(L_p\)-ball constrained homogeneous polynomial optimization problems. Math. Oper. Res. 39(4), 1084–1108 (2014)

    Article  MathSciNet  Google Scholar 

  27. Hu, S.: Relations of the nuclear norm of a tensor and its matrix flattenings. Linear Algebra Appl. 478, 188–199 (2015)

    Article  MathSciNet  Google Scholar 

  28. Hu, S., Li, G.: Convergence rate analysis for the higher order power method in best rank one approximations of tensors. Numer. Math. 140(4), 993–1031 (2018)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  30. Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455–500 (2009)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  32. Kruskal, J.B.: Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra Appl. 18(2), 95–138 (1977)

    Article  MathSciNet  Google Scholar 

  33. Latała, R.: Some estimates of norms of random matrices. Proc. Am. Math. Soc. 133(5), 1273–1282 (2005)

    Article  MathSciNet  Google Scholar 

  34. Latała, R., Strzelecka, M.: Operator \(\ell _p\rightarrow \ell _q\) norms of random matrices with iid entries. ar**v preprint. https://doi.org/10.48550/ar**v.2401.09814 (2024)

  35. Li, Z.: Bounds on the spectral norm and the nuclear norm of a tensor based on tensor partitions. SIAM J. Matrix Anal. Appl. 37(4), 1440–1452 (2016)

    Article  MathSciNet  Google Scholar 

  36. Li, Z., Nakatsukasa, Y., Soma, T., Uschmajew, A.: On orthogonal tensors and best rank-one approximation ratio. SIAM J. Matrix Anal. Appl. 39(1), 400–425 (2018)

    Article  MathSciNet  Google Scholar 

  37. Li, Z., Zhao, Y.-B.: On norm compression inequalities for partitioned block tensors. Calcolo 57(1), 1–27 (2020)

    Article  MathSciNet  Google Scholar 

  38. Lim, L.-H.: Singular values and eigenvalues of tensors: a variational approach. In: 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, New York City. 2005, pp. 129–132. IEEE (2005)

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

    Article  MathSciNet  Google Scholar 

  40. Nguyen, Q., Tudisco, F., Gautier, A., Hein, M.: An efficient multilinear optimization framework for hypergraph matching. IEEE Trans. Pattern Anal. Mach. Intell. 39(6), 1054–1075 (2016)

    Article  Google Scholar 

  41. Ni, G.: Hermitian tensor and quantum mixed state. ar**v preprint. https://doi.org/10.48550/ar**v.1902.02640 (2019)

  42. Nie, J., Yang, Z.: Hermitian tensor decompositions. SIAM J. Matrix Anal. Appl. 41(3), 1115–1144 (2020)

    Article  MathSciNet  Google Scholar 

  43. Nikiforov, V.: Combinatorial methods for the spectral \(p\)-norm of hypermatrices. Linear Algebra Appl. 529, 324–354 (2017)

    Article  MathSciNet  Google Scholar 

  44. Qi, L.: The best rank-one approximation ratio of a tensor space. SIAM J. Matrix Anal. Appl. 32(2), 430–442 (2011)

    Article  MathSciNet  Google Scholar 

  45. Seginer, Y.: The expected norm of random matrices. Comb. Probab. Comput. 9(2), 149–166 (2000)

    Article  MathSciNet  Google Scholar 

  46. Sidiropoulos, N.D., Bro, R.: On the uniqueness of multilinear decomposition of N-way arrays. J. Chemom.: J. Chemom. Soc. 14(3), 229–239 (2000)

    Article  Google Scholar 

  47. Steinberg, D.: Computation of matrix norms with applications to robust optimization. Research thesis, Technion-Israel University of Technology, 2 (2005)

  48. Tudisco, F., Arrigo, F., Gautier, A.: Node and layer eigenvector centralities for multiplex networks. SIAM J. Appl. Math. 78(2), 853–876 (2018)

    Article  MathSciNet  Google Scholar 

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

    MathSciNet  Google Scholar 

  50. Van Handel, R.: On the spectral norm of Gaussian random matrices. Trans. Am. Math. Soc. 369(11), 8161–8178 (2017)

    Article  MathSciNet  Google Scholar 

  51. Vannieuwenhoven, N., Nicaise, J., Vandebril, R., Meerbergen, K.: On generic nonexistence of the Schmidt–Eckart–Young decomposition for complex tensors. SIAM J. Matrix Anal. Appl. 35(3), 886–903 (2014)

    Article  MathSciNet  Google Scholar 

  52. Wang, L., Chu, M.T.: On the global convergence of the alternating least squares method for rank-one approximation to generic tensors. SIAM J. Matrix Anal. Appl. 35(3), 1058–1072 (2014)

    Article  MathSciNet  Google Scholar 

  53. Wang, M., Duc, K.D., Fischer, J., Song, Y.S.: Operator norm inequalities between tensor unfoldings on the partition lattice. Linear Algebra Appl. 520, 44–66 (2017)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  56. Zeng, C.: Further results on tensor nuclear norms. Calcolo 60(3), 34 (2023)

    Article  MathSciNet  Google Scholar 

  57. Zhang, T., Golub, G.H.: Rank-one approximation to high order tensors. SIAM J. Matrix Anal. Appl. 23(2), 534–550 (2001)

    Article  MathSciNet  Google Scholar 

Download references

Funding

This work was partially supported by the National Natural Science Foundation of China (12201319) and the Fundamental Research Funds for the Central Universities, Nankai University (63231142).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences and LPMC, Nankai University, Tian**, China

    Chao Zeng

Authors
  1. Chao Zeng
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Chao Zeng is the single author of the manuscript and responsible for this work.

Corresponding author

Correspondence to Chao Zeng.

Ethics declarations

Conflict of interest

The author declares he/she has no financial interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zeng, C. On the tensor spectral \({\textbf{p}}\)-norm and its higher order power method. Calcolo 61, 38 (2024). https://doi.org/10.1007/s10092-024-00588-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10092-024-00588-y

Keywords

Mathematics Subject Classification

Search

Navigation