2006 · 55 citations · 7 references
EngineeringComputer ScienceElectrical EngineeringInformation TheoryOptimizationWireless CommunicationsChannel EstimationDigital Signal ProcessingMaximum Likelihood EstimationSignal Detection TheoryTime ComplexityBit Error RateBit-error Rate AnalysisDetectorsPolynomial Time ComplexityRandom Matrix TheoryRayleigh FadingSemidefinite Programming RelaxationSignal-to-noise Ratio
Despite its optimal bit-error-rate (BER) performance, maximum-likelihood (ML) detection is known to be NP-hard and suffers from high computational complexity. The currently popular suboptimal detectors either achieve a polynomial time complexity at the expense of BER performance degradation (e.g., MMSE detector), or offer a near ML performance with a complexity that is exponential in the worst case. The paper considers a highly efficient (polynomial worst case complexity) quasi-ML detection method based on semi-definite (SDP) relaxation. It is shown that, for a standard vector Rayleigh fading channel, this SDP-based quasi-ML detector achieves, in the high signal-to-noise ratio (SNR) region, a BER which is identical to that of the exact ML detector. In the low SNR region, we use the random matrix theory to show that the SDP-based detector serves as a constant factor approximation to the ML detector for large systems.
7