Dehomogenization for completely positive tensors

Jiawang Nie; Xindong Tang; Zi Yang; Suhan Zhong

doi:10.3934/naco.2022037

Article Contents

2023, Volume 13, Issue 2: 340-363. Doi: 10.3934/naco.2022037

This issue Previous Article On the simultaneous design of broadband beamformer filters and configuration Next Article

Dehomogenization for completely positive tensors

1.
Department of Mathematics, University of California, San Diego, 9500 Gilman Drive, La Jolla, CA, USA, 92093
2.
Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
3.
Department of Electrical & Computer Engineering, University of California, Santa Barbara, CA, USA, 93106
4.
Department of Mathematics, Texas A&M University, College Station, TX, USA, 77843

Suhan Zhong
Suhan Zhong

Received: June 2022

Revised: October 2022

Early access: November 2022

Published: January 2023

Jiawang Nie and Suhan Zhong are partially supported by NSF grant DMS-2110780

Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

A real symmetric tensor is completely positive (CP) if it is a sum of symmetric tensor powers of nonnegative vectors. We propose a dehomogenization approach for studying CP tensors. This gives new Moment-SOS relaxations for CP tensors. Detection for CP tensors and the linear conic optimization with CP tensor cones can be solved more efficiently by the dehomogenization approach.

Keywords:

Mathematics Subject Classification: Primary: 90C23, 15A69, 44A60, 90C22.

Citation:

FullText(HTML)

Table 1. Comparison of some dimensions

(n, k)	$ \binom{n+2k}{2k} $	$ \binom{n-1+2k}{2k} $	$ \binom{n+k}{k} $	$ \binom{n-1+k}{k} $
(2, 2)	15	5	6	3
(2, 3)	28	7	10	4
(2, 4)	45	9	15	5
(3, 2)	35	15	10	6
(3, 3)	84	28	20	10
(3, 4)	165	45	35	15
(4, 2)	70	35	15	10
(4, 3)	210	84	35	20
(4, 4)	495	165	70	35
(5, 2)	126	70	21	15
(5, 3)	462	210	56	35
(5, 4)	1287	495	126	70

| Show Table

DownLoad: CSV

Table 2. Comparison between relaxations (28) and (34)

	With Dehomogenization Relaxation (28)			No Dehomogenization Relaxation (34)
Example	time	accuracy	order	time	accuracy	order
5.1(A)	1.03	$ 1.38\cdot 10^{-6} $	3	2.77	$ 1.71\cdot 10^{-6} $	3
5.1(B)	0.52	$ 1.97\cdot 10^{-6} $	2	0.39	$ 2.05\cdot 10^{-6} $	2
5.1(C)	0.11	not CP	2	0.14	not CP	2
5.2 (ⅰ)	0.22	not CP	4	0.58	not CP	4
5.2(ⅱ)	0.49	$ 4.13\cdot 10^{-6} $	3	1.05	$ 1.54\cdot 10^{-6} $	3
5.3 (ⅰ)	2.22	$ 4.96\cdot 10^{-6} $	3	2.44	$ 5.51\cdot 10^{-6} $	3
5.3(ⅱ)	1.48	$ 9.17\cdot 10^{-8} $	3	2.14	$ 2.10\cdot 10^{-5} $	4
5.4	3.77	$ 1.06\cdot 10^{-9} $	6	36.69	$ 5.54\cdot 10^{-6} $	6

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific, 2003. doi: 10.1142/9789812795212.
[2]	I. M. Bomze, Copositive optimization–Recent developments and applications, European J. Oper. Res., 216 (2012), 509-520. doi: 10.1016/j.ejor.2011.04.026.
[3]	A. Cichocki, R. Zdunek, A. H. Phan and S. Amari, Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multiway Data Analysis and Blind Source Separation, Wiley, New York, 2009.
[4]	P. Comon, G. Golub, L.-H. Lim and B. Mourrain, Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl., 30 (2008), 1254-1279. doi: 10.1137/060661569.
[5]	E. De. Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12 (2002), 875-892. doi: 10.1137/S1052623401383248.
[6]	P. J. Dickinson and L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, Comput. Optim. Appl., 57 (2014), 403-415. doi: 10.1007/s10589-013-9594-z.
[7]	M. Dür, Copositive programming–A survey, in Recent Advances in Optimization and Its Applications in Engineering (eds. M. Diehl, F. Glineur, E. Jarlebring, and W. Michiels), Springer, Berlin, 2010, 3-20.
[8]	J. Fan, J. Nie and A. Zhou, Tensor eigenvalue complementarity problems, Mathematical Programming, 170 (2018), 507-539. doi: 10.1007/s10107-017-1167-y.
[9]	J. Fan, J. Nie and A. Zhou, Completely positive binary tensors, Math. Oper. Res., 44 (2019), 1087-1100. doi: 10.1287/moor.2018.0963.
[10]	J. Fan and A. Zhou, The CP-matrix approximation problem, SIAM J. Matrix Anal. Appl., 37 (2016), 171-194. doi: 10.1137/15M1012086.
[11]	J. Fan and A. Zhou, A semidefinite algorithm for completely positive tensor decomposition, Comput. Optim. Appl., 66 (2017), 267-283. doi: 10.1007/s10589-016-9870-9.
[12]	M. Hall and M. Newman, Copositive and completely positive quadratic forms, Proceedings of the Cambridge Philosophical Society, 59 (1963), 32933.
[13]	D. Henrion and J. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, Positive Polynomials in Control, Springer, Berlin, Heidelberg, (2005), 293-310. doi: 10.1007/10997703_15.
[14]	D. Henrion, J. Lasserre and J. Löfberg, Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24 (2009), 761-779. doi: 10.1080/10556780802699201.
[15]	D. Henrion, M. Korda and J. Lasserre, The Moment-SOS Hierarchy, World Scientific, Singapore, 2020.
[16]	C. Hillar and J. Nie, An elementary and constructive solution to Hilbert's 17th problem for matrices, Proc. Amer. Math. Soc., 136 (2008), 73-76. doi: 10.1090/S0002-9939-07-09068-5.
[17]	J. Landsberg, Tensors: Geometry and Applications, Graduate Studies in Mathematics, 128, AMS, Providence, RI, 2012. doi: 10.1090/gsm/128.
[18]	J. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2000), 796-817. doi: 10.1137/S1052623400366802.
[19]	J. Lasserre, An Introduction to Polynomial and Semi-algebraic Optimization, Cambridge University Press, 2015. doi: 10.1017/CBO9781107447226.
[20]	M. Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Applications, 149, pp. 157–270, Springer, 2009. doi: 10.1007/978-0-387-09686-5_7.
[21]	L. H. Lim, Tensors and Hypermatrices, in Handbook of Linear Algebra (eds. L. Hogben), 2^nd edition, CRC Press, Boca Raton, FL, 2013.
[22]	Z. Luo and L. Qi, Completely positive tensors: properties, easily checkable subclasses, and tractable relaxations, SIAM J. Matrix Anal. Appl., 37 (2016), 1675-1698. doi: 10.1137/15M1025220.
[23]	O. Mason and R. Shorten, On linear copositive Lyapunov functions and the stability of switched positive linear systems, IEEE Trans. Automat. Control, 52 (2007), 1346-1349. doi: 10.1109/TAC.2007.900857.
[24]	J. Nie, Polynomial matrix inequality and semidefinite representation, Math. Oper. Res., 36 (2011), 398-415. doi: 10.1287/moor.1110.0498.
[25]	J. Nie, Certifying convergence of Lasserre's hierarchy via flat truncation, Math. Program., 142 (2013), 485-510. doi: 10.1007/s10107-012-0589-9.
[26]	J. Nie, The $\mathcal{{A}}$-truncated $K$-moment problem, Found. Comput. Math., 14 (2014), 1243-1276. doi: 10.1007/s10208-014-9225-9.
[27]	J. Nie, Optimality conditions and finite convergence of Lasserre's hierarchy, Math. Program., 146 (2014), 97-121. doi: 10.1007/s10107-013-0680-x.
[28]	J. Nie, Linear optimization with cones of moments and nonnegative polynomials, Math. Program., 153 (2015), 247-274. doi: 10.1007/s10107-014-0797-6.
[29]	J. Nie, Tight relaxations for polynomial optimization and Lagrange multiplier expressions, Math. Program., 178 (2019), 1-37. doi: 10.1007/s10107-018-1276-2.
[30]	J. Nie and X. Zhang, Real eigenvalues of nonsymmetric tensors, Comput. Optim. Appl., 70 (2018), 1-32. doi: 10.1007/s10589-017-9973-y.
[31]	J. Nie, Z. Yang and X. Zhang, A complete semidefinite algorithm for detecting copositive matrices and tensors, SIAM J. Optim., 28 (2018), 2902-2921. doi: 10.1137/17M115308X.
[32]	M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42 (1993), 969-984. doi: 10.1512/iumj.1993.42.42045.
[33]	L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238. doi: 10.1016/j.laa.2013.03.015.
[34]	L. Qi, C. Xu and and Y. Xu, Nonnegative tensor factorization, completely positive tensors, and a hierarchical elimination algorithm, SIAM J. Matrix Anal. Appl., 35 (2014), 1227-1241. doi: 10.1137/13092232X.
[35]	A. Shashua and T. Hazan, Non-negative tensor factorization with applications to statistics and computer vision, ACM International Conference Proceeding Series: Proceedings of the 22nd International Conference on Machine Learning, 119 (2005), 792-799.
[36]	J. Sponsel and M. Dür, Factorization and cutting planes for completely positive matrices by copositive projection, Math. Program., 143 (2014), 211-229. doi: 10.1007/s10107-012-0601-4.
[37]	J. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.
[38]	C. Xu, Z. Luo, L. Qi and Z. Chen, $\{0, 1\}$ completely positive tensors and multi-hypergraphs, Linear Algebra Appl., 510 (2016), 110-123. doi: 10.1016/j.laa.2016.08.016.
[39]	T. Zhang and G. H. Golub, Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl., 23 (2001), 534-550. doi: 10.1137/S0895479899352045.
[40]	A. Zhou and J. Fan, The CP-matrix completion problem, SIAM J. Matrix Anal. Appl., 35 (2014), 127-142. doi: 10.1137/130919490.
[41]	A. Zhou and J. Fan, Completely positive tensor recovery with minimal nuclear value, Comput. Optim. Appl., 70 (2018), 419-441. doi: 10.1007/s10589-018-0003-5.