Towards Efficient and Optimal Joint Beamforming and Antenna Selection: A Machine Learning Approach

This work revisits the joint transmit beamforming and antenna selection problem. Existing approaches find approximate solutions to this NP-hard problem via various heuristics, e.g., convex/nonconvex relaxation, greedy method, and (deep) supervised learning. However, optimality (or even feasibility) of these heuristics is not guaranteed. To avoid sub-optimal solutions, an effective branch and bound (B&B) algorithm is proposed. B&B algorithms are ensured to return optimal solutions, but have scalability challenges. In order to enhance efficiency, a graph neural network (GNN)-based classfier is trained with imitation learning to accelerate the B&B algorithm---where the GNN is carefully designed to suit the dynamic nature of wireless communication scenarios. The GNN-based acceleration is shown to provably retain the optimality of B&B with high probability, while substantially reducing the computational burden, under reasonable conditions. Numerical experiments show that our GNN-based method always finds near-optimal and feasible solutions with significantly reduced complexity relative to the plain-vanilla B&B.