Source-linked AI summary
Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part II: Algorithms
Gesualdo Scutari, Daniel P. Palomar, Sergio Barbarossa
TL;DR
The paper addresses optimal decentralized precoding and multiplexing for non-cooperative links sharing physical resources under power, spectral-mask, and error-probability constraints. It formulates the problems as strategic games and develops distributed waterfilling and gradient-projection algorithms to reach Nash equilibria. The proposed convergence conditions cover both sequential and simultaneous methods, while simultaneous IWFA is reported to be faster than sequential IWFA.
Problem
The paper seeks decentralized solutions for mutual-information or finite-constellation rate maximization among non-cooperative links sharing time and bandwidth under practical constraints.
Method
The paper formulates both problems as strategic non-cooperative games and proposes sequential and simultaneous iterative waterfilling and gradient-projection algorithms.
Results
The paper provides sufficient conditions for global convergence of the proposed algorithms, with simultaneous IWFA reported to converge faster than sequential IWFA.
Takeaways & Limitations
The algorithms retain distributed operation and low complexity while extending equilibrium computation to settings with spectral-mask constraints.
Abstract
from arXiv · showhide
In this two-part paper, we address the problem of finding the optimal precoding/multiplexing scheme for a set of non-cooperative links sharing the same physical resources, e.g., time and bandwidth. We consider two alternative optimization problems: P.1) the maximization of mutual information on each link, given constraints on the transmit power and spectral mask; and P.2) the maximization of the transmission rate on each link, using finite order constellations, under the same constraints as in P.1, plus a constraint on the maximum average error probability on each link. Aiming at finding decentralized strategies, we adopted as optimality criterion the achievement of a Nash equilibrium and thus we formulated both problems P.1 and P.2 as strategic noncooperative (matrix-valued) games. In Part I of this two-part paper, after deriving the optimal structure of the linear transceivers for both games, we provided a unified set of sufficient conditions that guarantee the uniqueness of the Nash equilibrium. In this Part II, we focus on the achievement of the equilibrium and propose alternative distributed iterative algorithms that solve both games. Specifically, the new proposed algorithms are the following: 1) the sequential and simultaneous iterative waterfilling based algorithms, incorporating spectral mask constraints; 2) the sequential and simultaneous gradient projection based algorithms, establishing an interesting link with variational inequality problems. Our main contribution is to provide sufficient conditions for the global convergence of all the proposed algorithms which, although derived under stronger constraints, incorporating for example spectral mask constraints, have a broader validity than the convergence conditions known in the current literature for the sequential iterative waterfilling algorithm.
1 Introduction and Motivation
The paper seeks decentralized precoding and multiplexing strategies for non-cooperative links sharing resources, formulating rate optimization as games whose Nash equilibria must be reached iteratively. Part II proposes waterfilling and gradient-projection algorithms with global convergence conditions, including spectral masks.
- Optimization problems: The paper studies mutual-information maximization and finite-constellation transmission-rate maximization under power, spectral-mask, and error-probability constraints.These are formulated as strategic non-cooperative games using Nash equilibrium as the optimality criterion.
- Game formulation: Part I reduced both matrix-valued games to a unified vector-valued power-control game without performance loss.Each user allocates power across frequency bins while treating multiuser interference as additive colored noise.
- Distributed computation: Distributed algorithms update users’ strategies either sequentially under a Gauss-Seidel schedule or simultaneously under a Jacobi schedule.Iterative updates are required because each user’s choice changes the interference perceived by others.
- Iterative waterfilling: The paper generalizes sequential IWFA with spectral masks and memory, and introduces simultaneous IWFA to address slow convergence and scheduling requirements.Simultaneous IWFA uses previous-iteration interference while retaining distributed operation and low complexity.
- Iterative waterfilling: Simultaneous IWFA is reported to converge faster than sequential IWFA while preserving distributed and low-complexity operation.The comparison is presented as a convergence-speed result for both algorithms.
- Gradient projection and convergence: The paper also proposes sequential and simultaneous iterative gradient-projection algorithms and gives sufficient conditions for global convergence of the distributed algorithms.The convergence conditions are stated to have broader validity than earlier conditions, including results developed without mask constraints.
2 System Model and Problem Formulation
The model is a Gaussian vector interference channel with non-cooperative links, where each player optimizes frequency-bin power under power, spectral-mask, and, for finite constellations, error-probability constraints. The resulting equilibria are characterized by constrained waterfilling fixed points.
- System model: The system is a Gaussian vector interference channel composed of Q non-cooperative links, with interference treated as additive colored noise.The formulation targets distributed algorithms without interference cancellation.
- Optimization problems: P.1 maximizes mutual information under transmit-power and spectral-radiation-mask constraints, while P.2 maximizes finite-constellation transmission rate with an average uncoded error-probability constraint.P.2 retains the constraints of P.1 and adds the error-probability requirement.
- Optimal strategy: Part I showed that optimal transmission uses Gaussian signaling and diagonal transmission through channel eigenmodes, regardless of channel state, power budget, masks, and interference levels.This result enables recasting both matrix-valued games as a vector power-control game without performance loss.
- Strategy constraints: Each player’s strategy is a power allocation across frequency bins, bounded by total-power and per-bin spectral-mask constraints.The payoff depends on the player’s allocation and the other players’ allocations; the SNR gap distinguishes P.1 from P.2.
- Equilibrium characterization: The Nash equilibria coincide with solutions of a nonlinear fixed-point equation involving each user’s constrained waterfilling operator.The water level is selected to satisfy the user’s power constraint, and the feasible set includes interval bounds on per-bin power.
- Problem addressed: Classical power-control results apply only as special cases without spectral masks, whereas the paper addresses the constrained system through totally distributed algorithms.The target is to reach the fixed-point solutions that yield the Nash equilibria of the game.
3 Waterfilling Operator as a Projector
The waterfilling operator can be interpreted as a Euclidean projection onto a simplex, including weighted and spectral-mask-constrained cases. This projector interpretation supports convergence analysis for distributed iterative algorithms in multiuser games.
- Projector interpretation: The paper interprets the waterfilling operator as a proper Euclidean projector.This interpretation is introduced to prove convergence properties of subsequent algorithms.
- Projector interpretation: 22: Lemma 1 extends the projection result to optimization with interval bounds [0, pmax(k)].The interval bounds represent spectral mask constraints.
- Single-user waterfilling: The single-user waterfilling solution is the projection of −insr onto a simplex.The graphical interpretation applies to the two-dimensional simplex in the two-user single-carrier case.
- Weighted projection: With any positive weight vector, waterfilling is a projection onto the simplex under a weighted Euclidean norm.The weighted norm uses weights w1, . . . , wN.
- Graphical interpretation: In the two-user graphical case, interior points allocate power across both channels, whereas exterior points allocate all power to the channel with highest normalized gain.The gray region distinguishes these allocation regimes.
- Multiuser extension: In the multiuser game, each user’s waterfilling operator is the projection of −insrq(p−q) onto the simplex Pq.The operator depends on the other users through received interference, and Nash equilibria correspond to fixed points of the associated mapping.
- Multiuser extension: The fixed-point formulation makes all Nash equilibria of the game correspond to fixed points of the waterfilling mapping.Properties of this mapping are used to derive sufficient convergence conditions for distributed iterative algorithms.
4 Distributed Algorithms
This section develops distributed iterative algorithms for reaching Nash equilibria, including sequential and simultaneous waterfilling and gradient projection methods. Under sufficient conditions, these algorithms converge globally to the unique equilibrium, with simultaneous waterfilling offering faster updates than sequential waterfilling.
- The section proposes totally distributed iterative algorithms based on waterfilling and gradient projection mappings.The algorithms include sequential and simultaneous variants of both classes.
- Sequential and simultaneous waterfilling algorithms update users’ power allocations sequentially or at the same time.The sequential IWFA follows a Gauss-Seidel scheme, while simultaneous algorithms update all users concurrently.
- Under the stated sufficient conditions, sequential IWFA converges linearly to the unique Nash equilibrium from any feasible initialization and updating schedule.The result also establishes global convergence and uniqueness under condition (C1).
- The same sufficient conditions guarantee that simultaneous IWFAs converge linearly and globally to the unique Nash equilibrium.Additional weaker convergence conditions are also provided for the simultaneous algorithms.
- Simultaneous IWFA is faster than sequential IWFA, especially with many active links, while simultaneous IGPA has similar convergence speed and serves as an alternative.Sequential updates force each user to wait for previously scheduled users, whereas simultaneous updates avoid that waiting.
- The gradient projection approach uses the equivalence between Nash equilibria and solutions of a nonlinear variational inequality problem.This equivalence enables totally distributed algorithms with the same computational complexity as the IWFAs.
5 Conclusions
The paper studies decentralized algorithms for reaching Nash equilibria in wideband non-cooperative games, covering mutual-information and finite-constellation rate optimization under power, spectral-mask, and error-probability constraints. It proposes sequential and simultaneous waterfilling and gradient-projection methods, derives global-convergence conditions, and identifies broader validity than prior sequential-IWFA conditions.
- The two optimization games address mutual-information maximization and finite-constellation transmission-rate maximization under power, spectral-mask, and average-error constraints.
- Part II focuses on reaching the equilibria characterized in Part I through totally decentralized algorithms.
- The sequential IWFA generalizes iterative waterfilling to incorporate spectral-mask constraints, while the simultaneous IWFA converges faster than the sequential version.
- Sequential and simultaneous IGPAs provide alternative gradient-projection methods, linking Nash equilibria with solutions of the corresponding variational inequality problem.
- The simultaneous IGPA has approximately the same convergence speed and computational complexity as the simultaneous IWFA, making it an alternative to waterfilling-based algorithms.
- Sufficient conditions are derived for global convergence of all proposed algorithms; despite stronger constraints such as spectral masks, these conditions have broader validity than prior sequential-IWFA conditions.
- Extensions to totally asynchronous updates and to channels or interference covariance matrices known only with estimation error remain under investigation.
A Proof of Lemma 1
The proof establishes feasibility and characterizes the optimizer of the constrained convex problem through KKT conditions. It partitions solutions according to whether each component is zero, interior, or at its spectral maximum, with a multiplier chosen to satisfy the total constraint.
- A solution exists for the convex problem under the stated feasibility assumptions, including nontrivial aggregate spectral-mask capacity.
- Because the problem satisfies Slater’s condition, the KKT conditions are necessary and sufficient for optimality.
- The proof formulates the Lagrangian and its KKT conditions using nonnegative primal and dual variables.
- The componentwise optimizer is partitioned into zero, interior, and upper-bound cases according to the multiplier and the spectral-mask limit.
- The multiplier is selected so that the normalized sum constraint is satisfied.
B Properties of Waterfilling Projection
The section rewrites waterfilling as a mapping on an effective feasible set and establishes its nonexpansive and contraction properties under suitable conditions.
- Effective feasible set: The effective feasible set Peff removes carriers that a user would never use under the given power budget and interference level.This set contains feasible allocations with zero power on those carriers.
- Waterfilling mapping: Nash equilibria correspond to fixed points of the waterfilling mapping T on Peff.At least one fixed point exists because the game has a Nash equilibrium.
- Projection property: The waterfilling projector is nonexpansive in the weighted seminorm used for the effective feasible set.The proof uses equivalence between the projection optimization problem and an objective modified by the effective-set construction.
- Contraction property: Under condition (63), T is a block-contraction with respect to the weighted block-maximum norm.The contraction proof combines the waterfilling operator bound with the nonexpansive projector property.
- Contraction property: The contraction analysis applies for any relaxation parameters αq in [0,1), and the sufficient condition does not depend on their particular values.The matrix α combines the relaxation parameters with the interference coupling matrix Hmax.
C Proof of Theorem 1 and Theorem 2
Theorem 1 and Theorem 2 are proved by identifying the sequential algorithms with Gauss–Seidel iterations of the waterfilling mapping and applying its contraction properties.
- Algorithmic representation: The sequential IWFA is an instance of the smoothed sequential IWFA, with iterates confined to Peff after initialization.The effective set therefore suffices for analyzing subsequent convergence.
- Gauss–Seidel convergence: A block-contraction mapping has a unique fixed point, and Gauss–Seidel iterations from any point in Peff converge linearly to it.This proposition supplies the general convergence mechanism for the sequential waterfilling algorithms.
- Theorem 1: Algorithm 2 globally converges under condition (63).The result follows by combining the contraction proposition with the Gauss–Seidel convergence proposition.
- Theorem 2: The convergence guarantee is unaffected by the particular relaxation parameters, provided every αq belongs to [0,1).Condition (63) is independent of the parameter set.
- Corollaries: Conditions (C2) and (C3) are derived from the contraction condition using positive weighting vectors and the spectral radius of Hmax.The weighting vector can be selected through a geometric optimization formulation.
D Proof of Theorem 3
Theorem 3 establishes linear convergence of both gradient-projection algorithms by applying contraction arguments to the same waterfilling mapping.
- Theorem 3: Algorithms 3 and 4 linearly converge to the unique Nash equilibrium from any arbitrary starting point in P when T is a contraction.The proof uses the block-maximum norm and the contraction result for T.
E Proof of Theorem 4
Theorem 4 analyzes Algorithm 4 through error-vector contraction and proves convergence to the Nash equilibrium under matrix-norm conditions.
- Error-vector analysis: Algorithm 4 is analyzed using a mapping T and an error vector defined relative to a Nash equilibrium fixed point.The error construction incorporates the relaxation matrix Dα.
- Contraction bound: The proof bounds the error using the triangle inequality, the Euclidean projector's nonexpansiveness, and the structure of Peff.Diagonal matrices Hrq and a permutation matrix are used in the resulting bound.
- Contraction condition: The matrix norm ∥H∥2,mat used in the analysis is the spectral norm induced by the vector norm defining the projection.The matrix H is constructed from the per-carrier matrices H(k).
- Theorem 4: Algorithm 4 converges to the Nash equilibrium from any starting point in P when the stated sufficient conditions hold.Under the same condition, the convergence is linear.
F Proof of Convergence of Algorithm 5 and Algorithm 6
The proof establishes convergence of Algorithms 5 and 6 by showing that their projected mappings are contractions under sufficient conditions. Consequently, both IGPAs converge from any initialization to the game's unique Nash equilibrium.
- The convergence guarantee follows by requiring the combined mapping of the projected updates to be a block-contraction under the norm ∥·∥G,block.
- The proof uses the projection's non-expansive property to transfer contraction from the auxiliary mapping RG to the update mapping TG.
- For simplicity, the derivation considers identity weighting matrices, with Gq = I for every q.
- The Jacobian-based conditions use the spectral norm and define ∇r fq(p) as the matrix of component gradients with respect to pr.
- Algorithms 5 and 6 converge to the unique Nash equilibrium from any initial condition in P when a scalar δ ∈ [0, 1) satisfies the stated condition.
- Suitable sufficiently small β > 0 and δ ∈ [0, 1), close to one, can satisfy condition (96) under the stated assumptions.