Efficient multiuser detector based on box-constrained dichotomous coordinate descent and regularization

Abstract

The presented iterative multiuser detection technique was based on joint deregularized and box-constrained solution to quadratic optimization with iterations similar to that used in the nonstationary Tikhonov iterated algorithm. The deregularization maximized the energy of the solution, which was opposite to the Tikhonov regularization where the energy was minimized. However, combined with box-constraints, the deregularization forced the solution to be close to the binary set. It further exploited the box-constrained dichotomous coordinate descent algorithm and adapted it to the nonstationary iterative Tikhonov regularization to present an efficient detector. As a result, the worst-case and average complexity are reduced down as K^2.8 and K^2.5 floating point operation per second, respectively. The development improves the “efficient frontier” in multiuser detection, which is illustrated by simulation results. In addition, most operations in the detector are additions and bit-shifts. This makes the proposed technique attractive for fixed-point hardware implementation.

Keywords

dichotomous coordinate descent / de-regularization / low complexity / multiuser detection / Tikhonov regularization

References

[1] VerduS.Multiuser detection [M], 1998Cambridge, UKCambridge University Press

[2] HasegawaF., LuoJ., PattipatiK., WillettP., PhamD.. Speed and accuracy comparison of techniques for multiuser detection in synchronous CDMA [J]. IEEE Trans Commun, 2004, 52(4): 540-545

[3] VaranasiM. K.. Decision feedback multiuser detection: A systematic approach [J]. IEEE Trans Inform Theory, 1999, 45(1): 219-240

[4] LuoJ., PattipatiK. R., WillettP. K., HasegawaF.. Near-optimal multiuser detection in synchronous CDMA using probabilistic data association [J]. IEEE Comm Letters, 2001, 5(9): 361-363

[5] LUO J, PATTIPATI K, WILLETT P, BRUNEL L. Branch-and-bound-based fast optimal algorithm for multiuser detection in synchronous CDMA [C]// Proc IEEE Int Conf on Communications, ICC’2003. Anchorage, Alaska, USA, 2003: 3336–3340.

[6] ZAKHAROV Y V, LUO J, KASPARIS C. Joint box-constraint and deregularization in multiusr detection [C]// 14th European Signal Processing Conference. Florence, Italy, 2006: 1–5.

[7] EnglH. W.. Necessary and sufficient conditions for convergence of regularization methods for solving linear operator equations of the first kind [J]. Numerical Functional Analysis and Optimization, 1981, 3(2): 201-222

[8] KasparisC., PiechockiR. J., FletcherP. N., NixA. R.. A bootstrap multiuser detector for CDMA based on Tikhonov regularization [C]. Proc IEEE International Symposium Acoustic, Speed, and Signal Processing, 2003Hong KongIEEE Press69-72

[9] ZakharovY., LuoJ., KasparisC.Efficient multiuser detection based on box-constraint relaxation, regularization with negative diagonal loading and coordinate-descent iterations [M], 2006U.K.University of York

[10] RASMUSSEN L K, ALEXANDER P D, LIM T J. A linear model for CDMA signals received with multiple antennas over multipath fading channels [C]// CDMA Techniques for Third Generation Mobile Systems. Norwell Kluwer Academic Publishers, 1999: 23–57.

[11] JensenM. A., WallaceJ. W.. A review of antennas and propagation for MIMO wireless communications [J]. IEEE Trans Antennas and Propagation, 2004, 52(11): 2810-2824

[12] Vishnu VardhanK., MohammedS. K., ChockalingamA., Sundar RajanB.. A low complexity detector for large MIMO systems and multiuser CDMA systems [J]. IEEE Journal on Selected Areas in Communications, 2008, 26(3): 473-485

[13] SpasojevicP., GeorghiadesC. N.. The slowest descent method and its application to sequence estimation [J]. IEEE Trans Commun, 2001, 49(9): 1592-1604

[14] TeyanC., ZakharovY. V., ChunshanL.. Low complexity channel estimate based adaptive linear equalizer [J]. IEEE Signal Processing Letters, 2011, 18(7): 427-430

[15] QuanZ., RibeiroM. V.. A low cost STBC-OFDM system with improved reliability for power line communications [C]. 2011 IEEE International Symposium on Power Line Communications and Its Applications (ISPLC), 2011New JerseyIEEE Press261-266

[16] VorobyovS. A., GershanA. B., LuoZ. Q.. Robust adaptive beamforming using worst-case performance optimization: a solution to the mismatch problem [J]. IEEE Trans Signal Processing, 2003, 51(2): 313-324

[17] NeumaierA.. Solving ill-conditioned and singular linear systems: A tutorial on regularization [J]. SIAM Review, 1998, 40(3): 636-666

[18] HankeM., GroetschC. W.. Nonstationary iterated Tikhonov regularization [J]. J Optim Theory Appl, 1998, 98(1): 37-53

[19] TanP. H., RasmussenL. K., LimT. J.. Box-constrained maximum-likelihood detection in CDMA [C]. Proc IEEE 51st Vehicular Technology Conf Spring2000, 2000Tokyo, JapanIEEE Press517-521

[20] TanP. H., RasmussenL. K., LimT. J.. Constrained maximum-likelihood detection in CDMA [J]. IEEE Trans Commun, 2001, 49(1): 142-153

[21] YenerA., YatesR. D., UlukusS.. CDMA multiuser detection: A nonlinear programming approach [J]. IEEE Trans Commun, 2002, 50(6): 1016-1024

[22] ZAKHAROV Y V, TOZER T C. Box-constrained multiuser detection based on multiplication-free coordinate descent optimization [C]// Proc Fifth IEEE Workshop on Signal Processing Advances in Wireless Communications. Lisboa, Portugal, 2004: 11–14.

[23] ZakharovY., TozerT. C.. Multiplication-free iterative algorithm for LS problem [J]. Electronics Letters, 2004, 40(9): 567-569

[24] LiuJ., ZakharovY., WeaverB.. Architecture and FPGA design of dichotomous coordinate descent algorithms [J]. IEEE Trans Circuits and Systems. Part I: Regular Papers, 2009, 56(11): 2425-2438

[25] QuanZ., LiuJ., ZakharovY.. FPGA design of box-constrained MIMO detector [C]. IEEE International Conference on Communications ICC 09, 2009New JerseyIEEE Press1-5

[26] LiuJ., WeaverB., ZakharovY.. FPGA implementation of multiplication-free complex division [J]. Electronics Letters, 2008, 44(2): 95-96

[27] QuanZ., LiuJ., ZakharovY.. FPGA implementation of DCD based CDMA multiuser detector [C]. 15th Int Conf on Digital Signal Processing, 2007New JerseyIEEE Press319-322

[28] LiuJ., QuanZ., ZakharovY.. Parallel FPGA implementation of DCD algorithm [C]. 15th Int Conf on Digital Signal Processing, 2007New JerseyIEEE Press331-334