PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Multiuser Transmit Beamforming: A Difficult Problem with a Simple Solution Structure

Emil Björnson, Mats Bengtsson, Björn Ottersten

arXiv:1404.0408v2cs.IT

TL;DR

Multiuser transmit beamforming must balance competing performance objectives, yet its optimization is generally NP-hard. This lecture characterizes an optimal linear beamforming structure with enough design parameters to preserve optimality, revealing interference-limited and balanced regimes across SNRs.

  • Problem

    General transmit beamforming optimization is generally NP-hard, making the competing performance objectives difficult to optimize jointly.

  • Method

    The lecture develops a simple structure for optimal linear transmit beamforming with sufficient design parameters to avoid loss of optimality.

  • Results

    At high SNR, optimal beamforming reduces interference leakage, while at intermediate SNR it balances the conflicting objectives.

  • Takeaways & Limitations

    The resulting simple structure provides insights into optimal beamforming and its geometric interpretation across arbitrary SNR.

  • Takeaways & Limitations

    In general, heuristic beamforming requires all K design degrees of freedom, while simpler schemes may lack sufficient freedom to achieve optimal performance.

Abstract

from arXiv · show

Transmit beamforming is a versatile technique for signal transmission from an array of $N$ antennas to one or multiple users [1]. In wireless communications, the goal is to increase the signal power at the intended user and reduce interference to non-intended users. A high signal power is achieved by transmitting the same data signal from all antennas, but with different amplitudes and phases, such that the signal components add coherently at the user. Low interference is accomplished by making the signal components add destructively at non-intended users. This corresponds mathematically to designing beamforming vectors (that describe the amplitudes and phases) to have large inner products with the vectors describing the intended channels and small inner products with non-intended user channels. While it is fairly easy to design a beamforming vector that maximizes the signal power at the intended user, it is difficult to strike a perfect balance between maximizing the signal power and minimizing the interference leakage. In fact, the optimization of multiuser transmit beamforming is generally a nondeterministic polynomial-time (NP) hard problem [2]. Nevertheless, this lecture shows that the optimal transmit beamforming has a simple structure with very intuitive properties and interpretations. This structure provides a theoretical foundation for practical low-complexity beamforming schemes. (See this lecture note for the complete abstract/introduction)

RELEVANCE · PREREQUISITES · PROBLEM (P1): POWER MINIMIZATION WITH SINR CONSTRAINTS

The lecture develops an interpretable, optimal linear transmit-beamforming structure with enough design parameters to preserve optimality and accommodate practical cellular constraints. It prepares this analysis by formulating a downlink SDMA power-minimization problem that meets fixed user SINR targets with minimum transmit power.

  • RELEVANCE: Transmit beamforming strengthens intended-user signals while reducing interference toward non-intended users through adapted main-lobes and weak side-lobes.The visualization describes beam adaptation in a line-of-sight scenario.
  • RELEVANCE: Existing schemes may lack sufficient degrees of freedom to achieve optimal performance.This limitation motivates a structure with enough design flexibility to preserve optimality.
  • RELEVANCE: Optimal beamforming is structured to retain sufficient design parameters, provide insight, and extend to practical cellular-network constraints.The lecture’s purpose is to expose a simple optimal structure without sacrificing optimality.
  • PREREQUISITES: Readers need basic knowledge of linear algebra, communication theory, and convex optimization.These are the prerequisites stated for the lecture note.
  • PROBLEM (P1): POWER MINIMIZATION WITH SINR CONSTRAINTS: The modeled system is a downlink with an N-antenna base station serving K single-antenna users through SDMA and linear beamforming vectors w1, . . . , wK.Each data signal is unit-power normalized, and hk denotes user k’s channel.
  • PROBLEM (P1): POWER MINIMIZATION WITH SINR CONSTRAINTS: The squared norm ||wk||2 represents the transmit power allocated to user k, while wk/||wk|| is its beamforming direction.The direction is a vector-space direction and corresponds to a physical direction only in LoS scenarios.
  • PROBLEM (P1): POWER MINIMIZATION WITH SINR CONSTRAINTS: Although the γ-parameters affect the optimal beamforming solution, the solution structure remains the same.This simpler problem prepares the later analysis of a general SINR-based utility formulation and optimal beamforming structure.
  • PROBLEM (P1): POWER MINIMIZATION WITH SINR CONSTRAINTS: Problem (P1) minimizes transmit power subject to fixed SINR targets γ1, . . . , γK for all users.The targets can represent SINRs required to achieve specified data rates and directly affect the optimal solution.

SOLUTION TO PROBLEM (P1)

The nonconvex beamforming problem is reformulated through phase rotation into a convex second-order cone problem, enabling strong duality and KKT-based analysis. The optimal beamformers have directions determined by the Lagrange multipliers, while their powers follow from active SINR constraints and linear equations.

  • Convex reformulation: Phase ambiguity allows each beamforming vector to be rotated so its intended-channel inner product is real-valued and positive, yielding a convex SINR reformulation.The reformulated SINR constraint is a second-order cone constraint.
  • Convex reformulation: Strong duality holds and the KKT conditions are necessary and sufficient for the reformulated problem, with these properties also holding for the original problem (P1).The Lagrange multipliers λk are associated with the kth SINR constraints.
  • Optimal beamforming structure: The stationarity KKT conditions show that each optimal wk is parallel to a matrix-inverse expression involving the identity matrix, channel vectors, and Lagrange multipliers.This establishes the optimal beamforming direction for each user as a function of the multipliers.
  • Optimal beamforming structure: The SINR constraints hold with equality at the solution, so the known beamforming directions reduce the unknown beamforming powers to K linear equations.Combining the resulting powers and directions gives the structure of optimal beamforming as a function of λ1, . . . , λK.

PROBLEM (P2): GENERAL TRANSMIT BEAMFORMING OPTIMIZATION

Problem (P2) seeks to maximize an arbitrary utility function that is strictly increasing in all users’ SINRs under a total transmit-power limit P. Although this optimization is generally NP-hard for many common utilities, the optimal solution structure can nevertheless be obtained easily.

  • Optimization objective: P2 maximizes an arbitrary utility function f(SINR1, ..., SINRK) that is strictly increasing in every user’s SINR.The optimization is over the beamforming vectors w1, ..., wK.
  • Optimization objective: The optimization imposes a total transmit-power constraint limited by P.
  • Computational difficulty: P2 is generally NP-hard for many common utility functions, including sum rate.Despite the concise formulation, the problem is generally very hard to solve.
  • Optimal-solution structure: Nevertheless, the optimal solution structure of P2 can be obtained easily.

SOLUTION STRUCTURE TO PROBLEM (P2)

The optimal beamforming for (P2) can be obtained by solving (P1) at the optimal SINR values, while its characterization yields a simple common-matrix structure. This connection explains both the equivalence and the practical value of the solution form.

  • Connection between (P1) and (P2): Solving (P1) with γ_k = SINR⋆_k for all users produces beamforming vectors that also solve (P2).The resulting vectors are feasible for (P2) and achieve its optimal SINR values.
  • Connection between (P1) and (P2): (P1) minimizes the power required to achieve prescribed SINRs, whereas (P2) must jointly determine the optimal SINRs and beamforming vectors.This difference makes finding the SINR targets in (P2) the difficult part of the connection.
  • Optimal beamforming structure: Because the matrix inverse in (10) is common to all users, the optimal beamforming vectors can be collected into a compact matrix form.The construction uses the channel matrix H, the diagonal matrix Λ of λ-parameters, and a diagonal power-allocation matrix P.

INTUITION BEHIND THE OPTIMAL STRUCTURE

The optimal beamforming direction combines alignment with the intended channel and suppression of interference toward co-user channels. It therefore lies between maximum ratio transmission and a direction orthogonal to the co-user channels, with the balance determined by the utility function and user priorities.

  • Structure: The optimal beamforming direction has two main components: the intended-user channel h_k and a matrix involving the co-user channels.These components jointly shape the direction used for multiuser transmission.
  • MRT: MRT aligns the beamforming vector with h_k and maximizes the received signal power for K = 1.This follows from the Cauchy-Schwarz inequality.
  • Multiuser limitation: For multiple users, MRT is not optimal because it does not account for inter-user interference.The optimal direction modifies the channel-based direction to reduce interference in co-user directions.
  • Geometric interpretation: The optimal beamforming lies between MRT and a vector orthogonal to all co-user channels, balancing signal power against interference suppression.This geometric interpretation is illustrated in Figure 2.
  • User priorities: The balance depends on the utility function f(·, . . . , ·), while λ_i ≥0 represents user i’s priority.A larger λ_i means that other users’ beamforming vectors will be more orthogonal to h_i.

Asymptotic Properties

As SNR decreases, optimal beamforming converges to maximum-ratio transmission (MRT), while at high SNR it converges to zero-forcing beamforming (ZFBF). With very large arrays, channel orthogonality makes ZFBF asymptotically optimal, although MRT performs relatively well without matching ZFBF.

  • SNR asymptotics: At low SNR, noise dominates interference, so the beamforming vectors become scaled channel vectors, equivalent to MRT.This regime is represented by σ2 →∞.
  • SNR asymptotics: At high SNR with N ≥ K, interference dominates noise and the solution becomes ZFBF, eliminating inter-user interference by orthogonal projection.The condition N ≥ K provides at least one spatial degree of freedom per user.
  • SNR asymptotics: At arbitrary SNR, optimal beamforming balances the MRT and ZFBF extremes.MRT maximizes signal power, whereas ZFBF removes interference.
  • Large-array asymptotics: As N →∞, user channels become orthogonal because channel norms grow proportionally to N while cross-products grow more slowly.The resulting orthogonality reduces interference and permits lower transmit power.
  • Large-array asymptotics: For very large arrays, ZFBF is asymptotically optimal, while MRT performs relatively well but does not achieve ZFBF’s performance.This follows from asymptotic channel orthogonality.

Relationship to Receive Beamforming

Uplink receive beamforming resembles downlink transmit beamforming but differs fundamentally because interference arrives through other users’ channels rather than their beamforming vectors. This difference enables separate per-user optimization, yielding a receive beamformer that is optimal across uplink SINR objectives and also minimizes MSE, while parameter matching with transmit beamforming is generally limited to symmetric scenarios.

  • Interference structure: A fundamental difference is that downlink interference comes from other users’ beamformers, whereas uplink interference arrives through other users’ channels.This difference has a fundamental impact on the optimization.
  • Per-user optimization: Because each uplink SINR contains only its own receive beamforming vector, the beamformer can be optimized separately for each user.The uplink scenario uses a unit-norm receive beamforming vector v_k to spatially discriminate user k from interfering signals.
  • Optimal solution: The receive-beamforming solution follows from maximizing a generalized Rayleigh quotient.This characterization establishes the stated optimal solution.
  • Optimality properties: The same receive beamformer is optimal regardless of which function of the uplink SINRs is optimized and also minimizes the mean squared error.It is therefore known as the Wiener filter and minimum MSE (MMSE) filter.
  • Transmit–receive relationship: Transmit and receive beamforming share the same structure, but setting λ_k equal to uplink power q_k is generally optimal for downlink beamforming only in symmetric scenarios.In general, the parameters differ because uplink signals traverse different channels and experience channel-norm variations, while downlink signals reach each user through a single channel.

Heuristic Transmit Beamforming

Heuristic beamforming uses the optimal beamforming structure with judiciously selected λ-parameters, yielding low-complexity schemes such as regularized zero-forcing or transmit MMSE beamforming. These heuristics can approach optimal performance when there are many more antennas than users, but generally lack the degrees of freedom needed for asymmetric conditions.

  • Heuristic construction: The beamforming structure provides a foundation for heuristic schemes that select λ-parameters to obtain close-to-optimal beamforming.Finding the optimal λ-parameters is generally difficult.
  • Heuristic construction: Setting all parameters equal produces regularized zero-forcing, also known as transmit MMSE or related signal-to-leakage-and-noise ratio beamforming.The single parameter can be optimized for a transmission scenario by conventional line search.
  • Optimality conditions: The heuristic direction is truly optimal only in special symmetric scenarios, where transmit MMSE performs well because it satisfies the optimal beamforming structure.The example assumes equally strong, well-separated channels and a utility symmetric in SINR1, ..., SINRK.
  • Limitations: In general, optimal beamforming requires all K λ-degrees of freedom because a single regularized-ZFBF parameter cannot manage asymmetric user channels and utility functions.Fine-tuning the K = 4 parameters has exponential complexity in K.

EXTENSIONS

The section briefly outlines extensions to settings with multiple base stations and practical power constraints.

  • The paper considers extensions involving multiple BSs and practical power constraints.

Multiple Cooperating Base Stations · General Power and Shaping Constraints

With multiple cooperating base stations, each user can be served by only a subset of antennas, so beamforming balances signal power and interference leakage within that subset. More general practical power and shaping requirements are modeled by quadratic constraints whose weighting matrices control power in specified subspaces and interference directions.

  • Multiple Cooperating Base Stations: Each user is served by only a subset of cooperating base stations, avoiding the need to distribute all users’ data to every base station.The association is represented by a diagonal matrix D_k, with d_k,n = 1 when antenna n transmits to user k and 0 otherwise.
  • Multiple Cooperating Base Stations: The effective beamforming vector for user k is D_kw_k rather than w_k.Substituting this effective vector into the derivations yields the corresponding optimal beamforming structure.
  • Multiple Cooperating Base Stations: Signal-power and interference-leakage balancing occurs only among antennas that transmit to the particular user.The optimal structure uses positive parameters λ_1, . . . , λ_K.
  • General Power and Shaping Constraints: Practical systems impose constraints beyond total transmit power, including per-antenna and per-base-station limits, EIRP regulations, and interference suppression toward other systems.These requirements motivate a general constrained formulation.
  • General Power and Shaping Constraints: L quadratic constraints model power limits in specified subspaces through positive semidefinite, user-specific weighting matrices Q_ℓ,k and bounds P_ℓ.The total-power case uses L = 1 and Q_1,k = I_N, while per-antenna constraints use L = N with one nonzero diagonal element per weighting matrix.
  • General Power and Shaping Constraints: User-specific weighting matrices can precisely shape interference, such as limiting leakage at user i by selecting Q_ℓ,k = h_i h_i^H for k ≠ i and Q_ℓ,i = 0.This construction limits the relevant interference leakage to P_ℓ.
  • General Power and Shaping Constraints: The optimal beamforming under these constraints introduces L nonnegative parameters μ_1, . . . , μ_L that represent the importance of shaping each power constraint.A large μ_ℓ suppresses transmission into the subspace weighted by Q_ℓ,k, whereas an inactive constraint has μ_ℓ = 0 and no effect.
  • General Power and Shaping Constraints: The shaping parameters satisfy Σ_{ℓ=1}^L P_ℓ μ_ℓ = P_max, where P_max = max_ℓ P_ℓ.This relation characterizes the parameters associated with the active power constraints.

LESSONS LEARNED AND FUTURE AVENUES · AUTHORS · REPRODUCIBLE RESEARCH

Although optimal multiuser transmit beamforming is difficult to compute, it has a simple, intuitive structure with one design parameter per user. The structure extends to practical multi-cell scenarios and motivates open problems and reproducible Matlab implementations.

  • LESSONS LEARNED AND FUTURE AVENUES: Optimal multiuser transmit beamforming has a simple, intuitive structure with only one design parameter per user.
  • LESSONS LEARNED AND FUTURE AVENUES: At low SNRs, optimal beamforming maximizes received signal powers; at high SNRs, it minimizes interference leakage.
  • LESSONS LEARNED AND FUTURE AVENUES: At intermediate SNRs, optimal beamforming balances maximizing received signal power against minimizing interference leakage.
  • LESSONS LEARNED AND FUTURE AVENUES: The optimal beamforming structure can be extended to practical multi-cell scenarios.
  • LESSONS LEARNED AND FUTURE AVENUES: Open problems include robustness to imperfect CSI, multi-stream beamforming for multi-antenna users, and multicasting to user groups.
  • LESSONS LEARNED AND FUTURE AVENUES: Another open problem is adaptive λ-parameter selection based on the utility function.
  • AUTHORS: The authors are affiliated with Link¨oping University, Sup´elec, KTH Royal Institute of Technology, and the University of Luxembourg.
  • REPRODUCIBLE RESEARCH: Supplementary downloadable material provides Matlab code that can reproduce all results and is available through the authors' GitHub repository.
Loading 1404.0408v2…