Semidefinite programming for detection in linear systems - optimality conditions and space-time decoding

Optimal maximum likelihood detection of finite alphabet symbols in general requires time consuming exhaustive search methods. The computational complexity of such techniques is exponential in the size of the problem and for large problems sub-optimal algorithms are required. To find a solution in polynomial time, a semidefinite programming approach is taken to estimate binary symbols in a general linear system. A condition under which the proposed method provides optimal solutions is derived. As an application, the proposed algorithm is used as a decoder for a linear space-time block coding system and the results are illustrated with numerical examples.