The cubic spherical optimization problems
HTML articles powered by AMS MathViewer
- by Xinzhen Zhang, Liqun Qi and Yinyu Ye;
- Math. Comp. 81 (2012), 1513-1525
- DOI: https://doi.org/10.1090/S0025-5718-2012-02577-4
- Published electronically: February 3, 2012
- PDF | Request permission
Abstract:
In this paper, the cubic spherical optimization problems, including the cubic one-spherical/two-spherical/three-spherical optimization problems, are discussed. We first show that the two-spherical optimization problem is a special case of the three-spherical optimization problem. Then we show that the one-spherical optimization problem and the two-spherical optimization problem have the same optimal value when the tensor is symmetric. In addition, NP-hardness of them are established. For the cubic three-spherical optimization problem, we discuss the conditions under which the problem is polynomial time solvable and if the polynomial time approximation scheme (PTAS) exists. Then we present a relative quality bound by finding the largest singular values of matrices. Finally, a practical method for solving the cubic three-spherical optimization problem is proposed and preliminary numerical results are reported.References
- Immanuel M. Bomze and Etienne De Klerk, Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, J. Global Optim. 24 (2002), no. 2, 163–185. Dedicated to Professor Naum Z. Shor on his 65th birthday. MR 1934026, DOI 10.1023/A:1020209017701
- J.F. Cardoso, High-order contrasts for independent component analysis. Neural Computation, 11 (1999), 157–192.
- P. Comon, Independent component analysis, a new concept? Signal Processing, 36 (1994), 287–314.
- Simai He, Zhening Li, and Shuzhong Zhang, Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Math. Program. 125 (2010), no. 2, Ser. B, 353–383. MR 2733568, DOI 10.1007/s10107-010-0409-z
- Eleftherios Kofidis and Phillip A. Regalia, On the best rank-1 approximation of higher-order supersymmetric tensors, SIAM J. Matrix Anal. Appl. 23 (2001/02), no. 3, 863–884. MR 1896822, DOI 10.1137/S0895479801387413
- L. De Lathauwer, First-order perturbation analysis of the best rank-$(R_1, R_2, R_3)$ approximation in multilinear algebra. Journal of Chemometrics, 18 (2004), 2–11.
- Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle, On the best rank-1 and rank-$(R_1,R_2,\cdots ,R_N)$ approximation of higher-order tensors, SIAM J. Matrix Anal. Appl. 21 (2000), no. 4, 1324–1342. MR 1780276, DOI 10.1137/S0895479898346995
- Chen Ling, Jiawang Nie, Liqun Qi, and Yinyu Ye, Biquadratic optimization over unit spheres and semidefinite programming relaxations, SIAM J. Optim. 20 (2009), no. 3, 1286–1310. MR 2546345, DOI 10.1137/080729104
- W.S. Lu and S.C. Pei, On optimal low-rank approximation of multidimensional discrete signals. IEEE Transacations on Circuits and Systems II, 45 (1998), 417–422.
- Yu. Nesterov, Random walk in a simplex and quadratic optimization over convex polytopes. CORE Discussion Paper 2003/71, CORE, Catholic University of Louvain, Louvain-la-Neuve, Belgium, 2003.
- J. Nie, Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces. preprint, 2009.
- Liqun Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (2005), no. 6, 1302–1324. MR 2178089, DOI 10.1016/j.jsc.2005.05.007
- Liqun Qi, Fei Wang, and Yiju Wang, $Z$-eigenvalue methods for a global polynomial optimization problem, Math. Program. 118 (2009), no. 2, Ser. A, 301–316. MR 2470793, DOI 10.1007/s10107-007-0193-6
- Tong Zhang and Gene H. Golub, Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl. 23 (2001), no. 2, 534–550. MR 1871328, DOI 10.1137/S0895479899352045
- Xinzhen Zhang, Chen Ling, Liqun Qi, and Ed Xuekui Wu, The measure of diffusion skewness and kurtosis in magnetic resonance imaging, Pac. J. Optim. 6 (2010), no. 2, 391–404. MR 2668347
Bibliographic Information
- Xinzhen Zhang
- Affiliation: Department of Mathematics, School of Science, Tianjin University, Tianjin, 300072, China.
- Email: xzzhang@tju.edu.cn
- Liqun Qi
- Affiliation: Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong.
- Email: maqilq@polyu.edu.hk
- Yinyu Ye
- Affiliation: Department of Management Science and Engineering, Stanford University, Stanford, CA94305 and The Hong Kong Polytechnic University, Hong Kong.
- Email: yinyu-ye@stanford.edu
- Received by editor(s): June 4, 2009
- Received by editor(s) in revised form: June 2, 2011
- Published electronically: February 3, 2012
- Additional Notes: The first author is supported by the National Natural Science Foundation of China (Grant Nos. 11101303 and 11171180), and Independent Innovation Fund of Tianjin University
The second author is supported by the Hong Kong Research Grant Council - © Copyright 2012 American Mathematical Society
- Journal: Math. Comp. 81 (2012), 1513-1525
- MSC (2010): Primary 15A18, 15A69, 90C60
- DOI: https://doi.org/10.1090/S0025-5718-2012-02577-4
- MathSciNet review: 2904588