The Low-Rank Approximation of Fourth-Order Partial-Symmetric and Conjugate Partial-Symmetric Tensor

doi:10.1007/s40305-022-00425-5

Abstract

Abstract: We present an orthogonal matrix outer product decomposition for the fourth-order conjugate partial-symmetric (CPS) tensor and show that the greedy successive rank-one approximation (SROA) algorithm can recover this decomposition exactly. Based on this matrix decomposition, the CP rank of CPS tensor can be bounded by the matrix rank, which can be applied to low-rank tensor completion. Additionally, we give the rank-one equivalence property for the CPS tensor based on the SVD of matrix, which can be applied to the rank-one approximation for CPS tensors.

Key words: Conjugate partial-symmetric tensor, Approximation algorithm, Rank-one equivalence property, Convex relaxation

CLC Number:

Amina Sabir, Peng-Fei Huang, Qing-Zhi Yang. The Low-Rank Approximation of Fourth-Order Partial-Symmetric and Conjugate Partial-Symmetric Tensor[J]. Journal of the Operations Research Society of China, 2023, 11(4): 735-758.

TrendMD

References

[1] Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455-500 (2009)
[2] De Lathauwer, L., Castaing, J., Cardoso, J.-F.: Fourth-order cumulant-based blind identification of underdetermined mixtures. IEEE Trans. Signal Process. 55(6), 2965-2973 (2007)
[3] Jiang, B., Ma, S., Zhang, S.: Tensor principal component analysis via convex optimization. Math. Program. 150(2), 423-457 (2015)
[4] Hillar, C.J., Lim, L.-H.: Most tensor problems are np-hard. J. ACM 60(6), 1-39 (2013)
[5] 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)
[6] Zhang, X., Ling, C., Qi, L.: The best rank-1 approximation of a symmetric tensor and related spherical optimization problems. SIAM J. Matrix Anal. Appl. 33(3), 806-821 (2012)
[7] 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. 16(7), 589-601 (2009)
[8] Jiang, B., Li, Z., Zhang, S.: Characterizing real-valued multivariate complex polynomials and their symmetric tensor representations. SIAM J. Matrix Anal. Appl. 37(1), 381-408 (2016)
[9] Ni, G.: Hermitian tensors. arXiv:1902.02640v2 (2019)
[10] Nie, J., Yang, Z.: Hermitian tensor decompositions. SIAM J. Matrix Anal. Appl. 41(3), 1115-1144 (2020)
[11] Aubry, A., De Maio, A., Jiang, B., Zhang, S.: Ambiguity function shaping for cognitive radar via complex quartic optimization. IEEE Trans. Signal Process. 61(22), 5603-5619 (2013)
[12] Aittomaki, T., Koivunen, V.: Beampattern optimization by minimization of quartic polynomial. In: 2009 IEEE/SP 15th Workshop on Statistical Signal Processing, pp. 437-440. IEEE (2009)
[13] Madani, R., Lavaei, J., Baldick, R.: Convexification of power flow equations in the presence of noisy measurements. IEEE Trans. Autom. Control 64(8), 3101-3116 (2019)
[14] Fu, T., Jiang, B., Li, Z.: On decompositions and approximations of conjugate partial-symmetric complex tensors. arXiv preprint arXiv:1802.09013 (2018)
[15] Lathauwer, L.D., De Lathauwer, L.: A link between the canonical decomposition in multilinear algebra and simultaneous matrix diagonalization. SIAM J. Matrix Anal. Appl. 28(3), 642-666 (2006)
[16] Jiang, B., Ma, S., Zhang, S.: Low-m-rank tensor completion and robust tensor pca. IEEE J. Selected Topics Signal Process. 12(6), 1390-1404 (2018)
[17] Tisseur, F., Meerbergen, K.: The quadratic eigenvalue problem. Siam rev. Siam Rev. 43(2) (2001)
[18] De Silva, V., Lim, L.-H.: Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM J. Matrix Anal. Appl. 30(3), 1084-1127 (2008)
[19] Wang, Y., Qi, L.: On the successive supersymmetric rank-1 decomposition of higher-order supersymmetric tensors. Numer. Linear Algebra Appl. 14(6), 503-519 (2010)
[20] Zhang, T., Golub, G.H.: Rank-one approximation to high order tensors. SIAM J. Matrix Anal. Appl. 23(2), 534-550 (2001)
[21] Fu, T.R., Fan, J.Y.: Successive partial-symmetric rank-one algorithms for almost unitarily decomposable conjugate partial-symmetric tensors. J. Oper. Res. Soc. China 7(1), 147-167 (2018)
[22] Chen, B., He, S., Li, Z., Zhang, S.: Maximum block improvement and polynomial optimization. SIAM J. Optim. (2012). https://doi.org/10.1137/110834524
[23] Zhang, T., Golub, G.H.: Rank-one approximation to high order tensors. SIAM J. Matrix Anal. Appl. 23(2), 534-550 (2001)
[24] Kolda, T., Mayo, J.: Shifted power method for computing tensor eigenpairs. SIAM J. Matrix Anal. Appl. 32(4), 1095-1124 (2010)
[25] Yuning, Yang, Yunlong, Feng, Xiaolin, Huang, Johan, A.K.: Suykens: Rank-1 tensor properties with applications to a class of tensor optimization problems. SIAM J. Optim. 26(1), 171-196 (2016)
[26] Golub, G.H., Van Loan, C.F.: Matrix computations, 4th edn. Johns Hopkins (2013)
[27] Ma, S., Goldfarb, D., Chen, L.: Fixed point and bregman iterative methods for matrix rank minimization. Math. Program. 128(1-2), 321-353 (2011)
[28] Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1-2), 459-494 (2014)
[29] Cai, J.F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20(4), 1956-1982 (2008)
[30] Wang, Y., Dong, M., Xu, Y.: A sparse rank-1 approximation algorithm for high-order tensors. Appl. Math. Lett. 102, 106140 (2020)
[31] Wang, X., Navasca, C.: Low rank approximation of tensors via sparse optimization. Numer. Linear Algebra Appl. 25(2), (2017). https://doi.org/10.1002/nla.2136
[32] Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471-501 (2010)