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

doi:10.1007/s11464-020-0833-1

Front. Math. China

2020, Vol. 15

Issue (2) : 255-284 https://doi.org/10.1007/s11464-020-0833-1

SURVEY ARTICLE

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

Haibin CHEN¹(

), Yiju WANG¹, Guanglu ZHOU²

¹. School of Management Science, Qufu Normal University, Rizhao 276826, China
². Department of Mathematics and Statistics, Curtin University, Perth, WA, Australia

Download: PDF(402 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Haibin CHEN

Issue Date: 18 May 2020

Cite this article:

Haibin CHEN,Yiju WANG,Guanglu ZHOU. High-order sum-of-squares structured tensors: theory and applications[J]. Front. Math. China, 2020, 15(2): 255-284.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-020-0833-1
https://academic.hep.com.cn/fmc/EN/Y2020/V15/I2/255

1	R Badeau, R Boyer. Fast multilinear singular value decomposition for structured tensors. SIAM J Matrix Anal Appl, 2008, 30: 1008–1021 https://doi.org/10.1137/060655936
2	K Browne, S Qiao, Y Wei. A Lanczos bidiagonalization algorithm for Hankel matrices. Linear Algebra Appl, 2009, 430: 1531–1543 https://doi.org/10.1016/j.laa.2008.01.012
3	H Che, H Chen, M Li. 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 https://doi.org/10.1007/s11075-018-0482-6
4	H Che, H Chen, Y Wang. M-positive semi-definiteness and M-positive definiteness of fourth-order partially symmetric Cauchy tensors. J Inequal Appl, 2019, 2019: 32 https://doi.org/10.1186/s13660-019-1986-x
5	H Che, H Chen, Y Wang. C-eigenvalue inclusion theorems for piezoelectric-type tensors. Appl Math Lett, 2019, 89: 41–49 https://doi.org/10.1016/j.aml.2018.09.014
6	H Che, Y Wang, M Li. A smoothing inexact Newton method for P0 nonlinear complementarity problem. Front Math China, 2012, 7(6): 1043–1058 https://doi.org/10.1007/s11464-012-0245-y
7	H Chen. A new extra-gradient method for generalized variational inequality in Euclidean space. Fixed Point Theory Appl, 2013, 2013: 1–11 https://doi.org/10.1186/1687-1812-2013-139
8	H Chen, Y Chen, G Li, L Qi. 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 https://doi.org/10.1002/nla.2125
9	H Chen, Z Huang, L Qi. Copositivity detection of tensors: theory and algorithm. J Optim Theory Appl, 2017, 174: 746–761 https://doi.org/10.1007/s10957-017-1131-2
10	H Chen, Z Huang, L Qi. Copositive tensor detection and its applications in physics and hypergraphs. Comput Optim Appl, 2018, 69: 133–158 https://doi.org/10.1007/s10589-017-9938-1
11	H Chen, G Li, L Qi. SOS tensor decomposition: theory and applications. Commun Math Sci, 2016, 8: 2073–2100 https://doi.org/10.4310/CMS.2016.v14.n8.a1
12	H Chen, G Li, L Qi. Further results on Cauchy tensors and Hankel tensors. Appl Math Comput, 2016, 275: 50–62 https://doi.org/10.1016/j.amc.2015.11.051
13	H Chen, L Qi. Positive definiteness and semi-definiteness of even order symmetric Cauchy tensors. J Ind Manag Optim, 2015, 11: 1263–1274 https://doi.org/10.3934/jimo.2015.11.1263
14	H Chen, L Qi, L Caccetta, G Zhou. Birkhoff-von Neumann theorem and decomposition for doubly stochastic tensors. Linear Algebra Appl, 2019, 583: 119–133 https://doi.org/10.1016/j.laa.2019.08.027
15	H Chen, L Qi, Y Song. Column sufficient tensors and tensor complementarity problems. Front Math China, 2018, 13(2): 255–276 https://doi.org/10.1007/s11464-018-0681-4
16	H Chen, Y Wang. A family of higher-order convergent iterative methods for computing the Moore-Penrose inverse. Appl Math Comput, 2011, 218: 4012–4016 https://doi.org/10.1016/j.amc.2011.05.066
17	H Chen, Y Wang. On computing minimal H-eigenvalue of sign-structured tensors. Front Math China, 2017, 12(6): 1289–1302 https://doi.org/10.1007/s11464-017-0645-0
18	H Chen, Y Wang. High-order copositive tensors and its applications. J Appl Anal Comput, 2018, 8: 1863–1885
19	H Chen, Y Wang, G Wang. Strong convergence of extragradient method for generalized variational inequalities in Hilbert space. J Inequal Appl, 2014, 2014: 223 https://doi.org/10.1186/1029-242X-2014-223
20	H Chen, Y Wang, Y Xu. An alternative extragradient projection method for quasi- equilibrium problems. J Inequal Appl, 2018, 2018: 26 https://doi.org/10.1186/s13660-018-1619-9
21	H Chen, Y Wang, H Zhao. Finite convergence of a projected proximal point algorithm for the generalized variational inequalities. Oper Res Lett, 2012, 40: 303–305 https://doi.org/10.1016/j.orl.2012.03.011
22	Y Chen, L Qi, Q Wang. Positive semi-definiteness and sum-of-squares property of fourth order four dimensional Hankel tensors. J Comput Appl Math, 2016, 302: 356–368 https://doi.org/10.1016/j.cam.2016.02.019
23	W Ding, L Qi, Y Wei. Fast Hankel tensor-vector products and application to exponential data fitting. Numer Linear Algebra Appl, 2015, 22: 814–832 https://doi.org/10.1002/nla.1970
24	W Ding, L Qi, Y Wei. Inheritance properties and sum-of-squares decomposition of Hankel tensors: theory and algorithms. BIT, 2017, 57: 169–190 https://doi.org/10.1007/s10543-016-0622-0
25	D Feng, M Sun, X Wang. A family of conjugate gradient method for large-scale nonlinear equations. J Inequal Appl, 2017, 2017: 236 https://doi.org/10.1186/s13660-017-1510-0
26	C Fidalgo, A Kovacec. Positive semi-definite diagonal minus tail forms are sums of squares. Math Z, 2011, 269: 629–645 https://doi.org/10.1007/s00209-010-0753-y
27	C Hillar, L Lim. Most tensor problems are NP-hard. J ACM, 2013, 60: 45 https://doi.org/10.1145/2512329
28	S Hu, G Li, L Qi. A tensor analogy of Yuan’s theorem of the alternative and polynomial optimization with sign structure. J Optim Theory Appl, 2016, 168: 446–474 https://doi.org/10.1007/s10957-014-0652-1
29	C Li, Y Li. Double B tensors and quasi-double B tensors. Linear Algebra Appl, 2015, 466: 343–356 https://doi.org/10.1016/j.laa.2014.10.027
30	G Li, L Qi, Q Wang. Positive semi-definiteness of generalized anti-circulant tensors. Commun Math Sci, 2016, 14(4): 941–952 https://doi.org/10.4310/CMS.2016.v14.n4.a3
31	S Lian. Smoothing approximation to l1 exact penalty function for inequality constrained optimization. Appl Math Comput, 2012, 219(6): 3113–3121 https://doi.org/10.1016/j.amc.2012.09.042
32	L Lim. 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	B Liu, B Qu, N Zheng. A successive projection algorithm for solving the multiple-sets split feasibility problem. Numer Funct Anal Optim, 2014, 35: 1459–1466 https://doi.org/10.1080/01630563.2014.895755
34	Z Luo, L Qi. Completely positive tensors: properties, easily checkable subclasses and tractable relaxations. SIAM J Matrix Anal Appl, 2016, 37: 1675–1698 https://doi.org/10.1137/15M1025220
35	M N L Narasimhan. Principles of Continuum Mechanics. New York: John Wiley & Sons, 1993
36	L Qi. Eigenvalue of a real supersymmetric tensor. J Symbolic Comput, 2005, 40: 1302–1324 https://doi.org/10.1016/j.jsc.2005.05.007
37	L Qi. Symmetric nonnegative tensors and copositive tensors. Linear Algebra Appl, 2013, 439: 228–238 https://doi.org/10.1016/j.laa.2013.03.015
38	L Qi. Hankel tensors: associated Hankel matrices and Vandermonde decomposition. Commun Math Sci, 2015, 13: 113–125 https://doi.org/10.4310/CMS.2015.v13.n1.a6
39	L Qi, H Chen, Y Chen. Tensor Eigenvalues and Their Applications. Adv Mech Math, Vol 39. Singapore: Springer, 2018
40	L Qi, Z Luo. Tensor Analysis: Spectral Theory and Special Tensors. Philadelphia: SIAM, 2017 https://doi.org/10.1137/1.9781611974751
41	L Qi, Y Song. An even order symmetric B tensor is positive definite. Linear Algebra Appl, 2014, 457: 303–312 https://doi.org/10.1016/j.laa.2014.05.026
42	L Qi, Q Wang, Y Chen. Three dimensional strongly symmetric circulant tensors. Linear Algebra Appl, 2015, 482: 207–220 https://doi.org/10.1016/j.laa.2015.05.024
43	L Qi, C Xu, Y Xu. Nonnegative tensor factorization, completely positive tensors, and a hierarchical elimination algorithm. SIAM J Matrix Anal Appl, 2014, 35: 1227–1241 https://doi.org/10.1137/13092232X
44	V D Silva, L Lim. Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM J Matrix Anal Appl, 2008, 30(3): 1084–1127 https://doi.org/10.1137/06066518X
45	M Sun, Y Wang, J Liu. Generalized Peaceman-Rachford splitting method for multiple- block separable convex programming with applications to robust PCA. Calcolo, 2017, 54: 77–94 https://doi.org/10.1007/s10092-016-0177-0
46	G Wang. Existence-stability theorems for strong vector set-valued equilibrium problems in reflexive Banach space. J Inequal Appl, 2015, 2015: 239 https://doi.org/10.1186/s13660-015-0760-y
47	G Wang, G Zhou, L Caccetta. Z-eigenvalue inclusion theorems for tensors. Discrete Contin Dyn Syst Ser B, 2017, 22(1): 187–198 https://doi.org/10.3934/dcdsb.2017009
48	W Wang, H Chen, Y Wang. A new C-eigenvalue interval for piezoelectric-type tensors. Appl Math Lett, 2020, 100: 106035 https://doi.org/10.1016/j.aml.2019.106035
49	X Wang. Alternating proximal penalization algorithm for the modified multiple-sets split feasibility problems. J Inequal Appl, 2018, 2018: 48 https://doi.org/10.1186/s13660-018-1641-y
50	X Wang, H Chen, Y Wang. Solution structures of tensor complementarity problem. Front Math China, 2018, 13(4): 935–945 https://doi.org/10.1007/s11464-018-0675-2
51	Y Wang, L Caccetta, G Zhou. Convergence analysis of a block improvement method for polynomial optimization over unit spheres. Numer Linear Algebra Appl, 2015, 22: 1059–1076 https://doi.org/10.1002/nla.1996
52	Y Wang, L Qi, X Zhang. A practical method for computing the largest M-eigenvalue of a fourth-order partially symmetric tensor. Numer Linear Algebra Appl, 2009, 16: 589–601 https://doi.org/10.1002/nla.633
53	Y Wang, K Zhang, H Sun. Criteria for strong H-tensors. Front Math China, 2016, 11(3): 577–592 https://doi.org/10.1007/s11464-016-0525-z
54	Y Wei, W Ding. Theory and Computation of Tensors: Multi-Dimensional Arrays. London: Elsevier/Academic Press, 2016
55	X Xu, T Chan, C Chan. Optimal option purchase decision of a loss-averse retailer under emergent replenishment. Int J Prod Res, 2019, 57(4): 4594–4620 https://doi.org/10.1080/00207543.2019.1579935
56	X Xu, Z Meng. 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 https://doi.org/10.1080/00207543.2013.854940
57	H Zhang, Y Wang. A new CQ method for solving split feasibility problem. Front Math China, 2010, 5(1): 37–46 https://doi.org/10.1007/s11464-009-0047-z
58	K Zhang, H Chen, P Zhao. A potential reduction method for tensor complementarity problem. J Ind Manag Optim, 2019, 15(2): 429–443 https://doi.org/10.3934/jimo.2018049
59	K Zhang, Y Wang. An H-tensor based iterative scheme for identifying the positive definiteness of multivariate homogeneous forms. J Comput Appl Math, 2016, 305: 1–10 https://doi.org/10.1016/j.cam.2016.03.025
60	L Zhang, L Qi, G Zhou. M-tensors and some applications. SIAM J Matrix Anal Appl, 2014, 35: 437–452 https://doi.org/10.1137/130915339
61	G Zhou, G Wang, L Qi, M Alqahtani. A fast algorithm for the spectral radii of weakly reducible nonnegative tensors. Numer Linear Algebra Appl, 2018, 25: e2134 https://doi.org/10.1002/nla.2134

[1]	Yizheng FAN, Zhu ZHU, Yi WANG. Least H-eigenvalue of adjacency tensor of hypergraphs with cut vertices[J]. Front. Math. China, 2020, 15(3): 451-465.
[2]	Haibin CHEN, Liqun QI, Yisheng SONG. Column sufficient tensors and tensor complementarity problems[J]. Front. Math. China, 2018, 13(2): 255-276.
[3]	Junjie YUE,Liping ZHANG,Mei LU. Largest adjacency, signless Laplacian, and Laplacian H-eigenvalues of loose paths[J]. Front. Math. China, 2016, 11(3): 623-645.
[4]	Haibin CHEN,Liqun QI. Spectral properties of odd-bipartite Z-tensors and their absolute tensors[J]. Front. Math. China, 2016, 11(3): 539-556.
[5]	Jinshan XIE, An CHANG. H-Eigenvalues of signless Laplacian tensor for an even uniform hypergraph[J]. Front Math Chin, 2013, 8(1): 107-127.

Viewed

Full text

Abstract

Cited

Shared

Discussed