PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking WMMSE: Can Its Complexity Scale Linearly With the Number of BS Antennas?

Xiaotong Zhao, Siyuan Lu, Qingjiang Shi, Zhi-Quan Luo

arXiv:2205.06225v2eess.SP

TL;DR

Massive MU-MIMO WSR maximization is NP-hard, while classical WMMSE has cubic complexity in the number of BS antennas, limiting its use for very large arrays. The paper develops linear-complexity methods for SPC and PAPCs by exploiting solution structure and recursive per-antenna updates, with convergence to stationary points. Simulations report substantially lower complexity, including 0.4 seconds versus 97 seconds at M = 1024 for R-WMMSE versus WMMSE.

  • Problem

    WSR maximization in massive MU-MIMO is NP-hard, and existing optimization-based approaches generally have cubic complexity in the number of BS antennas.

  • Method

    The paper proposes R-WMMSE for SPC by exploiting low-dimensional subspace and full-power properties, and PAPC-WMMSE for PAPCs using recursive per-antenna block updates.

  • Results

    At M = 1024, R-WMMSE takes 0.4 seconds to converge versus 97 seconds for WMMSE, while achieving almost the same WSR performance under the reported SPC setting.

  • Takeaways & Limitations

    R-WMMSE and PAPC-WMMSE provide linear-complexity WMMSE approaches with simple updates and guaranteed convergence to stationary points for massive MU-MIMO WSR maximization.

Abstract

from arXiv · show

Precoding design for maximizing weighted sum-rate (WSR) is a fundamental problem for downlink of massive multi-user multiple-input multiple-output (MU-MIMO) systems. It is well-known that this problem is generally NP-hard due to the presence of multi-user interference. The weighted minimum mean-square error (WMMSE) algorithm is a popular approach for WSR maximization. However, its computational complexity is cubic in the number of base station (BS) antennas, which is unaffordable when the BS is equipped with a large antenna array. In this paper, we consider the WSR maximization problem with either a sum-power constraint (SPC) or per-antenna power constraints (PAPCs). For the former, we prove that any nontrivial stationary point must have a low-dimensional subspace structure, and then propose a reduced-WMMSE (R-WMMSE) with linear complexity by exploiting the solution structure. For the latter, we propose a linear-complexity WMMSE approach, named PAPC-WMMSE, by using a novel recursive design of the algorithm. Both R-WMMSE and PAPC-WMMSE have simple closed-form updates and guaranteed convergence to stationary points. Simulation results verify the efficacy of the proposed designs, especially the much lower complexity as compared to the state-of-the-art approaches for massive MU-MIMO systems.

I. INTRODUCTION

The introduction frames WSR-maximizing precoding as an NP-hard problem whose computational cost is especially challenging for massive MU-MIMO. It proposes linear-complexity WMMSE variants for SPC and PAPCs, supported by structural analysis and convergence guarantees.

  • Massive MU-MIMO precoding must maximize weighted sum-rate under power constraints, but WSR maximization is NP-hard and difficult for hundreds or thousands of BS antennas.
  • Classical WMMSE is widely used because of its simple closed-form updates, yet its matrix inversion makes complexity cubic in the number of BS antennas.
  • The paper asks whether precoding can achieve linear complexity in BS antennas while retaining convergence guarantees, and answers affirmatively for SPC and PAPCs.
  • R-WMMSE with linear complexity for the SPC case: For SPC, R-WMMSE exploits low-dimensional subspace and full-power properties to reduce the decision space and avoid high-dimensional WMMSE operations.
  • PAPC-WMMSE for the PAPC case: For PAPCs, PAPC-WMMSE splits precoders into per-antenna blocks and uses recursive design to obtain closed-form updates, linear complexity, and convergence to stationary points.
  • PAPC-WMMSE for the PAPC case: The proposed PAPC-WMMSE is reported to outperform state-of-the-art algorithms in both WSR performance and CPU time.

B. Problem Formulation

The paper formulates weighted sum-rate maximization for downlink MU-MIMO under sum-power and per-antenna constraints. Both formulations are nonconvex and NP-hard, with PAPCs introducing multiple quadratic constraints.

  • B. Problem Formulation: The optimization seeks precoders for all users that maximize system weighted sum-rate subject to power constraints.
  • B. Problem Formulation: Each user’s priority is represented by weight α_k, while R_k denotes that user’s achievable rate.
  • B. Problem Formulation: The paper considers two constraint classes: a sum-power constraint and per-antenna power constraints.
  • 1) WSR Maximization With SPC: Under SPC, total transmit power across all BS antennas is limited by a single budget P_max.
  • 2) WSR Maximization With PAPCs: PAPCs impose an individual transmit-power limit P_m on each BS antenna through the corresponding diagonal element of the precoder covariance.
  • 2) WSR Maximization With PAPCs: PAPC optimization is more difficult than SPC optimization because it contains more quadratic constraints.
  • 2) WSR Maximization With PAPCs: Both SPC and PAPC WSR maximization problems are NP-hard because their objectives are highly nonlinear and nonconvex.

III. THE CLASSICAL WMMSE: A REVISIT

The classical WMMSE framework transforms WSR maximization into an equivalent weighted MSE minimization problem with auxiliary variables and solves it by block coordinate descent. Its precoder update remains the computational bottleneck for massive arrays.

  • WMMSE reformulates WSR maximization as a tractable weighted MSE minimization problem using auxiliary variables.
  • The reformulation can be derived through a matrix variational identity with auxiliary variables Γ and Ω.
  • The auxiliary variables in WMMSE play the same roles as the variational variables in the matrix identity.
  • Although the joint problem is nonconvex, it is convex in each block variable, enabling block coordinate descent updates.
  • The algorithm updates U, W, and P sequentially, with U and W obtained through closed-form block updates.
  • The precoder update requires an M-dimensional matrix inversion for SPC or interior-point methods, producing complexity of at least O(M^3).
  • Algorithm 1 initializes feasible P and W_k = I, then repeats updates until the WSR-related stopping criterion is within ε.

IV. THE PROPOSED R-WMMSE FOR THE SPC CASE

For the SPC case, the paper reduces WMMSE’s high-dimensional precoder updates by exploiting the structure of nontrivial stationary points, yielding an equivalent lower-dimensional formulation and a linear-complexity R-WMMSE algorithm.

  • The original SPC WMMSE algorithm requires high-dimensional matrix inversion in each iteration, giving cubic complexity in the number of BS antennas.
  • Important properties: Any nontrivial stationary point is a triviality-excluding solution whose precoders lie in the range space of HᴴH, so P_k = HᴴH X_k.The paper defines trivial stationary points as those producing zero WSR.
  • Problem reformulation: The low-dimensional subspace property reduces the decision variable from P ∈ C^(M×D) to X ∈ C^(N×D) when M ≫ N.
  • Problem reformulation: Although the reduced problem has a smaller decision space, applying WMMSE still requires bisection to handle the power constraint.
  • Problem reformulation: Every nontrivial stationary point satisfies the SPC with equality, enabling the power constraint to be eliminated through the fractional structure of SINR.
  • R-WMMSE derivation: The resulting reformulation is equivalent to an unconstrained weighted sum-MSE minimization problem, from which the paper derives the reduced WMMSE algorithm.

B. The Proposed R-WMMSE Algorithm

R-WMMSE applies block coordinate descent to a reduced SPC formulation, using closed-form updates and exploiting lower-dimensional matrix operations. Its complexity is linear in the number of BS antennas, and its limit points are stationary.

  • Algorithm design: R-WMMSE applies block coordinate descent to the reduced problem, with globally solvable closed-form updates for U, W, and X.The objective is convex in each block variable separately.
  • Algorithm design: The reduced formulation replaces the original precoders through a low-dimensional representation involving H and X.The final precoders are recovered as Pk = √β H^H H Xk.
  • Complexity: O(MN^2) preprocessing is linear in M, while each subsequent iteration is independent of M and dominated by an O(D^3) inversion.This is lower than the O(M^3) complexity of classical WMMSE.
  • Complexity: When N = D, the Woodbury identity enables an efficient inversion strategy requiring only one large-scale N-dimensional matrix inversion.The recursion avoids repeated large-scale inversions during the iterative process.
  • Convergence: Every limit point generated by R-WMMSE is a stationary point of the reduced problem, with the corresponding precoders yielding a nontrivial stationary point of the original SPC problem.The paper therefore establishes convergence to stationary points while retaining linear complexity in M.
  • Extension to PAPCs: Normalizing an R-WMMSE solution produces a feasible PAPC solution, but that solution may be far from optimal under PAPCs.This motivates a separate PAPC-WMMSE design rather than relying on straightforward normalization.

V. THE PROPOSED PAPC-WMMSE FOR THE PAPCS CASE

PAPC-WMMSE directly handles per-antenna constraints by splitting the precoder into antenna-wise blocks and recursively exploiting their structure. The resulting algorithm has closed-form updates, linear per-iteration complexity, and stationary-point convergence.

  • Algorithm design: PAPC-WMMSE directly applies the WMMSE framework to the WSR problem with per-antenna power constraints.The method is developed as an iterative solution rather than by normalizing an SPC solution.
  • Closed-form updates: Each antenna-wise subproblem is a convex quadratic problem whose scaled-norm structure permits a closed-form solution instead of bisection.The quadratic term with respect to pm has the required scaled Euclidean norm form.
  • Recursive design: Recursive computation reuses the special structure of the precoder matrix, avoiding quadratic aggregation across antennas and producing the linear-complexity PAPC-WMMSE algorithm.The algorithm iteratively updates U, W, and pm for all antennas until convergence.
  • Convergence: Every limit point generated by PAPC-WMMSE is a stationary point of the PAPC-constrained problem.The convergence result applies to the iterative sequence of U, W, and P.
  • Complexity: Each PAPC-WMMSE iteration has complexity O(MND), which is linear in the number of BS antennas and below the cubic complexity of existing algorithms.The dominant contributions are the updates in lines 3–5 and the block-diagonal computations in lines 7–11.

A. Simulation Setup

The simulations use a single-cell massive MU-MIMO setup with randomized channels, specified power constraints, and equal user priority weights. Results are averaged over 100 channel realizations.

  • System setup: The simulated BS has M antennas, while each of K users has 4 receive antennas and 2 or 4 data streams.The setup models a single-cell massive MU-MIMO system.
  • Power constraints: The SPC budget is Pmax = 10 W, while the PAPC maximum transmit power is Pmax/M per antenna.The two constraint settings use matched total-power scaling.
  • Channel model: Channels follow a circularly symmetric standard complex normal distribution with user-to-BS pathloss based on distances from 0.1 to 0.3 km.The pathloss model is 128.1 + 37.6 log10(ω) dB.
  • Evaluation protocol: User priority weights are equal, and simulation results are averaged over 100 randomly generated channel realizations.Noise power is also set equally for all users.
  • Implementation: Computations use Matlab R2020a on an AMD Ryzen 7 5800H system with 16 GB RAM and Windows 10 64-bit.

B. R-WMMSE Performance Evaluation for the SPC Case

For the SPC case, R-WMMSE matches WMMSE’s WSR while substantially reducing computation as the antenna array grows. The simulations also report convergence and WSR advantages over ZF or normalized baselines in the evaluated settings.

  • Convergence: R-WMMSE and WMMSE converge to the same WSR value, with R-WMMSE often converging better during the first iterations from the same initialization.The reported explanation is that R-WMMSE relaxes the SPC during iterations.
  • Computational complexity: At M = 128, R-WMMSE requires about 20% of WMMSE’s average CPU time, while both algorithms’ CPU times increase slowly with K.
  • Computational complexity: At M = 1024, WMMSE takes 97 seconds versus 0.4 seconds for R-WMMSE, making R-WMMSE 200+ times faster for M > 1000.The observed behavior is consistent with linear complexity for R-WMMSE and cubic complexity for WMMSE in M.
  • WSR performance: R-WMMSE achieves almost the same WSR as WMMSE and significantly outperforms ZF across the evaluated SNRs with M = 128, K = 16, and Dk = 4.The cited discussion attributes the WMMSE/ZF gap to ZF’s lack of optimized power control.
  • PAPC comparison: PAPC-WMMSE converges within 20 iterations in one case and 5 iterations in another, while achieving much better WSR than normalized WMMSE.
  • PAPC comparison: Under PAPCs, PAPC-WMMSE uses less CPU time than normalized WMMSE at M = 128 and scales linearly with M in the reported analysis.At M = 512, HBF and normalized WMMSE take significantly more time than PAPC-WMMSE.
  • PAPC comparison: Under PAPCs, PAPC-WMMSE outperforms HBF and normalized WMMSE in WSR across the evaluated SNRs, while normalized ZF performs worst.

APPENDIX A PROOF OF PROPOSITION 2

The proof analyzes the KKT conditions of the SPC-constrained WSR problem. It establishes that nontrivial stationary points correspond to a positive power-constraint multiplier and lie in the channel-induced low-dimensional subspace.

  • KKT analysis: The proof uses KKT conditions, including stationarity, complementary slackness, and primal and dual feasibility, for the SPC problem.
  • Multiplier property: Any nontrivial stationary point has a strictly positive SPC Lagrange multiplier, λ⋆ > 0.
  • Multiplier property: Assuming λ⋆ = 0 leads to HkP⋆k = 0 for every user, contradicting the nontriviality of the stationary point.
  • Multiplier property: Conversely, λ⋆ > 0 rules out a trivial stationary point because the stationarity condition would imply P⋆ = 0, violating the power constraint.
  • Subspace property: Using λ⋆ > 0 in the stationarity conditions shows that each precoder block lies in the range space of H^H.

APPENDIX B EZF PRECODING

EZF precoding constructs an equivalent channel from dominant right singular vectors and then applies zero forcing to that reduced channel. The resulting precoder also satisfies the low-dimensional subspace property.

  • Construction: EZF first applies thin SVD to each user channel and selects the Dk right singular vectors associated with the largest singular values.
  • Construction: The selected right singular vectors form an equivalent channel on which ZF precoding is performed.
  • Subspace property: The EZF precoder’s range is contained in the range space of H^H, so it follows the low-dimensional subspace property.
  • Stationary-point analysis: The appendix establishes stationary-point equivalence by comparing the KKT conditions of the relevant constrained and unconstrained problems.

APPENDIX D PROOF OF THEOREM 2

The proof establishes convergence of the block-coordinate procedure for the transformed R-WMMSE problem. It then maps any stationary point of that problem to a nontrivial stationary point of the original WSR problem.

  • Convergence proof: Because the transformed objective is continuously differentiable and convex in each block variable, BCD theory guarantees convergence to a stationary point.
  • Stationary-point mapping: The proof defines a stationary point of the transformed problem and constructs the corresponding precoder P⋆ from it.
  • Stationary-point mapping: The constructed solution is therefore a nontrivial stationary point of the original SPC-constrained WSR problem.
  • Stationary-point mapping: Relations between the transformed and original objectives, together with the update conditions, show that the constructed P⋆ satisfies the original KKT stationarity condition.
Loading 2205.06225v2…