[en] This paper investigates the optimal signal detection problem with a particular interest in large-scale multiple-input multiple-output (MIMO) systems. The problem is NP-hard and can be solved optimally by searching the shortest path on the decision tree. Unfortunately, the existing optimal search algorithms often involve prohibitively high complexities, which indicates that they are infeasible in large-scale MIMO systems. To address this issue, we propose a general heuristic search algorithm, namely, hyper-accelerated tree search (HATS) algorithm. The proposed algorithm employs a deep neural network (DNN) to estimate the optimal heuristic, and then use the estimated heuristic to speed up the underlying memory-bounded search algorithm. This idea is inspired by the fact that the underlying heuristic search algorithm reaches the optimal efficiency with the optimal heuristic function. Simulation results show that the proposed algorithm reaches almost the optimal bit error rate (BER) performance in large-scale systems, while the memory size can be bounded. In the meanwhile, it visits nearly the fewest tree nodes. This indicates that the proposed algorithm reaches almost the optimal efficiency in practical scenarios, and thereby it is applicable for large-scale systems. Besides, the code for this paper is available at https://github.com/skypitcher/hats.
Disciplines :
Electrical & electronics engineering
Author, co-author :
He, Le; Guangzhou University > School of Computer Science and Cyber Engineering
He, Ke ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SigCom ; Guangzhou University > Computer Science and Cyber Engineering
Fan, Lisheng; Guangzhou University > Computer Science and Cyber Engineering
Lei, Xianfu; Southwest Jiaotong University > School of Information Science and Technology
Nallanathan, Arumugam; Queen Mary University of London > School of Electronic Engineering and Computer Science
Karagiannidis, George; Aristotle University of Thessaloniki > Wireless Communications and Information Processing Group (WCIP)
External co-authors :
yes
Language :
English
Title :
Toward Optimally Efficient Search With Deep Learning for Large-Scale MIMO Systems
Publication date :
May 2022
Journal title :
IEEE Transactions on Communications
ISSN :
0090-6778
Publisher :
Institute of Electrical and Electronics Engineers, United States
B. Hassibi and H. Vikalo, "On the sphere-decoding algorithm I. Expected complexity," IEEE Trans. Signal Process., vol. 53, nos. 1-8, pp. 2806-2818, Aug. 2005.
N. Sommer, M. Feder, and O. Shalvi, "Closest point search in lattices using sequential decoding," in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Sep. 2005, pp. 1053-1057.
C. M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), 5th ed. Cambridge, U.K.: Springer, 2007.
P. J. G. Teunissen, "Integer least-squares theory for the GNSS compass," J. Geodesy, vol. 84, no. 7, pp. 433-447, 2010.
J. Goldberger and A. Leshem, "A Gaussian tree approximation for integer least-squares," in Proc. Neural Inf. Process. Syst. (NIPS), 2009, pp. 638-645.
S. Yang and L. Hanzo, "Fifty years of MIMO detection: The road to large-scale MIMOs," IEEE Commun. Surveys Tuts., vol. 17, no. 4, pp. 1941-1988, 4th Quart., 2015.
L. Sanguinetti, E. Björnson, and J. Hoydis, "Toward massive MIMO 2.0: Understanding spatial correlation, interference suppression, and pilot contamination," IEEE Trans. Commun., vol. 68, no. 1, pp. 232-257, Jan. 2020.
E. Björnson, L. Sanguinetti, H. Wymeersch, J. Hoydis, and T. L. Marzetta, "Massive MIMO is a reality-What is next?: Five promising research directions for antenna arrays," Digit. Signal Process., vol. 94, pp. 3-20, Nov. 2019.
L. Lu, G. Y. Li, A. L. Swindlehurst, A. Ashikhmin, and R. Zhang, "An overview of massive MIMO: Benefits and challenges," IEEE J. Sel. Topics Signal Process., vol. 8, no. 5, pp. 742-758, Jun. 2014.
E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, "Closest point search in lattices," IEEE Trans. Inf. Theory, vol. 48, no. 8, pp. 2201-2214, Aug. 2002.
W. Zhao and G. B. Giarmakis, "Reduced complexity closest point decoding algorithms for random lattices," IEEE Trans. Wireless Commun., vol. 5, no. 1, pp. 101-111, Jan. 2006.
D. Micciancio, "The hardness of the closest vector problem with preprocessing," IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 1212-1215, Mar. 2001.
W. Chen et al., "An improved lower bound for approximating the minimum integral solution problem with preprocessing over norm," J. Combinat. Optim., vol. 30, no. 3, pp. 447-455, Oct. 2015.
L. Liu, Y. Li, C. Huang, C. Yuen, and Y. L. Guan, "A new insight into GAMP and AMP," IEEE Trans. Veh. Technol., vol. 68, no. 8, pp. 8264-8269, Aug. 2019.
Z. Guo and P. Nilsson, "Algorithm and implementation of the K-best sphere decoding for MIMO detection," IEEE J. Sel. Areas Commun., vol. 24, no. 3, pp. 491-503, Mar. 2006.
L. Liu, C. Liang, J. Ma, and L. Ping, "Capacity optimality of AMP in coded systems," IEEE Trans. Inf. Theory, vol. 67, no. 7, pp. 4429-4445, Jul. 2021.
S. Bäro, J. Hagenauer, and M. Witzke, "Iterative detection of MIMO transmission using a list-sequential (LISS) detector," in Proc. IEEE Int. Conf. Commun. (ICC), May 2003, pp. 2653-2657.
Z. Yang, C. Liu, and J. He, "A new approach for fast generalized sphere decoding in MIMO systems," IEEE Signal Process. Lett., vol. 12, no. 1, pp. 41-44, Jan. 2005.
A. D. Murugan, H. El Gamal, M. O. Damen, and G. Caire, "A unified framework for tree search decoding: Rediscovering the sequential decoder," IEEE Trans. Inf. Theory, vol. 52, no. 3, pp. 933-953, Mar. 2006.
T. Cui, T. Ho, and C. Tellambura, "Heuristic tree search for detection and decoding of uncoded and linear block coded communication systems," in Proc. IEEE Int. Conf. Commun. (ICC), Jun. 2006, pp. 391-396.
Y. Dai and Z. Yan, "Memory-constrained tree search detection and new ordering schemes," IEEE J. Sel. Topics Signal Process., vol. 3, no. 6, pp. 1026-1037, Dec. 2009.
R. Y. Chang, W. H. Chung, and S. J. Lin, "A algorithm inspired memory-efficient detection for MIMO systems," IEEE Wireless Commun. Lett., vol. 1, no. 5, pp. 508-511, Oct. 2012.
N. T. Nguyen, K. Lee, and H. Dai, "Application of deep learning to sphere decoding for large MIMO systems," IEEE Trans. Wireless Commun., vol. 20, no. 10, pp. 6787-6803, Oct. 2021.
S. J. Russell, "Efficient memory-bounded search methods," in Proc. Eur. Conf. Artif. Intell. (ECAI), 1992, pp. 1-5.
Y. S. Han, C. R. P. Hartmann, and C.-C. Chen, "Efficient priorityfirst search maximum-likelihood soft-decision decoding of linear block codes," IEEE Trans. Inf. Theory, vol. 39, no. 5, pp. 1514-1523, Sep. 1993.
R. Dechter and J. Pearl, "Generalized best-first search strategies and the optimality of A," J. ACM, vol. 32, no. 3, pp. 505-536, Jul. 1985.
H. Kim, S. Oh, and P. Viswanath, "Physical layer communication via deep learning," IEEE J. Sel. Areas Inf. Theory, vol. 1, no. 1, pp. 5-18, May 2020.
J. Xia, K. He, W. Xu, S. Zhang, L. Fan, and G. K. Karagiannidis, "A MIMO detector with deep learning in the presence of correlated interference," IEEE Trans. Veh. Technol., vol. 69, no. 4, pp. 4492-4497, Apr. 2020.
K. He, L. He, L. Fan, Y. Deng, G. K. Karagiannidis, and A. Nallanathan, "Learning-based signal detection for MIMO systems with unknown noise statistics," IEEE Trans. Commun., vol. 69, no. 5, pp. 3025-3038, May 2021.
H. He, C.-K. Wen, S. Jin, and G. Y. Li, "Model-driven deep learning for MIMO detection," IEEE Trans. Signal Process., vol. 68, pp. 1702-1715, 2020.
J. Xue et al., "Transceiver design of optimum wirelessly powered fullduplex MIMO IoT devices," IEEE Trans. Commun., vol. 66, no. 5, pp. 1955-1969, May 2018.
B. Lin, F. Gao, S. Zhang, T. Zhou, and A. Alkhateeb, "Deep learningbased antenna selection and CSI extrapolation in massive MIMO systems," IEEE Trans. Wireless Commun., vol. 20, no. 11, pp. 7669-7681, Nov. 2021.
J. Ma, S. Zhang, H. Li, F. Gao, and S. Jin, "Sparse Bayesian learning for the time-varying massive MIMO channels: Acquisition and tracking," IEEE Trans. Commun., vol. 67, no. 3, pp. 1925-1938, Mar. 2019.
S. Zhang, S. Zhang, F. Gao, J. Ma, and O. A. Dobre, "Deep learning optimized sparse antenna activation for reconfigurable intelligent surface assisted communication," IEEE Trans. Commun., vol. 69, no. 10, pp. 6691-6705, Oct. 2021.
Q. Hu, F. Gao, H. Zhang, S. Jin, and G. Y. Li, "Deep learning for channel estimation: Interpretation, performance, and comparison," IEEE Trans. Wireless Commun., vol. 20, no. 4, pp. 2398-2412, Apr. 2021.
A. Askri and G. R.-B. Othman, "DNN assisted sphere decoder," in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2019, pp. 1172-1176.
M. Mohammadkarimi, M. Mehrabi, M. Ardakani, and Y. Jing, "Deep learning-based sphere decoding," IEEE Trans. Wireless Commun., vol. 18, no. 9, pp. 4368-4378, Sep. 2019.
J. Sun, Y. Zhang, J. Xue, and Z. Xu, "Learning to search for MIMO detection," IEEE Trans. Wireless Commun., vol. 19, no. 11, pp. 7571-7584, Nov. 2020.
K. He and Y. Deng, "Efficient memory-bounded optimal detection for GSM-MIMO systems," IEEE Trans. Commun., vol. 70, no. 1, pp. 280-295, Jan. 2022.
J. Werfel, X. Xie, and H. S. Seung, "Learning curves for stochastic gradient descent in linear feedforward networks," in Proc. Neural Inf. Process. Syst. (NIPS), 2003, pp. 1197-1204.
D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization," in Proc. Int. Conf. Learn. Represent. (ICLR), 2015, pp. 1-15.
C. Oestges, "Validity of the Kronecker model for MIMO correlated channels," in Proc. IEEE 63rd Veh. Technol. Conf. (VTC), 2006, pp. 2818-2822.
N. Prasad, K. Y. Kalbat, and X. Wang, "Optimally efficient max-log APP demodulation in MIMO systems," IEEE J. Sel. Topics Signal Process., vol. 5, no. 8, pp. 1400-1414, Dec. 2011.
