Efficient implementation of quasi- maximum-likelihood detection based on semidefinite relaxation

Mikalai Kisialiou; Xiaodong Luo; Zhi Quan Luo

doi:10.1109/TSP.2009.2027741

Efficient implementation of quasi- maximum-likelihood detection based on semidefinite relaxation

Mikalai Kisialiou, Xiaodong Luo, Zhi Quan Luo

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

36 Scopus citations

Abstract

In this paper we develop two quasi-maximum likelihood (ML) channel detectors for multiuser detection: semidefinite relaxation (SDR) detector and phase-shift-keying (PSK) detector. These detectors can deliver near-ML bit error rate (BER) performance with a polynomial worst-case complexity. The SDR detector for binary-phase-shift-keying (BPSK) constellation is based on a convex SDR, whereas the PSK detector for M-PSK constellations is based on a nonconvex low-rank SDR. The SDR detector is implemented using a dual-scaling interior-point method, while the PSK detector is based on a coordinate descent strategy on a feasible region homotopy. We use dynamic dimension reduction and warm start techniques to achieve signal-to-noise ratio (SNR)-sensitive improvements for both detectors. Numerical simulations of BER performance and running time indicate the effectiveness of the two quasi-ML detectors when compared to the conventional sphere decoder and its variants.

Original language	English (US)
Article number	5165035
Pages (from-to)	4811-4822
Number of pages	12
Journal	IEEE Transactions on Signal Processing
Volume	57
Issue number	12
DOIs	https://doi.org/10.1109/TSP.2009.2027741
State	Published - Dec 2009

Bibliographical note

Funding Information:
Manuscript received March 16, 2007; accepted April 28, 2009. First published July 14, 2009; current version published November 18, 2009. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Xiaodong Cai. This research is supported in part by the National Science Foundation, Grant DMS-0610037. A preliminary version of this paper was published in the Proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP), Hong Kong, 2003, vol. 6, pp. VI 561–VI 564, and the Proceedings of the International Conference on Acoustics, Speech and Signal Processing (ICASSP), Philadelphia, PA, 2005, vol. 3, pp. III 433–III 436.

Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.

Keywords

Dimension reduction
Duality
MIMO systems
Maximum-likelihood detection
Semidefinite relaxation (SDR)

Publisher link

10.1109/TSP.2009.2027741

Find It

Find It at U of M Libraries

Cite this

@article{2f39c26b5c7848d2b9e9eb213164363a,

title = "Efficient implementation of quasi- maximum-likelihood detection based on semidefinite relaxation",

abstract = "In this paper we develop two quasi-maximum likelihood (ML) channel detectors for multiuser detection: semidefinite relaxation (SDR) detector and phase-shift-keying (PSK) detector. These detectors can deliver near-ML bit error rate (BER) performance with a polynomial worst-case complexity. The SDR detector for binary-phase-shift-keying (BPSK) constellation is based on a convex SDR, whereas the PSK detector for M-PSK constellations is based on a nonconvex low-rank SDR. The SDR detector is implemented using a dual-scaling interior-point method, while the PSK detector is based on a coordinate descent strategy on a feasible region homotopy. We use dynamic dimension reduction and warm start techniques to achieve signal-to-noise ratio (SNR)-sensitive improvements for both detectors. Numerical simulations of BER performance and running time indicate the effectiveness of the two quasi-ML detectors when compared to the conventional sphere decoder and its variants.",

keywords = "Dimension reduction, Duality, MIMO systems, Maximum-likelihood detection, Semidefinite relaxation (SDR)",

author = "Mikalai Kisialiou and Xiaodong Luo and Luo, {Zhi Quan}",

note = "Funding Information: Manuscript received March 16, 2007; accepted April 28, 2009. First published July 14, 2009; current version published November 18, 2009. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Xiaodong Cai. This research is supported in part by the National Science Foundation, Grant DMS-0610037. A preliminary version of this paper was published in the Proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP), Hong Kong, 2003, vol. 6, pp. VI 561–VI 564, and the Proceedings of the International Conference on Acoustics, Speech and Signal Processing (ICASSP), Philadelphia, PA, 2005, vol. 3, pp. III 433–III 436. Copyright: Copyright 2009 Elsevier B.V., All rights reserved.",

year = "2009",

month = dec,

doi = "10.1109/TSP.2009.2027741",

language = "English (US)",

volume = "57",

pages = "4811--4822",

journal = "IEEE Transactions on Signal Processing",

issn = "1053-587X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "12",

}

TY - JOUR

T1 - Efficient implementation of quasi- maximum-likelihood detection based on semidefinite relaxation

AU - Kisialiou, Mikalai

AU - Luo, Xiaodong

AU - Luo, Zhi Quan

N1 - Funding Information: Manuscript received March 16, 2007; accepted April 28, 2009. First published July 14, 2009; current version published November 18, 2009. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Xiaodong Cai. This research is supported in part by the National Science Foundation, Grant DMS-0610037. A preliminary version of this paper was published in the Proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP), Hong Kong, 2003, vol. 6, pp. VI 561–VI 564, and the Proceedings of the International Conference on Acoustics, Speech and Signal Processing (ICASSP), Philadelphia, PA, 2005, vol. 3, pp. III 433–III 436. Copyright: Copyright 2009 Elsevier B.V., All rights reserved.

PY - 2009/12

Y1 - 2009/12

N2 - In this paper we develop two quasi-maximum likelihood (ML) channel detectors for multiuser detection: semidefinite relaxation (SDR) detector and phase-shift-keying (PSK) detector. These detectors can deliver near-ML bit error rate (BER) performance with a polynomial worst-case complexity. The SDR detector for binary-phase-shift-keying (BPSK) constellation is based on a convex SDR, whereas the PSK detector for M-PSK constellations is based on a nonconvex low-rank SDR. The SDR detector is implemented using a dual-scaling interior-point method, while the PSK detector is based on a coordinate descent strategy on a feasible region homotopy. We use dynamic dimension reduction and warm start techniques to achieve signal-to-noise ratio (SNR)-sensitive improvements for both detectors. Numerical simulations of BER performance and running time indicate the effectiveness of the two quasi-ML detectors when compared to the conventional sphere decoder and its variants.

AB - In this paper we develop two quasi-maximum likelihood (ML) channel detectors for multiuser detection: semidefinite relaxation (SDR) detector and phase-shift-keying (PSK) detector. These detectors can deliver near-ML bit error rate (BER) performance with a polynomial worst-case complexity. The SDR detector for binary-phase-shift-keying (BPSK) constellation is based on a convex SDR, whereas the PSK detector for M-PSK constellations is based on a nonconvex low-rank SDR. The SDR detector is implemented using a dual-scaling interior-point method, while the PSK detector is based on a coordinate descent strategy on a feasible region homotopy. We use dynamic dimension reduction and warm start techniques to achieve signal-to-noise ratio (SNR)-sensitive improvements for both detectors. Numerical simulations of BER performance and running time indicate the effectiveness of the two quasi-ML detectors when compared to the conventional sphere decoder and its variants.

KW - Dimension reduction

KW - Duality

KW - MIMO systems

KW - Maximum-likelihood detection

KW - Semidefinite relaxation (SDR)

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

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

U2 - 10.1109/TSP.2009.2027741

DO - 10.1109/TSP.2009.2027741

M3 - Article

AN - SCOPUS:70450277222

SN - 1053-587X

VL - 57

SP - 4811

EP - 4822

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

IS - 12

M1 - 5165035

ER -

Efficient implementation of quasi- maximum-likelihood detection based on semidefinite relaxation

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this