Multi-group Multicast Beamforming: Optimal Structure and Efficient Algorithms

Min Dong, Qiqi Wang

Abstract

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.

Introduction

In the evolution of wireless communications, multicast beamforming stands as a vital technique for efficiently delivering content to multiple users simultaneously. While unicast beamforming (one-to-one) is well-understood, multi-group multicast beamforming—where a base station transmits different messages to distinct sets of subscribers—presents a significantly more complex challenge. This complexity arises from the dual requirements of maintaining intra-group fairness (ensuring the user with the weakest channel in a group receives an adequate signal) and managing inter-group interference (preventing beams for one group from disrupting another).

Mathematically, these problems, categorized as Quality of Service (QoS) and Max-Min Fairness (MMF), are non-convex and NP-hard. Traditional approaches like Semi-Definite Relaxation (SDR) suffer from poor scalability, becoming computationally prohibitive as the number of transmit antennas ($N$) increases. This research addresses these limitations by characterizing the elusive optimal structure of the multicast beamformer and leveraging that structure to design efficient algorithms for massive MIMO systems.

The Optimal Beamforming Structure

The primary breakthrough of this work is the discovery that the optimal multicast beamformer is not an arbitrary vector, but a weighted Minimum Mean Square Error (MMSE) filter. This structure reveals that the beamformer points toward a "weighted group-channel direction"—a specific linear combination of the channel vectors of all users within that group.

By applying Successive Convex Approximation (SCA) and Lagrangian duality, the authors demonstrate that the classic concept of uplink-downlink duality, previously established for unicast scenarios, can be generalized to multicast. This insight is transformative: it shows that the optimal beamforming vector balances the signal gain for the intended group against the interference caused to all other groups, effectively acting as a generalized version of the optimal multi-user unicast beamformer.

Breaking the Dimensionality Barrier

A critical finding for practical implementation is the low-dimensional structure inherent in the optimal solution. The research proves that the complexity of finding the optimal beamformer is primarily dependent on the number of users per group ($K$), rather than the number of transmit antennas ($N$).

In massive MIMO systems where $N$ might reach hundreds or thousands, this independence is a game-changer. By transforming the optimization problem into this lower-dimensional space, the proposed algorithms maintain high performance without the exponential increase in computational cost typically associated with large antenna arrays.

Methodology and Asymptotic Analysis

The study evaluates these theoretical insights using standard Rayleigh fading and pathloss models through extensive Monte Carlo simulations. The authors propose several algorithmic variations:

  1. OptBFwSDR/SCA: Iterative methods that utilize the identified optimal structure to find Lagrange multipliers.
  2. AsymBFwSCA: A closed-form approximate beamformer derived from asymptotic analysis for scenarios where $N$ is very large.

One of the key observations is the "slow convergence of orthogonality." While interference theoretically vanishes as $N \to \infty$, it does so slowly in practice. The proposed weighted MMSE structure accounts for this residual interference, making it far more robust for realistic antenna counts (e.g., $N=64$ or $128$) than simpler asymptotic methods like Block-Diagonal Zero-Forcing (BDZF).

Key Results

The performance gains of the proposed methods are substantial:

  • Computational Speed: In simulations with $N=500$ antennas, the proposed structure-based method achieved solutions in approximately 1.4 seconds. In contrast, traditional Direct SDR required over 75 minutes, and Direct SCA failed to converge entirely.
  • Optimality: The algorithms consistently reach the theoretical lower bound of the optimization problem, significantly outperforming existing low-complexity alternatives.
  • Asymptotic Efficiency: The closed-form AsymBFwSCA provides a "zero-cost" solution for massive arrays, performing nearly identically to iterative versions once the antenna count exceeds 200.

Limitations and Future Work

Despite these advancements, some challenges remain for real-world deployment. The SCA-based methods require an initial feasible starting point, which can be difficult to identify in "overloaded" systems where the number of users exceeds the number of antennas. Additionally, the current framework assumes perfect Channel State Information (CSI); investigating the impact of channel estimation errors on the optimal structure is a necessary next step. Finally, extending this single-cell logic to multi-cell coordinated beamforming with per-base-station power constraints remains an open area for research.

Conclusion

By characterizing the optimal structure of multi-group multicast beamforming as a weighted MMSE filter, this research provides both a theoretical foundation and a practical toolkit for next-generation wireless systems. The ability to decouple optimization complexity from antenna count ensures that as hardware scales toward massive MIMO, the software governing signal delivery can remain efficient and near-optimal.

Summary updated

Abstract

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.
BibTeX
@article{dong2020multi,
  author = {Min Dong and Qiqi Wang},
  title = {{Multi-group Multicast Beamforming: Optimal Structure and Efficient Algorithms}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=TdRnoDxH55},
}
Figure