Algorithms used in SDR Detector
SDR Detector is based on a dual scaling interior point method (implemented in C), with several key modifications to allow warm start, early termination and efficient stepsize selection. The warm start is made possible by truncated version of the popular Sphere Decoder. The resulting interior point algorithm has a worst case polynomial complexity. The following resources provide the foundation for the implementation of SDR Detector:
- Semidefinite Programming (SDP) Detector:
- SDP Detector was introduced in W.K. Ma, T.N. Davidson, K.M. Wong, Z.-Q. Luo, and P.C. Ching, "Quasi-maximum-likelihood multiuser
detection using semi-definite relaxation,"IEEE
Transactions on Signal Processing, vol. 50, no. 4, pp. 912-922, 2002.
- Performance analysis of SDP Detector can be found in
M. Kisialiou and Z.-Q. Luo, "Performance analysis of quasi-maximum-likelihood detector based on semidefinite programming," Proc. of ICASSP '05, vol. 3, pp. III 433 - III 436, Philadelphia, PA, March 2005.
- Implementation of the dual scaling algorithm in DSDP is described in S.J. Benson and Yinyu Ye, "DSDP5: Software for semidefinite programming," ACM Transactions on Mathematical Software, September 2005.
- Sphere Decoder (SD):
- The foundation of SD is an algorithm for computing the shortest vector in lattices, first published in U. Fincke and M. Pohst, "Improved methods for
calculating vectors of short length in a lattice, including a
complexity analysis,'' Mathematics of Computation,
vol. 44, pp. 463-471, 1985.
- SD was applied to maximum-likelihood detection problem in E. Viterbo and J. Boutros, "A universal
lattice code decoder for fading channels,'' IEEE
Transactions on Information Theory, pp. 1639-1642, 1999.
Algorithms used in PSK Detector
The core of PSK Detector is the coordinate descent method implemented over a homotopy of the relaxed feasible set. A warm start procedure and a dimension reduction technique allow to make efficient use of symbol reliabilities to deliver near optimal error probability with highly optimized running time. The following resources provide the foundation for the implementation of SDR Detector:
- Phase-Shift-Keying (PSK) Detector:
- PSK Detector was introduced in Z.-Q. Luo, X. Luo, and M. Kisialiou, "An efficient quasi-maximum-likelihood decoder for PSK signals," Proc. of ICASSP '03, vol. 6, pp. VI 561 - VI 564, Hong Kong, 2003.
|