In this work, we propose ultra-low-complexity design solutions for multi-group multicast beamforming in large-scale systems. For the quality-of-service (QoS) problem, by utilizing the optimal multicast beamforming structure obtained recently in [2], we convert the original problem into a non-convex weight optimization problem of a lower dimension and propose two fast first-order algorithms to solve it. Both algorithms are based on successive convex approximation (SCA) and provide fast iterative updates to solve each SCA subproblem. The first algorithm uses a saddle point reformulation in the dual domain and applies the extragradient method with an adaptive step-size procedure to find the saddle point with simple closed-form updates. The second algorithm adopts the alternating direction method of multipliers (ADMM) method by converting each SCA subproblem into a favorable ADMM structure. The structure leads to simple closed-form ADMM updates, where the problem in each update block can be further decomposed into parallel subproblems of small sizes, for which closed-form solutions are obtained. We also propose efficient initialization methods to obtain favorable initial points that facilitate fast convergence. Furthermore, taking advantage of the proposed fast algorithms, for the max-min fair (MMF) problem, we propose a simple closed-form scaling scheme that directly uses the solution obtained from the QoS problem, avoiding the conventional computationally expensive method that iteratively solves the inverse QoS problem. We further develop lower and upper bounds on the performance of this scaling scheme. Simulation results show that the proposed algorithms offer near-optimal performance with substantially lower computational complexity than the state-of-the-art algorithms for large-scale systems.
翻译:在这项工作中,我们提出了适用于超大规模系统中多组组播波束成形的超低复杂度设计解决方案。对于服务质量(QoS)问题,通过利用最近在[2]中获得的最优多播波束成形结构,我们将原始问题转化为低维的非凸权重优化问题,并提出了两种快速的一阶算法来解决它。两种算法均基于连续凸逼近(SCA),并提供快速的迭代更新,以解决每个SCA子问题。第一种算法使用双重域中的鞍点重构方法,并采用带自适应步长程序的外推法来找到具有简单闭式更新的鞍点。第二种算法采用多路交叉方向乘积法(ADMM)方法,通过将每个SCA子问题转化为有利的ADMM结构。该结构导致简单的闭合式ADMM更新,其中每个更新块中的问题可以进一步分解为小尺寸的并行子问题,从而得到闭合式的解。我们还提出了有效的初始化方法,以获得有利的初始点,以促进快速收敛。此外,利用所提出的快速算法,针对最大最小公平(MMF)问题,我们提出了一个简单的闭合式缩放方案,直接使用从QoS问题获得的解决方案,避免了传统的计算密集型方法,该方法迭代求解反向QoS问题。我们进一步开发了该缩放计划性能的下限和上限。仿真结果表明,所提出的算法在超大规模系统中比现有的算法具有极佳的近似性能和大幅降低的计算复杂度。