Multi-Group Multicast Beamforming: Optimal Structure and Efficient Algorithms

Min Dong, Qiqi Wang

TL;DR

This paper finally characterizes the elusive optimal structure of multi-group multicast beamforming, a problem long considered computationally "hard" (NP-hard). By proving that the optimal beamformer is a weighted MMSE filter with an inherent low-dimensional structure, the authors develop algorithms that achieve near-optimal performance in massive MIMO systems while remaining independent of the number of antennas.

What Problem Does This Paper Address?

In wireless communications, multicast beamforming is the art of using multiple antennas to send a single message to a group of users simultaneously. Multi-group multicast takes this a step further: the base station sends different messages to different groups (e.g., different streaming channels to different sets of subscribers).

The challenge is two-fold:

  1. Intra-group fairness: You must ensure the user with the weakest channel in a group still receives a clear signal.
  2. Inter-group interference: Beams intended for Group A shouldn't drown out the signal for Group B.

Mathematically, these problems (Quality of Service - QoS, and Max-Min Fairness - MMF) are non-convex and NP-hard. Traditional solutions like Semi-Definite Relaxation (SDR) become prohibitively slow as the number of antennas ($N$) grows, making them useless for the "Massive MIMO" arrays (hundreds of antennas) central to 5G and 6G.

Methods

The authors combine Successive Convex Approximation (SCA) with Lagrangian duality to "crack" the problem's structure. Their approach involves:

  • Uplink-Downlink Duality: They generalize a classic result from unicast (one-to-one) communications to the multicast (one-to-many) scenario.
  • Fixed-Point Iteration: They propose a fast iterative method to find the optimal Lagrange multipliers, which they prove is asymptotically optimal as the number of antennas goes to infinity.
  • Dimension Reduction: Because they identified that the optimal beamformer is a linear combination of the users' channels within a group, they transform the optimization problem from one that scales with $N$ (antennas) to one that scales with $K$ (users per group).
  • Asymptotic Analysis: For very large arrays, they derive closed-form expressions that provide "plug-and-play" beamforming weights without needing complex iterations.

Datasets

As a theoretical communications paper, it does not use "datasets" in the machine learning sense. Instead, it evaluates performance using:

  • Synthetic Channel Models: Standard Rayleigh fading models and pathloss models (where signal strength drops based on distance, e.g., $\beta = d^{-3}$).
  • Monte Carlo Simulations: Averaging results over hundreds of random channel realizations to ensure statistical significance.

Key Insights and Ideas

  • The "Group-Channel Direction": The paper reveals that the optimal beamformer isn't just pointing at one user; it points toward a "weighted group-channel direction." This direction is a specific weighted sum of all users' channels in that group.
  • Complexity Independence: Perhaps the most significant "aha" moment is that the beamforming problem has an inherent low-dimensional structure. Even if you have 1,000 antennas, if your group only has 5 users, the core optimization only needs to happen in a 5-dimensional space.
  • Weighted MMSE Filter: The optimal structure is essentially a generalized version of the Minimum Mean Square Error (MMSE) filter. It balances signal gain for the intended group against the interference caused to all other groups.
  • Slow Convergence of Orthogonality: The authors explain why simple "asymptotic" methods often fail in practice: while interference eventually disappears as $N \to \infty$, it does so very slowly. Their proposed structure accounts for this residual interference, making it much more robust for realistic antenna counts (e.g., $N=64$ or $128$).

Key Results

  • Speed: The proposed algorithms (OptBFwSDR/SCA) maintain a nearly constant computation time regardless of the number of antennas. In tests with $N=500$, the proposed method took ~1.4 seconds, while traditional Direct SDR took over 75 minutes (and Direct SCA failed to converge).
  • Optimality: The algorithms consistently hit the "lower bound" (the theoretical best possible performance), outperforming existing low-complexity methods like Block-Diagonal Zero-Forcing (BDZF) by several decibels.
  • Asymptotic Accuracy: Their closed-form approximate beamformer (AsymBFwSCA) performs nearly identically to the full iterative version once the antenna count exceeds ~200, offering a "zero-cost" solution for massive arrays.

Limitations and Future Work

  • Initial Feasibility: The SCA method requires an initial "feasible" starting point. While the authors suggest using a small-scale SDR solution to find one, finding this point can still be tricky in highly congested or "overloaded" systems (where users outnumber antennas).
  • Perfect CSI: The paper assumes the base station has perfect Channel State Information (CSI). In the real world, channel estimation is noisy, and the impact of this uncertainty on the "optimal structure" remains an open question.
  • Multi-cell Extension: While the authors mention that the structure could extend to multi-cell coordinated beamforming, the specific math for handling per-base-station power constraints is left for future research.

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},
}

Loading related content...

Figure