×

Tightness of a new and enhanced semidefinite relaxation for MIMO detection. (English) Zbl 1412.90104

Summary: In this paper, we consider a fundamental problem in modern digital communications known as multiple-input multiple-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefinite-relaxation-based (SDR-based) algorithms have been proposed to solve the problem in the literature. In this paper, we first show that conventional SDR is generally not tight for the problem. Then, we propose a new and enhanced SDR and show its tightness under an easily checkable condition, which essentially requires the level of the noise to be below a certain threshold. The above results have answered an open question posed by A. M. C. So [in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 698–711 (2010; Zbl 1288.94005)]. Numerical simulation results show that our proposed SDR significantly outperforms the conventional SDR in terms of the relaxation gap.

MSC:

90C22 Semidefinite programming
90C20 Quadratic programming
90C46 Optimality conditions and duality in mathematical programming
90C27 Combinatorial optimization

Citations:

Zbl 1288.94005
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] F. Alizadeh, J.-P. A. Haeberly, and M. L. Overton, {\it Complementarity and nondegeneracy in semidefinite programming}, Math. Program., 77 (1997), pp. 111-128. · Zbl 0890.90141
[2] A. S. Bandeira, N. Boumal, and A. Singer, {\it Tightness of the maximum likelihood semidefinite relaxation for angular synchronization}, Math. Program., 163 (2017), pp. 145-167. · Zbl 1365.90188
[3] A. S. Bandeira, Y. Khoo, and A. Singer, {\it Open problem: Tightness of maximum likelihood semidefinite relaxations}, in Proceedings of the 27th Conference on Learning Theory, Proc. Mach. Learn. Res. 35, 2014, pp. 1265-1267; available at .
[4] A. Beck and M. Teboulle, {\it Global optimality conditions for quadratic optimization problems with binary constraints}, SIAM J. Optim., 11 (2000), pp. 179-188. · Zbl 0990.90089
[5] N. Boumal, {\it Nonconvex phase synchronization}, SIAM J. Optim., 26 (2016), pp. 2355-2377. · Zbl 1356.90111
[6] O. Damen, A. Chkeif, and J.-C. Belfiore, {\it Lattice code decoder for space-time codes}, IEEE Commun. Lett., 4 (2000), pp. 161-163.
[7] K. R. Davidson and S. J. Szarek, {\it Local Operator Theory, Random Matrices and Banach Spaces}, in Handbook of the Geometry of Banach Spaces, Vol. I, North-Holland, Amsterdam, 2001, pp. 317-366. · Zbl 1067.46008
[8] X. Fan, J. Song, D. P. Palomar, and O. C. Au, {\it Universal binary semidefinite relaxation for ML signal detection}, IEEE Trans. Commun., 61 (2013), pp. 4565-4576.
[9] F. S. Foucart and H. Rauhut, {\it A Mathematical Introduction to Compressive Sensing}, Birkhäuser, Basel, Switzerland, 2013. · Zbl 1315.94002
[10] M. Goemans and D. Williamson, {\it Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming}, J. ACM, 42 (1995), pp. 1115-1145. · Zbl 0885.68088
[11] M. Goemans and D. Williamson, {\it Approximation algorithms for Max-\(3\)-Cut and other problems via complex semidefinite programming}, J. Comput. Syst. Sci., 68 (2004), pp. 442-470. · Zbl 1093.90038
[12] M. Honig, U. Madhow, and S. Verdu, {\it Blind adaptive multiuser detection}, IEEE Trans. Inf. Theory, 41 (1995), pp. 944-960. · Zbl 0832.94008
[13] S. Jacobsson, G. Durisi, M. Goldstein, and C. Studer, {\it Quantized precoding for massive MU-MIMO}, IEEE Trans. Commun., 65 (2017), pp. 4670-4684.
[14] J. Jaldén, {\it Detection for Multiple Input Multiple Output Channels}, Ph.D. Thesis, School of Electrical Engineering, KTH, Stockholm, Sweden, 2006.
[15] J. Jaldén, C. Martin, and B. Ottersten, {\it Semidefinite programming for detection in linear systems – Optimality conditions and space-time decoding}, in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’03), IEEE Press, Piscataway, NJ, 2003, pp. 9-12.
[16] J. Jaldén and B. Ottersten, {\it The diversity order of the semidefinite relaxation detector}, IEEE Trans. Inf. Theory, 54 (2008), pp. 1406-1422. · Zbl 1328.94024
[17] M. Kisialiou and Z.-Q. Luo, {\it Performance analysis of quasi-maximum-likelihood detector based on semi-definite programming}, in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’05), IEEE Press, Piscataway, NJ, 2005, pp. 433-436.
[18] M. Kisialiou and Z.-Q. Luo, {\it Probabilistic analysis of semidefinite relaxation for binary quadratic minimization}, SIAM J. Optim., 20 (2010), pp. 1906-1922. · Zbl 1229.90117
[19] R. Kohno, H. Imai, and M. Hatori, {\it Cancellation techniques of co-channel interference in asynchronous spread spectrum multiple access systems}, Trans. IECE Japan, 66-A (1983), pp. 416-423.
[20] C. Lemarechal and F. Oustry, {\it SDP relaxations in combinatorial optimization from a Lagrangian point of view}, in Advances in Convex Analysis and Global Optimization, N. Hadijsavvas and P. M. Paradalos, eds., Kluwer, Norwell, MA, 2001, pp. 119-134. · Zbl 1160.90639
[21] H. Liu, M.-C. Yue, and A. M.-C. So, {\it On the estimation performance and convergence rate of the generalized power method for phase synchronization}, SIAM J. Optim., 27 (2017), pp. 2426-2446. · Zbl 1387.90199
[22] H. Liu, M.-C. Yue, and A. M.-C. So, {\it A discrete first-order method for large-scale MIMO detection with provable guarantees}, in Proceedings of the 18th IEEE Workshop on Signal Processing Advances in Wireless Communications (SPAWC’17), IEEE Press, Piscataway, NJ, 2017, pp. 669-673.
[23] Y.-F. Liu, M. Hong, and Y.-H. Dai, {\it Max-min fairness linear transceiver design problem for a multi-user SIMO interference channel is polynomial time solvable}, IEEE Signal Process. Lett., 20 (2013), pp. 27-30.
[24] C. Lu and Y.-F. Liu, {\it An efficient global algorithm for single-group multicast beamforming}, IEEE Trans. Signal Process., 65 (2017), pp. 3761-3774. · Zbl 1414.94388
[25] C. Lu, Y.-F. Liu, and J. Zhou, {\it An efficient global algorithm for nonconvex complex quadratic problems with applications in wireless communications}, in Proceedings of the 6th IEEE/CIC International Conference on Communications in China (ICCC’17), IEEE Press, Piscataway, NJ, 2017, pp. 1-5.
[26] Z.-Q. Luo, W.-K. Ma, A. M.-C. So, Y. Ye, and S. Zhang, {\it Semidefinite relaxation of quadratic optimization problems}, IEEE Signal Process. Mag., 27 (2010), pp. 20-34.
[27] W.-K. Ma, P.-C. Ching, and Z. Ding, {\it Semidefinite relaxation based multiuser detection for M-ary PSK multiuser systems}, IEEE Trans. Signal Process., 52 (2004), pp. 2862-2872.
[28] A. D. Maio, S. D. Nicola, Y. Huang, Z.-Q. Luo, and S. Zhang, {\it Design of phase codes for radar performance optimization with a similarity constraint}, IEEE Trans. Signal Process., 57 (2009), pp. 610-621. · Zbl 1391.94188
[29] A. Mobasher, M. Taherzadeh, R. Sotirov, and A. K. Khandani, {\it A near-maximum-likelihood decoding algorithm for MIMO systems based on semi-definite programming}, IEEE Trans. Inf. Theory, 53 (2007), pp. 3869-3886. · Zbl 1325.94066
[30] A. D. Murugan, H. E. Gamal, M. O. Damen, and G. Caire, {\it A unified framework for tree search decoding: Rediscovering the sequential decoder}, IEEE Trans. Inf. Theory, 52 (2006), pp. 933-953. · Zbl 1317.94159
[31] W. Pu, Y.-F. Liu, J. Yan, H. Liu, and Z.-Q. Luo, {\it Optimal estimation of sensor biases for asynchronous multi-sensor data fusion}, Math. Program. 170 (2018), pp. 357-386. · Zbl 1391.90580
[32] K. S. Schneider, {\it Optimum detection of code division multiplexed signals}, IEEE Trans. Aerosp. Electron. Syst., 15 (1979), pp. 181-185.
[33] N. Z. Shor and A. S. Davydov, {\it Method of obtaining estimates in quadratic extremal problems with Boolean variables}, Cybern. Syst. Anal., 21 (1985), pp. 207-210. · Zbl 0593.90052
[34] A. Singer, {\it Angular synchronization by eigenvectors and semidefinite programming}, Appl. Comput. Harmon. Anal., 30 (2011), pp. 20-36. · Zbl 1206.90116
[35] A. M.-C. So, {\it Probabilistic analysis of the semidefinite relaxation detector in digital communications}, in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’\(10)\), SIAM, Philadelphia, PA, 2011, pp. 698-711. · Zbl 1288.94005
[36] A. M.-C. So, J. Zhang, and Y. Ye , {\it On approximating complex quadratic optimization problems via semidefinite programs}, Math. Program., 110 (2007), pp. 93-110. · Zbl 1192.90134
[37] F. Sohrabi, Y.-F. Liu, and W. Yu, {\it One-bit precoding and constellation range design for massive MIMO with QAM signaling}, IEEE J. Sel. Topics Signal Process., 12 (2018), pp. 557-570.
[38] M. Soltanalian and P. Stoica, {\it Designing unimodular codes via quadratic optimization}, IEEE Trans. Signal Process., 62 (2014), pp. 1221-1234. · Zbl 1394.94967
[39] J. Sun, Q. Qu, and J. Wright, {\it When are Nonconvex Problems Not Scary?}, preprint, , 2016.
[40] P. H. Tan and L. K. Rasmussen, {\it The application of semidefinite programming for detection in CDMA}, IEEE J. Sel. Areas Commun., 19 (2001), pp. 1442-1449.
[41] M. K. Varanasi, {\it Decision feedback multiuser detection: A systematic approach}, IEEE Trans. Inf. Theory, 45 (1999), pp. 219-240. · Zbl 0947.94008
[42] S. Verdú, {\it Computational complexity of optimum multiuser detection}, Algorithmica, 4 (1989), pp. 303-312. · Zbl 0684.68066
[43] S. Verdú, {\it Multiuser Detection}, Cambridge University Press, New York, 1998. · Zbl 0931.68006
[44] I. Waldspurger, A. Aspremont, and S. Mallat, {\it Phase recovery, MaxCut and complex semidefinite programming}, Math. Program., 149 (2015), pp. 47-81. · Zbl 1329.94018
[45] Z. Xie, R. T. Short, and C. K. Rushforth, {\it A family of suboptimum detectors for coherent multi-user communications}, IEEE J. Sel. Areas Commun., 8 (1990), pp. 683-690.
[46] S. Yang and L. Hanzo, {\it Fifty years of MIMO detection: The road to large-scale MIMOs}, IEEE Commun. Surveys Tuts., 17 (2015), pp. 1941-1988.
[47] S. Zhang and Y. Huang, {\it Complex quadratic optimization and semidefinite programming}, SIAM J. Optim., 16 (2006), pp. 871-890. · Zbl 1113.90115
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.