Tightness of a new and enhanced semidefinite relaxation for MIMO detection

Cheng Lu, Ya Feng Liu, Wei Qiang Zhang, Shuzhong Zhang

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

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 semidefnite-relaxation-based (SDR-based) algorithms have been proposed to solve the problem in the literature. In this paper, we frst 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 So in [Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), SIAM, Philadelphia, PA, 2011, pp. 698-711]. Numerical simulation results show that our proposed SDR signifcantly outperforms the conventional SDR in terms of the relaxation gap.

Original languageEnglish (US)
Pages (from-to)719-742
Number of pages24
JournalSIAM Journal on Optimization
Volume29
Issue number1
DOIs
StatePublished - Jan 1 2019

Fingerprint

Semidefinite Relaxation
Tightness
Multiple-input multiple-output (MIMO)
Quadratic programming
Communication
Computer simulation
Quadratic Programming
Annual
Modulus
Numerical Simulation
Unit

Keywords

  • Complex quadratic programming
  • MIMO detection
  • Semidefnite relaxation
  • Tight relaxation

Cite this

Tightness of a new and enhanced semidefinite relaxation for MIMO detection. / Lu, Cheng; Liu, Ya Feng; Zhang, Wei Qiang; Zhang, Shuzhong.

In: SIAM Journal on Optimization, Vol. 29, No. 1, 01.01.2019, p. 719-742.

Research output: Contribution to journalArticle

Lu, Cheng ; Liu, Ya Feng ; Zhang, Wei Qiang ; Zhang, Shuzhong. / Tightness of a new and enhanced semidefinite relaxation for MIMO detection. In: SIAM Journal on Optimization. 2019 ; Vol. 29, No. 1. pp. 719-742.
@article{ddd3cc1eb81b47e790e1ca74389a93c6,
title = "Tightness of a new and enhanced semidefinite relaxation for MIMO detection",
abstract = "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 semidefnite-relaxation-based (SDR-based) algorithms have been proposed to solve the problem in the literature. In this paper, we frst 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 So in [Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), SIAM, Philadelphia, PA, 2011, pp. 698-711]. Numerical simulation results show that our proposed SDR signifcantly outperforms the conventional SDR in terms of the relaxation gap.",
keywords = "Complex quadratic programming, MIMO detection, Semidefnite relaxation, Tight relaxation",
author = "Cheng Lu and Liu, {Ya Feng} and Zhang, {Wei Qiang} and Shuzhong Zhang",
year = "2019",
month = "1",
day = "1",
doi = "10.1137/17M115075X",
language = "English (US)",
volume = "29",
pages = "719--742",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",

}

TY - JOUR

T1 - Tightness of a new and enhanced semidefinite relaxation for MIMO detection

AU - Lu, Cheng

AU - Liu, Ya Feng

AU - Zhang, Wei Qiang

AU - Zhang, Shuzhong

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 semidefnite-relaxation-based (SDR-based) algorithms have been proposed to solve the problem in the literature. In this paper, we frst 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 So in [Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), SIAM, Philadelphia, PA, 2011, pp. 698-711]. Numerical simulation results show that our proposed SDR signifcantly outperforms the conventional SDR in terms of the relaxation gap.

AB - 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 semidefnite-relaxation-based (SDR-based) algorithms have been proposed to solve the problem in the literature. In this paper, we frst 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 So in [Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), SIAM, Philadelphia, PA, 2011, pp. 698-711]. Numerical simulation results show that our proposed SDR signifcantly outperforms the conventional SDR in terms of the relaxation gap.

KW - Complex quadratic programming

KW - MIMO detection

KW - Semidefnite relaxation

KW - Tight relaxation

UR - http://www.scopus.com/inward/record.url?scp=85065445862&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065445862&partnerID=8YFLogxK

U2 - 10.1137/17M115075X

DO - 10.1137/17M115075X

M3 - Article

VL - 29

SP - 719

EP - 742

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 1

ER -