High-order sum-of-squares structured tensors: theory and applications

Abstract

Tensor decomposition is an important research area with numerous applications in data mining and computational neuroscience. An important class of tensor decomposition is sum-of-squares (SOS) tensor decomposition. SOS tensor decomposition has a close connection with SOS polynomials, and SOS polynomials are very important in polynomial theory and polynomial optimization. In this paper, we give a detailed survey on recent advances of high-order SOS tensors and their applications. It first shows that several classes of symmetric structured tensors available in the literature have SOS decomposition in the even order symmetric case. Then, the SOS-rank for tensors with SOS decomposition and the SOS-width for SOS tensor cones are established. Further, a sharper explicit upper bound of the SOS-rank for tensors with bounded exponent is provided, and the exact SOS-width for the cone consists of all such tensors with SOS decomposition is identified. Some potential research directions in the future are also listed in this paper.

Key words： Sum-of-squares (SOS) tensor; positive semi-definite (PSD) tensor; H-eigenvalue; structured tensor

References

1 Badeau R, Boyer R. Fast multilinear singular value decomposition for structured tensors. SIAM J Matrix Anal Appl, 2008, 30: 1008–1021

2 Browne K, Qiao S, Wei Y. A Lanczos bidiagonalization algorithm for Hankel matrices. Linear Algebra Appl, 2009, 430: 1531–1543

3 Che H, Chen H, Li M. A new simultaneous iterative method with a parameter for solving the extended split equality problem and the extended split equality fixed point problem. Numer Algorithms, 2018, 79: 1231–1256

4 Che H, Chen H, Wang Y. M-positive semi-definiteness and M-positive definiteness of fourth-order partially symmetric Cauchy tensors. J Inequal Appl, 2019, 2019: 32

5 Che H, Chen H, Wang Y. C-eigenvalue inclusion theorems for piezoelectric-type tensors. Appl Math Lett, 2019, 89: 41–49

6 Che H, Wang Y, Li M. A smoothing inexact Newton method for P₀ nonlinear complementarity problem. Front Math China, 2012, 7(6): 1043–1058

7 Chen H. A new extra-gradient method for generalized variational inequality in Euclidean space. Fixed Point Theory Appl, 2013, 2013: 1–11

8 Chen H, Chen Y, Li G, Qi L. A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test. Numer Linear Algebra Appl, 2018, 25: e2125

9 Chen H, Huang Z, Qi L. Copositivity detection of tensors: theory and algorithm. J Optim Theory Appl, 2017, 174: 746–761

10 Chen H, Huang Z, Qi L. Copositive tensor detection and its applications in physics and hypergraphs. Comput Optim Appl, 2018, 69: 133–158

11 Chen H, Li G, Qi L. SOS tensor decomposition: theory and applications. Commun Math Sci, 2016, 8: 2073–2100

12 Chen H, Li G, Qi L. Further results on Cauchy tensors and Hankel tensors. Appl Math Comput, 2016, 275: 50–62

13 Chen H, Qi L. Positive definiteness and semi-definiteness of even order symmetric Cauchy tensors. J Ind Manag Optim, 2015, 11: 1263–1274

14 Chen H, Qi L, Caccetta L, Zhou G. Birkhoff-von Neumann theorem and decomposition for doubly stochastic tensors. Linear Algebra Appl, 2019, 583: 119–133

15 Chen H, Qi L, Song Y. Column sufficient tensors and tensor complementarity problems. Front Math China, 2018, 13(2): 255–276

16 Chen H, Wang Y. A family of higher-order convergent iterative methods for computing the Moore-Penrose inverse. Appl Math Comput, 2011, 218: 4012–4016

17 Chen H, Wang Y. On computing minimal H-eigenvalue of sign-structured tensors. Front Math China, 2017, 12(6): 1289–1302

18 Chen H, Wang Y. High-order copositive tensors and its applications. J Appl Anal Comput, 2018, 8: 1863–1885

19 Chen H, Wang Y, Wang G. Strong convergence of extragradient method for generalized variational inequalities in Hilbert space. J Inequal Appl, 2014, 2014: 223

20 Chen H, Wang Y, Xu Y. An alternative extragradient projection method for quasi- equilibrium problems. J Inequal Appl, 2018, 2018: 26

21 Chen H, Wang Y, Zhao H. Finite convergence of a projected proximal point algorithm for the generalized variational inequalities. Oper Res Lett, 2012, 40: 303–305

22 Chen Y, Qi L, Wang Q. Positive semi-definiteness and sum-of-squares property of fourth order four dimensional Hankel tensors. J Comput Appl Math, 2016, 302: 356–368

23 Ding W, Qi L, Wei Y. Fast Hankel tensor-vector products and application to exponential data fitting. Numer Linear Algebra Appl, 2015, 22: 814–832

24 Ding W, Qi L, Wei Y. Inheritance properties and sum-of-squares decomposition of Hankel tensors: theory and algorithms. BIT, 2017, 57: 169–190

25 Feng D, Sun M, Wang X. A family of conjugate gradient method for large-scale nonlinear equations. J Inequal Appl, 2017, 2017: 236

26 Fidalgo C, Kovacec A. Positive semi-definite diagonal minus tail forms are sums of squares. Math Z, 2011, 269: 629–645

27 Hillar C, Lim L. Most tensor problems are NP-hard. J ACM, 2013, 60: 45

28 Hu S, Li G, Qi L. A tensor analogy of Yuan’s theorem of the alternative and polynomial optimization with sign structure. J Optim Theory Appl, 2016, 168: 446–474

29 Li C, Li Y. Double B tensors and quasi-double B tensors. Linear Algebra Appl, 2015, 466: 343–356

30 Li G, Qi L, Wang Q. Positive semi-definiteness of generalized anti-circulant tensors. Commun Math Sci, 2016, 14(4): 941–952

31 Lian S. Smoothing approximation to l₁ exact penalty function for inequality constrained optimization. Appl Math Comput, 2012, 219(6): 3113–3121

32 Lim L. Singular values and eigenvalues of tensors: a variational approach. In: 2005 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2005, 129–132

33 Liu B, Qu B, Zheng N. A successive projection algorithm for solving the multiple-sets split feasibility problem. Numer Funct Anal Optim, 2014, 35: 1459–1466

34 Luo Z, Qi L. Completely positive tensors: properties, easily checkable subclasses and tractable relaxations. SIAM J Matrix Anal Appl, 2016, 37: 1675–1698

35 Narasimhan M N L. Principles of Continuum Mechanics. New York: John Wiley & Sons, 1993

36 Qi L. Eigenvalue of a real supersymmetric tensor. J Symbolic Comput, 2005, 40: 1302–1324

37 Qi L. Symmetric nonnegative tensors and copositive tensors. Linear Algebra Appl, 2013, 439: 228–238

38 Qi L. Hankel tensors: associated Hankel matrices and Vandermonde decomposition. Commun Math Sci, 2015, 13: 113–125

39 Qi L, Chen H, Chen Y. Tensor Eigenvalues and Their Applications. Adv Mech Math, Vol 39. Singapore: Springer, 2018

40 Qi L, Luo Z. Tensor Analysis: Spectral Theory and Special Tensors. Philadelphia: SIAM, 2017

41 Qi L, Song Y. An even order symmetric B tensor is positive definite. Linear Algebra Appl, 2014, 457: 303–312

42 Qi L, Wang Q, Chen Y. Three dimensional strongly symmetric circulant tensors. Linear Algebra Appl, 2015, 482: 207–220

43 Qi L, Xu C, Xu Y. Nonnegative tensor factorization, completely positive tensors, and a hierarchical elimination algorithm. SIAM J Matrix Anal Appl, 2014, 35: 1227–1241

44 Silva V D, Lim L. Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM J Matrix Anal Appl, 2008, 30(3): 1084–1127

45 Sun M, Wang Y, Liu J. Generalized Peaceman-Rachford splitting method for multiple- block separable convex programming with applications to robust PCA. Calcolo, 2017, 54: 77–94

46 Wang G. Existence-stability theorems for strong vector set-valued equilibrium problems in reflexive Banach space. J Inequal Appl, 2015, 2015: 239

47 Wang G, Zhou G, Caccetta L. Z-eigenvalue inclusion theorems for tensors. Discrete Contin Dyn Syst Ser B, 2017, 22(1): 187–198

48 Wang W, Chen H, Wang Y. A new C-eigenvalue interval for piezoelectric-type tensors. Appl Math Lett, 2020, 100: 106035

49 Wang X. Alternating proximal penalization algorithm for the modified multiple-sets split feasibility problems. J Inequal Appl, 2018, 2018: 48

50 Wang X, Chen H, Wang Y. Solution structures of tensor complementarity problem. Front Math China, 2018, 13(4): 935–945

51 Wang Y, Caccetta L, Zhou G. Convergence analysis of a block improvement method for polynomial optimization over unit spheres. Numer Linear Algebra Appl, 2015, 22: 1059–1076

52 Wang Y, Qi L, Zhang X. A practical method for computing the largest M-eigenvalue of a fourth-order partially symmetric tensor. Numer Linear Algebra Appl, 2009, 16: 589–601

53 Wang Y, Zhang K, Sun H. Criteria for strong H-tensors. Front Math China, 2016, 11(3): 577–592

54 Wei Y, Ding W. Theory and Computation of Tensors: Multi-Dimensional Arrays. London: Elsevier/Academic Press, 2016

55 Xu X, Chan T, Chan C. Optimal option purchase decision of a loss-averse retailer under emergent replenishment. Int J Prod Res, 2019, 57(4): 4594–4620

56 Xu X, Meng Z. Coordination between a supplier and a retailer in terms of prot concession for a two-stage supply chain. Int J Prod Res, 2014, 52(7): 2122–2133

57 Zhang H, Wang Y. A new CQ method for solving split feasibility problem. Front Math China, 2010, 5(1): 37–46

58 Zhang K, Chen H, Zhao P. A potential reduction method for tensor complementarity problem. J Ind Manag Optim, 2019, 15(2): 429–443

59 Zhang K, Wang Y. An H-tensor based iterative scheme for identifying the positive definiteness of multivariate homogeneous forms. J Comput Appl Math, 2016, 305: 1–10

60 Zhang L, Qi L, Zhou G. M-tensors and some applications. SIAM J Matrix Anal Appl, 2014, 35: 437–452

61 Zhou G, Wang G, Qi L, Alqahtani M. A fast algorithm for the spectral radii of weakly reducible nonnegative tensors. Numer Linear Algebra Appl, 2018, 25: e2134