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.

Keywords

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

RIGHTS & PERMISSIONS

2020 Higher Education Press