|
The cubic spherical optimization problems
Authors:
Xinzhen Zhang, Liqun Qi and Yinyu Ye
Journal:
Math. Comp. 81 (2012), 1513-1525
MSC (2010):
Primary 15A18, 15A69, 90C60
Posted:
February 3, 2012
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
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
- 1.
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
(2003i:90048), http://dx.doi.org/10.1023/A:1020209017701
- 2.
J.F. Cardoso, High-order contrasts for independent component analysis. Neural Computation, 11 (1999), 157-192.
- 3.
P. Comon, Independent component analysis, a new concept? Signal Processing, 36 (1994), 287-314.
- 4.
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
(2011j:90138), http://dx.doi.org/10.1007/s10107-010-0409-z
- 5.
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 (electronic). MR 1896822
(2003a:15029), http://dx.doi.org/10.1137/S0895479801387413
- 6.
L. De Lathauwer, First-order perturbation analysis of the best rank-
 approximation in multilinear algebra. Journal of Chemometrics, 18 (2004), 2-11.
- 7.
Lieven
De Lathauwer, Bart
De Moor, and Joos
Vandewalle, On the best rank-1 and
rank-(𝑅₁,𝑅₂,\𝑐𝑑𝑜𝑡𝑠,𝑅_{𝑁})
approximation of higher-order tensors, SIAM J. Matrix Anal. Appl.
21 (2000), no. 4, 1324–1342 (electronic). MR 1780276
(2001i:15034), http://dx.doi.org/10.1137/S0895479898346995
- 8.
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
(2010h:90087), http://dx.doi.org/10.1137/080729104
- 9.
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.
- 10.
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.
- 11.
J. Nie, Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces. preprint, 2009.
- 12.
Liqun
Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic
Comput. 40 (2005), no. 6, 1302–1324. MR 2178089
(2006j:15031), http://dx.doi.org/10.1016/j.jsc.2005.05.007
- 13.
Liqun
Qi, Fei
Wang, and Yiju
Wang, 𝑍-eigenvalue methods for a global polynomial
optimization problem, Math. Program. 118 (2009),
no. 2, Ser. A, 301–316. MR 2470793
(2009m:90111), http://dx.doi.org/10.1007/s10107-007-0193-6
- 14.
Tong
Zhang and Gene
H. Golub, Rank-one approximation to high order tensors, SIAM
J. Matrix Anal. Appl. 23 (2001), no. 2, 534–550
(electronic). MR
1871328 (2002j:15039), http://dx.doi.org/10.1137/S0895479899352045
- 15.
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
(2011j:94027)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2010):
15A18,
15A69,
90C60
Retrieve articles in all journals
with MSC (2010):
15A18,
15A69,
90C60
Additional 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
DOI:
http://dx.doi.org/10.1090/S0025-5718-2012-02577-4
PII:
S 0025-5718(2012)02577-4
Keywords:
Cubic spherical optimization,
approximation solution,
polynomial time approximation scheme (PTAS)
Received by editor(s):
June 4, 2009 and, in revised form June 2, 2011
Posted:
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
Article copyright:
© Copyright 2012 American Mathematical Society
|
