Zhi-Quan (Tom) Luo is a professor in the Department of Electrical and Computer Engineering at the University of Minnesota (Twin Cities) where he holds an endowed ADC Chair in digital technology. He received his B.Sc. degree in Applied Mathematics in 1984 from Peking University, China, and a Ph.D degree in Operations Research from MIT in 1989. From 1989 to 2003, Dr. Luo was with the Department of Electrical and Computer Engineering, McMaster University, Canada, where he later served as the department head and held a senior Canada Research Chair in Information Processing. His research interests lie in the union of optimization algorithms, data communication and signal processing. Dr. Luo is a fellow of IEEE and SIAM. He is a recipient of the IEEE Signal Processing Society's Best Paper Award in 2004 and 2009, and the EURASIP Best Paper Award in 2011. He was awarded the 2010 Farkas Prize from the INFORMS Optimization Society. Dr. Luo currently chairs the IEEE Signal Processing Society's Technical Committee on Signal Processing for Communications and Networking (SPCOM). He has held editorial positions for several international journals including Journal of Optimization Theory and Applications, Mathematics of Computation, IEEE Transactions on Signal Processing, SIAM Journal on Optimization, Management Sciences and Mathematics of Operations Research.
We consider the NP-hard problem of finding a minimum norm vector in $n$-dimensional real or complex Euclidean space, subject to $m$ concave homogeneous quadratic constraints. We show that the semidefinite programming relaxation for this nonconvex quadratically constrained quadratic program (QP) provides an $O(m^2)$ approximation in the real case, and an $O(m)$ approximation in the complex case. Moreover, we show that these bounds are tight up to a constant factor. When the Hessian of each constraint function is of rank one (namely, outer products of some given so-called {\it steering} vectors) and the phase spread of the entries of these steering vectors are bounded away from $\pi/2$, we establish a certain "constant factor" approximation (depending on the phase spread but independent of $m$ and $n$) for both the SDP relaxation and a convex QP restriction of the original NP-hard problem. When the homogeneous quadratic constraints are separable and $m=n$, we show that the SDP relaxation is actually tight. All theoretical results will be illustrated through a transmit beamforming application in wireless communication.
