Successive Partial-Symmetric Rank-One Algorithms for Almost Unitarily Decomposable Conjugate Partial-Symmetric Tensors

doi:10.1007/s40305-018-0194-6

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (1): 147-167.doi: 10.1007/s40305-018-0194-6

Special Issue: Vector and tensor optimization

Previous Articles Next Articles

Successive Partial-Symmetric Rank-One Algorithms for Almost Unitarily Decomposable Conjugate Partial-Symmetric Tensors

Tao-Ran Fu¹, Jin-Yan Fan²

1 School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai 200240, China;
2 School of Mathematical Sciences, and MOE-LSC, Shanghai Jiao Tong University, Shanghai 200240, China

Received:2017-11-12 Revised:2018-01-12 Online:2019-03-30 Published:2019-03-30
Contact: Tao-Ran Fu, Jin-Yan Fan E-mail:taoran30@sjtu.edu.cn;jyfan@sjtu.edu.cn
Supported by:
This work was partially supported by the National Natural Science Foundation of China (No. 11571234).

Abstract

Abstract: In this paper, we introduce the almost unitarily decomposable conjugate partial-symmetric tensors, which are different from the commonly studied orthogonally decomposable tensors by involving the conjugate terms in the decomposition and the perturbation term. We not only show that successive rank-one approximation algorithm exactly recovers the unitary decomposition of the unitarily decomposable conjugate partial-symmetric tensors. The perturbation analysis of successive rank-one approximation algorithm for almost unitarily decomposable conjugate partial-symmetric tensors is also provided to demonstrate the robustness of the algorithm.

Key words: Approximation algorithm, Complex tensor, Perturbation analysis

Tao-Ran Fu, Jin-Yan Fan. Successive Partial-Symmetric Rank-One Algorithms for Almost Unitarily Decomposable Conjugate Partial-Symmetric Tensors[J]. Journal of the Operations Research Society of China, 2019, 7(1): 147-167.

TrendMD

References

[1] Kolda, T.G., Bader, B.W.:Tensor decompositions and applications. Siam Rev. 51(3), 455-500(2009)
[2] Anandkumar, A., Ge, R., Hsu, D.J., Kakade, S.M., Telgarsky, M.:Tensor decompositions for learning latent variable models. J. Mach. Learn. Res. 15(1), 2773-2832(2014)
[3] McCullagh, P.:Tensor methods in Statistics. Chapman and Hall, London (1987)
[4] Batselier, K., Liu, H., Wong, N.:A constructive algorithm for decomposing a tensor into a finite sum of orthonormal rank-1 terms. SIAM J. Matrix Anal. Appl. 36(3), 1315-1337(2015)
[5] Kolda, T.G.:Orthogonal tensor decompositions. SIAM J. Matrix Anal. Appl. 23(1), 243-255(2000)
[6] Robeva, E.:Orthogonal decomposition of symmetric tensors. SIAM J. Matrix Anal. Appl. 37(1), 86-102(2016)
[7] Wang, L., Chu, M., Yu, B.:Orthogonal low rank tensor approximation:alternating least squares method and its global convergence. SIAM J. Matrix Anal. Appl. 36(1), 1-19(2015)
[8] Kolda, T.G., Bader, B.W., Kenny, J.:Higher-order web link analysis using multilinear algebra. In:IEEE International Conference on Data Mining, IEEE Computer Society, pp. 242-249(2005)
[9] Wang, Y., Qi, L.:On the successive supersymmetric rank-1 decomposition of higher-order supersymmetric tensors. Numer Linear Algebra Appl. 14(6), 503-519(2007)
[10] Zhang, T., Golub, G.H.:Rank-one approximation to high order tensors. SIAM J. Matrix Anal. Appl. 23(2), 534-550(2006)
[11] Mu, C., Hsu, D., Goldfarb, D.:Successive rank-one approximations for nearly orthogonally decomposable symmetric tensors. SIAM J. Matrix Anal. Appl. 36(4), 1638-1659(2015)
[12] Kolda, T.G.:Symmetric Orthogonal Tensor Decomposition is Trivial (2015). arXiv:1503.01375
[13] Aittomaki, T., Koivunen, V.:Beampattern optimization by minimization of quartic polynomial. In:Proceedings of 2009 IEEE/SP 15th Workshop on Statistical Signal Processing, pp. 437-440(2009)
[14] Hilling, J.J., Sudbery, A.:The geometric measure of multipartite entanglement and the singular values of a hypermatrix. J. Math. Phys. 51(7), 072102(2010)
[15] Josz, C.:Application of Polynomial Optimization to Electricity Transmission Networks. Ph.D. Dissertation, Université Pierre et Marie Curie, Paris (2016)
[16] Boralevi, A., Draisma, J., Horobet, E., Robeva, E.:Orthogonal and unitary tensor decomposition from an algebraic perspective (2015). arXiv:1512.08031
[17] 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)
[18] Mu, C., Hsu, D., Goldfarb, D.:Greedy approaches to symmetric orthogonal tensor decomposition. SIAM J. Matrix Anal. Appl. 38(4), 1210-1226(2017)

Successive Partial-Symmetric Rank-One Algorithms for Almost Unitarily Decomposable Conjugate Partial-Symmetric Tensors

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 9

Recommended Articles

Metrics

Comments

[1]	Ru-Bing Chen, Ling-Fa Lu, Jin-Jiang Yuan, Li-Qi Zhang. Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery [J]. Journal of the Operations Research Society of China, 2020, 8(1): 133-143.
[2]	Yao Xu, Yong Chen, Peng Zhang, Randy Goebel. Approximation Algorithms for Vertex Happiness [J]. Journal of the Operations Research Society of China, 2019, 7(3): 429-448.
[3]	Lu Han · Da-Chuan Xu · Dong-Lei Du·Chen-Chen Wu. A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem [J]. Journal of the Operations Research Society of China, 2017, 5(2): 219-.
[4]	Jian Li· Yu Liu. Approximation Algorithms for Stochastic Combinatorial Optimization Problems [J]. Journal of the Operations Research Society of China, 2016, 4(1): 1-.
[5]	Shi-Sheng Li · Ren-Xia Chen. Scheduling a Bounded Parallel-Batching Machine with Incompatible Job Families and Rejection [J]. Journal of the Operations Research Society of China, 2014, 2(4): 499-.
[6]	Chen-Chen Wu · Da-Chuan Xu · Jia Shu. An Approximation Algorithm for the Stochastic Fault-Tolerant Facility Location Problem [J]. Journal of the Operations Research Society of China, 2013, 1(4): 511-522.
[7]	Jia-Ting Shao · Da-Chuan Xu. An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties [J]. Journal of the Operations Research Society of China, 2013, 1(3): 339-346.
[8]	Dong-Lei Du · Da-Chuan Xu. An Almost Tight Lower Bound for the Scheduling Problem to Meet Two Min-Sum Objectives [J]. Journal of the Operations Research Society of China, 2013, 1(1): 159-.
[9]	Si-Mai He · Zhe-Ning Li · Shu-Zhong Zhang. Approximation Algorithms for Discrete Polynomial Optimization [J]. Journal of the Operations Research Society of China, 2013, 1(1): 3-.