Multi-Group Multicast Beamforming: Optimal Structure and Efficient Algorithms

This paper considers the multi-group multicast beamforming optimization problem, for which the optimal solution has been unknown due to the non-convex and NP-hard nature of the problem. By utilizing the successive convex approximation numerical method and Lagrangian duality, we obtain the optimal multicast beamforming solution structure for both the quality-of-service (QoS) problem and the max-min fair (MMF) problem. The optimal structure brings valuable insights into multicast beamforming: We show that the notion of uplink-downlink duality can be generalized to the multicast beamforming problem. The optimal multicast beamformer is a weighted MMSE filter based on a group-channel direction: a generalized version of the optimal downlink multi-user unicast beamformer. We also show that there is an inherent low-dimensional structure in the optimal multicast beamforming solution independent of the number of transmit antennas, leading to efficient numerical algorithm design, especially for systems with large antenna arrays. We propose efficient algorithms to compute the multicast beamformer based on the optimal beamforming structure. Through asymptotic analysis, we characterize the asymptotic behavior of the multicast beamformers as the number of antennas grows, and in turn, provide simple closed-form approximate multicast beamformers for both the QoS and MMF problems. This approximation offers practical multicast beamforming solutions with a near-optimal performance at very low computational complexity for large-scale antenna systems.