Low-Complexity Multi-user Detection Based on Gradient Information for Uplink Grant-Free NOMA

Massive machine type communication (mMTC) serves an irreplaceable role in the development process of the Internet of Things (IoT). Because of its characteristics of massive connection and sporadic transmission, compressed sensing (CS) has been applied in joint user activity and data detection in the uplink grant-free non-orthogonal multiple access (NOMA) system. In previous work, greedy iterative-based multi-user detection (MUD) algorithms were developed in mMTC scenarios because of the computational benefit and competitive performance. However, conventional greedy iterative-based MUD algorithms still suffer from high computational complexity due to the process of large-size matrix inversion with the accession of massive devices into the system. In this paper, gradient information is used to address this problem. A low-complexity gradient descent-based gradient pursuit MUD (GDGP-MUD) algorithm is proposed, which uses the gradient information of error function in the process of iteration as a new updating direction, instead of the matrix inversion process. Then, a multi-step quasi-Newton MUD (MSQN-MUD) algorithm is proposed to improve the precision of detection while maintaining low complexity. In the algorithm, high-order information in the process of adjacent iteration is used effectively to update data values more accurately. Moreover, the convergence and complexity analysis of both algorithms are derived. The analysis shows that both proposed algorithms have lower computational consumption than most of the state-of-the-art greedy-based MUD algorithms. It is worth noting that in comparison to most existing CS-based MUD algorithms, the two proposed algorithms do not require the exact user sparsity level and, thus, reduce the dependence on prior knowledge. The numerical experiments demonstrate that the proposed algorithms have better real-time performance than existing greedy-based MUD algorithms with similar symbol error rate performance.