High Performance Adaptive Algorithms for Single-Group Multicast Beamforming

The single-group multicast beamforming problem is NP-hard, and the available approximations do not always achieve favorable performance-complexity tradeoffs. This paper introduces a new class of adaptive multicast beamforming algorithms that features guaranteed convergence and state-of-the-art performance at low complexity. Each update takes a step in the direction of an inverse signal-to-noise ratio (SNR) weighted linear combination of the SNR-gradient vectors of all the users. Convergence of this update to a Karush-Kuhn-Tucker (KKT) point of proportionally fair beamforming is established. Simulations show that the proposed approach can enable better performance than the prior state-of-art in terms of multicast rate, at considerably lower complexity. This reveals an interesting link between max-min-fair and proportionally fair multicast beamforming formulations. For cases where there is no initial channel state information at the transmitter, an online algorithm is developed that simultaneously learns the user channel correlation matrices and adapts the beamforming vector to maximize the minimum (long-term average) SNR among the users, using only periodic binary SNR feedback from each receiver. The online algorithm uses the analytic center cutting plane method to quickly learn the user correlation matrices with limited signaling overhead.