Efficient implementation of a quasi-maximum-likelihood detector based on semi-definite relaxation

Mikalai Kisialiou, Zhi Quan Luo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Existing approaches to the Maximum-Likelihood (ML) detection problem in digital communications either suffer from exponential complexity (e.g. Sphere Decoder and its variants) or exhibit significant Bit-Error-Rate (BER) degradation (e.g. LMMSE Detector). In this paper we present an efficient implementation of a semi-definite relaxation-based detector (SDR Detector) which can achieve nearoptimal BER performance with worst-case polynomial complexity. This implementation (available online) can be 100 times faster than an off-the-shelf SeDuMi-based implementation, outperforms Sphere Decoder in low Signal-to-Noise Ratio (SNR) or high dimension regimes, and matches the speed of Sphere Decoder in the high SNR regime. The core of the detector is an optimized dual-scaling interiorpoint method (implemented in C) for the relaxed semi-definite program. SNR-sensitive improvements are achieved by a dimension reduction strategy and a warm start technique based on a truncated version of the Sphere Decoding algorithm. Extensive numerical simulations show that the BER performance and the running time of SDR Detector compare favorably to that of other near-optimal detection strategies.

Original languageEnglish (US)
Title of host publication2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07
PagesIV1329-IV1332
DOIs
StatePublished - 2007
Event2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07 - Honolulu, HI, United States
Duration: Apr 15 2007Apr 20 2007

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume4
ISSN (Print)1520-6149

Other

Other2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07
Country/TerritoryUnited States
CityHonolulu, HI
Period4/15/074/20/07

Keywords

  • Duality
  • Interior-point methods
  • MIMO systems
  • Maximum likelihood detection
  • Semi-definite relaxation

Fingerprint

Dive into the research topics of 'Efficient implementation of a quasi-maximum-likelihood detector based on semi-definite relaxation'. Together they form a unique fingerprint.

Cite this