QoS-Based Resource Allocation and Transceiver Optimization (Foundations and Trends in Communications and Information Theory)

FnT CIT 2:6 Martin Schubert and Holger Boche QoS-Based Resource Allocation and Transceiver Optimization derives a compr...

Author: Martin Schubert | Holger Boche

52 downloads 540 Views Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

FnT CIT 2:6

Martin Schubert and Holger Boche QoS-Based Resource Allocation and Transceiver Optimization derives a comprehensive theoretical framework for SIR balancing, with and without noise. The theory considers the possible use of receive strategies (e.g. interference filtering or channel assignment), which can be included in the model in an abstract way. Power allocation and receiver design are mutually interdependent, thus joint optimization strategies are derived. QoS-Based Resource Allocation and Transceiver Optimization provides a better understanding of interference balancing and the characterization of the QoS feasible region. It also provides a generic algorithmic framework, which may serve as a basis for the development of new resource allocation algorithms. QoS-Based Resource Allocation and Transceiver Optimization is an invaluable resource for every engineer and researcher working on multiuser interference problems in wireless communications.

QoS-Based Resource Allocation and Transceiver Optimization

QoS-Based Resource Allocation and Transceiver Optimization

Foundations and Trends® in Communications and Information Theory 2: 6 (2005)

QoS-Based Resource Allocation and Transceiver Optimization Martin Schubert and Holger Boche

Martin Schubert and Holger Boche

This book is originally published as Foundations and Trends1 in Communications and Information Technology, Volume 2 Issue 6 (2005), ISSN: 1567-2190.

the essence of knowledge

QoS-Based Resource Allocation and Transceiver Optimization

QoS-Based Resource Allocation and Transceiver Optimization Martin Schubert Fraunhofer German-Sino Lab for Mobile Communications MCI

Holger Boche Technical University of Berlin Fraunhofer Institute for Telecommunications Heinrich-Hertz-Institut HHI Fraunhofer German-Sino Lab for Mobile Communications MCI

Boston – Delft

R Foundations and Trends in Communications and Information Theory

Published, sold and distributed by: now Publishers Inc. PO Box 1024 Hanover, MA 02339 USA Tel. +1-781-985-4510 www.nowpublishers.com [email protected] Outside North America: now Publishers Inc. PO Box 179 2600 AD Delft The Netherlands Tel. +31-6-51115274 A Cataloging-in-Publication record is available from the Library of Congress The preferred citation for this publication is M. Schubert and H. Boche, QoS-Based R Resource Allocation and Transceiver Optimization, Foundation and Trends in Communications and Information Theory, vol 2, no 6, pp 383–529, 2005 Printed on acid-free paper ISBN: 1-933019-73-5 c 2006 M. Schubert and H. Boche

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, mechanical, photocopying, recording or otherwise, without prior written permission of the publishers. Photocopying. In the USA: This journal is registered at the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923. Authorization to photocopy items for internal or personal use, or the internal or personal use of specific clients, is granted by now Publishers Inc for users registered with the Copyright Clearance Center (CCC). The ‘services’ for users can be found on the internet at: www.copyright.com For those organizations that have been granted a photocopy license, a separate system of payment has been arranged. Authorization does not extend to other kinds of copying, such as that for general distribution, for advertising or promotional purposes, for creating new collective works, or for resale. In the rest of the world: Permission to photocopy must be obtained from the copyright owner. Please apply to now Publishers Inc., PO Box 1024, Hanover, MA 02339, USA; Tel. +1 781 871 0245; www.nowpublishers.com; [email protected] now Publishers Inc. has an exclusive license to publish this material worldwide. Permission to use this content must be obtained from the copyright license holder. Please apply to now Publishers, PO Box 179, 2600 AD Delft, The Netherlands, www.nowpublishers.com; e-mail: [email protected]

R Foundations and Trends in Communications and Information Theory Volume 2 Issue 6, 2005 Editorial Board

Editor-in-Chief: Sergio Verd´ u Department of Electrical Engineering Princeton University Princeton, New Jersey 08544, USA [email protected] Editors Venkat Anantharam (UC. Berkeley) Ezio Biglieri (U. Torino) Giuseppe Caire (Eurecom) Roger Cheng (U. Hong Kong) K.C. Chen (Taipei) Daniel Costello (U. Notre Dame) Thomas Cover (Stanford) Anthony Ephremides (U. Maryland) Andrea Goldsmith (Stanford) Dave Forney (MIT) Georgios Giannakis (U. Minnesota) Joachim Hagenauer (TU Munich) Te Sun Han (Tokyo) Babak Hassibi (Caltech) Michael Honig (Northwestern) Johannes Huber (Erlangen) Hideki Imai (Tokyo) Rodney Kennedy (Canberra) Sanjeev Kulkarni (Princeton)

Amos Lapidoth (ETH Zurich) Bob McEliece (Caltech) Neri Merhav (Technion) David Neuhoff (U. Michigan) Alon Orlitsky (UC. San Diego) Vincent Poor (Princeton) Kannan Ramchandran (Berkeley) Bixio Rimoldi (EPFL) Shlomo Shamai (Technion) Amin Shokrollahi (EPFL) Gadiel Seroussi (HP-Palo Alto) Wojciech Szpankowski (Purdue) Vahid Tarokh (Harvard) David Tse (UC. Berkeley) Ruediger Urbanke (EPFL) Steve Wicker (Georgia Tech) Raymond Yeung (Hong Kong) Bin Yu (UC. Berkeley)

Editorial Scope R Foundations and Trends in Communications and Information Theory will publish survey and tutorial articles in the following topics:

• Coded modulation

• Multiuser detection

• Coding theory and practice

• Multiuser information theory

• Communication complexity

• Optical communication channels

• Communication system design

• Pattern recognition and learning

• Cryptology and data security

• Quantization

• Data compression

• Quantum information processing

• Data networks

• Rate-distortion theory

• Demodulation and Equalization

• Shannon theory

• Denoising • Detection and estimation

• Signal processing for communications

• Information theory and statistics

• Source coding

• Information theory and computer science

• Storage and recording codes

• Joint source/channel coding

• Wireless Communications

• Speech and Image Compression

• Modulation and signal design

Information for Librarians R in Communications and Information Theory, 2005, Foundations and Trends Volume 2, 6 issues. ISSN paper version 1567-2190. ISSN online version 15672328. Also available as a combined paper and online subscription.

R Foundations and Trends in Communications and Information Theory Vol. 2, No 6 (2005) 383–529 c 2006 M. Schubert and H. Boche

DOI: 10.1561/0100000010

QoS-Based Resource Allocation and Transceiver Optimization Martin Schubert1 and Holger Boche2 1

2

Fraunhofer German-Sino Lab for Mobile Communications MCI, Einsteinufer 37, 10587 Berlin, Germany, [email protected] Technical University of Berlin, Dept. of Electrical Engineering, Heinrich-Hertz Chair for Mobile Communications, HFT-6, Einsteinufer 25, 10587 Berlin, Germany; Fraunhofer German-Sino Lab for Mobile Communications MCI, Einsteinufer 37, 10587 Berlin, Germany; Fraunhofer Institute for Telecommunications, Heinrich-Hertz-Institut (HHI), Einsteinufer 37, 10587 Berlin, Germany, [email protected]

Abstract The control and reduction of multiuser interference is a fundamental problem in wireless communications. In order to increase the spectral efficiency and to provide individual quality-of-service (QoS), it is required to jointly optimize the power allocation together with possible receive and transmit strategies. This often leads to complex and difficult-to-handle problem formulations. There are many examples in the literature, where the special structure of the problem is exploited in order to solve special cases of this problem (e.g. multiuser beamforming or CDMA). So it is desirable to have a general theory, which can be applied to many practical QoS measures, like rates, delay, BER, etc. These measures can all be related to the signal-to-interference ratio (SIR) or the signal-to-interference-plus-noise ratio (SINR). This leads to the problem of SIR and SINR balancing, which is fundamental for many problems in communication theory.

In this text we derive a comprehensive theoretical framework for SIR balancing, with and without noise. The theory considers the possible use of receive strategies (e.g. interference filtering or channel assignment), which can be included in the model in an abstract way. Power allocation and receiver design are mutually interdependent, thus joint optimization strategies are derived. The main purpose of this text is to provide a better understanding of interference balancing and the characterization of the QoS feasible region. We also provide a generic algorithmic framework, which may serve as a basis for the development of new resource allocation algorithms. We study different interference models, which are general enough to be valid for a wide range of system designs, but which are also specific enough to facilitate efficient algorithmic solutions. One important class of interference functions is based on axioms, which characterize the impact of the power allocation of the interference received by the individual users. Another class of interference functions is based on non-negative coupling matrices, which may be parameter-dependent in order to model the possible impact of receive strategies. Both models are studied with and without noise. We analyze the resulting QoS feasible region (the set of jointly achievable QoS) and discuss different allocation strategies for min-max fairness and sum-power minimization. Finally we study geometrical properties of the QoS region, which can be shown to be convex for log-convex interference functions.

Contents

1 Introduction

1

1.1 1.2 1.3

3 6 9

QoS-based power and resource allocation Related results in wireless communications Outline

2 Axiomatic SIR-Balancing Theory

13

2.1 2.2 2.3 2.4 2.5 2.6 2.7

14 21 29 32 34 36 37

Axiom-based interference model Existence of a min-max optimal power allocation Achievable balanced SIR margin Generalized achievability of SIR targets Special monotonicity properties Comparison of min-max and max-min optimization Summary

3 Matrix-Based SIR Balancing

39

3.1 3.2 3.3 3.4 3.5 3.6

39 49 56 63 73 80

Min-max balancing and Perron root minimization Characterization of boundary points Achievability under an adaptive receive strategy Uniqueness of the power allocation Irreducible coupling matrices Min-max and max-min balancing ix

3.7 3.8

Duality Summary

84 86

4 General SINR Balancing Theory

89

4.1 4.2 4.3 4.4 4.5 4.6

89 91 91 94 96 99

Axiomatic interference model Continuity of interference functions Feasibility Sum power minimization and fixed-point iteration Relation with SINR balancing Summary

5 Matrix-Based SINR Balancing and Algorithmic Solutions 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8

Matrix-based interference function Sum-power minimization Fixed-point iteration Matrix-based iteration Convergence and comparison with the fixed-point iteration Relationship with spectral radius optimization Application example: Beamforming Summary

101 101 102 104 104 106 110 116 121

6 Geometrical Properties for Log-Convex Interference Functions

123

6.1 6.2 6.3 6.4 6.5

124 126 127 132 133

Log-convexity of linear interference functions Worst-case interference functions Convexity of the QoS feasible region Resource allocation by weighted QoS optimization Summary

Acknowledgements

135

Appendix

137

A.1 A.2 A.3 A.4 A.5

Some definitions and results Proof of Theorem 2.9 Proof of Theorem 2.22 Proof of Theorem 3.2 Proof of Theorem 4.3

References

137 138 139 140 141 143

1 Introduction

The wireless channel is a broadcast medium, so each communication link is possibly interfered by other users transmitting at the same resource. The traditional way of handling interference is to assign all links orthogonal resources, in time (TDMA), frequency (FDMA), or code space (CDMA). This considerably simplifies the system design since the links are no longer coupled by interference. However, reserving each link a fixed resource often comes at the cost of sacrificing spectral efficiency. The available bandwidth is generally best exploited by letting transmitted signals interfere with each other in a controlled way (see e.g. [76, 75]). Also, orthogonality may be lost because of system imperfections and the effects of the time-varying multipath channel. It can be said that interference and power constraints are the main hurdle in achieving a high per-user throughput in heavily loaded multiuser networks, as will be required in the future. Since interference plays an important role in the optimal exploitation of the given bandwidth, it is generally not sufficient to regard the system as a collection of point-to-point communication links. The quality-of-service (QoS) of each link depends on its own transmission power, but also on the power levels of the other links, which 1

2

Introduction

are experienced as interference. This results in a competitive situation, where all users try to compensate interference by increasing its own transmission power, which in turn increases the overall interference in the system. A transmission strategy which neglects these interdependencies is likely to cause uncontrollable and exceeding interference, which means a waste of the overall system efficiency. Thus, it is desirable to find a suitable equilibrium that optimally exploits the available resources. This requires a joint optimization of all communication links. Optimization can be performed with respect to various design goals, like the overall efficiency, max-min fairness, proportional fairness, network utility maximization, etc. There is no such thing as “the” optimal communication strategy. There exists a great deal of literature on resource allocation from various points of view. For example, there are network-centric strategies, which aim at finding a stable performance trade-off by bidding strategies, accounting for traffic, channel quality, and revenues. User-centric strategies, which are closely related to power control, aim at fulfilling user-specific QoS requirements. Both strategies have in common that they are determined and limited by the QoS feasible region (the set of jointly achievable QoS). The purpose of this text is not to give a comprehensive overview on allocation strategies, but rather to provide a fundamental theoretical framework which helps to understand the underlying effects of interference coupling, and to characterize the QoS feasible region. A fundamental question in this context is: what is the region of jointly achievable QoS, and how can certain points be achieved in a spectrally efficient way? This question is closely related to the classical power allocation problem, but in this text we will go one step further in assuming that interference not only depends on the power allocation, but also on adaptive receive strategies, like interference filtering or channel assignment. The additional optimization of the receive strategy adds new degrees of freedom to the problem of resource allocation. Thus, new concepts and algorithms are required. Since power allocation and receive strategies are intricately intertwined, our approach is to use abstract models, which provide a better understanding of the underlying structure of the problem at hand.

1.1. QoS-based power and resource allocation

3

In this respect, the work can be seen as a theoretical basis, which can be applied to solve existing problems in wireless communications.

1.1

QoS-based power and resource allocation

In this section we give an overview on some aspects of QoS-Based power allocation. We start by introducing the basic model used throughout this text, which will be refined later on. 1.1.1

Interference functions

Consider a network with K communication links, whose transmission powers are collected in a power allocation vector p = [p1 , . . . , pK ]T > 0 . as illustrated in Fig. 1.1. The interference power experienced by the kth user can be modeled by a function Ik (p). The functions I1 , . . . , IK describe how the links are affected by mutual cross-talk. Different definitions of Ik (p) and the resulting QoS region will be analyzed in this text. It should be noted that the mapping Ik : RK + 7→ R+ can be linear or non-linear, and it can also model the impact of adaptive receiver designs, like MMSE or interference cancellation, as well as other system aspects. A few examples are listed in the following.

Fig. 1.1 Example of an interference-coupled multiuser system with four transmitter-receiver pairs.

4

Introduction

• Ik (p) = [Ψ p]k , where the positive coupling matrix Ψ > 0 contains interference coefficients, which determine in which way the users are affected by cross-talk (interference). This is a common model in power control theory (see e.g. [96]). • Ik (p) = minz∈Z [Ψ(z) p]k , where the adjustable receive strategy z (from a compact set of possible strategies Z, as discussed later in Section 3.1.1) has impact on the interference structure. This specific model, which holds e.g. for multiantenna beamforming or CDMA designs, and many more, will be studied in Sections 3 and 5. • Ik (p) = maxc fk (p, c), where fk (p, c) is the interference for a given power allocation p under some interference uncertainty c. This definition can be used, e.g. to model worst-case interference under imperfect channel knowledge. This model will be discussed in Section 6. But instead of focusing on a particular model, this text aims at characterizing basic properties, which are a common for a wide range of interference functions. To this end, we introduce an axiomatic characterization of interference functions in Section 2. This generic model contains the above examples as special cases. The axiomatic framework will be gradually refined in the following sections. By introducing additional properties, more results can be shown. 1.1.2

The QoS feasible region

The signal-to-interference ratio (SIR) of the kth user is pk SIRk (p) = , 1≤k≤K, (1.1) Ik (p) where pk is the desired transmission power of the kth user. Note, that the function Ik (p) can include receiver noise. If noise is part of the assumed model (as in Sections 4 and 5), then we will emphasize this by using “SINR” instead of “SIR”. If we use SIR, then we discuss the general case where noise can be included or not. In this case, we need Ik (p) > 0 to ensure that (1.1) is well defined. The term “QoS” is commonly used to describe the performance and reliability of a communication link. In order to keep the results

1.1. QoS-based power and resource allocation

5

as general as possible, we do not make any specific assumption on QoS, except that it is related to the SIR by a monotonic and bijective function φ: QoSk (p) = φ SIRk (p) , 1 ≤ k ≤ K . (1.2) √ Some examples are BER: φ(x) = Q( x), MMSE: φ(x) = 1/(1 + x), BER-slope for α-fold diversity: φ(x) = x−α , or capacity: φ(x) = log(1 + x). Let γ be the inverse function of φ, then γk = γ(Qk ),

1≤k≤K,

(1.3)

is the minimum SIR level needed by the kth user to satisfy the QoS target Qk . Thus, the problem of achieving certain QoS requirements, carries over to the problem of achieving SIR targets γk > 0, ∀k. In the following we will also summarize the targets in a diagonal matrix Γ = diag{γ1 , . . . , γK } .

(1.4)

It is desirable to find a power allocation p > 0 such that SIRk (p) ≥ γk , for all k = 1, . . . , K. This can be rewritten as mink SIRk (p)/γk ≥ 1 or equivalently as maxk γk Ik (p)/pk ≤ 1. We say that the target Γ is feasible if and only if C(Γ) ≤ 1, where γk Ik (p) . (1.5) C(Γ) = inf max p>0 1≤k≤K pk In the following we will refer to (1.5) as the “min-max balancing problem”. The optimum C(Γ) provides a single measure for the joint feasibility of the targets Γ. Note that the optimization is over p > 0 to ensure that Ik (p)/pk is always defined (see Section 2.1.1). However, this does not restrict the generality of the results since p can be made arbitrarily small. The min-max optimum C(Γ) can be used to characterize the QoS feasible region: Q = [φ(γ1 ), . . . , φ(γK )] : C(Γ) ≤ 1 . (1.6)

6

Introduction

Fig. 1.2 QoS-based resource allocation strategies, illustrated for two users with QoS requirements Q1 and Q2

A fundamental problem in resource allocation theory is to find a feasible point [Q1 , . . . , QK ] ∈ Q according to certain design criteria, like network efficiency, stability, or fairness. The optimization strategy can depend on many parameters, like operator revenue, user requests, queuing lengths, individual link priorities, etc. Examples for different points of interest are depicted in Fig. 1.2. But there exists no joint optimization framework. They actual problem structure strongly depends on the geometry of Q and on the definition of the underlying interference function. So the purpose of this text is not to give a comprehensive overview on allocation strategies, but rather to provide a theoretical framework which helps to understand underlying principles. Most of the optimization problems illustrated in Fig. 1.2 are directly connected with the min-max balancing problem (1.5) and the associated QoS feasible region Q. In the following we will study the QoS (resp. SIR) feasible region for different interference functions Ik (p), including adaptive receive strategies and worst-case designs. But before we start with the most basic (axiomatic) interference model in Section 2, we provide some additional motivation by discussing the relationship of the generic interference model with problems in wireless communications.

1.2

Related results in wireless communications

A few examples for possible definitions of the interference function Ik (p) have already been given in Section 1.1.2. We will now discuss the SIR balancing problem in the context of previous work.

1.2. Related results in wireless communications

7

The linear function Ik (p) = [Ψ p]k is a classical model, which is used, e.g. in power control theory. The square matrix Ψ ≥ 0 models the link gains between all receiver/transmitter pairs. The min-max problem (1.5) for this case was already studied in [1] in the context of power balancing for satellite communication systems employing frequency reuse. Under the assumption that Ψ is non-negative and irreducible (see Section 3.1.4 for a definition), it was shown that the min-max-optimal power allocation is given as the principal eigenvector of Ψ, and the optimum is the maximal eigenvalue (Perron root). This work was later extended by [42, 2, 46, 94, 95, 93, 33, 34]. An overview is given in [96, 38]. The above model can be extended to include AWG receiver noise, i.e., Ik (p) = [Ψ p]k + σ 2 . The presence of noise results in a situation where possible constraints on the transmission power do matter. Thus, the power allocation problem can be formulated so as to minimize the total power while maintaining certain SINR levels at the receiver. The optimal power allocation is obtained as the solution of a system of linear equations. Iterative solutions were proposed in [26, 43, 31, 4, 3, 7, 87]. The same power minimization problem was considered in [91, 39], where Ik (p) was not defined by a coupling matrix, but by using an axiomatic framework, equivalent to the one used in Section 4.1. Since the mid-nineties, there has been a series of publications on multiuser beamforming for the downlink channel. In analogy to the power control problem, it was first proposed in [28, 29], to maximize the minimum SIR, assuming that the SIR not only depends on the power allocation, but also on a set of transmit beamformers u1 , . . . , uK ∈ CM , which can be seen as a bank of linear unity-norm filters, which distribute all K signals across the M elements of an antenna array. Given M × M array covariance matrices R1 , . . . , RK , the interference expeP ∗ rienced by the kth receiver is l6=k pl ul Rk ul . This is illustrated in Fig. 1.3. The resulting min-max balancing problem is inf

∗ l6=k pl ul Rk ul pk u∗k Rk uk

P max

p>0,u1 ,...,uK 1≤k≤K

s.t. kuk k2 = 1 .

(1.7)

8

Introduction

Fig. 1.3 Crosstalk is caused by non-orthogonal beams in a cellular system with multiuser beamforming, where a base station (BS) is simultaneously connected with K mobiles.

It can be observed that the interference in the numerator is not only affected by the powers, but also by the beamformers, thus beamforming adds an additional degree of freedom to the optimization. Problem (1.7) is difficult to handle in its direct form, since all the interference terms are coupled by the transmit beamformers u1 , . . . , uK . The kth beamformer uk can be adjusted such that the desired power u∗k Rk uk becomes maximal. However, this strategy is generally not optimal for the other users, which are affected by the interference caused by uk . There is no obvious way how to obtain a good tradeoff between desired power and interference. It was recognized in [44] that problem (1.7) can be reformulated as an eigenvalue optimization problem, which can be solved by an iterative algorithm. This work was further extended by [10, 13], where it was shown that this algorithm is closely connected with an equivalent uplink channel (see also the discussion in Sections 5.6.4, 3.5.4 and 5.7). By optimizing the uplink interference functions Ik (p) = min uk

u∗k

P

l6=k pl Rl u∗k Rk uk

uk

s.t. kuk k2 = 1 ,

(1.8)

the optimal downlink beamformers can be found. Note that the beamformer uk in (1.8) is adaptively adjusted for each power allocation p. This results in a non-linear dependency between the powers and the experienced interference. Nevertheless, the min-max SIR balancing problem (1.5) can be solved efficiently for the special choice of interference functions (1.8).

1.3. Outline

9

Downlink beamforming was also studied under the assumption of additional receiver noise [97, 21, 22, 70, 30, 89, 50, 78, 73, 6, 57, 58, 85]. Similar to the noiseless case, the uplink/downlink duality can be exploited in order to develop iterative algorithmic solutions. In [50, 78], an optimal algorithm was proposed, which consists of an iterative optimization of powers and beamformers for a “virtual uplink” problem. In retrospective, this algorithm can also be understood as a special case of the axiomatic interference model proposed in [91]. An equivalent axiomatic model will be studied in detail in Section 4. Another iterative solution was proposed in [57, 58, 9], where techniques from the theory of non-negative matrices were used to prove monotonicity and convergence. This was extended in [52], where it was shown that additional constraints on the beamformers can be added without affecting the convergence. This already points to the existence of a more general framework for interference balancing which will be introduced in Sections 4 and 5. Many of the results in [57, 58, 9, 52] can also be understood in the context of this general theory. Besides beamforming, there are other examples for joint power allocation and receiver/transmitter optimization. This includes results on CDMA equalization [76, 71, 79, 72], multi-antenna MMSE filtering [88, 53, 51, 54, 20, 36, 37, 61], as well as recent progress on transceiver optimization for point-to-point MIMO systems [47]. Information-theoretical aspects of MIMO communication have been studied, e.g. in [25, 69, 86, 74, 77, 80, 82, 92] All these results all have in common that they aim at a better understanding of the joint optimization of interference-coupled links in a network. While the discussed examples are focused on particular scenarios, it is desirable to have a general theory for resource allocation over the QoS region, where QoS can stand for different performance measures, like SINR, MMSE, or capacity. So the motivation behind this text is to find general principles behind interference balancing, which include some of the discussed results as special cases.

1.3

Outline

The sections of this text build on each other. Starting with the most general case, we successively add specifying assumptions, which

10

Introduction

sometimes restrict the generality, but also allow to show more specific properties. We will conclude each section with a short summary of the main results. We start in Section 2 with an axiomatic interference model, which describes an interference situation in a most abstract and general way. The properties shown here can be regarded as the most common basis for interference balancing. Section 3 focuses on the practically relevant case where interference can be modeled with a non-negative coupling matrix. This is known in the literature as the “SIR Balancing Problem”. But unlike classical power control theory, we assume that the powers are optimized jointly with an adaptive receiver design. This generalizes known results and algorithms from the aforementioned beamforming example [28, 29, 44, 10, 13]. The impact of the receiver design on the interference is modeled by a parameter-dependent coupling matrix. This adds an additional degree of freedom, so classical results and concepts need to be reconsidered. From Section 4 on, we study the impact of an additional noise component, which leads to the problem of SINR balancing. Section 4 starts with an axiomatic model, which extends the model of Section 2 by an additional axiom which requires that the interference function is strictly monotone with respect to noise. This constant power level can also be regarded as a fixed interferer, thus the model can be seen as a special case of the more general model used in Section 2, where all interferers are assumed to be varying. Section 5 further specifies the interference functions. As for the SIR balancing case, we use a parameter-dependent coupling matrix in order to model the impact of interference and noise. The assumption of a fixed noise component leads to additional properties. We study the problems of SINR-constrained power minimization and power-constrained SINR balancing. Section 6 investigates the QoS feasible region under the assumption of log-convex interference functions. In this case, it can be shown that the resulting QoS region is convex. This useful property is the basis for the development of fast-convergent algorithms for resource allocation and scheduling.

1.3. Outline

11

Notation Some general notational conventions are: matrices and vectors are set in boldface. Let y be a vector, then yl := [y]l is the lth component. We use := for definitions. Finally, y ≥ 0 means component-wise inequality, i.e., yl ≥ 0 for all indices l. The set R+ does include the zero element, while R++ only contains strictly positive elements.

2 Axiomatic SIR-Balancing Theory

A key question in interference balancing is whether certain SIR targets γ1 , . . . , γK > 0 are feasible, and if so, how can they be achieved? So in this section, we study the existence of a power allocation p such that SIRk (p) =

pk ≥ γk , Ik (p)

∀k = 1, 2, . . . , K .

(2.1)

We start by assuming that the interference functions Ik (p) are characterized in a most fundamental and general way, based on an axiomatic framework. This analysis can be seen as the basis for the following sections, where we will assume additional properties, under which additional results can be shown. In this respect, the results presented here represent the most general case. All the other scenarios, including the SINR balancing problem discussed in Sections 4 and 5, can be seen as special cases of the axiomatic interference model, which will be derived in the following Section 2.1. All properties shown here are inherited by the more specific models studied later, but not the other way round. 13

14

2.1

Axiomatic SIR-Balancing Theory

Axiom-based interference model

In this section, we will consider interference functions Ik , which are defined as follows. Definition 2.1. The interference function Ik : RK + 7→ R+ is characterized by the following axioms. A1 : Ik (p) ≥ 0 A2 : Ik (µp) = µIk (p) for all µ ≥ 0 A3 : Ik (p(1) ) ≥ Ik (p(2) ) if p(1) ≥ p(2)

(non-negativity) (scalability) (monotonicity)

Axioms A1–A3 are basic properties, which are are typical for interference in general. Property A1 follows from the fact that Ik stands for a power level. Property A2 describes the fact that a scaling of the powers immediately results in a scaling of the received interference. Property A3 means that increasing transmission power can never reduce interference. This axiomatic approach bears some similarities with the concept of standard interference functions introduced by Yates [91]. However, Yates’ model requires strict positivity of the interference function and Ik (µp) < µIk (p) for all µ > 1. This is a typical behavior whenever Ik includes a fixed noise component, which does not depend on p. Although this may seem incompatible with property A2, it is not, since we can consider the extended power allocation p = [p1 , . . . , pK , σ 2 ], which includes the noise power σ 2 . So scaling p means scaling interference and noise. This specific case will be studied later in Section 4, where it will be shown that Yates’ model [91] is a special case of the model A1–A3. That is, all properties which will be derived for A1–A3 also hold in the presence of noise, but the converse is generally not true. The general framework A1–A3 plays an important role for the characterization of the SIR feasible region. It also provides the basis for the investigation of more specific models. For example, the impact of noise can be modeled by adding an additional axiom, which requires strict monotonicity with respect to a noise component (see Section 4).

2.1. Axiom-based interference model

15

It should be noted that interference need not be caused by other users, also self-interference can occur. Self-interference means that Ik (p) depends on the users own power pk . This happens, e.g. in a CDMA Rake receiver [49]. If we assume no self-interference, as in Sections 2.2.3 and 2.1.3, then this will be explicitly stated. Otherwise, possible self-interference is included in the model. It is important to notice that SIRk (p) is invariant with respect to a scaling of p, which follows from (1.1) and A2. Thus, we can reformulate the min-max balancing problem (1.5) as γk Ik (p) γk Ik (p) C(Γ) = inf max = inf max . (2.2) p>0 1≤k≤K 1≤k≤K pk pk P p>0 p =1 k k

That is, the optimization can be restricted to power vectors with kpk1 = 1. This means that possible power constraints do not matter, since the allocation can be arbitrarily scaled. This behavior typically holds for interference functions which have no fixed noise component. Later, in Section 4 we will study the case where the assumption of fixed receiver noise causes a different behavior (a fixed noise power means that we scale the extended allocation p, such that the last component equals the noise.) In the remainder of this section we will study fundamental properties of the interference functions, like positivity and continuity. These properties will be required later in this text. It will be shown in the following sections that under certain conditions, positivity and continuity are a direct consequence of A1–A3. 2.1.1

Interference coupling and positivity

The interference functions defined by A1–A3 are non-negative. That is, zero interference can occur, e.g. due to the impact of interference filtering or cancellation strategies. This seems to be problematic at first sight, since the SIR (2.1) is only defined for positive interference functions. However, this seeming inconsistency can be easily solved by agreeing on the following assumptions: • For each user k there exists a positive power allocation p(k) > 0 such that Ik (p(k) ) > 0.

16

Axiomatic SIR-Balancing Theory

• Whenever the ratio pk /Ik (p) or the inverse Ik (p)/pk is considered, only positive power allocations p > 0 are allowed. It should be noted that these are technical assumptions, which do not restrict the generality of the results. The first assumption means, roughly speaking, that if p > 0, then all users are affected by interference. This is intuitively clear, since in this section and the following we focus on the characterization of the QoS feasible region by interference balancing. Users which are never affected by interference are always feasible and need not to be considered. Even though they can cause interference to others, this does not affect the overall feasibility. This is because the QoS feasible region in the absence of power constraints is only limited by mutual interference coupling. In the absence of noise, a user causing interference can make its own power arbitrarily small. This has no effect on the feasibility, since this user also receives no interference. In conclusion, users which do not fulfill the first assumption have no impact on the interference coupling in the system, so they can be safely excluded from the analysis. The second assumption is only needed to ensure that the SIR expressions are always defined. Even though the first assumption only requires the existence of only one positive power allocation such that the interference is strictly positive, the following lemma shows that this implies strict positivity for all power allocations. Lemma 2.2. If there exists a p ˆ > 0 such that Ik (ˆ p) > 0, then Ik (p) > 0 for all p > 0. Proof. Suppose that Ik (ˆ p) > 0. For an arbitrary p > 0, there exists a scalar λ > 0 such that λp > p ˆ . Applying A2 and A3, we have λIk (p) = Ik (λp) ≥ Ik (ˆ p) > 0. Thus, as long as positive powers p > 0 are considered, all users experience strictly positive interference. This even holds if Ik (p) includes an adaptive receiver design for interference suppression, as for the beamforming example (1.7), which is a special case of the axiomatic model. Lemma 2.2 shows that if the optimal beamformer leaves interference

2.1. Axiom-based interference model

17

for one positive power allocation, then it will leave interference for all positive power allocations. This positivity property allows to formulate the min-max balancing problem (2.2), which provides a necessary and sufficient condition for feasibility, given a set of non-trivial QoS targets Qk > 0. However, it should be noted that the infimum over all positive powers p > 0 is not always associated with an optimizer p ˆ > 0. Sometimes, the level max1≤k≤K γk Ik (p)/pk approaches the infimum as one or more power components tend to zero. This effect will be discussed in more detail in Section 2.2 (see Example 2.5). It will be shown that the formal requirement of strictly positive powers can be avoided by using a fixedpoint representation of the min-max balancing optimum. Note, that these effects do not occur for the interference model in Section 4, where an additional noise component will be introduced. In this case, the power allocation cannot be arbitrarily scaled anymore. The noise always prevents the power to become arbitrarily small. Besides these aspects, the assumption of positive powers is also natural, since we are interested in achieving positive targets γk > 0. Users with no SIR requirements are inactive and need not to be considered. 2.1.2

Continuity of interference functions

Many of the following results will be based on the continuity of Ik (p). The following Theorem 2.3 shows that for general axiom-based interference functions Ik (p), p > 0, continuity follows as a direct consequence of A2 and A3. Then, Theorem 2.4 shows how far this property can be extended to the case p ≥ 0. Later, in Section 3.1.3 we will focus on a special class of matrix-based interference functions, for which continuity even holds for p ≥ 0. Theorem 2.3. Consider an arbitrary p ˜ > 0 and a sequence p(n) which converges to p ˜ for n → ∞, then lim Ik (p(n) ) = Ik (˜ p),

n→∞

Thus, Ik (p) is continuous for p > 0.

1≤k≤K.

(2.3)

18

Axiomatic SIR-Balancing Theory (a)

(b)

Proof. Let p(a) > 0, p(b) > 0 and B = maxk pk /pk , thus, p(a) ≤ Bp(b) . Using A2 and A3, we have Ik (p(a) ) ≤ BIk (p(b) ), ∀k. This holds for all indices k = 1, 2, . . . , K, thus (a)

p Ik (p(a) ) ≤ B = max l(b) . (b) 1≤k≤K Ik (p ) 1≤l≤K p max

(2.4)

l

(a)

(b)

Similarly, we can define b = mink pk /pk and using A2 and A3, we can show (a)

p Ik (p(a) ) min ≥ b = min l(b) . 1≤k≤K Ik (p(b) ) 1≤l≤K p

(2.5)

l

(n)

Now, consider sequences pk → p˜k , ∀k, where p ˜ > 0 is arbitrary. Since p(n) converges towards p ˜ , we can assume p(n) > 0 without loss of gen(n) erality. Since limn→∞ pk = p˜k , we have (n)

p lim max k = 1 n→∞ 1≤k≤K p ˜k (n)

p lim min k = 1 . n→∞ 1≤k≤K p ˜k Applying (2.4) and (2.5) we have Ik (p(n) ) ≤1 1≤k≤K Ik (˜ p)

lim sup max n→∞

Ik (p(n) ) ≥1, 1≤k≤K Ik (˜ p)

lim inf min n→∞

and thus Ik (p(n) ) =1, n→∞ Ik (˜ p) lim

from which (2.3) follows. Theorem 2.3 shows continuity for p > 0. Next, we study how far this can be generalized to p ≥ 0. To this end, consider an arbitrary

2.1. Axiom-based interference model

19

(n)

p ≥ 0 and a sequence p(n) ≥ 0 with limn→∞ pk = pk , 1 ≤ k ≤ K. Let (n)

(l)

(2.6)

(l)

(2.7)

1≤k≤K.

(2.8)

p¯k = sup pk l≥n

p(n) = inf pk , k l≥n

Thus, (n)

≤ pk ≤ p¯k , p(n) k

(n+1)

From the definitions (2.6) and (2.7) we have p ¯k (n+1) (n) pk ≥ pk . Thus, for all k, there exist limits

(n)

≤ p¯k , ∀k, and

p(n) ) , C¯k = lim Ik (¯ n→∞

C k = lim Ik (p(n) ) . n→∞

Inequality (2.8) implies C¯k ≥ C k , ∀k. Theorem 2.4. Let p ≥ 0 be fixed and let p(n) ≥ 0 be a sequence with (n) limn→∞ pk = pk , 1 ≤ k ≤ K, then lim Ik (p(n) ) = Ik (p),

n→∞

lim inf Ik (p(n) ) ≥ Ik (p), n→∞

∀k

(2.9)

∀k .

(2.10) (n)

Proof. First, consider the sequence p(n) . If pk = 0, then pk = 0 for (n)

all n. If pk > 0, then there exists an n0 such that pk > 0 for all n ≥ n0 . Because of (2.8), there exists an n1 such that for all n ≥ n1 and all k (n) with pk > 0, we always have pk > 0. If Ik (p) = 0, then Ik (p(n) ) = 0. This follows from (2.8) and A1 and A3. Thus, (2.9) has been shown for this special case. It remains to consider the case Ik (p) > 0. Let O(p) = {k : pk > 0}. Because of (2.8), we have Ik (p) ≥ Ik (p(n) ) . Defining αn = max

pk

k∈O(p) p(n) k

,

(2.11)

20

Axiomatic SIR-Balancing Theory

we have Ik (p) ≤ αn Ik (p(n) ) .

(2.12)

(n)

Since limn→∞ pk = pk , ∀k, we have limn→∞ αn = 1. Since limn→∞ Ik (p(n) ) = C k , we can conclude with (2.11) and (2.12) that (2.9) holds. Inequality (2.10) is a consequence of (2.9) and the fact that Ik (p(n) ) ≥ Ik (p(n) ). The result (2.9) in Theorem 2.4 shows continuity for monotonically increasing sequences. For arbitrary sequences we only have property (2.10). (n) Since p¯k ≥ pk , ∀k, we have Ik (¯ p(n) ) ≥ Ik (p), ∀k. But generally, it is not possible to obtain a lower bound. Although we have (n) (n) mink∈O(p) pk /¯ pk = cn and limn→∞ cn = 1, the property pk ≥ cn p¯k , k ∈ O(p) is not sufficient for finding a lower bound for Ik (p). Such a bound need not exist for k ∈ [1, K]\O(p). 2.1.3

Continuity for K = 2

Now, we show that continuity always holds for K = 2 under the assumption that no self-interference occurs and that there exists a p > 0 such that Ik (p) > 0 for all k, which means that the interference functions are guaranteed to be strictly positive (see Lemma 2.2). Then, the interference I1 (p) only depends on the power of user 2. This dependency can be expressed by a monotone function f1 (p2 ) = I1 (p). From A2 we have f1 (λp2 ) = λf1 (p2 ). That is, the interference scales linearly with the power. The same can be shown for the second user. There exist constants c1 , c2 > 0 such that I1 (p) = c1 p2 ,

c1 > 0 ,

(2.13)

I2 (p) = c2 p1 ,

c2 > 0 .

(2.14)

Thus, the functions Ik (p) are continuous for p ≥ 0.

2.2. Existence of a min-max optimal power allocation

2.2

21

Existence of a min-max optimal power allocation

The min-max SIR balancing problem (2.2), as discussed in the introduction, characterizes the QoS feasible region. The optimum C(Γ) is a single measure for the quality of the compound multiuser channel. Thus, a thorough understanding of min-max balancing is not only important from a theoretical point of view, but also as a basis for the development of practical algorithms. We start by discussing a fundamental aspect of SIR balancing, namely the existence of an optimizer. To this end, we assume that there exists a p > 0 such that Ik (p) > 0, ∀k. Lemma 2.2 implies that the interference is always strictly positive, so we can start by discussing the functions SIRk (p), which are always well defined. An alternative fixed-point representation will be used later in 2.2.2. The section ends with special cases in 2.2.3.

2.2.1

SIR balancing with positive powers

Note, that the existence of an optimizer p > 0 is not always guaranteed. It can happen that the infimum C(Γ), as defined in (2.2), is not achieved, but approached by maxk γk /SIRk (p) arbitrarily close, so all quantities γk /SIRk are asymptotically balanced at the common level C(Γ). In this sense, the expression ‘SIR balancing’ is justified. These effects will be illustrated by the following example. Example 2.5. (no min-max optimizer exists) Consider the simple interference function I(p) = Ψp, where Ψ=

h

Ψ(1) 0 V Ψ(2)

i

,

with blocks Ψ(1) and Ψ(2) along the diagonal, and an off-diagonal Block V > 0. The first sub-system Ψ(1) receives no interference, because its off-diagonal block is zero. The second sub-system receives interference from the first system. The amount of interference is determined by the coupling coefficients V.

22

Axiomatic SIR-Balancing Theory

Now, consider a power allocation p =

λ1 v(1) , where v(l) is the λ v(2) 2

unity-norm right principal eigenvector of Ψ(l) , l = 1, 2, respectively, and ρ(l) = ρ(Ψ(l) ) = 1 is the spectral radius. We have Ψ(l) v(l) = ρv(l) . Positivity v(l) > 0 is ensured since the blocks are irreducible. For the first subsystem, with user indices k = 1, 2, the power allocation λ1 v(1) balances all inverse SIR at the common level ρ(1) , i.e., [Ψp]k λ1 [Ψ(1) v(1) ]k = = ρ(1) , [p]k λ1 [v(1) ]k

k = 1, 2 .

(2.15)

For the second subsystem, with user indices k = 3, 4, we have an additional interference term λ2 [Ψ(2) v(2) ]k−2 [Ψp]k λ1 [Vv(1) ]k−2 + , = [p]k λ2 [v(2) ]k−2 λ2 [v(2) ]k−2 =

λ1 [Vv(1) ]k−2 + ρ(2) . λ2 [v(2) ]k−2

k = 3, 4

(2.16)

(2.17)

It can be observed from (2.17) that [Ψp]k /[p]k > ρ(2) , k = 3, 4, which means that the inverse SIR of the users 3, 4 are strictly larger than the spectral radius ρ(2) . This is because the interference caused by the coefficients V is strictly positive. However, the level ρ(2) can be approached arbitrarily close. By varying the scaling factors λ1 and λ2 in (2.17), we can make the interference term arbitrarily small. In order to limit the gap between ρ(2) and maxk=3,4 [Ψp]k /[p]k to a value , we can choose scaling factors λ1 () and λ2 () such that λ1 () [Vv(1) ]k−2 ≤ , λ2 () [v(2) ]k−2

k = 3, 4

must be fulfilled. As tends to zero, the ratio λ1 ()/λ2 () tends to λ ()v(1) zero as well. This means that the power allocation p() = λ1 ()v(2) has 2 components which become either very small or very large, depending on the chosen normalization. If we choose the common normalization kp() k1 = 1, then the components of users 1, 2 tend to zero. This effect is illustrated in Fig. 2.1. The example 2.5 illustrates how the achievability of certain balanced SIR levels depends on the interference structure. For any > 0, there

2.2. Existence of a min-max optimal power allocation

(a) The largest power component is normalized to one. The powers of users 1, 2 tend to zero as the gap tends to zero.

23

(b) The smallest power component is normalized to one. The powers of users 3, 4 tend to infinity as the gap tends to zero.

Fig. 2.1 Illustration of Example 2.5: Power components tend to infinity as the infimum C(Γ) is achieved asymptotically.

exists a power allocation p() > 0 such that [Ψp() ]k ≤ C(Γ) + , 1≤k≤K [p() ]k

C(Γ) ≤ max

∀k .

(2.18)

By letting → 0, it is always possible to balance the inverse SIR (possibly weighted) to a common level C(Γ). Now, consider the function X Ik (p, ) = Ik (p) + pk , 1 ≤ k ≤ K , (2.19) k

with > 0. The resulting min-max optimum is C(Γ, ) = inf

p>0

γk Ik (p, ) . 1≤k≤K pk max

(2.20)

The following lemma will be needed in the following. Lemma 2.6. For every > 0, there exists a p() > 0 such that ()

γk Ik (p() , ) = C(Γ, )pk ,

1≤k≤K.

(2.21)

24

Axiomatic SIR-Balancing Theory

Proof. From (2.20) we know that for every δ > 0 there exists a vector p(δ) > 0 with kp(δ) k1 = 1, such that max

γk Ik (p(δ) , )

1≤k≤K

(δ)

≤ C(Γ, ) + δ .

(2.22)

pk

From (2.19) follows ≤ Ik (p(δ) , ). Since inequality (2.22) holds for all k ∈ {1, 2, . . . , K}, we have (δ) γk ≤ γk Ik (p(δ) , ) ≤ C(Γ, ) + δ pk . (2.23) Next, consider the sequence {δn }, δn → 0. Since kp(δn ) k = 1, there exists a convergence point p ˆ ≥ 0, such that lim

n→∞

K X

(δ )

|pk n − pˆk | = 0 .

k=1

Inequality (2.23) implies that for all 1 ≤ k ≤ K, (δ )

lim γk Ik (p(δn ) , ) ≤ lim (C(Γ, ) + δn )pk n

n→∞

n→∞

= C(Γ, )ˆ pk ,

1≤k≤K.

(2.24)

Combining (2.23) and (2.24) we have 0 < γk ≤ C(Γ, )ˆ pk ,

1≤k≤K.

Thus, p ˆ > 0. Note, that p ˆ depends on . It remains to show equality (2.21). From (2.24) and (2.3) we know that γk Ik (ˆ p, ) ≤ C(Γ, )ˆ pk ,

1≤k≤K.

(2.25)

Now, suppose there exists a k0 such that γk0 Ik0 (ˆ p, ) < C(Γ, )ˆ pk 0 . Since Ik has the special form (2.19), a reduction of the power pˆk0 would reduce the interference to all other links k 6= k0 . This means that (2.25) would be fulfilled with strict inequality for all links, which implies γk Ik (p, ) . p>0 1≤k≤K pk Thus, it would be possible to achieve a balanced value smaller than the global infimum, which is a contradiction. C(Γ, ) > inf max

2.2. Existence of a min-max optimal power allocation

25

Lemma 2.6 shows that, for an arbitrary > 0, a balanced optimum can always be achieved with the modified interference functions Ik (p, ) and p > 0. This result will be needed in the next section 2.2.2 to prove Theorem 2.7. 2.2.2

Existence of a non-negative fixed-point

From Example 2.5 it becomes clear that if we require, kpk1 = 1, then some components of the power vector can tend to zero when min-max balancing is performed. But actual zeros could not be admitted because we discussed the ratio γk Ik (p)/pk . In this section, we will use an alternative way of expressing this balanced state. Zeros in the power allocation can be admitted if we consider the fixed-point equation γk Ik (p) = µ pk , ∀k. The existence of a fixed point p ≥ 0 (excluding the trivial all-zero allocation p = 0) will be characterized in the following by Lemma 2.6 and Theorem 2.7, which show that components of the power allocation p can tend to zero, in which case also the interference tends to zero (because of the min-max principle). Letting → 0, we can show the following result. Theorem 2.7. There always exists a vector p∗ ≥ 0, p∗ 6= 0 such that γk Ik (p∗ ) = C(Γ)p∗k ,

1≤k≤K.

(2.26)

Proof. For 0 < 1 < 2 we have Ik (p, 1 ) < Ik (p, 2 ) and thus C(Γ, 1 ) ≤ C(Γ, 2 ) . Since C(Γ, ) is non-negative, the limit M = lim→0 C(Γ, ) exists. First, we show that M = C(Γ). Since Ik (p) ≤ Ik (p, ), 1 ≤ k ≤ K, we have M ≥ C(Γ) .

(2.27)

It is known from (2.2) that for every δ > 0, there exists a vector p(δ) > 0, with kp(δ) k1 = 1, such that max

1≤k≤K

γk Ik (p(δ) ) (δ)

pk

≤ C(Γ) + δ .

26

Axiomatic SIR-Balancing Theory

The inequality is fulfilled for all indices 1 ≤ k ≤ K, thus γk Ik (p(δ) , ) (δ) pk

=

γk Ik (p(δ) ) (δ) pk

γk

+

≤ C(Γ) + δ +

(δ)

pk γk (δ)

1≤k≤K.

,

(2.28)

pk It follows that M ≤ C(Γ, ) ≤ max

γk Ik (p(δ) , )

k

(δ)

pk

≤ C(Γ) + δ + max

1≤k≤K

γk (δ)

.

(2.29)

pk

For → 0, we have M ≤ C(Γ) + δ, which holds for all δ > 0. Thus, M ≤ C(Γ), which implies that the inequality (2.27) must be fulfilled with equality, i.e., lim C(Γ, ) = C(Γ) .

(2.30)

→0

We know from Lemma 2.6 that for every > 0 there exists a p∗ () > 0 such that γk Ik (p∗ (), ) = C(Γ, )p∗k (),

1≤k≤K.

(2.31)

Since kp∗ ()k1 = 1 can be assumed, and p∗ () > 0, there exists a subsequence {n } and a p∗ ≥ 0 such that lim

n→∞

K X

|p∗k (n ) − p∗k | = 0 .

k=1

With (2.30), the continuity of Ik (Thm. 2.3), and (2.31), we have C(Γ)p∗k = lim C(Γ, n )p∗k (n ) n→∞

= lim γk Ik (p∗ (n ), n ) n→∞

= lim γk Ik (p(n )) n→∞

= γk Ik (p∗ ), which concludes the proof.

1≤k≤K,

(2.32)

2.2. Existence of a min-max optimal power allocation

27

Theorem 2.7 shows that there always exists a non-trivial allocation p∗ ≥ 0 such that the ratios SIRk (p∗ )/γk are balanced at the same level. Defining I(p) = [I1 (p), . . . , IK (p)]T ,

(2.33)

the fixed-point characterization (2.26) can be rewritten in compact matrix notation as ΓI(p∗ ) = C(Γ)p∗ .

(2.34)

Later, in Theorem 2.14 it will be shown that if there exists a p∗ > 0 such that (2.34) is fulfilled, then p∗ is the optimizer of the SIR balancing problem (2.2). Otherwise, the infimum (2.2) is only approached asymptotically and no optimizer exists. Then, the quantities SIRk (p)/γk are only balanced asymptotically. In this case we know from Theorem 2.7 that the balanced state can be characterized by allowing power components equal to zero. In the following section we will show that for K = 2, 3 and with no self-interference, there always exists an optimizer p > 0. A solution p ≥ 0 can only occur for K ≥ 4. 2.2.3

Special behavior for K = 2, 3

Now, the existence of a strictly positive optimizer is shown under the following assumptions: (1) no self-interference occurs, (2) for each index k there exists a p > 0 such that Ik (p) > 0. The second assumption implies that the interference functions are always positive for p > 0 (see Lemma 2.2). Theorem 2.8. Suppose that 1) and 2) are fulfilled. Also, p0 ≥ 0 fulfills γk Ik (p0 ) = C(Γ)p0k , ∀k, and there exists an index k0 such that p0k0 = 0, then p0 has at least two zero components.

28

Axiomatic SIR-Balancing Theory

Proof. Suppose that p0k0 = 0 is the only zero component. Because of 1) and 2), we have Ik0 (p0 ) > 0, which leads to the contradiction 0 < γk0 Ik0 (p0 ) = C(Γ)p0k0 = 0. Theorem 2.9. Suppose that 1) and 2) are fulfilled. For K = 2, 3, there exists exactly one vector p ≥ 0, p 6= 0, such that C(Γ)pk = γk Ik (p), ∀k, and this vector fulfills p > 0. Proof. see Appendix A.2. The boundary of the SIR feasible region is characterized by C(Γ) = 1. For K = 2, 3 it follows from the above results, that all boundary points are always effectively achievable, i.e., there always exists a p > 0 such that γk Ik (p) = pk , ∀k. This need not be true for K ≥ 4, as shown by the following example. Example 2.10. Consider the function Ik (p) = [Bp]k , where " # B=

0 b 0 0

b 0 0 0

0 0 0 b

0 0 b 0

.

We choose the target Γ such that C(Γ) = 1, i.e., γk = 1/b, ∀k. Then, γk Ik (p) = pk , ∀k, is fulfilled, e.g. by the vectors [1111] or [0011]. Thus, there exist different power allocations, which can be strictly positive or not. From Theorem 2.8 we know that such a behavior can only occur for K ≥ 4. Note, that in this example the balanced state is characterized by the fixed-point equation. Since we do not use the SIR, we can set the powers to zero, which otherwise would lead to an indeterminate expression (see also the discussion in Section 2.1.1). The following theorem is interesting in the context of strict positivity. It shows that ambiguities in the power allocation can only exist under certain conditions. Theorem 2.11. Suppose that 1) and 2) are fulfilled. Let K be arbitrary. Suppose that there are two vectors p(1) , p(2) > 0 such that

2.3. Achievable balanced SIR margin

29

Fig. 2.2 The infeasible SIR region is convex for K = 2

γk Ik (p) = C(Γ)pk , ∀k. Without loss of generality we can scale p(1) ≥ p(2) , where equality holds for one component. Then equality holds for at least two components. Proof. The proof is in analogy to the proof of Theorem 2.9 for K = 3.

For K = 2, the results allow for an interesting geometrical interpretation. Using (2.13) and (2.14), we have 0 c1 C(Γ)p = Γ p , c1 , c2 > 0 . c2 0 The boundary of the feasible region is the set of Γ = diag{γ1 , γ2 } for which C(Γ) = 1. Thus, the boundary is described by 1 . γ2 = c1 c2 γ1 It follows that the infeasible SIR region for K = 2 is convex (see illustration Fig. 2.2). This was already observed in the context of power control [96, 64] and multiuser beamforming [56]. Here we show that this result extents to more general classes of receiver designs. However, this property does not extend to K ≥ 4, as was recently shown in [64].

2.3

Achievable balanced SIR margin

Theorem 2.7 shows that the SIR balancing problem (2.2) leads (at least asymptotically) to a solution p∗ ≥ 0, which fulfills the fixed-point

30

Axiomatic SIR-Balancing Theory

characterization (2.34). In this section we investigate how this characterization is related to the min-max optimum C(Γ), as defined in (2.2). Note, that pk = 0 means that the kth user is switched off, thus no interference is caused by this user. In general, this means that better SIR levels might be achievable for the other users. This is specified by the following theorem. Theorem 2.12. Let µ > 0 and p∗ ≥ 0 fulfill γk Ik (p∗ ) = µp∗k ,

1≤k≤K,

(2.35)

then µ ≤ C(Γ). Proof. The result is shown by contradiction. Suppose that µ > C(Γ), then the definition (2.2) implies the existence of a vector p ¯ > 0 such that γk Ik (¯ p) < µ¯ pk ,

1≤k≤K.

This relation holds for all vectors c¯ p with c > 0. Now, we can choose c ∗ ∗ such that c¯ pk ≥ pk , ∀k, where p > 0 fulfills (2.35), and c¯ pk0 = p∗k0 for one arbitrary component k0 . Defining p ˜ := c¯ p, we have µ=

γk0 Ik0 (p∗ ) γk0 Ik0 (p∗ ) γk0 Ik0 (˜ p) = ≤ <µ, ∗ pk0 p˜k0 p˜k0

which is a contradiction and hence concludes the proof. The following example shows that the theorem is strict in a sense that it cannot be improved even for the simple case when Ik (p) is based on a matrix. In particular, the case µ < C(Γ) is possible. hExamplei 2.13. Consider h the i function Ikh(p) i= [Ψp]k , where Ψ = (1) Ψ(1) 0 = 01 10 and Ψ(2) = µ0 µ0 , 0 < µ < 1, and an ˆ Ψ(2) , with Ψ Ψ ˆ > 0. Then, there exists an eigenvector p arbitrary Ψ ˜ ≥ 0 such that Ψ˜ p = µ˜ p,

p ˜ = [0, 0, 1, 1]T .

But there also exists a strictly positive eigenvector p ˆ > 0 such that Ψˆ p=p ˆ,

p ˆ = [1, 1, a, b]T ,

2.3. Achievable balanced SIR margin

31

where a and b solve the equations ˆ 11 + Ψ ˆ 12 , a = µb + Ψ ˆ 21 + Ψ ˆ 22 . b = µa + Ψ This example shows that there can exist different allocations p ≥ 0 such that (2.35) is fulfilled. In particular, it is possible to achieve a level µ < C(Γ). However, this requires that users are switched off (zero power). Now, Theorem 2.14 shows that if there exists a p > 0 which balances all SIR, then µ = C(Γ). Theorem 2.14. Suppose there exists a µ > 0 and p∗ > 0 such that γk Ik (p∗ ) = µp∗k ,

1≤k≤K,

(2.36)

then µ = C(Γ). Proof. In Theorem 2.12 it was shown that µ ≤ C(Γ), thus it remains to show equality. We know from Theorem 2.7 that there exists a vector p ˆ ≥ 0, p ˆ 6= 0, such that γk Ik (ˆ p) = C(Γ)ˆ pk ,

1≤k≤K.

(2.37)

Each scaled version of p∗ fulfills (2.36), thus we can choose p∗k ≥ pˆk , ∀k, and p∗k0 = pˆk0 > 0 for some index k0 . Thus, C(Γ) =

γk0 Ik0 (ˆ p) γk0 Ik0 (ˆ p) γk0 Ik0 (p∗ ) = ≤ =µ. pˆk0 p∗k0 p∗k0

Thus µ ≤ C(Γ) can only be fulfilled with equality. It can be concluded that the SIR balancing problem (2.2) is equivalent to the problem of finding the maximum µ such that γk Ik (p) = µ·k , p > 0. Assume that C (1) (Γ) is the balanced optimum (2.2) for interference (1) functions Ik (p), and C (2) (Γ) is the optimum for interference func(2) (1) (2) tions Ik (p). If Ik (p) ≥ Ik (p) for p > 0, then C (1) (Γ) ≥ C (2) (Γ).

32

Axiomatic SIR-Balancing Theory

This is clear from the min-max characterization (2.2). An interesting observation is that this property immediately transfers to functions Ik (p) = [Ψp]k , where Ψ is a non-negative coupling matrix. In this case, the optimum C(Γ) can be interpreted as the spectral radius of (1) (2) a coupling matrix ΓΨ. Thus, element-wise monotonicity Ψkl ≥ Ψkl implies ρ(ΓΨ(1) ) ≥ ρ(ΓΨ(2) ). This result, which is a by-product of the min-max approach, would otherwise be more difficult to prove.

2.4

Generalized achievability of SIR targets

So far, we have focused on the existence of power allocations p which fulfill the equations γk Ik (p) = C(Γ)pk , ∀k. Without loss of generality, we can assume that Γ is a boundary point, i.e., C(Γ) = 1. Thus, if the equations are fulfilled by p∗ > 0, then SIRk (p∗ ) = γk , ∀k. The following set PE (Γ) contains all power allocations which achieve Γ with equality. PE (Γ) = {p > 0 : γk Ik (p) = pk , ∀k} .

(2.38)

From a practical point of view, it is not necessary to require equality. The actual SIR can be larger than the target, i.e., SIRk (p) > γk . This seems to be a waste of resources since the target is over-fulfilled. However, there are cases where SIRk (p) ≥ γk cannot be fulfilled with equality (see the example at the end of this section). This is a peculiarity of the noiseless case, where SIRk (p) is not affected by a scaling of p. Thus, we will also consider the set PO (Γ), which contains all positive power allocations for which SIRk (p) ≥ γk . PO (Γ) = {p > 0 : γk Ik (p) ≤ pk , ∀k} .

(2.39)

We have PE (Γ) ⊆ PO (Γ). Both sets can be empty. In the following we will use a general approach to characterize PE (Γ), which is based on the behavior of iterations of the interference function. To this end, consider the vector-valued mapping " γ I (p) # 1 1 .. V(p) = . γK IK (p)

and the set V PO (Γ) = {p > 0 : ∃˜ p ∈ PO (Γ) with p = V p ˜ }.

33

2.4. Generalized achievability of SIR targets

Each p ˜ ∈ PO (Γ) fulfills p ˜ > 0. We assume that the interference functions fulfill the property stated in Lemma 2.2, thus we have strictly positive interference functions Ik (˜ p) > 0, ∀k. Moreover, p ˜ ≥ V(˜ p) follows from the definition (2.39). Thus, applying V recursively to p ˜ leads to a monotonically decreasing sequence p ˜ ≥ V(˜ p) ≥ V V(˜ p) ≥ . . . . Applying the mapping l times to the set PO (Γ), we have V l PO (Γ) ⊆ V l−1 PO (Γ) . Theorem 2.15. PO (Γ) 6= ∅.

We have PE (Γ) 6= ∅ if and only if

T∞

l=1 V

l

×

T l P (Γ) . From the definition (2.38) it can Proof. Define PO = ∞ V O l=1 be observed that V PE (Γ) = PE (Γ), which means that the mapping V can be applied recursively to PE (Γ) without altering this set. Since PE (Γ) ⊆ PO (Γ), we also have V PE (Γ) ⊆ V PO (Γ) . This can be shown for any repeated mapping of both sets, so PE (Γ) ⊆ PO . Consequently, PE (Γ) 6= ∅ implies PO 6= ∅. ˆ > 0 with p ˆ ∈ PO . The Conversely, suppose that PO 6= ∅. Let p (n) (n−1) (0) sequence p ˆ = V(ˆ p ), p ˆ =p ˆ is component-wise monotonically (n+1) (n) decreasing, i.e., p ˆk ≤p ˆ k , ∀k. Thus, there exists a limit p ˜ ≥ 0 with (n) limn→∞ p ˆ k = p˜k . We have p ˜ ∈ PO and thus p ˜ > 0. Since ˆ (n) = lim V(ˆ p(n−1) ) = V(˜ p) p ˜ = lim p n→∞

n→∞

we can conclude that p ˜ ∈ PE (Γ). For K = 2 and no self-interference, the interference functions have the special structure (2.13) and (2.14). It follows (see Thm. 2.9) that PO (Γ) = PE (Γ) 6= ∅. The same holds for K = 3, as shown in Section 2.2.3. For K = 2, 3, (no self-interference) all boundary points are effectively achievable, i.e., SIRk (p) ≥ γk , ∀k. Example 2.16. For K = 4, we can have PE (Γ) = ∅ and PO (Γ) 6= ∅, T l thus ∞ l=1 V PO (Γ) = ∅. This can be shown by an example. Consider " # Ψ=

0 1 0 0

1 0 0 0

0 0 0 b

0 0 b 0

,

34

Axiomatic SIR-Balancing Theory

where 0 < b < 1 and Γ = diag{[1, 1, 1, 1]}, then there exists a vector p∗ > 0 such that [ΓΨp∗ ]k ≤ p∗k , where strict inequality holds for the last two components. But this inequality can not be fulfilled with equality since the second block is isolated (no other blocks in the same row) and has a spectral radius smaller than one (see also Section 3.2 for more details). The sequence (p∗ )(n) = V((p∗ )(n−1) ) converges to a limit limn→∞ (p∗ )(n) = [1, 1, 0, 0], thus the set PE (Γ) is empty.

Example 2.17. An example for the case PO (Γ) = PE (Γ) is the interference function Ik (p, ), as defined in (2.19). Since Ik (p, ) is strictly monotonically increasing in each power component, we always have p() ∈ PE (Γ). This corresponds to a system where all users are coupled.

2.5

Special monotonicity properties

We have shown that the system of equations (2.26) is connected with the SIR balancing problem (2.2). The existence of a non-negative solution has been shown in Theorem 2.7. The following questions remain: • when is (2.26) fulfilled by a strictly positive vector p∗ > 0? • when is the solution unique? With the general model based on A1–A3, it was not possible to provide general answers to these questions (except for K = 2, 3 and no self interference). Thus, in the following we consider cases where Ik has certain monotonicity properties. We consider three different scenarios M1–M3. M1: Let p ≥ 0 be arbitrary and p∗ ≥ p, then for all l with p∗l > pl , we have Ik (p∗ ) > Ik (p),

∀k 6= l .

35

2.5. Special monotonicity properties

M2: Let p ≥ 0 be arbitrary and p∗ ≥ p, p∗ > 0, then for all l with pl = 0, we have Ik (p∗ ) > Ik (p),

∀k 6= l .

M3: Let p > 0 be arbitrary and p∗ ≥ p, then for all l with p∗l > pl , we have Ik (p∗ ) > Ik (p),

∀k 6= l .

Property M1 is the most general property. It means that decreasing one users power always reduces the interference experienced by all other users. Property M2 says that by switching off one user, we strictly reduce the interference of all other users. M2 is included in M1, but not vice versa. Finally, property M3 is similar to M1, but less restrictive since it is only required for positive powers p > 0. Theorem 2.18. Let Ik have property M1. If p ¯ ≥ 0, p ¯ 6= 0, fulfills γk Ik (¯ p) = C(Γ)¯ pk ,

1≤k≤K,

(2.40)

then p ¯ > 0. Proof. From Theorem 2.7 we know that there always exists a nontrivial solution p ¯ ≥ 0. Thus, there exists an index k such that p¯k > 0. Property M1 implies Il (¯ p) > Il (0) = 0, ∀l 6= k. From (2.40) it follows that p¯l > 0, ∀l 6= k, and thus p ¯ > 0. The theorem shows that if the interference function is characterized by M1, then each power allocation which satisfies (2.40) must be strictly positive. The following corollary shows uniqueness of this solution. Corollary 2.19. If Ik has property M1, then there always exists exactly one vector p ¯ > 0, with k¯ pk1 = 1, such that (2.40) holds. Proof. This follows Theorem 2.14.

from

Theorem

2.7,

Theorem

2.18,

and

36

Axiomatic SIR-Balancing Theory

Theorem 2.20. Let Ik have property M2. If p∗ > 0 fulfills γk Ik (p∗ ) = C(Γ)p∗k ,

1≤k≤K,

(2.41)

then all vectors p ¯ which fulfill (2.41) are strictly positive, i.e., p ¯ > 0. Proof. It has been shown (Thm. 2.7) that there exists a p ¯ ≥ 0 which fulfills (2.41). It remains to show that p ¯ is strictly positive under the assumption that there exists a p∗ > 0 which fulfills (2.41). The proof is by contradiction. Suppose that p¯l = 0 for an arbitrary index l. Power allocations which fulfill (2.41) can be scaled arbitrarily, thus we can assume p∗ ≥ p ¯ . Thus, there exists a k0 6= l with 0 < p∗k0 = p¯k0 , such that C(Γ) =

γk0 Ik0 (¯ p) γk0 Ik0 (¯ p) γk0 Ik0 (p∗ ) = < = C(Γ) . ∗ p¯k0 pk0 p∗k0

The inequality follows from M2 and the assumption p¯l = 0. From this contradiction we can conclude p¯l > 0, ∀l.

Theorem 2.21. Let Ik have properties M2 and M3. Suppose there exists a p∗ > 0 such that (2.41) holds, then this solution is unique, i.e., there is no other vector p ¯ ≥ 0 which fulfills (2.41). Proof. It is known from Theorem 2.20 that the existence of one solution p∗ > 0 would imply p ¯ > 0 for every other solution p ¯ that fulfills (2.41). ∗ ∗ We can scale p such that p ¯ ≥ p and with M3 this would lead to a contradiction.

2.6

Comparison of min-max and max-min optimization

Consider the min-max problem (2.2), which was shown to provide a necessary and sufficient indicator for feasibility. SIR targets Γ are feasible if and only if C(Γ) ≤ 1. Sometimes it is useful to consider a modified problem where minimization and maximization are interchanged. This leads to the

2.7. Summary

37

max-min formulation γk Ik (p) c(Γ) = sup min . pk p>0 1≤k≤K

(2.42)

Note, that this problem formulation is not motivated by minimax theory, where usually also the order of the optimization domain is interchanged. The motivation for (2.42) comes from SIR balancing. If c(Γ) = C(Γ) holds, then this means that all users can be balanced at the same level. This can lead to interesting analytical possibilities, as shown in the context of multiuser beamforming [10], where c(Γ) = C(Γ) was used to prove monotonicity and global convergence of an iterative algorithm which converges towards the optimum C(Γ). The following theorem shows the general relation between C(Γ) and c(Γ). Later, in Section 3.5.1 we will discuss a specific scenario for which equality holds. Theorem 2.22. The min-max optimum C(Γ) is an upper bound of the max-min optimum c(Γ), i.e., c(Γ) ≤ C(Γ) .

Proof. The proof is given in the Appendix A.3. More properties will be shown for the matrix-based model in Section 3.6.

2.7

Summary

In this section we have introduced a generic definition for interference functions Ik (p) based on the axiomatic framework A1–A3. This is the common basis for all interference functions considered in this text. All properties shown here apply to the special cases discussed later on. The axioms A1–A3 imply some fundamental properties, like positivity and continuity. Based on these properties, we investigate the min-max balancing problem (1.5). It is shown that in the optimum, the quantities pk /γk Ik (p) (the weighted SIR) are always balanced.

38

Axiomatic SIR-Balancing Theory

But since the interference function is solely characterized by A1–A3, it can happen that some interference functions tend to zero, along with the powers. This asymptotic characterization can be avoided by introducing a fixed-point representation, which allows zero components in the power vector. This is an alternative way to express the balanced state achieved by the min-max design goal. It is shown that there always exists a fixed-point p∗ ≥ 0 such that ΓI(p∗ ) = C(Γ)p∗ . If there exist a p∗ > 0 such that this characterization is fulfilled, then this solution is unique and an optimizer of the min-max problem (1.5). It can be ruled out that there is another positive vector which achieves a balanced state. A smaller balanced level can only be achieved by allowing powers to be set to zero.

3 Matrix-Based SIR Balancing

In the previous section, we have studied the SIR balancing problem under the assumption that the interference functions Ik (p) are defined by axioms A1–A3. This characterization is very general, and can be regarded as a basis for many classes of interference functions. Also general are the properties which can be shown under this model. In this section, we consider an important sub-class of the axiomatic model. Namely, we assume that Ik (p) depends on p in a way that is defined by a parameter-dependent coupling matrix. This model still fulfills the axioms A1–A3, thus it inherits all the properties that have been shown in the previous Section 2. In addition, the special matrix structure can be exploited in order to show some useful properties and an algorithmic solution for min-max balancing.

3.1

Min-max balancing and Perron root minimization

We start by discussing the matrix-based interference model, and the connection between min-max balancing and an eigenvalue optimization problem. For linear interference models Ik (p) = [Ψ p]k , where Ψ ≥ 0 is irreducible, it is well known that the min-max optimum is characterized 39

40

Matrix-Based SIR Balancing

by the spectral radius (Perron root) ρ(ΓΨ) [42, 2, 46, 94, 95, 93, 33, 34]. Properties of the spectral radius related with the QoS feasible region were shown in [16, 17, 63]. In the following we extend these results to a more general model, which includes the possible use of an adaptive receive strategy. 3.1.1

Matrix-based interference model

Assume that the cross-talk between all transmitter-receiver pairs is characterized by a K × K non-negative coupling matrix Ψ(z), where the parameter z stands for an abstract receive strategy, which will be specified in the following. The component Ψkl is the link gain between the lth transmitter and the kth receiver. Thus, the kth row of Ψ(z) determines how the kth receiver is affected by interference. The total interference power experienced by the kth user is given as [Ψ(z)p]k . Unless otherwise stated, Ψ(z) can model self-interference (non-zero entries on the main diagonal). The receive strategy z is deliberately kept general, in order for the model to be applicable for a wide range of systems (examples will be given in Sections 3.5.4 and 5.7). It does not stand for any particular technique, it is rather defined by some properties: Definition 3.1. The parameter z (the “receive strategy”) has the following properties: (1) z is chosen from a compact set Z. (2) A joint strategy z ∈ Z is a tuple of K independent userspecific strategies zk ∈ Zk , where Zk is the compact set of possible strategies of user k. We have Z = Z1 × Z2 × · · · × ZK (Cartesian product). Since the strategies do not depend on each other, the kth row of Ψ(z) only depends on zk . (3) If Z is a non-discrete set, then Ψ(z) is assumed to be continuous on Z. (4) In each row of Ψ(z), there is at least one non-zero component, so each user is coupled with at least one other user. Property (1) is required to ensure that the optimization over the receive strategy always yields an optimizer.

3.1. Min-max balancing and Perron root minimization

41

Property (2) implies that the interference of the kth user [Ψ(z)p]k (and thus SIRk ), only depends on zk , so the K receive strategies z1 , . . . , zK can be chosen independently. This is typical, e.g. for a bank of receivers, where the users are received independently. Given p, one user’s choice of receiver has no direct effect on the interference experienced by other users. Property (4) means that for a positive power allocation p > 0, each user receives interference from at least one other user. This technical assumption does not restrict the generality of the results, since interference-free users are always feasible, as discussed in Section 2.1.1. It should be noted that the choice of z does not mean a choice between different types of receive filters (like MMSE, matched filter). The parameter z determines how exactly the interference depends on the power allocation. As an example consider the coefficients of a linear filter u, which can be constrained to kuk = 1, so the filter coefficients are chosen from a compact set. Linear filtering was already discussed in Section 1.2 in the context of multiuser beamforming. Specific examples of how the results of this section can be applied to multiuser beamforming will be given in Section 3.5.4 for the noiseless case, and in Section 5.7 for an interference function including noise. 3.1.2

Feasibility and min-max balancing

Consider a fixed parameter z, which leads to an SIR SIRk (p, zk ) =

pk , [Ψ(z)p]k

∀k .

(3.1)

As discussed in the introduction, SIR targets Γ are feasible if and only if C(Γ, z) ≤ 1, where C(Γ, z) =

inf p>0:kpk1 =1

[ΓΨ(z)p]k max 1≤k≤K pk

! (3.2)

is smaller than one. Note, that we can constrain the optimization in (3.2) to kpk1 = 1 since the SIR expression in the brackets is invariant with respect to a scaling of p.

42

Matrix-Based SIR Balancing

The optimum C(Γ, z) characterizes the feasibility of a certain point Γ for a given z. The region of all jointly achievable SIR is n o S(z) = Γ : C(Γ, z) ≤ 1 . For different choices of z, we can obtain different feasible regions. The overall feasible region S, which can be achieved by jointly optimizing over p > 0 and z ∈ Z, is given as the union of regions over all possible z. [ S= S(z) . z∈Z

This is illustrated in Fig. 3.1. A global indicator for feasibility is C(Γ) = inf C(Γ, z) . z∈Z

(3.3)

The optimum C(Γ) provides a single measure for the achievability of SIR targets Γ = diag{γ1 , . . . , γK } > 0. If C(Γ) > 1, then Γ can never be supported, regardless of the choice of the receive strategy. So the overall region S can be defined as S = {Γ : C(Γ) ≤ 1} .

(3.4)

Fig. 3.1 The SIR feasible region with adaptive receiver design z is the union of regions associated with all possible choices z ∈ Z. As an example, each z could stand for a fixed choice of coefficients of a linear filter, then the associated trade-off curve is obtained by the variations of the powers, and the entire region is obtained by taking the union over all possible filter coefficients.

3.1. Min-max balancing and Perron root minimization

43

A subset of special interest is the boundary ∂S = {Γ : C(Γ) = 1} .

(3.5)

The boundary completely characterizes the region, thus in the remainder of this section will focus on ∂S. Now, consider the interference functions Ik (p) = min [Ψ(z)p]k , zk ∈Zk

k ∈ {1, 2, . . . , K} .

(3.6)

For any given power allocation p, the receivers are adaptively adjusted so as to minimize the interference of the respective user, which is equivalent to maximizing SIRk (p), ∀k, individually. Under the interference model (3.6), a point Γ is feasible if and only if C 0 (Γ) ≤ 1, where ! γk Ik (p) 0 C (Γ) = inf max . (3.7) pk p>0:kpk1 =1 1≤k≤K The following theorem shows that the region S, as defined in (3.4), is equivalently characterized by the optimum C 0 (Γ). Theorem 3.2. The eigenvalue optimization problem (3.3) and the min-max problem (3.7) achieve the same optimum, i.e., C(Γ) = C 0 (Γ). Proof. see Appendix A.4. This shows that the receive strategy in the interference function (3.6) is optimal, in the sense that it achieves arbitrary points in the SIR feasible region S. Note, that the matrix-based interference function (3.6) is an important special case of the general axiomatic model used in the previous section. It can be verified that the interference functions (3.6) fulfill the axioms A1–A3. Thus, all the properties shown in Part 2 apply. The special matrix structure of the function allows to show additional properties, like the continuity on the boundary, which will be shown in the next section.

44

Matrix-Based SIR Balancing

3.1.3

Continuity of the interference function

Continuity of the function Ik (p) was already shown in Section 2.1.2 for p > 0. For the special matrix-based interference function (3.6), this can be extended to power vectors p ≥ 0. Theorem 3.3. The function Ik (p), as defined in (3.6), is continuous for p ≥ 0. Proof. For p > 0, continuity follows from Theorem 2.3, since (3.6) fulfills the axioms A1–A3. Now, consider the sequence p(n) ≥ 0, with limn→∞ p(n) = p, where p ≥ 0 is arbitrary. Let z(p) and z(p(n) ) be the receive strategy which minimizes the interference for given p and p(n) , respectively. Then, X X (n) Ik (p) − Ik (p(n) ) = Ψkl z(p) pl − Ψkl z(p(n) ) pl l

≥

X

l

Ψkl

(n) z(p) (pl − pl ) .

(3.8)

l

Here we have exploited that that X X (n) (n) Ψkl z(p(n) ) pl = min Ψkl (z)pl . zk ∈Zk

l

l

Similarly, we can show that Ik (p) − Ik (p(n) ) ≤

X

(n) Ψkl z(p(n) ) (pl − pl ) .

l

Defining (n)

K1

=

X

=

X

(n) Ψkl z(p) |pl − pl |

l (n)

K2

(n) Ψkl z(p(n) ) |pl − pl |

l

it follows from (3.8) and (3.9) that (n)

(n)

|Ik (p) − Ik (p(n) )| ≤ max(K1 , K2 ) .

(3.9)

3.1. Min-max balancing and Perron root minimization

45

Since Z is a compact set, we have X Ck := max Ψkl (z) < +∞ , z∈Z

(n)

thus, K1

l

can be upper bounded as follows. X (n) Ψkl z(p) max |pr − p(n) K1 ≤ r | 1≤r≤K

l

≤ Ck · kp − p(n) k∞ . Similarly, we have (n)

K2

≤ Ck · kp − p(n) k∞ .

Thus, |Ik (p) − Ik (p(n) )| ≤ Ck · kp − p(n) k∞ . Since p(n) → p, we can conclude that lim Ik (p(n) ) = Ik (p) ,

n→∞

which means that Ik is continuous. Continuity will be required later, e.g. in Section 3.5.3, where an iterative algorithm is derived. 3.1.4

Interference-coupling and irreducibility

The interference coupling can be modeled by a directed graph, where each user is represented by a node. The nodes are connected by directed edges which are given by the positive entries of the link gain matrix Ψ. If Ψij > 0 then there is a connection from node i to node j. A graph is called strongly connected if for each pair of nodes (Ni , Nj ) there is a sequence of directed edges leading from Ni to Nj . In the following, a set of users will be called coupled by cross-talk if its directed graph is strongly connected. This can be expressed mathematically by the notion of irreducibility (see e.g. [27, 41, 60]). Examples for reducible and irreducible coupling matrices are illustrated in Fig. 3.2.

46

Matrix-Based SIR Balancing

(a) Ψ is reducible: its directed graph is not strongly connected because node 1 has no impact on the other nodes.

(b) Ψ is irreducible: the graph is strongly connected. Fig. 3.2 Illustration of irreducibility: The coupling matrix Ψ ≥ 0 is irreducible if and only if its associated graph is strongly connected.

The assumption of irreducibility is common in the literature. If Ψ ≥ 0 is irreducible, then all users in the system are coupled by interference. This entails some useful properties, which are summarized by the following theorem.

Theorem 3.4. (Perron-Frobenius) Suppose that ΨK×K ≥ 0 is irreducible, then each of the following is true: • The spectral radius ρ(Ψ) is an eigenvalue of Ψ. The value ρ(Ψ) is the radius of the smallest circle, centered at the origin, which encloses all of Ψ’s eigenvalues. • ρ(Ψ) is a simple root of the characteristic polynomial of Ψ. • There exists a vector p > 0, with kpk1 = 1, such that Ψ p = ρ(Ψ) p. The matrix Ψ has no other positive eigenvectors, except for positive multiples of p.

3.1. Min-max balancing and Perron root minimization

47

Assuming irreducibility, we can use the properties of Theorem 3.4 in order to determine the min-max optimum (3.7). Since the interference function (3.6) fulfills the axioms A1–A3, we know from Theorem 2.7 that there always exists a vector p ˆ ≥ 0, p ˆ 6= 0 such that γk Ik (ˆ p) = min [ΓΨ(z)ˆ p]k = C(Γ)ˆ pk , zk ∈Zk

∀k .

(3.10)

Suppose that Ψ(z) is irreducible for any receive strategy z ∈ Z. Since the minimization in (3.10) is over a compact set Z, we know that there exists a strategy zˆ such that ΓΨ(ˆ z )ˆ p = C(Γ)ˆ p.

(3.11)

If Ψ(z) is irreducible, then also ΓΨ(z) is irreducible. From Theorem 3.4 it becomes clear that the optimum C(Γ) is the spectral radius of the weighted coupling matrix ΓΨ(ˆ z ) and p ˆ is the associated principal righthand eigenvector. All other eigenvectors can be ruled out since they have negative components. The power allocation which fulfills (3.11) is strictly positive. Thus, for the special case when Ψ(ˆ z ) is irreducible, the infimum in (3.2) is always achieved and can be replaced by the minimum. The targets Γ are feasible if and only if C(Γ) = ρ(ΓΨ(ˆ z )) ≤ 1, where ρ is the spectral radius, or equivalently, the maximal eigenvalue. This connection between the SIR balancing optimum and the spectral radius was already observed in [1, 42, 2, 46, 94]. An overview is given in [96, 38]. The assumption of irreducibility is common in power control and resource allocation theory, where Ψ is mostly assumed to be strictly positive. However, the problem at hand differs from this classical problem formulation, in that we consider the joint optimization of transmission powers p and the receive strategy z. The coupling matrix Ψ(z) can depend on the parameter z in such a way that interference terms are canceled or nulled out. Thus, Ψ(z) can become reducible, which means that the system becomes partly or even fully decoupled and the Perron-Frobenius theorem cannot be applied. Thus, it is desirable to have a more general notion of feasibility, which is not based on the assumption of irreducibility. The most general case is to assume that Ψ(z) is non-negative and real. Unless otherwise

48

Matrix-Based SIR Balancing

stated, this will be the context in which we will study the max-min SIR balancing problem in the following sections. 3.1.5

General characterization of feasibility based on the spectral radius

Consider an arbitrary real coupling matrix Ψ(z) ≥ 0, which is not necessarily irreducible. The following theorem shows that also in this case the spectral radius ρ provides a general measure for feasibility, which is equivalent to the SIR balancing optimum. Theorem 3.5. The SIR-balancing optimum equals the minimum spectral radius, i.e., γk Ik (p) C(Γ) = inf max (3.12) pk p>0:kpk1 =1 1≤k≤K = inf ρ ΓΨ(z) . (3.13) z∈Z

Proof. With the Collatz-Wielandt type characterization of the spectral radius [35, 84], we have [ΓΨ(z)p]k = C(Γ, z) . (3.14) ρ ΓΨ(z) = inf max p>0 1≤k≤K pk Taking the infimum over z ∈ Z, and using definition (3.3) and Theorem 3.2, the result follows. In order to ensure the existence of an optimizer, we need the following property. Theorem 3.6. The spectral radius ρ ΓΨ(z) is continuous on Z. Proof. The spectral radius is a solution of a polynomial equation, which depends continuously on its coefficients, which in turn depend continuously on the components of Ψ(z). By assumption, Ψ(z) is continuous on Z (see beginning of Section 3.1.1).

3.2. Characterization of boundary points

49

This leads to an alternative characterization of the SIR feasible region: S = {Γ : inf ρ ΓΨ(z) ≤ 1} . z∈Z

(3.15)

In (3.15) we can replace “inf” by “min”. That is, there always exists as receive strategy which achieves the optimum. It can be concluded that for special matrix-based interference functions (3.6), feasibility is always characterized by the minimum spectral radius, even if Ψ(z) is not irreducible.

3.2

Characterization of boundary points

It was shown in the previous section that the boundary ∂S of the SIR feasible region S can be described either by a min-max SIR balancing problem (3.12) or an eigenvalue optimization problem (3.13). While problem (3.13) always has a solution, the same is not true for (3.12). In the following we will study different effects that can occur. In order to simplify the discussion, we start by characterizing the boundary for fixed receivers z (and thus a fixed coupling matrix Ψ). This approach is useful since it simplifies the problem, but nevertheless provides insight into the occurring effects. 3.2.1

Frobenius normal form

Consider an arbitrary non-negative square coupling matrix Ψ. We may assume, without loss of generality, that after simultaneous permutations of rows and columns, Ψ is reduced to a block-triangular matrix with irreducible blocks along the diagonal (which we denote as diagonal blocks in the following). This is known as the Frobenius normal form [27, p. 75] 

Ψ(1,1)

0

 (2,1) (2,2) Ψ Ψ Ψ=  .. ..  . . Ψ(N,1) Ψ(N,2)

 ... 0 ..  .. . .  .  .. . 0  . . . Ψ(N,N )

(3.16)

50

Matrix-Based SIR Balancing

The diagonal square blocks Ψ(n) := Ψ(n,n) have a minimum dimension of two. This follows from assumption 4 on page 40, which says that each user is coupled with least one other user. If Ψ is irreducible, then (3.16) consists of one single block. Definition 3.7. (isolated block) A diagonal block Ψ(n) is called isolated iff Ψ(n,l) = 0 for l = 1, 2, . . . , n − 1. By permuting the indices, the matrix can be arranged, without loss of generality, such that the isolated blocks are the first elements on the main diagonal. Definition 3.8. (block-irreducible) A matrix is Ψ is called blockirreducible, iff it has the following block-diagonal structure " (1) # Ψ

0

..

Ψ= 0

. Ψ(N )

and each block on the diagonal is irreducible. For any diagonal block Ψ(n) , we have ρ(Γ(n) Ψ(n) ) ≤ ρ(ΓΨ). Definition 3.9. (maximal block) The block Γ(n) Ψ(n) is called maximal iff ρ(Γ(n) Ψ(n) ) = ρ(ΓΨ). There is always at least one maximal diagonal block. As a consequence, the overall feasible region S can be expressed in terms of the feasible regions of the irreducible diagonal blocks: S = S (1) × S (2) × · · · × S (N ) , where S (n) = {Γ(n) : ρ(Γ(n) Ψ(n) ) ≤ 1} . Assume that the SIR targets associated with the nth sub-block are collected in a diagonal matrix Γ(n) , i.e., Γ = diag{Γ(1) , . . . , Γ(N ) }. Since Γ is diagonal, the sub-block Γ(n) Ψ(n) is irreducible. The overall spectral radius is given as ρ(ΓΨ) = maxn ρ(Γ(n) Ψ(n) ).

3.2. Characterization of boundary points

51

If Ψ is reducible, this means that users are decoupled (or partly decoupled). Then, different effects can occur, which will be specified in the next sections. 3.2.2

Classification of boundary points

In the remainder of this section, we will assume that Γ is a boundary point. This definition of a boundary point is directly related to the max-min balancing optimum discussed in Section 3.1. Definition 3.10. (boundary point) A point Γ is called a boundary point (BP) of S iff ρ(ΓΨ) = 1. If the matrix Ψ is irreducible, then we know from the PerronFrobenius Theorem 3.4 that there exists a power allocation p ˆ > 0 such that ΓΨˆ p=p ˆ , which means that the SIR targets Γ can be achieved with equality. However, the same need not hold if Ψ is reducible. In order to be able to describe the occurring effects in an adequate way, we introduce the following classification of boundary points. Definition 3.11. (effectively achievable) A boundary point Γ is called effectively achievable iff there exists a power allocation p > 0 such that SIRk (p) ≥ γk , ∀k, which can be rewritten in matrix notation as ΓΨp ≤ p .

(3.17)

Note, that ρ(ΓΨ) < 1 implies that all diagonal blocks have a spectral radius smaller than one. This means that the interference experienced by each diagonal sub-block can be compensated by the power allocation. In this case, Γ is always effectively achievable. Thus, we will focus our attention on the more interesting boundary, for which varying effects may occur. In general, the condition ρ(ΓΨ) = 1 is not sufficient for a boundary point Γ to be effectively achievable, as will be shown in the following. But first, we introduce two further definitions. A special case of achievability is when (3.17) is fulfilled with equality.

52

Matrix-Based SIR Balancing

Definition 3.12. (EBP) An effectively achievable boundary point Γ is called an equality boundary point (EBP) iff there exists a power allocation p > 0 such that SIRk (p) = γk , ∀k, which can be rewritten as ΓΨp = p .

(3.18)

Finally, it might be possible to increase a component of Γ without decreasing the spectral radius. Definition 3.13. (SBP) A boundary point Γ is called a strict boundary point (SBP) iff no component of Γ can be enlarged without leaving the region S. Having introduced these concepts and definitions, we now investigate under which conditions the different behaviors occur. If Ψ is irreducible, then we already know from Theorem 3.4 that a boundary point Γ is always an EBP and an SBP. However, this need not be true for arbitrary Ψ ≥ 0. 3.2.3

Necessary and sufficient conditions for achievability

Now, we show that achievability and strictness of a boundary point Γ only depend on the structure of the coupling matrix Ψ(z). If we assume a fixed receiver design z, then all boundary points share these properties. The choice of z, however, generally depends on Γ. For different z, the point Γ may have different properties. This case will be studied later in Section 3.3. We start by assuming an arbitrary fixed parameter z and Ψ := Ψ(z). Theorem 3.14. A boundary point Γ ∈ ∂S is effectively achievable if and only if every maximal diagonal block is isolated. Proof. Consider the diagonal blocks Γ(n) Ψ(n) , 1 ≤ n ≤ N . Assume that the set of maximal blocks is a subset of the isolated blocks. Without loss of generality, we can choose the indices, such that the blocks Γ(1) Ψ(1) , . . . , Γ(ˆv) Ψ(ˆv) are maximal and isolated. Other blocks are nonmaximal and possibly isolated. Thus, we have ρ(Γ(n) Ψ(n) ) < 1, n > vˆ

3.2. Characterization of boundary points

53

and ρ(Γ(n) Ψ(n) ) = 1, 1 ≤ n ≤ vˆ. These blocks are also isolated, this implies Γ(n) Ψ(n) p(n) = p(n)

1 ≤ n ≤ vˆ ,

where p(n) is the min-max optimal power vector associated with the block Γ(n) Ψ(n) . The power allocation of the non-maximal block vˆ + 1 can be found in the same way if this block is isolated. Since ρ(Γ(ˆv+1) Ψ(ˆv+1) ) < 1, the associated targets Γ(ˆv+1) are effectively achievable. If the block Ψ(ˆv+1) is not isolated, then this block receives interference from the blocks Ψ(ˆv+1,1) , . . . , Ψ(ˆv+1,ˆv) . The interference vector is n(ˆv+1) =

vˆ X

Ψ(ˆv+1,m) p(m) .

m=1

In order to fulfill target SIR’s Γ(ˆv+1) , the power allocation p(ˆv+1) must fulfill (I − Γ(ˆv+1) Ψ(ˆv+1) )p(ˆv+1) = Γ(ˆv+1) n(ˆv+1) .

(3.19)

Since ρ(Γ(ˆv+1) Ψ(ˆv+1) ) < 1, there exists a unique positive allocation p(ˆv+1) which solves (3.19). Having found p(ˆv+1) , we are now able to compute the optimal allocation p(ˆv+2) , by using the same argumentation as above. In this way, we can show that there exists a unique power allocation iT h p ˆ = p(1) , . . . , p(N ) , for which the point Γ = diag{γ1 , . . . γK } is effectively achievable. Conversely, assume that Γ is effectively achievable. The proof is by contradiction. Suppose that a maximal block with index n0 is not isolated. The set of user indices associated with this block is denoted (n ) by In0 . Achievability implies that for every k ∈ In0 , there exists a pk 0 such that (n0 )

pk P

l∈In0

(n ) (n0 )

Ψkl 0 pl

(n0 )

+ nk

≥ γk ,

(3.20)

54

Matrix-Based SIR Balancing (n )

where nk 0 contains the interference power caused by blocks Ψ(n0 ,1) , . . . , Ψ(n0 ,n0 −1) to the kth user. Since the block n0 is not iso(n ) lated, there is at least one index k ∈ In0 for which nk 0 > 0. Since (3.20) holds by assumption, there exists a strictly positive power vector p(n0 ) such that the target Γ(n0 ) is achieved with equality, i.e., p(n0 ) = (I − Γ(n0 ) Ψ(n0 ) )−1 Γ(n0 ) n(n0 ) . Strict positivity implies that ρ(Γ(n0 ) Ψ(n0 ) ) < 1, which is a contradiction since block n0 is maximal. Note, that an EBP is always effectively achievable, but the converse need not hold. A necessary and sufficient condition is provided by the following theorem. Theorem 3.15. An effectively achievable boundary point Γ is an EBP if and only if the maximal blocks coincide with the isolated blocks. Proof. Suppose that Γ is an EBP. Consider an arbitrary isolated block with block index n0 and user index set In0 . By assumption, we have (n0 )

pk P

l∈In0

(n ) (n0 )

Ψkl 0 pl

= γk ,

k ∈ In0 .

This can be rewritten as Γ(n0 ) Ψ(n0 ) p(n0 ) = p(n0 ) , thus ρ(Γ(n0 ) × Ψ(n0 ) ) = 1. Consequently, each isolated block is a maximal block. The existence of non-isolated maximal blocks is ruled out by Theorem 3.14. Conversely, suppose that the maximal blocks coincide with the isolated blocks. If Γ were not an EBP, this would imply the existence of an isolated block with spectral radius smaller than one, which would be a contradiction.

Example 3.16. The following example illustrates the case when Γ cannot be achieved effectively by a power vector p > 0 exists, so the fixed-point characterization can only be fulfilled by allowing zero powers.

3.2. Characterization of boundary points

55

Consider a boundary point Γ and the weighted coupling matrix h i A 0 ΓΨ = 0 B . The spectral radius is ρ(ΓΨ) = max ρ(A), ρ(B) . Assume that the irreducible sub-blocks are chosen such that only the first block is maximal, i.e., ρ(ΓΨ) = ρ(A) > ρ(B). The second sub-block is not maximal, thus ΓΨ does not have a strictly positive principal eigenvector. But the irreducible sub-blocks A and B have strictly positive principal eigenvectors p(A) and p(B) , respectively (according to the Perron/Frobenius theory). (A) ¯ (B) = Thus, ΓΨ has non-negative eigenvectors p ¯ (A) = p 0 and p 0 p(B) , which fulfill ΓΨ p ¯ (A) = ρ(A) p ¯ (A) ΓΨ p ¯ (B) = ρ(B) p ¯ (B) . From (3.14), we know that the optimum C(Γ) (optimization over p > 0) equals the spectral radius ρ(ΓΨ). The example shows that if we replace the constraint p > 0 by p ≥ 0, i.e., if users are allowed to switch off their powers, then a smaller level (associated with a larger QoS region) can be achieved. This is exactly what is stated by Theorem 2.12 in Section 2.3. That is, ΓΨ can have two different eigenvectors p ≥ 0 with different associated eigenvalues. 3.2.4

Necessary and sufficient condition for strictness

Now we study under which conditions the boundary point Γ is a strict boundary point, as defined in Definition 3.13. Theorem 3.17. A boundary point Γ is an SBP if and only if all diagonal blocks are maximal, i.e., ρ(ΓΨ(n) ) = 1, n ∈ {1, 2, . . . , N }. Proof. Assume that all diagonal blocks are maximal. Increasing one or more components of Γ increases the spectral radius of at least one block, thus the overall coupling matrix ΓΨ has a spectral radius ρ(ΓΨ) > 1, which would imply that Γ is not contained in the region S. Conversely,

56

Matrix-Based SIR Balancing

if Γ is an SBP, then all blocks must be maximal. Otherwise, there would exist a non-maximal sub-block, for which at least one SIR component could be enlarged, which would be a contradiction. Note, that an SBP is not always an EBP. This is because ρ(ΓΨ) = maxn ρ(Γ(n) Ψ(n) ), which means that non-zero off-diagonal blocks do not affect the overall spectral radius. Thus, it may happen that Γ is strict, but achievability is prevented by interference caused by offdiagonal blocks. Corollary 3.18. An SBP is an EBP if and only if ΓΨ is blockirreducible and all blocks Γ(n) Ψ(n) , 1 ≤ n ≤ N , are maximal. Proof. This is a consequence of Theorems 3.15 and 3.17. Examples will be given in later in Section 3.3.3, where the different types of boundary points will be discussed in the context of adaptive receiver design.

3.3

Achievability under an adaptive receive strategy

Now, consider again the case where the parameter z ∈ Z can be chosen adaptively. Whether a boundary point Γ is an EBP or an SBP depends on the structure of Ψ(z), and thus on the choice of z. The set Z(Γ) can contain multiple receive strategies, which are equivalent in terms of the spectral radius. However, different z may lead to different optimal coupling matrices Ψ(z). Thus, it can happen (see the examples in Section 3.3.3) that for one strategy z ∈ Z(Γ), the targets Γ are effectively achievable, but for another strategy they are not. If Γ is effectively achievable for different receive strategies, one could expect that different Ψ(z) generally lead to different power allocations. But it will be shown in Section 3.4 that this is not the case. Under certain conditions, the optimal power allocation is unique 3.3.1

Optimal receive strategies

A target Γ is feasible if and only if there exists a z ∈ Z such that ρ ΓΨ(z) ≤ 1. Let Γ ∈ ∂S be a boundary point of the SIR feasible

3.3. Achievability under an adaptive receive strategy

57

region S. From Theorem 3.6 we know that ρ ΓΨ(z) is continuous on the compact set Z, thus the optimum (3.15) always exists, and it is possible to replace the infimum by the minimum. The set of optimal receive strategies for a boundary point Γ with 1 = minz∈Z ρ ΓΨ(z) is Z(Γ) = {z ∈ Z : 1 = ρ ΓΨ(z) } .

(3.21)

If z ∈ Z(Γ), then the target Γ ∈ ∂S is feasible (at least in the asymptotic sense). All other receive strategies never achieve the boundary. Every z ∈ Z(Γ) solves the optimization problem minz∈Z ρ ΓΨ(z) . Such an optimal receive strategy always exists, i.e., Z(Γ) 6= ∅.

Theorem 3.19. zˆ ∈ Z(Γ) if and only if for all z ∈ Z xT ΓΨ(z)y . 1 = ρ ΓΨ(ˆ z ) ≤ inf max y>0 x≥0 xT y

(3.22)

Proof. We use [10] [ΓΨ(z)y]k xT ΓΨ(z)y = max . x≥0 1≤k≤K [y]k xT y max

(3.23)

The result follows from combining (3.14) and (3.23). The min-max optimum (3.12) and the minimum spectral radius (3.13) are equivalent indicators for feasibility. This holds for general non-negative coupling matrices Ψ(z) ≥ 0, without requiring irreducibility. However, this equivalence is limited to the optimum. There is no general “transformation law” between the optimizers of problems (3.12) and (3.13). In particular, a strictly positive min-max optimizer p ˆ>0 does not always exist, which means that the infimum (3.12) is possibly not achieved. But we know from Theorem 2.7 that there always exists a nonnegative power vector p ¯ ≥ 0 (allowing zeros) such that γk Ik (¯ p) = C(Γ)¯ pk ,

1≤k≤K.

(3.24)

58

Matrix-Based SIR Balancing

This power allocation p ¯ is associated with a receive strategy zp¯ , obtained from minimizing the individual interference terms, as in (3.6). This optimal receive strategy fulfills γk Ik (¯ p) = γk

K X

Ψkl (zp¯ )¯ pl ,

∀k .

(3.25)

l=1

So (3.24) can be rewritten as ΓΨ(zp¯ )¯ p = C(Γ)¯ p. This shows that p ¯ is the right principal eigenvector of the matrix ΓΨ(zp¯ ), and ρ ΓΨ(zp¯ ) = C(Γ) is the associated maximal eigenvalue. It can be concluded that, given the receive strategy zp¯ , the optimum C(Γ) in (3.24) is achieved by all links, thus zp¯ minimizes the spectral radius. For a boundary point Γ, we have zp¯ ∈ Z(Γ). Now, an interesting question is whether each ˆ z ∈ Z(Γ) is a solution of the SIR balancing problem (2.2). The answer is provided by the following theorem. Theorem 3.20. The optimizer ˆ z ∈ Z(Γ) solves the min-max problem (2.2) if and only if the matrix ΓΨ(ˆ z) has a positive eigenvector p ˆ > 0, PK associated with an eigenvalue C(Γ), such that Ik (ˆ p) = l=1 Ψkl (ˆ z)ˆ pl , for all k. Proof. If ˆ z ∈ Z(Γ) solves the min-max problem, then there is an associated p ˆ , which is the right eigenvector of ΓΨ(ˆ z), with eigenvalue C(Γ). Also, Ik (ˆ p) = [Ψ(ˆ z)ˆ p]k is fulfilled, since otherwise an improvement could be achieved. Conversely, if these properties are fulfilled, then this can be rewritten as γk Ik (ˆ p) = [ΓΨ(ˆ z)ˆ p]k = C(Γ)ˆ pk , ∀k. 3.3.2

Optimal power allocation

Since Γ is a boundary point, we have inf p>0 maxk γk Ipkk(p) = 1. As discussed in the previous section, there always exists a vector p∗ ≥ 0 such that γk Ik (p∗ ) = p∗k , ∀k. But the following set is of particular interest: P(Γ) = {p > 0 : p = ΓI(p)} ,

(3.26)

3.3. Achievability under an adaptive receive strategy

59

A vector p ∈ P(Γ) achieves the targets Γ with equality, i.e., SIRk (p) = γk , ∀k. The following Corollary shows that no other power allocation can achieve a larger balanced SIR margin. Corollary 3.21. Suppose there exist µ1 , µ2 > 0 and p(1) , p(2) > 0, with ΓI(p(l) ) = µl p(l) , l = 1, 2. Then, µ1 = µ2 . Proof. Ik (p) fulfills the axioms A1–A3 introduced in Section 2. Thus, the result is a consequence of Theorem 2.14. That is, every p ∈ P(Γ) is an optimizer of the min-max balancing problem (3.12). Conversely, every min-max optimizer (if existent) is contained in the set P(Γ). Note, that P(Γ) can be empty, as will be discussed later. Corollary 3.22. p ˆ ∈ P(Γ) if and only if there exists a zˆ ∈ Z(Γ) such that zˆk = arg min [ΓΨ(z)ˆ p]k ,

k = 1...K ,

(3.27)

zk ∈Zk

ΓΨ(ˆ z )ˆ p=p ˆ.

(3.28)

Proof. The proof is similar to the proof of Theorem 3.20. The result follows from the definition of P(Γ), as given in (3.26), and the fact that the optimization strategy (3.27) is optimal with respect to the spectral radius. That is, a strategy zˆ which fulfills (3.27) for a given boundary point Γ, is contained in the set Z(Γ). Thus, for each p ˆ ∈ P(Γ) there exists a zˆ ∈ Z(Γ) such that the optimality conditions (3.27) and (3.28) are jointly fulfilled. If zˆ is charac terized by (3.27) and ρ Γ(n) Ψ(n) (ˆ z ) = 1, then we say that this block is strictly maximal, since its spectral radius cannot be decreased. If the set P(Γ) is non-empty, then a p ˆ ∈ P(Γ) can be computed by an iterative strategy, which will be derived later in Section 3.5. Note, that the optimizer of (3.27) is not always unique. Also, not every zˆ ∈ Z(Γ) fulfills the conditions (3.27) and (3.28). These effects will be illustrated by examples in the remainder of this section.

60

Matrix-Based SIR Balancing

3.3.3

Examples for achievability and strictness

Next, we construct examples, which show that there can exist different optimal receive strategies zˆ(1) , zˆ(2) , ∈ Z(Γ), under which the boundary point Γ has different properties. Example 3.23. We first provide an example for a case where z ∈ Z(Γ) does not fulfill (3.27) and (3.28), thus P(Γ) is empty. To this end, consider a partly coupled system characterized by a cross-talk matrix " # Ψ(z) =

0 z1 z2 0 A11 A12 A21 A22

0 0 0 z4

0 0 z3 0

,

(3.29)

where A11 , A22 , A21 , A12 > 0 are constant and z1 , z2 , z3 , z4 ≥ ˆb > 0. The target Γ = diag{γ1 , . . . , γ4 } fulfills γ1 = γ2 = 1/ˆb, γ3 = γ4 , and 1 < γ3 < 1/ˆb. The receive strategy zˆ(1) is chosen such that " # ˆ Ψ(ˆ z (1) ) =

0 b ˆb 0 A11 A12 A21 A22

0 0 0 b∗

0 0 b∗ 0

,

where b∗ = 1/γ3 and thus b∗ > ˆb. The matrix Ψ(ˆ z (1) ) has two irre ∗ ˆ ducible blocks Ψ(a) = 0ˆ b and Ψ(b) = b0∗ b0 on the main diagonal. b 0

With Γ(a) = diag{γ1 , γ2 } and Γ(b) = diag{γ3 , γ4 } and the above definitions, we have ρ(Γ(a) Ψ(a) ) = ρ(Γ(b) Ψ(b) ) = 1. Thus, zˆ(1) ∈ Z(Γ) and both diagonal blocks are maximal. However, the second block is not strictly maximal and condition (3.27) is not fulfilled. We have b∗ > ˆb, thus γ3 and γ4 can be increased while maintaining ρ(Γ(b) Ψ(b) ) = 1. Thus, Γ is not an SBP. Moreover, the second block Ψ(b) is not isolated. Since ρ(Γ(b) Ψ(b) ) = 1, this means that there does not exist a p ˆ > 0 such that ΓΨ(ˆ z (1) ) p ˆ≤p ˆ and condition (3.28) is not fulfilled. That is, Γ is not effectively achievable, i.e., ΓΨ(ˆ z (1) )ˆ p≤p ˆ cannot be fulfilled (see Theorem. 3.14).

Example 3.24. Now, we show that ΓΨ(ˆ z ) can have a strictly positive dominant right eigenvector p ˆ such that (3.28) is fulfilled, but zˆ ∈ Z(Γ)

3.3. Achievability under an adaptive receive strategy

61

does not fulfill the first optimality condition (3.27) for all indices k = 1 . . . K. For the model (3.29), the receive strategy zˆ(2) ∈ Z(Γ) is chosen such that " 0 ˆb 0 0 # Ψ(ˆ z (2) ) =

ˆb 0 A11 A12 A21 A22

0 0 0 ˜b ˜b 0

,

where ˆb < ˜b < 1/γ3 . Thus, the spectral radius of the second (nonisolated) block Γ(b) Ψ(b) (ˆ z (2) ) is smaller than one, while the spectral radius of the first block equals one. According to Theorem 3.15, the point Γ is an EBP, i.e., there exist a p ˆ > 0 such that ΓΨ(ˆ z (2) )ˆ p=p ˆ, thus condition (3.28) is fulfilled. However, condition (3.27) is not fulfilled. Since ˜b > ˆb, we can reduce ˜b as in the previous example. Thus, Γ is not an SBP. This example shows that the set Z(Γ) can contain different optimal receive strategies leading to different behaviors. A positive right eigenvector exists for the strategy zˆ(2) , thus Γ is an EBP. But the example shows that there might be other parameters, for which Γ is not effectively achievable. Not only does the spectral radius ρ ΓΨ(z) matter, but also the choice of z. Example 3.25. Next, we construct examples, which show that for an SBP Γ, there can exist two different solutions zˆ(1) , zˆ(2) ∈ Z(Γ), such that ΓΨ(ˆ z (1) ) has a positive right eigenvector p ˆ > 0, and zˆ(1) is charac(2) terized by (3.27), but ΓΨ(ˆ z ) has no positive eigenvector. Thus, the achievability of an SBP can also depend on the choice of the receive strategy. Suppose that Ψ(z) is parametrized by z in the following way: " 0 # z 0 0 1

Ψ(z) =

z2 0 0 0 g(z3 ) g(z3 ) 0 f (z3 ) g(z4 ) g(z4 ) f (z4 ) 0

,

(3.30)

where g(zk ) = zk − ˆb and z1 , z2 , z3 , z4 ≥ ˆb > 0. The target Γ fulfills γ1 = γ2 = 1/ˆb and γ3 = γ4 = 1/f (ˆb). The function f is chosen such that f (˜b) = f (ˆb) is a global minimum, achieved by different strategies ˜b and ˆb.

62

Matrix-Based SIR Balancing

(1) The first solution zˆ(1) ∈ Z(Γ) fulfills zˆk = ˆb, ∀k. The resulting matrix Ψ(ˆ z (1) ) is block-irreducible. Both blocks are strictly maximal, which means that zˆ(1) and p ˆ (1) are coupled by the optimization problem (3.27).

Example 3.26. Consider again the model (3.30). The solution zˆ(2) ∈ (2) (2) Z(Γ) fulfills zˆk = ˆb, k = 1, 2, and zˆk = ˜b, k = 3, 4, where ˜b > ˆb, thus g(˜b) = ˜b − ˆb > 0. Since f (˜b) = f (ˆb), both blocks of ΓΨ(ˆ z (2) ) are maximal. They are even strictly maximal, since f (˜b) is an absolute minimum (no improvement can be achieved). However, the off-diagonal block is not zero, thus no eigenvector p > 0 exists.

3.3.4

Special behavior for K = 2 and K = 3

In the previous section it was shown that the set P(Γ) can be empty. However, this does not hold for the special case when the number of users is K = 2 or K = 3. Also, we assume that for each user k, there exists a power allocation p(k) > 0 such that Ik (p(k) ) > 0, then Ik (p) > 0 for all p > 0. As an additional assumption, we require that the components of the main diagonal of Ψ are zero (no self interference). Theorem 3.27. For K = 2, 3 and the above assumptions, the set P(Γ) is always non-empty and consists of a single element. The minmax strategy (3.12) and the eigenvalue optimization problem (3.13) are equivalent. Proof. Let’s start with K = 2. Since the interference is positive, we 0 Ψ12 have minz∈Z ρ ΓΨ(z) = ρ(ΓΨ), where Ψ = Ψ is the coupling 0 21 matrix obtained from independent optimization over the rows, i.e., Ψ12 = min Ψ12 (z1 ) > 0 , z1 ∈Z1

Ψ21 = min Ψ21 (z2 ) > 0 . z2 ∈Z2

3.4. Uniqueness of the power allocation

63

Thus, for K = 2, the optimization does not depend on the power allocation. The 2 × 2-matrix Ψ resulting from the spectral radius optimization problem (3.13) is always irreducible. This means that the set P(Γ) has a unique element p ˆ , which is given as the principal right eigenvector of ΓΨ. Let zˆ be an optimizer of (3.13), i.e., ρ ΓΨ(ˆ z ) = ρ(ΓΨ), then zˆ and the power allocation p ˆ are related by (3.27) and (3.28). For K = 3, we know from Theorem 2.7 that there always exists ap ˆ ≥ 0 such that γk pˆk = Ik (ˆ p), ∀k. This vector must even be strictly positive, since the existence of one or two zero components can be ruled out. Without loss of generality, assume that p ˆ = [a, 0, 0], with a > 0, then this would lead to the contradiction γ1 pˆ1 = I1 (ˆ p) = 0. Similarly, the assumption p ˆ = [a, b, 0], with a, b > 0, leads to the contradiction γ3 pˆ3 = I3 (ˆ p) > 0, because of the strict positivity of I(p) for p > 0 (see also Theorem. 2.8). Thus, the set P(Γ) is always non-empty. Also, p ∈ P(Γ) can be shown to be unique. But for K = 4, the set P(Γ) can be empty. This was already demonstrated by the previous examples in Section 3.3.3. Thus, the behavior which has been observed for K = 2, 3 cannot be generalized.

3.4

Uniqueness of the power allocation

Consider an EBP Γ. In this section, we investigate under which condition the targets Γ are achieved by a unique power allocation. 3.4.1

Strictly maximal blocks

Assume that Γ ∈ ∂S is an EBP with an optimal receive strategy zˆ ∈ Z(Γ). Thus, there exists a power allocation p ˆ > 0 such that SIRk (ˆ zk , p ˆ ) = γk , for all users k ∈ {1, 2, . . . , K}. This can be rewritten in matrix form as ΓΨ(ˆ z )ˆ p=p ˆ.

(3.31)

According to Theorem 3.15, all isolated blocks of ΓΨ(ˆ z ) must be maximal for the EBP assumption to hold. Since, the spectral radius of each block also depends on z, we need an additional characterization. To this

64

Matrix-Based SIR Balancing

end, we introduce the set Iiso = I1 ∪ · · · ∪ Ir , which contains the user indices associated with the r isolated blocks. Lemma 3.28. Let Γ be an EBP, i.e., there exists a receive strategy zˆ ∈ Z(Γ) such that ΓΨ(ˆ z ) has a right-hand eigenvector p ˆ > 0, then there exists at least one isolated block Γ(1) Ψ(1) (ˆ z ) (without loss of generality we can assume that it is the first one) with index set I1 ⊆ Iiso such that p ˆ and zˆ are related in the following way: zˆk = arg min zk ∈Zk

K X

Ψkl (zk )ˆ pl ,

k ∈ I1 .

(3.32)

l=1

Thus, the block Γ(1) Ψ(1) (ˆ z ) is strictly maximal. Proof. It follows from the EBP assumption that all isolated blocks (which are irreducible by definition) are maximal. Thus, there must exist at least one isolated block (e.g. the first one) such that min ρ Γ(1) Ψ(1) (z) = 1 = ρ Γ(1) Ψ(1) (ˆ z) . z∈Z

Otherwise it would be possible to achieve an overall spectral radius ρ ΓΨ(ˆ z ) < 1, which contradicts the EBP assumption. Since Γ(1) Ψ(1) (z) is irreducible, it will be shown that its right-hand principal eigenvector p ˆ (1) fulfills X zˆk = arg min Ψkl (zk )ˆ pl ∀k ∈ I1 . (3.33) zk ∈Zk

l∈I1

Since Γ(1) Ψ(1) (z) is isolated, the summation in (3.33) can be extended to all columns of the overall matrix Ψ(z), which leads to (3.32). The proof is by contradiction. Suppose that (3.33) does not hold, thus there exists an alternative optimal receive strategy z˜ = (˜ z1 , . . . , z˜K ), characterized by ρ Γ(1) Ψ(1) (˜ z ) = min ρ Γ(1) Ψ(1) (z) = 1 , (3.34) z∈Z

and there exists an index from I1 (let’s say k = 1 without loss of generality) such that X (1) X (1) Ψ1l (˜ z )ˆ pl < Ψ1l (ˆ z )ˆ pl . l

l

3.4. Uniqueness of the power allocation

65

For all other indices k ∈ I1 \ 1, we have z˜k = zˆk . Thus, Ψ(1) (˜ z ) and (1) Ψ (ˆ z ) have identical rows except for the first one. Now, consider the matrix ( (1) Ψ1l (˜ z) + 1 ≤ l ≤ K Ψ(1) (˜ z , ) = (1) Ψkl (˜ z) k ≥ 2; 1 ≤ l ≤ K with arbitrary 0 < < ˆ. Since Ψ(1) (˜ z ) is irreducible, the matrix Ψ(1) (˜ z , ) is irreducible as well. We can choose ˆ such that X (1) X (1) Ψ1l (˜ z , ˆ)ˆ pl = Ψ1l (ˆ z )ˆ pl . l

l

Since 0 < < ˆ, we have X (1) X (1) Ψ1l (˜ z , )ˆ pl < Ψ1l (ˆ z )ˆ pl . l

l

(3.35)

Since zˆ is defined to minimize ρ Γ(1) Ψ(1) (z) , this receive strategy, together with the eigenvector p ˆ , balances the SIR at a common maximum level. Multiplying (3.35) with γ1 /ˆ p1 on both sides, we obtain γ1

(1) z , )ˆ pl l Ψ1l (˜

P

pˆ1

<

γ1

(1) z )ˆ pl l Ψ1l (ˆ

P

pˆ1

= ρ Γ(1) Ψ(1) (ˆ z) .

(3.36)

For all other indices k = 2, 3, . . . , K we have γk

(1) z )ˆ pl l Ψkl (˜

P

pˆk

=

γk

(1) z )ˆ pl l Ψkl (ˆ

P

pˆk

= ρ Γ(1) Ψ(1) (ˆ z) .

Since Ψ(1) (˜ z , ) is irreducible, it follows that ρ Γ(1) Ψ(1) (˜ z , ) < ρ Γ(1) Ψ(1) (ˆ z) . With 0 < 1 < 2 , we have (1)

(1)

Ψkl (˜ z , 1 ) ≤ Ψkl (˜ z , 2 ),

1 ≤ k, l, ≤ K ,

and thus ρ Γ(1) Ψ(1) (˜ z , 1 ) ≤ ρ Γ(1) Ψ(1) (˜ z , 2 ) .

(3.37)

(3.38)

66

Matrix-Based SIR Balancing

The function ρ Γ(1) Ψ(1) (˜ z , ) is monotone, thus ρ Γ(1) Ψ(1) (˜ z ) = lim ρ Γ(1) Ψ(1) (˜ z , ) . →0

(3.39)

Combining (3.38) and (3.39) we have ρ Γ(1) Ψ(1) (˜ z ) < ρ Γ(1) Ψ(1) (ˆ z) = 1 , which contradicts (3.34). Lemma 3.28 provides a necessary condition for Γ to be an EBP. Receive strategies zˆk , k ∈ I1 characterized by (3.32) maximize the respective SIR of the users associated with this isolated block, thus no component of Γ(1) can be improved. Other isolated blocks may be strictly maximal or not. If there is one block which is not strictly maximal, then one or more SIR associated with this block can be improved. However, this improvement does not change the overall spectral radius and it is always restricted to a subset of users (see Lemma 3.28). It may never happen that all components can be improved simultaneously. Thus, a possible improvement of one or more components does not contradict the fact that Γ is a boundary point. Later, in Section 3.4.5, we will give examples for the described effects. This not only helps to better understand, but also shows that the results are strict, i.e., the effects can occur. 3.4.2

Equality boundary points

In the following we analyze and compare sub-blocks of Ψ(z) for different receive strategies z. For this analysis it is important to agree on a fixed user ordering. That is, the same choice of user indices must be assumed for all choices of z. For users associated with strictly maximal blocks, the optimal power allocation is shown to be unique by the following theorem. (ˆ z) Let Iopt ⊆ Iiso be the subset of users associated with strictly maximal blocks whose spectral radius cannot be reduced (i.e., for which (3.32) holds). We can renumber the users, such that the first J blocks (ˆ z) are strictly maximal, i.e., Iopt = I1 × · · · × IJ . It is important to notice (ˆ z)

that Iopt depends on Γ as well as on ˆ z.

3.4. Uniqueness of the power allocation

67

Theorem 3.29. Let Γ be an EBP with optimal receive strategies zˆ, z˜ ∈ Z(Γ) such that ΓΨ(ˆ z ) and ΓΨ(˜ z ) have right eigenvectors p ˆ>0 and p ˜ > 0, respectively. Then there exists a scalar µ such that p˜k = µˆ pk ,

(ˆ z)

k ∈ Iopt ,

(ˆ z)

where Iopt is the set of users associated with strictly maximal isolated blocks. Proof. Since eigenvectors can be arbitrarily scaled (the SIR is invariant with respect to a scaling of the power vector), we can assume p˜k > pˆk , ∀k, without loss of generality. (ˆ z) From Lemma 3.28 we know that Iopt ⊆ Iiso is non-empty. We have z˜k = arg min zk

K X

(ˆ z)

∀k ∈ Iopt

Ψkl (zk )˜ pl

l=1

= arg min zk

X

Ψkl (zk )˜ pl

(ˆ z)

∀k ∈ Iopt .

(3.40)

(ˆ z)

l∈Iopt

(ˆ z)

For k ∈ Iopt , the parameters z˜k and zˆk are characterized by γˆk = SIRk (˜ zk , p ˜ ) and γˆk = SIRk (ˆ zk , p ˆ ), respectively. Thus, X X p˜k = γˆk Ψkl (˜ zk )˜ pl = min γˆk Ψkl (zk )˜ pl zk

l6=k

≤ γˆk

l6=k

X

Ψkl (ˆ zk )˜ pl ,

(ˆ z)

∀k ∈ Iopt .

(3.41)

(ˆ z)

(3.42)

l6=k

Also, pˆk = γˆk

X

Ψkl (ˆ z )ˆ pl ,

∀k ∈ Iopt .

l6=k

Using p ˜>p ˆ , and combining (3.41) and (3.42), we have X (ˆ z) 0 < p˜k − pˆk ≤ γˆk Ψkl (ˆ z )(˜ pl − pˆl ), ∀k ∈ Iopt .

(3.43)

l6=k

Consider an isolated strictly maximal block with index r and user (ˆ z) indices Ir ⊆ Iopt . With (3.43) we have

68

Matrix-Based SIR Balancing

Bk := p˜k − pˆk ≤ γˆk

X

(r)

Ψkl (ˆ z )(˜ pl − pˆl ),

∀k ∈ Ir .

l∈Ir

Since the matrix block Γ(r) Ψ(r) (ˆ z ) is irreducible by definition, and Bk > 0, we have X (r) Bk = γk Ψkl (ˆ z )Bl , k ∈ Ir . l∈Ir

That is, the vector with components Bk , k ∈ Ir , is a right eigenvector of the matrix Γ(r) Ψ(r) (ˆ z ). Also, the vector p ˆ (r) (only components associated with Ir ) is a right eigenvector of Γ(r) Ψ(r) (ˆ z ). Eigenvectors are unique up to a scaling. With Bk := p˜k − pˆk we can conclude that p ˜ (r) (r) is a scaled version of p ˆ , which proves the result. The same can be shown for each isolated, strictly maximal block.

Remark 3.30. For each isolated, strictly maximal block, a different (ˆ z) scaling factor µ can be chosen, so the powers pˆk , k ∈ Iopt , are unique up to a block-wise scaling. Since the scaling does not affect the individual (ˆ z) SIR’s, we can as well choose µ = 1, thus pˆk = p˜k for k ∈ Iopt . Note, that this property pertains to the isolated strictly maximal blocks. The power vectors associated with the other blocks may be different.

Note, that Theorem 3.29 can be extended to any effectively achievable point characterized by ΓΨ(ˆ z )ˆ p≤p ˆ . However, the more interesting case here is where equality holds. Finally, it should be emphasized that, block-wise uniqueness of the power allocation does not necessarily mean uniqueness of the receive strategy zˆ ∈ Z(Γ) and the resulting coupling matrix Ψ(ˆ z ). The nonisolated block have a spectral radius smaller than one (since we focus on effectively achievable points). Thus, the optimal receive strategies zˆk , k ∈ Ir , for some non-isolated block with index r, (summarized by zˆ(r) ) need not be unique. The receive strategy zˆ(r) is part of the overall strategy zˆ ∈ Z(Γ), which is defined in (3.21). Since ρ Γ(r) Ψ(r) (ˆ z (r) ) < 1, we may as well replace zˆ(r) by another strategy z˜(r) , which would also lead to a spectral radius ρ Γ(r) Ψ(r) (˜ z (r) ) < 1. This new receive

3.4. Uniqueness of the power allocation

69

strategy would as well achieve targets Γ, however with a different power allocation. 3.4.3

Strict boundary points

Now, consider an EBP Γ ∈ ∂S, which is also an SBP (an SBP need not be an EBP in general), and a parameter zˆ ∈ Z(Γ). It follows from Corollary 3.18 that all blocks are maximal and isolated, i.e., ρ Γ(n) Ψ(n) (ˆ z ) = 1, 1 ≤ n ≤ N . The power allocation p ˆ > 0 which achieves Γ is given by ΓΨ(ˆ z )ˆ p=p ˆ (see (3.18) and the definition of an EBP). Theorem 3.31. Suppose that an EBP Γ is also an SBP, and there exist zˆ, z˜ ∈ Z(Γ) such that ΓΨ(ˆ z ) and ΓΨ(˜ z ) are block-irreducible, and the N blocks have principal right eigenvectors p ˆ (n) > 0, n = 1, 2, . . . , N , and p ˜ (n) > 0, respectively. Then p ˜ (n) = µn p ˆ (n) ,

1≤n≤N ,

(3.44)

where µn are arbitrary scaling factors. Thus the solution is unique up to a block-wise scaling. Proof. Since Γ is an SBP, no component of Γ can be improved. This implies X X Ψkl (zk )ˆ pl = γˆk Ψkl (ˆ zk )ˆ pl , 1 ≤ k ≤ K . (3.45) min γˆk zk ∈Zk

l

l

Analogously, (3.45) holds for the pair z˜, p ˜ . Thus, for all blocks n we have X (n) (n) (n) (n) (n) γˆk Ψkl (ˆ z )(˜ pl − pˆl ) ≥ p˜k − pˆk , k ∈ In . l∈In

In analogy to the proof of Theorem 3.29, we can conclude that (3.44) holds. Thus, if Γ is an SBP, then all matrices ΓΨ(˜ z ) with z˜ ∈ Z(Γ) have the same right eigenvector (if it exists, i.e., if Γ is also an EBP), up to

70

Matrix-Based SIR Balancing

a block-wise scaling. All these matrices have the same block-irreducible structure. The only possible ambiguities are the solutions of the minimization problems (3.45). 3.4.4

Interference structure

Next, we study how far uniqueness extends to the structure of the coupling matrix. The following theorem analyzes the behavior of a coupling matrix ΓΨ(ˆ z ) with different receive strategies, for which strictly positive power allocations exist. Theorem 3.32. Suppose that Γ is an EBP and there exist zˆ, z˜ ∈ Z(Γ) such that ΓΨ(ˆ z ) and ΓΨ(˜ z ) have strictly positive right eigenvectors, then ΓΨ(ˆ z ) and ΓΨ(˜ z ) have the same number of strictly maximal isolated blocks, and the blocks have the same positions and dimensions for both matrices. (ˆ z)

Proof. Let Iopt be the set of user indices associated with the strictly maximal isolated blocks of ΓΨ(ˆ z ) (characterized by Lemma 3.28). In the previous section it was shown that the right eigenvectors associated with these blocks are unique up to a block-wise scaling, thus we can (ˆ z) choose pˆk = p˜k , ∀k ∈ Iopt , without loss of generality. Now, let r be a block index such that Γ(r) Ψ(r) (ˆ z ) is strictly maximal and isolated. The power allocation associated with this sub-block is denoted as p ˆ (r) (part of the eigenvector p ˆ > 0). The set of user indices (ˆ z) associated with this block is denoted as Ir . Since Ir ⊆ Iopt , we have for all k ∈ Ir pˆk = γˆk

K X l=1

Ψkl (ˆ zk )ˆ pl = min γˆk zk ∈Zk

= min γˆk zk ∈Zk

= min γˆk zk ∈Zk

K X

Ψkl (zk )ˆ pl ,

k ∈ Ir

Ψkl (zk )ˆ pl ,

k ∈ Ir

Ψkl (zk )˜ pl ,

k ∈ Ir .

l=1

X l∈Ir

X l∈Ir

(3.46)

3.4. Uniqueness of the power allocation

71

We also have p˜k = γˆk

K X

Ψkl (˜ zk )˜ pl = min γˆk zk ∈Zk

l=1

K X

Ψkl (zk )˜ pl ,

k ∈ Ir .

(3.47)

k ∈ Ir .

(3.48)

l=1

Comparing (3.46) and (3.47), we have min γˆk

zk ∈Zk

X

Ψkl (zk )˜ pl = min γˆk zk ∈Zk

l∈Ir

K X

Ψkl (zk )˜ pl ,

l=1

Thus, Ψkl (˜ zk ) = 0 for all k ∈ Ir and l ∈ / Ir , which means that Ψ(r) (˜ zk ) (r) is isolated and has the same position and dimension as Ψ (ˆ zk ). Theorem 3.32 shows that z and p behave differently. For strictly maximal and isolated blocks, ambiguities can only exist with respect to z. This is because the optimization (3.32) can have different global optimizers, resulting in different coupling matrices Ψ. Theorem 3.32 is also interesting in another respect. Suppose that the users in Ψ(ˆ z ) are sorted such that Ψ(ˆ z ) has normal form (3.16). For the other optimal receive strategy z˜, the resulting matrix Ψ(˜ z) is not necessarily arranged in normal form. Nevertheless, the theorem asserts that under the given conditions, some properties of Ψ(ˆ z ) transfer to Ψ(˜ z ). 3.4.5

Examples for the uniqueness of the power allocation

The following example shows that the block-wise uniqueness of the power allocation (Thm. 3.29 and Thm. 3.32) only holds for the strictly maximal blocks, i.e., the results are strict and cannot be improved. Consider the coupling matrix " Ψ(z) =

0 z1 0 0 z2 0 0 0 |z3 −˜b|+ |z3 −˜b|+ 0 z3 |z4 −˜b|+ |z4 −˜b|+ z4 0

# ,

where z1 , z2 , z3 , z4 ≥ ˆb and 1 > ˜b > ˆb. The SIR targets are γ1 = γ2 = 1/ˆb and γ3 = γ4 = 1/˜b.

72

Matrix-Based SIR Balancing

Example 3.33. The first solution zˆ(1) ∈ Z(Γ) is chosen such that (1) (1) (1) (1) zˆ1 = zˆ2 = ˆb and zˆ3 = zˆ4 = ˜b. Thus, both diagonal blocks are maximal. The first block of Ψ(ˆ z (1) ) is even strictly maximal, since ˆb is the absolute minimum. The spectral radius of the second block can be improved, which means that this sub-block is not strictly maximal. Nevertheless, there exists a positive power allocation p = [1, 1, 1, 1]T , which achieves the targets Γ and which is an eigenvector of Ψ(ˆ z (1) ).

Example 3.34. Now, consider a second strategy zˆ(2) ∈ Z(Γ), where (2) (1) zˆ3 = zˆ4 = b∗ with ˆb < b∗ < ˜b. The first sub-block Γ(a) Ψ(a) (ˆ z (2) ) is (strictly) maximal and isolated. The second block has a spectral radius ρ(Γ(b) Ψ(b) (ˆ z (2) )) < 1, thus it is not maximal. According to Theorem 3.15, there exists an right eigenvector p(2) > 0, which achieves (2) (2) the targets Γ. We have p1 = p2 = 1 and the third component is (2) p3 = 2γ3 (˜b − b∗ ) /(1 − γ3 ρ∗ ). Thus, p(2) 6= p(1) . The structure characterization Theorem 3.32 is strict, in the sense that under the given assumptions, it cannot be extended to blocks other than the strictly maximal blocks. The example shows that the set Z(Γ) can contain solutions which lead to different behaviors. The resulting coupling matrix may or may not have a positive eigenvector. If such an eigenvector exists, then it may or may not be coupled with the receive strategy via the optimization problem (3.32). These examples show, that the set of optimal power allocations may generally contain different vectors. An exception is the block-irreducible case, where all blocks are isolated and strictly maximal. If there exists a solution zˆ(1) ∈ Z(Γ) such that Ψ(ˆ z (1) ) has certain properties, then the above examples show that these properties need not hold for a different choice zˆ(2) ∈ Z(Γ). Moreover, we assumed that the users are ordered such that Ψ(ˆ z (1) ) takes on the normal form (3.16). When comparing the receive strategy zˆ(1) with zˆ(2) , it is important that this ordering is not changed. Thus it can happen that Ψ(ˆ z (1) ) is (2) arranged in normal form, but Ψ(ˆ z ) is not.

3.5. Irreducible coupling matrices

73

The result Theorem 3.32 says that under certain conditions (existence of eigenvectors) some properties of the matrix Ψ(ˆ z (1) ) can always be transfered to Ψ(ˆ z (2) ). Namely, the structure of the strictly maximal blocks is preserved.

3.5

Irreducible coupling matrices

In this section we focus on the important case where the matrix ΓΨ(z) is irreducible. In this case, boundary points are effectively achievable and strict. Also, the min-max optimal power allocation can be found by an iterative algorithm. 3.5.1

Special properties for irreducible matrices

Consider the max-min optimum c(Γ), as discussed in Section 2.6. Let p ¯ > 0 be such that γk Ik (¯ p) = C(Γ)¯ pk ,

1≤k≤K,

(3.49)

then the min-max optimum C(Γ) equals the max-min optimum c(Γ). This is because γk Ik (p) γk Ik (¯ p) c(Γ) = sup min ≥ min = C(Γ) , 1≤k≤K 1≤k≤K p p ¯ p>0 k k where the last step follows from (3.49) and Theorem 2.7. From Theorem 2.22 we know that C(Γ) ≥ c(Γ), thus the inequality can only be fulfilled with equality. That is, c(Γ) = C(Γ) = ρ ΓΨ . Notice, that the converse need not hold, i.e., C(Γ) = c(Γ) does not necessarily imply (3.49), except if c(Γ) = C(Γ) for all Γ > 0. This is specified by the following theorem for the case of a fixed matrix Ψ and Ik (p) = [Ψp]k . Theorem 3.35. The following statements are equivalent: a) c(Γ) = C(Γ) for all Γ > 0, b) Ψ is irreducible,

74

Matrix-Based SIR Balancing

c) for every Γ > 0 there exists a p(Γ) > 0 such that ΓΨp(Γ) = C(Γ)p(Γ) .

(3.50)

Proof. If Ψ is irreducible, then we know from Theorem 3.4 (Perron/ Frobenius) that there always exists a p > 0 such that (3.50) is fulfilled, and c(Γ) = C(Γ) = ρ(ΓΨ). Thus, b) implies a) and c). We now prove a) ⇒ b) by contradiction. Suppose that c(Γ) = C(Γ) for all Γ, but Ψ is not irreducible. Then Ψ can be arranged in block normal form (3.16). Since C(Γ) = ρ(ΓΨ), we have C(Γ) = max ρ(Γ(n) Ψ(n) ) , 1≤n≤N

where Γ(n) Ψ(n) is the nth irreducible diagonal sub-block of ΓΨ. We have γk Ik (p) c(Γ) = sup min pk p>0 1≤k≤K γk Ik (p) . ≤ sup min pk p>0 k∈J (n) where J (n) is the index set associated with the nth diagonal block. This holds for all blocks 1 ≤ n ≤ N . If Ψ is not irreducible, then there is at least one isolated block. Without loss of generality, we can assume that the users are ordered such that Ψ(1) is the first isolated block. Exploiting the fact that Ψ(1) is isolated, we have K γk X c(Γ) ≤ sup min Ψkl pl p>0 k∈J (1) pk l=1 γk X Ψkl pl = ρ(Γ(1) Ψ(1) ) . = sup min p>0 k∈J (1) pk (1)

(3.51)

l∈J

Since the assumption a) holds for all Γ > 0, we can choose Γ such that ρ(Γ(1) Ψ(1) ) < max ρ(Γ(n) Ψ(n) ) = C(Γ) , n≥2

which, combined with (3.51), contradicts the assumption a).

3.5. Irreducible coupling matrices

75

It remains to show c) ⇒ b). To this end, we can assume C(Γ) = 1 without loss of generality. Let c) be fulfilled, i.e., (3.50) holds for all Γ, but Ψ is not irreducible. Then, Ψ can be arranged in block normal form (3.16) with at least one isolated sub-block. Since (3.50) is assumed to hold for all Γ, we can choose Γ such that one isolated sub-block has a spectral radius smaller than one. This would rule out the existence of a positive eigenvector p0 > 0 such that ΓΨp0 = p0 , thus it would contradict the assumption c). Hence, Ψ is irreducible. Recall, that the existence of a vector p ¯ > 0 such that γk Ik (¯ p) ≤ C(Γ)¯ pk ,

1≤k≤K,

(3.52)

does not imply that (3.52) can be fulfilled with equality. That is, a boundary point Γ with C(Γ) = 1 might be effectively achievable, i.e., there exists a power allocation p∗ > 0 such that SIRk (p∗ ) ≥ γk , ∀k. But there need not exist an allocation such that the targets γk are achieved with equality. Whether or not Γ can be achieved with equality depends on the structure of the coupling matrix Ψ (see definitions at the beginning of Section 3). In particular, SIRk (p∗ ) ≥ γk , ∀k can be fulfilled if and only if the set of maximal blocks is a subset of the isolated blocks. In this case, c(Γ) < C(Γ) holds. But c(Γ) = C(Γ) requires that the maximal blocks coincide with the isolated blocks. 3.5.2

Existence of a unique power allocation

The examples for K = 4 show that the existence of zˆ ∈ Z(Γ) does not necessarily imply the existence of an optimizer of the SIR balancing problem. Even though both problems have the same optimum (3.12), minimizing the spectral radius is generally not a suitable strategy for finding a solution of the SIR balancing problem (3.7), unless we make certain assumptions on the structure of Ψ. Corollary 3.36. Suppose there exists a zˆ ∈ Z(Γ) such that Ψ(ˆ z ) is irreducible, then P(Γ) contains exactly one single element. That is, the max-min balancing problem (3.7) has a unique optimizer p ˆ.

76

Matrix-Based SIR Balancing

Proof. Since Ψ(ˆ z ) is irreducible, Γ is an SBP, so uniqueness follows from Theorem 3.31. Theorem 3.4 (Perron/Frobenius) says that ΓΨ(ˆ z ) has a unique and strictly positive principal right eigenvector p ˆ . However, zˆ ∈ Z(Γ) need no be unique. It is possible that there is a second receive strategy z˜, which can lead to a different matrix ΓΨ(˜ z ). But even if there exists a vector p ˜ > 0 such that p ˜ = ΓΨ(˜ z )˜ p, then p ˆ and p ˜ are identical up to a scaling. Moreover, p ˆ and zˆ can be shown to be related via (3.27). Thus, the set P(Γ) is non-empty. Corollary 3.37. Suppose there exists a z˜ ∈ Z(Γ) such that Ψ(˜ z) is irreducible, then all matrices ΓΨ(˜ z ), with z˜ ∈ Z(Γ), which possess a strictly positive principal eigenvector, have the same eigenvector. Moreover, all these z˜ minimize the interference, i.e., condition (3.27) is fulfilled. Thus, if one finds an optimizer zˆ ∈ Z(Γ), such that condition (3.28) is fulfilled, then (3.27) must hold as well, otherwise zˆ is not an optimizer of the max-min problem. 3.5.3

Iterative algorithm for irreducible coupling matrices

Now, suppose that the matrix Ψ(z) is irreducible for all z ∈ Z. Let Γ be a boundary point of the region S, i.e., minz∈Z ρ ΓΨ(z) = 1. According to Corollary 3.18, Γ is an EBP and an SBP. No component of Γ can be improved. The matrix ΓΨ(z) has a strictly positive principal eigenvector p ˆ , which is unique, regardless of possible ambiguities of the receive strategy zˆ ∈ Z(Γ) (see Perron/Frobenius Theorem 3.4). All zˆk , k = 1, 2, . . . , K, solve the optimization problem (3.32). The following property is a consequence of Theorem 3.32. Corollary 3.38. Suppose that Ψ(ˆ z ) is irreducible for all zˆ ∈ Z(Γ), then all matrices ΓΨ(ˆ z ) have the same principal right eigenvector p ˆ>0 (up to a scaling).

3.5. Irreducible coupling matrices

77

If the boundary point Γ satisfies the conditions in Corollary 3.38, then it is an EBP and an SBP. That is, zˆ ∈ Z(Γ) is associated with a point for which no further improvement can achieved. We know from Lemma 3.28 that there is at least one optimal receive strategy zˆ ∈ Z(Γ) which leads to an eigenvector p ˆ > 0. The optimum is unique with respect to the power allocation. For each zˆ ∈ Z(Γ), the matrix ΓΨ(ˆ z ) has the same right eigenvector. Corollary 3.38 also says that each receive strategy zˆ which solves the optimization problem minz∈Z ρ ΓΨ(z) , is associated with the same principal eigenvector of ΓΨ(ˆ z ). Such an optimal zˆ is related to the right principal eigenvector p ˆ of the coupling matrix ΓΨ(ˆ z ) in a special way. That is, for given p ˆ , the receivers zˆ1 , . . . , zˆK fulfill the optimization problem (3.27). This motivates the following algorithm, which converges to the point Γ by alternately optimizing receivers z and powers p. The following steps are repeated until convergence. The superscript n denotes the nth iteration and ρ(n) := ρ ΓΨ(z (n) ) . (1) for given power allocation p(n−1) compute (n)

zk

= arg min zk ∈Zk

X

(n−1)

Ψkl (zk )pl

,

k ∈ {1, . . . , K} . (3.53)

l

(2) for given z (n) compute ΓΨ(z (n) )p(n) = ρ(n)p(n) .

(3.54)

An example for the optimization (3.53) is the beamforming optimization in Section 3.5.4, where z is a linear filter. Theorem 3.39. The sequence ρ(n) obtained by the iteration (3.53) and (3.54) monotonically converges to the global optimum of the minmax optimization problem (3.12). The associated eigenvector p(n) is the unique optimizer of (3.12).

78

Matrix-Based SIR Balancing

Proof. The proof is based on the min-max characterization of the spectral radius given in (3.22). We have ρ(n) = inf max y>0 x≥0

xT ΓΨ(z (n) )y xT y

≤ max

xT ΓΨ(z (n) )p(n−1) xT p(n−1)

≤ max

xT ΓΨT (z (n−1) )p(n−1) = ρ(n − 1) , xT p(n−1)

x≥0

x≥0

(3.55)

where the last inequality follows from (3.53), i.e., the parameter z (n) minimizes the components of the vector ΓΨ(z)p(n−1) . Thus, the sequence ρ(n) is monotonically decreasing. The sequence ρ(n) converges towards a limit ρˆ. Because of the continuity of the spectral radius (Thm. 3.6), the limit ρˆ is associated with a receive strategy zˆ, which fulfills the optimality conditions in Theorem 3.22. Thus, zˆ is an optimizer of the min-max problem. Note, that the convergence point zˆ need not be unique, but this does not matter since each convergence point fulfills the conditions in Theorem 3.22. Since Ψ(z) is irreducible by assumption, we know from Theorem 3.36 in Section 3.5.2 that the principal right eigenvector of ΓΨ(ˆ z ) is the unique optimizer of the min-max problem, regardless of possible ambiguities of the receive strategy. The algorithm can be extended to block-irreducible systems consisting of multiple independent sub-systems. The power allocation of each sub-system can be found by computing the principal eigenvector of the coupling matrix of the respective diagonal block. The blockspecific power vectors can be normalized independently, since there is no interference between the sub-systems. 3.5.4

Application to the beamforming example

We can apply the results to existing problems in wireless communications. Namely, we consider the multiuser beamforming problem in the absence of noise, as discussed in Section 1.2. In this case, the interference functions take on the specific form (1.8), with beamforming filters

3.5. Irreducible coupling matrices

79

u1 , . . . , uK . The coupling matrix Ψ as a function of u is given as ( u∗ Rl uk k l 6= k ∗ [Ψ(u)]kl = uk Rk uk . (3.56) 0 l=k The spatial array covariance matrices Rk are positive semi-definite, thus the interference component Ψkl (u) will be “nulled out” only if ul lies in the nullspace of Rk . In this way, u has impact on the structure of Ψ and on the way users are coupled by interference. Note, that the kth row of Ψ(u) only depends on uk . Also the other properties listed at the beginning of Section 3.1.1 are fulfilled. Thus, uplink beamforming is a special case of the generic interference model (3.6). For an overview on beamforming techniques in general, see e.g. [48, 40, 6] An interesting question is whether or not the power allocation resulting from the min-max SIR balancing problem is unique or not. Uniqueness was shown by Yates [91] for a different framework, including a fixed noise component (this will be discussed later in Section 4). But it is not clear whether uniqueness also holds for the interference functions (1.8). In order to explain the problem, suppose that Ψ(u) is irreducible. This is a common assumption in the related beamforming literature [29, 44, 10]. Irreducibility is fulfilled, e.g. when Rl has full rank, so u∗l Rk ul is always strictly positive. In this case, the optimum (3.7) (with optimizers u ˆi , p ˆ ) is characterized by ΓΨ(ˆ u) p ˆ = C(Γ) p ˆ, p)ˆ uk = 0, where which can be rewritten as u ˆ ∗k Bk (ˆ   X pk Rk  Bk (p) =  pl Rl − C(Γ) · . γk l6=k

The optimal beamformer, which solves (3.7), is related to p ˆ in the following way. u ˆ k = arg min [Ψ(u)ˆ p]k . uk :kuk k2 =1

It follows that 0 = u ˆ ∗k Bk (ˆ p)ˆ uk ≤ x∗ Bk (ˆ p)x, for all x with kxk2 = 1. This means that Bk (ˆ p) is positive semidefinite. Each beamformer u

80

Matrix-Based SIR Balancing

from the nullspace of Bk (ˆ p) is optimal with respect to the min-max balancing problem (3.7). If the nullspace has a dimensionality greater than one, then u ˆ is not unique. This happens, e.g. if the matrix pair P ( l6=k pˆl Rl , Rk ) has a minimum generalized eigenvalue with multiplicity greater than one. In this case, (1.8) is minimized by eigenvectors with different directions. This ambiguity of the optimal beamforming strategy u ˆ leads to a possible ambiguity of the coupling matrix Ψ(u). So it is difficult to say whether the optimal power allocation p ˆ , which is given as the right eigenvector of Ψ(ˆ u), is unique or not. The results from Section 3.4 provide an answer to this question. Since Ψ(u) is assumed to be irreducible, we know that for each optimal beamforming filter, the matrix Ψ(u) has the same right eigenvector.

3.6

Min-max and max-min balancing

A general discussion of the connection between Min-Max and Max-Min balancing for the axiomatic interference model was already started in Section 2.6. In this section, we will discuss additional properties which can be shown for the matrix-based model. 3.6.1

Continuity behavior of the functions C and c

It was shown that the min-max optimum C(Γ), as defined in (2.2), and the max-min optimum c(Γ), as defined in (2.42), can be equivalent under certain conditions. Such a behavior is desirable. For example, equivalence was used in [10] to derive upper/lower bounds which control the convergence behavior of an iterative algorithm for joint beamforming and power control. The value C(Γ) is closely linked to the problem of SIR balancing and it has some nice properties. In particular, C(Γ, ), as defined in (2.20), is continuous with respect to , monotonically decreasing for → 0, and converges towards C(Γ). The same behavior does not hold for c(Γ, ), defined as c(Γ, ) = sup min

p>0 1≤k≤K

γk Ik (p, ) . pk

(3.57)

3.6. Min-max and max-min balancing

81

To illustrate this, consider a coupling matrix h i (1) Ψ = ΨΨ(1,2) Ψ0(2) , such that ρ(Γ(1) Ψ(1) ) < ρ(Γ(2) Ψ(2) ). Let 1 be the all-one matrix, and ΓΨ + 1 =: ΓΨ . The matrix ΓΨ is strictly positive and thus irreducible. Consequently, c(Γ, ) = ρ(ΓΨ ) = C(Γ, ) , and thus, lim c(Γ, ) = lim ρ(ΓΨ ) = ρ(Γ(2) Ψ(2) ) .

→0

→0

On the other hand, we have (see (3.51)) c(Γ) ≤ ρ(Γ(1) Ψ(1) ) < ρ(Γ(2) Ψ(2) ) = lim c(Γ, ) . →0

Thus, c(Γ, ) does not converge to c(Γ). In this respect, c(Γ) is not continuous. Both problems (2.2) and (2.42) are equivalent if the coupling matrix is irreducible. Then, C(Γ) = c(Γ). Continuity plays an important role in the presence of error effects, e.g. when Ik (p) is only known approximately, then continuity ensures that small changes of p always have a limited effect on Ik (p). 3.6.2

Convexity of set of power allocations and relationship with max-min balancing

Finally, we show additional convexity properties under the assumption of the special interference function Ik , as defined in (3.6). Consider the power vector p(λ) = (1 − λ)p(1) + λp(2) , where p(1) , p(2) > 0, are arbitrary. Then, Ik p(λ) = min

zk ∈Zk

(1 − λ)

K X l=1

(1) Ψkl (zk )pl

+λ

K X l=1

! (2) Ψkl (zk )pl

82

Matrix-Based SIR Balancing

≥(1 − λ) min

K X

zk ∈Zk

! (1) Ψkl (zk )pl

l=1 K X

+ λ min

zk ∈Zk

!

(2) Ψkl (zk )pl

l=1 (1)

=(1 − λ)Ik (p

) + λIk (p(2) ) .

(3.58)

Thus, Ik is jointly concave. Consider the set M(α) = {p ≥ 0 : γk Ik (p) ≥ αpk , 1 ≤ k ≤ K, kpk1 = 1} . The set M(α) is a closed, bounded set and M(α) 6= ∅ if α < c(Γ). For α2 > α1 we have M(α2 ) ⊂ M(α1 ). For α > c(Γ) we have M(α) = ∅. Moreover, M(α) is a convex set because of the concavity of Ik . We have \ M(α) = M c(Γ) 6= ∅ . α
The set M c(Γ) is convex since the intersection of convex sets is convex. Theorem 3.40. Let Ψ(z) be irreducible for all z ∈ Z. If there exists p∗ > 0 with p∗ ∈ M c(Γ) , then γk Ik (p∗ ) = C(Γ)p∗k .

(3.59)

Proof. Suppose there exists a p∗ > 0 such that γk Ik (p∗ ) ≥ c(Γ) p∗k ,

1≤k≤K.

Then there exists a receive strategy z(p∗ ) such that ΓΨ z(p∗ ) p∗ ≥ c(Γ) p∗ ,

(3.60)

and it can even be shown that this inequality is fulfilled with equality for all indices, otherwise it would be possible to further increase the maximum c(Γ). This means that c(Γ) equals the spectral radius ρ ΓΨ z(p∗ ) and p∗ is the associated Perron eigenvector. We have γk Ik (p∗ ) = c(Γ)p∗ , ∀k. From Theorem 2.14 we know that c(Γ) equals the min-max optimum C(Γ), thus (3.59) is fulfilled.

3.6. Min-max and max-min balancing

83

Next, we show how the convexity results can be applied. Theorem 3.41. Let p∗ ∈ M c(Γ) with p∗ > 0 and there exists a constant c1 , such that the sequence p(n+1) = k

1 · γk Ik (p(n) ), c(Γ)

(1)

with pk =

γk Ik (p∗ ) c(Γ)

is bounded by c1 , i.e., (n+1)

max pk

1≤k≤K

≤ c1 ,

∀n ,

then c(Γ) = C(Γ) and there exists a p ˆ > 0 such that C(Γ)ˆ pk = γk Ik (ˆ p),

1≤k≤K.

(3.61)

Proof. Since p∗ ∈ M c(Γ) , we have γk Ik (p∗ ) ≥ c(Γ)p∗k

1≤k≤K. (1)

Without loss of generality we can assume c(Γ) = 1. Thus, pk ≥ (n+1)

p∗k > 0, 1 ≤ k ≤ K, and consequently pk (n)

sequence pk

(n)

≥ pk , 1 ≤ k ≤ K, i.e., the (n)

is monotonically increasing. Since pk

there must exists a p ˆ > 0 such that we have = pˆk = lim p(n+1) k n→∞

=

(n) limn→∞ pk

is bounded by c1 ,

= pˆk . Thus, for all k

1 lim γk Ik (p(n) ) c(Γ) n→∞ 1 p) . c(Γ) γk Ik (ˆ

Since p ˆ > 0, we have c(Γ) = C(Γ). Analogously, we can show the following result. Theorem 3.42. Let p∗ > 0 such that γk Ik (p∗ ) ≤ C(Γ)p∗k ,

1≤k≤K,

and there exists a constant c1 , such that the sequence (n+1)

p ¯k

=

1 C(Γ)

· γk Ik (¯ p(n) ),

(3.62)

84

Matrix-Based SIR Balancing

is bounded by c1 . Then, we have c(Γ) = C(Γ) and there exists a p ˆ>0 such that (3.61) holds. Proof. The proof is in analogy to the proof of Theorem 3.41. One can (n) exploit that p¯k is monotonically decreasing in n.

3.7

Duality

Thus far, we have assumed that Ψ(z) depends on z in the way specified at the beginning of Section 3.1.1. In particular, z consists of K separate strategies z1 , . . . , zK , and the kth row of Ψ(z) only depends on zk ∈ Zk . That is, in order to find the optimal zk , we only have to consider the kth row. There is no direct interaction. This assumption holds, e.g. for an uplink channels, where z stands for a bank of (independent) linear receivers, as discussed in Section 1.2. Now, we consider another class of interference functions, which depend on parameters z1 , . . . , zK in a column-wise fashion. That is, the kth column of Ψ(z) only depends on zk ∈ Zk . This means that zk only influences the interference that is caused by the kth transmitter. However, the interference [Ψ(z)p]k received by the kth receiver might depend on all parameters z1 , . . . , zK . Since zk only acts on the kth transmitter, it can be regarded as a strategy for interference avoidance. An example is downlink beamforming (possibly with dirty paper precoding) as discussed in Section 1.2. It is known from matrix theory, that ρ ΓΨ(z) = ρ ΓΨT (z) for an arbitrary choice of z. As a consequence, the strategy z which is optimal for transmit-oriented scenario (independent columns), is also optimal for the link characterized by the transpose coupling matrix ΨT (z). Clearly, both scenarios have the same SIR feasible region (3.15). This relationship was already observed in the context of power control [95], and was later used in the context of max-min-SIR downlink beamforming [10], where it was referred to as duality. If the matrix Ψ is irreducible (as assumed in [10]), then an optimal z and the associated unique power allocation can be found by applying the iterative algorithm proposed in Section 3.5.3 to the transpose link ΨT (z). The algorithmic solution becomes possible since

3.7. Duality

85

the independent columns of Ψ(z) translate into independent rows by the transpose operation. Having found an optimal z, we can compute the optimal power allocation as the principal right eigenvector of Ψ(z). But complete duality need not hold if Ψ is reducible. It still holds for the interior of the region, i.e., ρ ΓΨT (z) < 1 implies that Γ can be achieved in both links, with the same choice of z. However, the boundary structure generally differs. First, consider a fixed parameter z. Let Γ be an SBP and and EBP. According to Corollary 3.18, the matrix ΓΨ(ˆ z ), is block-irreducible. This property does not change when transposing Ψ(ˆ z ), thus Γ is also an EBP and an SBP in the downlink. For other boundary points, duality is not as straightforward. Suppose that Γ is effectively achievable in the uplink, but not an SBP. That is, the non-isolated blocks of ΓΨ(ˆ z ) have a spectral radius smaller than one and there exists a power allocation p ˆ such that SIRk (ˆ p) ≥ γˆk , 1 ≤ k ≤ K. In this case, the same point Γ need not be achievable in the downlink. The reason is that the interference coupling of the downlink users is described by the transpose Ψ(ˆ z ). This has the effect, that previously isolated maximal blocks need no longer be isolated in the transpose matrix. Then, a maximal diagonal block (the spectral radius is not changed by the transpose operation) can become non-isolated. The point Γ would be contained in the downlink region (defined by the spectral radius of the overall matrix), but it would not be effectively achievable. This is illustrated by the following example. Example 3.43. (dual system) Consider the coupling matrix  0  1 Ψ= 1 1

1 0 1 1

0 0 0 .5

0 0 .5 0

   . 

The maximal block is isolated, so the target Γ = I is effectively achievable. Taking the transpose of Ψ does not change the spectral radius,

86

Matrix-Based SIR Balancing

but may change the achievability of boundary points. Consider the transpose system   0 1 1 1   1 0 1 1  ΨT =  . 0 0 0 .5  0 0 .5 0 It can be observed that the maximal block is not isolated, so the target Γ = I is not effectively achievable. For variable z, the relationship between uplink and downlink boundary is even more complicated. Assume that there exists a receive strategy zˆ ∈ Z(Γ) such that Γ is effectively achievable in the uplink but not in the downlink. Then, there might exist another parameter z˜ ∈ Z(Γ) for which Γ is effectively achievable in the downlink.

3.8

Summary

In this section we have studied the practically relevant case of matrixbased interference functions, assuming that the non-negative coupling matrix Ψ(z) is parametrized by a receive strategy z. For example, the parameterz can represent a special choice of filter coefficients, or any other adaptive technique that can be optimized independently for each user. The matrix structure allows to extend the properties previously shown for the generic axiomatic model A1–A3. The matrix-based model is a special case of the axiomatic model, thus it inherits all its properties. In addition, it is shown that the interference functions are always continuous for all p ≥ 0 (not only for p > 0 as for the axiomatic model). Using results from classical matrix theory, it is shown that the minmax balancing problem can be interpreted as the minimization of the spectral radius ρ ΓΨ(z) over all possible receive strategies Z. The minimum spectral radius ρopt provides a single measure for the joint feasibility of a multiuser channel. SIR targets Γ are contained in the feasible region if and only if ρopt ≤ 1.

3.8. Summary

87

A deeper understanding of the SIR feasible region (and the associated QoS region) is obtained by analyzing the boundary, which includes all points Γ for which ρopt = 1. In this section, we do not require a fixed noise power component, and no constraints are imposed on the transmit powers. So it can happen that boundary points are only achieved asymptotically. One main aspect of this section is to characterize and explain these effects. By investigating the Frobenius block normal form of the coupling matrix, different effects, like achievability and strictness, are explained and related to the block structure of the matrix. Based on these results, it was shown that block-irreducibility of the coupling matrix is a necessary and sufficient requirement for the existence of a power allocation p > 0 fulfilling the fixed-point characterization ΓI(p) = C(Γ)p. For such boundary points, the optimum power allocation can be computed iteratively. The proposed iteration is monotone and converges to the global optimum of the min-max balancing problem.

4 General SINR Balancing Theory

Thus far we have assumed that interference is caused by K users, whose transmission powers are collected in a vector p. But a component of the power vector can also stand for a fixed noise power. The function Ik (p) can be defined appropriately to model interference plus noise. This means that the SIR model studied in the previous sections is general enough to incorporate noise. But there are additional properties, which are specific for systems with noise. In this section, we use an axiomatic approach to model interference and noise. This model is based on the axiomatic framework A1–A3, as introduced in Section 2. In order to model the impact of noise, we add an additional axiom A4, which requires strict monotonicity with respect to the noise component. It will be shown that this property plays an important role for the development of efficient algorithmic solutions.

4.1

Axiomatic interference model

The transmission powers of all K users are stacked in a K-dimensional vector p ≥ 0, referred to as the power allocation. We also consider the 89

90

General SINR Balancing Theory

extended power allocation p :=

h

p σ2

i

,

p ∈ RK+1 , +

where σ 2 > 0 is the noise power, which is assumed to be the same for all users for notational convenience. The model can be extended to individual noise powers. The interference (including noise) of the kth user is modeled by a function Jk : RK+1 7→ R+ . We call Jk an interference function if it + fulfills the following axioms: A1: Jk (p) is non-negative on RK+1 + A2: Jk (µp) = µJk (p) for all µ ≥ 0 A3: Jk (p(1) ) ≥ Jk (p(2) ) if p(1) ≥ p(2) (1)

(2)

A4: Jk (p(1) ) > Jk (p(2) ) if pK+1 > pK+1 and p(1) ≥ p(2) . The signal-to-interference-plus-noise ratio (SINR) is defined as SINRk (p) =

pk , Jk (p)

1≤k≤K.

(4.1)

In the following we will focus our attention on power allocations p ≥ 0 with a strictly positive noise component pK+1 > 0. With A4, it follows that Jk (p) is always strictly positive, and the SINR (4.1) is defined. This can be shown by contradiction. Suppose that there exists an arbitrary vector p ∈ RK+1 , with pK+1 > 0. There exists an α, with + 0 < α < 1, such that p0 := αp ≤ p with p0K+1 < pK+1 . This implies Jk (p0 < 0), which contradicts A1. Thus positivity is ensured if the noise is strictly positive. For most scenarios, the last component of p can be constrained to be a fixed and strictly positive noise power, i.e., pK+1 = σ 2 . Because of A2, the SINR is invariant with respect to a scaling of p. Thus, in the following, we can focus our attention on normalized power allocations p = p1 . All optimizations can be carried out with this normalized allocation. The “true” power allocation for an arbitrary noise power σ 2 is simply the scaled version σ 2 p. So unless otherwise stated, we will use the notation Jk (p) := Jk ([pT 1]T ) and SINRk (p) = SINRk (p) whenever fixed noise is assumed.

4.2. Continuity of interference functions

91

This notation is in accordance with the “standard interference function” introduced by Yates [91]. With axioms A1–A4 we have (1) Jk (p) > 0 (2) Jk (µp) < µJk (p) for µ > 1 (3) Jk (p(1) ) ≥ Jk (p(2) ) if p(1) ≥ p(2) The first property is a consequence of A4, as shown. The second property is a consequence of A2 and A4. The last property follows directly from A3. Thus, J (p) is a standard interference function, and all properties shown in [91] hold.

4.2

Continuity of interference functions

Some properties of the axiomatic framework A1–A4 were already exploited in [91, 14], where iterative algorithms were proposed for power allocation. Convergence is guaranteed if Jk (p) is continuous on RK+1 . + In [14], the requirement of continuity was formulated as an axiom. In this section we show that continuity is an immediate consequence of the properties A1–A4, thus no additional assumptions are needed. Theorem 4.1. Jk (p) is continuous for p > 0. That is, an arbitrary sequence p(n) with a limit p0 = limn→∞ p(n) , fulfills lim Jk (p(n) ) = Jk (p0 ),

n→∞

1≤k≤K.

Proof. Since Jk (p) satisfies the axioms A1–A3, the result follows from Theorem 2.3. The continuity shown in Theorem 4.1 will play an important role for the proof of convergence of the iterative algorithms. Notice, that it is sufficient to show continuity for p > 0. Since the interference function Jk (p) is strictly positive, the powers can never tend to zero, as for the general interference model studied in the previous sections.

4.3

Feasibility

Consider SINR targets γ1 , . . . , γK , which are collected in a matrix Γ = diag{γ1 , . . . , γK } .

92

General SINR Balancing Theory

In analogy to the definition of feasibility in Section 1.1.2, we say that SINR targets Γ are feasible if and only if C(Γ) ≤ 1, where γk Jk (p) C(Γ) = inf max . (4.2) p>0 1≤k≤K pk p =1 K+1

The balanced level C(Γ) provides a single measure for the joint feasibility of SINR targets Γ. It completely characterizes the SINR feasible region in the absence of power constraints. If Γ is a boundary point characterized by C(Γ) = 1, then the targets can only be achieved in an asymptotic sense. The reason is the fixed noise component pK+1 = 1. We have SINRk p1 < SINRk α·p , for 1 α > 1 and k = 1, 2, . . . , K. This follows from A3 and the definition (4.1). Thus, in the absence of power constraints, the SINR margin can always be improved by up-scaling p. Thus, boundary points are never effectively achievable. Now, consider the interior of the region, which is characterized by C(Γ) < 1. Theorem 4.2. Targets Γ are effectively achievable, i.e., there exists a power allocation p0 such that SINRk (p0 ) ≥ γk , ∀k ∈ {1, 2, . . . , K}, if and only if C(Γ) < 1. Proof. Suppose that there exists p0 = achievable, i.e., γk Jk (p0 ) ≤ 1, p0k

p0 1

such that Γ is effectively

∀k .

(4.3)

It can already be observed from (4.3) and (4.2) that C(Γ) ≤ 1, so it remains to show that this inequality is strict. To this end, consider the functions p J Jk λ·p k 1/λ 1 fk (λ) = = , λ∈R, (4.4) λ · pk pk which are the inverse SINR. The equality in (4.4) follows from property A3. From A4, we know that the functions fk (λ) are strictly monotonically decreasing in λ. In other words, by scaling the power vector p

4.3. Feasibility

93

by a common factor α, the SINR is strictly increased. This means that the infimum C(Γ) is approached asymptotically for λ → ∞, so the noise component can be neglected. The infimum C(Γ) is equivalently obtained by balancing the noise-less interference functions J k (p) := Jk p0 , i.e., C(Γ) = inf

p>0

γk J k (p) . 1≤k≤K pk max

(4.5)

Combining A4 and (4.3), we have γk J k (p0 ) γk Jk (p0 ) < ≤ 1, p0k p0k

1≤k≤K.

This holds for all k, thus γk J k (p0 ) <1. 1≤k≤K p0k max

This holds for one specific vector p0 . Taking the infimum over all possible power allocations, we obtain C(Γ) < 1. Conversely, assume that C(Γ) < 1, which implies the existence of a pˆ vector p ˆ > 0 such that J pˆk(ˆp) > γk , 1 ≤ k ≤ K. The functions Jk 1/λ k are strictly monotonically decreasing in λ. Because of the continuity of Jk (see Theorem 4.1), we have lim Jk

λ→∞

p ˆ 1/λ

= J k (ˆ p) <

pˆk . γk

Thus, there exists a λ with a power allocation p ˆ (λ) = λˆ p such that pˆk (λ) > γk , Jk p ˆ (λ)

1≤k≤K,

which proves that Γ is effectively achievable. The optimum C(Γ) provides an indicator for feasibility. Since C(Γ) is equivalently defined as the SIR balancing optimum (4.5), the results of the previous sections can be applied. Under certain conditions, C(Γ) can be computed iteratively (see Section 3.5.3). In the following, we will focus on points in the interior of the region. By Theorem 4.2, a point Γ is effectively achievable if and only if

94

General SINR Balancing Theory

C(Γ) < 1. It can be verified from (4.1) that the equation SINRk (p) ≥ γk can be rewritten as pk ≥ γk Jk (p). The following set contains all possible power allocations for which the target Γ is fulfilled. P(Γ) = {p > 0 : pk ≥ γk Jk (p), 1 ≤ k ≤ K} .

(4.6)

We have P(Γ) 6= ∅ if and only if C(Γ) < 1. A subset of P(Γ) is the set of power allocations which achieve Γ with equality: PE (Γ) = {p > 0 : pk = γk Jk (p), 1 ≤ k ≤ K} .

4.4

(4.7)

Sum power minimization and fixed-point iteration

If the set P(Γ) is non-empty, then the targets Γ are effectively achievable and we can choose the allocation which requires the minimal total power, i.e., Pmin (Γ) = min p

K X

s.t. p ∈ P(Γ).

pk

(4.8)

k=1

The set of power-optimal allocations is PO (Γ) = {p > 0 : p ∈ P(Γ) ; kpk1 = Pmin (Γ)}.

(4.9)

If the set P(Γ) is non-empty, then problem (4.8) has exactly one optimum, which can be found by the following fixed-point iteration [91] p(n+1) = ΓJ (p(n) ),

p(0) = [0, . . . , 0]T .

(4.10)

The initialization p(0) is chosen arbitrarily. If the iteration converges for one initialization, then it converges for any initialization p(0) ≥ 0. Theorem 4.3. If C(Γ) < 1, then the sequence p(n) obtained from the fixed-point iteration (4.10) is component-wise monotone and converges to the unique optimizer of the sum-power minimization problem (4.8). Proof. This was shown in [91]. An alternative proof based on the axioms A1–A4 is given in the Appendix A.5. If we choose an initialization p(0) = 0, then the sequence is component-wise monotonically increasing. Thus, we have

p(n)

4.4. Sum power minimization and fixed-point iteration (n+1)

(n)

95

(n)

pk ≥ pk , ∀k, and limn→∞ pk = p ˆ , where p ˆ is the optimizer of (4.8), which can be shown to be unique [91]. This is summarized by the following theorem: Theorem 4.4. There exists exactly one optimizer p ˆ ∈ PO (Γ), i.e., the set PO (Γ) consists of a single element. For all p ∈ P(Γ) we have p≥p ˆ. An interesting consequence of Theorem 4.4 is that for all scaling factors α = [α1 , . . . , αK ] > 0, we have X X αk pk ≥ αk pˆk (4.11) k

k

with equality if and only if p = p ˆ . Thus, p ˆ ∈ PO (Γ) not only solves the conventional power minimization problem (4.8), but also the modified problem min p>0

K X

αk pk

s.t. pk ≥ γk Jk (p),

1≤k≤K.

(4.12)

k=1

The following theorem, which will be required later in Section 5, characterizes the set of optimal power allocations. Theorem 4.5. The sets PO (Γ) and PE (Γ) are equal. If P(Γ) is nonempty, then PE (Γ) contains a single element, which is the unique optimizer of the power minimization problem (4.8). Proof. If there exists a p ˆ ∈ PO (Γ), then p ˆ ∈ PE (Γ). That is, the optimum (4.8) is achieved with tight constraints. Otherwise, it would be possible to further reduce the transmission power, as observed in [78]. ˜ ∈ PE (Γ) can be considered as an iniConversely, the vector p tialization of the iteration (4.10), which converges to the optimum. ˜ k = γk Jk (p ˜ ), ∀k, each iteration yields p ˜ , i.e., no improvement is Since p ˜ already is the unique optimum. achieved. That is, p

96

4.5

General SINR Balancing Theory

Relation with SINR balancing

The power minimization problem (4.8) is equivalent to a powerconstrained SINR balancing problem. The constraints SINRk ≥ γk , ∀k, can equivalently be expressed as maxk γk Jk (p)/pk ≤ 1. Thus, (5.4) can be rewritten as P (Γ) = min p>0

K X

pk

s.t.

k=1

max

1≤k≤K

γk Jk (p) ≤1, pk

(4.13)

where P (Γ) is the minimum total power required for achieving targets Γ. As shown in Theorem 4.5, the optimizer p ˆ achieves the targets Γ with equality. This means that the values SINRk (ˆ p)/γk , ∀k, are balanced at the same level. Another way of balancing the relative SINR is the following minmax problem. γk Jk (p) C(Γ, P ) = inf max p>0 1≤k≤K pk

s.t.

K X

pk ≤ P .

(4.14)

k=1

The following property is important. Lemma 4.6. The constraints in (4.14) are fulfilled with equality for the optimum. Proof. This can be shown by contradiction, similar to the proof in [78]. Suppose that the inequality is strict, then the power of the maximum user can be increased. Thereby, it can be shown that it would be possible to achieve a point below the global minimum, which is a contradiction. There is a trade-off between the achievable SINR margin and the total power. In order to specify this, consider scaling factors α > 0 and β > 0. The function C(αΓ, βP ) is monotonically increasing in α and monotonically decreasing in β. The first property is evident from the role of the targets γk in the balancing problem (4.14). The second property is stated by the lemma:

4.5. Relation with SINR balancing

97

Lemma 4.7. The function C(P ) := C(Γ, P ), as defined in (4.14), is strictly monotonically decreasing in P .

Proof. Assume power levels P1 and P2 , with P1 < P2 . Thus, there exists an α > 1 such that P2 = αP1 . Because of Lemma 4.6, the inequality constraints in (4.14) can be replaced by equality constraints. γk Jk (p) C(P1 ) = inf max s.t. kpk1 = P1 . (4.15) p>0 1≤k≤K pk Likewise, C(P2 ) can be found by optimizing over a variable q > 0, with kqk1 = P2 , instead. The optimization domain only differs by a scaling. If kpk1 = P1 , then kαpk1 = P2 , so C(P2 ) is equivalently given as γk Jk (αp) C(P2 ) = inf max s.t. kpk1 = P1 . (4.16) p>0 1≤k≤K αpk With axioms A2 and A4 we have p Jk 1/α Jk p1 Jk αp 1 = < . αpk pk pk It can be concluded that the optimum (4.16) is strictly smaller than the optimum (4.15). The lemma means that with increasing power, the achievable level mink SINRk /pk is increased. A target Γ is effectively achievable if and only if C(Γ, P ) < 1. The power minimum P (Γ) is the unique point for which C(Γ, P ) = 1. Then, Γ lies on the boundary of the SINR achievable region defined by the power constraint kpk1 ≤ P . This is illustrated in Fig. 4.1. Both problems are equivalent if Γ and P are appropriately chosen. However, they approach the problem from different points of view. The advantage of the power minimization approach (on which we focus in this section), is that it is relatively well understood and there is the fixed-point iteration (4.10), which has a couple of beneficial properties, which will be used in the following.

98

General SINR Balancing Theory

Fig. 4.1 Min-max balanced inverse SINR margin vs. total power.

On the other hand, the min-max problem (4.14) helps to understand the problem in a broader context. In particular, the power minimization problem (4.13) is only meaningful under the assumption of receiver noise and property A4 (strict monotonicity with respect to the noise component). Moreover, (4.13) can be infeasible, whereas the minmax problem (4.14) always provides an optimum C(Γ, P ) which can be regarded as an indicator of feasibility of targets Γ under a power constraint kpk1 ≤ P . There is an interesting connection to an eigenvalue optimization problem, studied in Section 5.6.1. For P → ∞, the power limited scenario considered in this section reduces to the SIR balancing problem. If either of the problems can be solved algorithmically, it is possible to find the solution of the other problem by using a bisection strategy, as observed in the context of beamforming [85]. This means that the optimal targets (or the optimal total power level) can be found iteratively, by checking for feasibility in each iteration. Depending on the result, the targets are either increased or decreased for the next step, until the optimum is achieved. A direct approach to max-min SINR balancing will be introduced in the following section.

4.6. Summary

4.6

99

Summary

In this section we have extended the generic axiomatic model A1–A3 by an additional axiom A4, which postulates that the interference function is strictly monotonic with respect to a noise power. To this end, we have introduced the extended power allocation p = [pT σ 2 ], which can be normalized such that σ 2 = 1 is the fixed noise power. This model corresponds to the concept of “standard interference functions” introduced by Yates [91], so all the properties and algorithms shown in [91] apply to the model A1–A4. Property A4 has the consequence that the SINR is invariant with respect to a scaling of the power vector p. Thus possible power constraints affect the SINR (resp. QoS) feasible region. By constraining P k pk ≤ Pmax , we obtain a region which is s strict subset of the general region considered in Section 2. The boundary of the constrained region is characterized by the min-max balancing problem subject to a power constraint. Depending on the chosen power constraint, different balanced levels can be achieved. A special balanced level is SINRk /γk = 1, ∀k, which means that all the targets γk are fulfilled with equality (provided that they are effectively achievable). This is the solution of the fixed-point equation [91], which characterizes the balanced state where the targets are achieved with minimum powers (sum power or component-wise). This fixed-point can be achieved by the iteration proposed in [91]. Any other balanced level can be achieved by iteratively varying the SINR targets γk , until the given power constraint is met with equality. A simple rule would be to decrease γk if they are infeasible, and to increase them if the power is strictly below the limit. This way, one can design an algorithm which converges to the solution of the powerconstrained min-max SINR balancing problem.

5 Matrix-Based SINR Balancing and Algorithmic Solutions

In this section, we focus again on the practically relevant case where the interference crosstalk is modeled by a K × K non-negative coupling matrix Ψ(z), which depends on a parameter z. As in Section 3, we do not make any assumption regarding the nature of z, except that z = {z1 , . . . , zK }, where zk stands for an abstract receive strategy chosen from the compact set Zk . In the following we will assume the presence of an additional noise component and a sum power constraint. In this sense, the scenario considered here is a special case of the more general analysis carried out in Section 3.

5.1

Matrix-based interference function

In the presence of noise, the users are not only coupled by interference, but also by a possible sum power constraint. Constraining the sum of all transmission powers means that increasing one users power necessarily leads to a decrease of another user’s power. This additional coupling effect depends on the noise enhancement factors N(z) = [N1 (z1 ), . . . , NK (zK )]T , which in turn depend on the choice of 101

102

Matrix-Based SINR Balancing and Algorithmic Solutions

the receive strategy z. For example, consider a linear beamforming receiver w applied to the output of an antenna array with noise power σ 2 , then the effective noise is kwk2 σ 2 , with a noise enhancement factor kwk2 . We can combine the coupling coefficients Ψ(z) and N(z) in an extended coupling matrix G(z) = Ψ(z) | N(z) .

(5.1)

The K × (K + 1) matrix G(z) determines the overall coupling between the users. In particular, G(z) p k is the interference+noise power experienced by the kth user. Without loss of generality, we can assume that the noise power is normalized such that pK+1 = 1. Thus, [N(z)]k is the effective noise power of the kth user. As in the previous Section 3, the kth row of the coupling matrix G(z) only depends on zk . Thus, for a given power allocation, the parameters zk can be adjusted independently. For each user, the optimal strategy is to choose the parameter zk which minimizes the interference. Thus, we are interested in interference functions Jk (p) = min G(z) p k , zk ∈Zk

k ∈ {1, 2, . . . , K} .

(5.2)

This receive strategy is optimal in that it achieves all points in the SINR feasible region, under the assumption of the matrix-based interference model G(z)p. A target Γ is effectively achievable if there exists a power allocation p > 0, with p = p1 , such that p ≥ ΓG(z)p. In the following section we will study feasible power allocations, which achieve the targets Γ with minimum sum-power.

5.2

Sum-power minimization

The optimal (sum-power efficient) transmission strategy is

Pmin (Γ) = min p>0 z∈Z

K X k=1

pk

s.t. pk ≥ [ΓG(z)p]k ,

1≤k≤K.

(5.3)

5.2. Sum-power minimization

103

With the definition (5.2), problem (5.3) is equivalent to the following optimization problem. Pmin (Γ) = min p>0

K X

pk

s.t. pk ≥ γk Jk (p),

1≤k≤K.

(5.4)

k=1

Note, that the optimization is only over p, whereas the optimization in (5.3) is over p and z. In (5.4), the optimal receiver design is implicitly contained in the definition of the functions Jk (p). The maximization of the individual SINR is also optimal with respect to the overall optimization goal, as defined by (5.3). This is a consequence of the separability of the receivers, i.e., the kth row of G(z) only depends on zk . It can be verified that the interference functions Jk (p) fulfill the axioms discussed in Section 4.1. Thus, all the properties shown in Section 4 also hold for the special matrix-based interference functions of the form (5.2). Also, the above power minimization problem is a special case of the more general problem formulation (4.8). An immediate consequence is the uniqueness of the optimizing power allocation. This is not obvious from the problem formulation (5.3), since the optimal receive strategy need not be unique itself. But formulation (5.4) is in accordance with the axiomatic framework, thus we know from Theorem 4.4 that (5.4) has a unique optimizer p. Thus, also the optimizer of (5.3) is unique. This is in good correspondence with the result in [11], where uniqueness was shown by a completely different approach in the context of multiuser beamforming. Solutions of (5.4) are contained in the set PO , as defined in (4.9). The following theorem characterizes solutions p ∈ PO for the matrixbased model (5.2). Theorem 5.1. p ˆ ∈ PO if and only if there exists a zˆ ∈ Z such that the following two equations are satisfied simultaneously ! K X zˆk = arg min Ψkl (zk )ˆ pk + Nk (zk ) (5.5) zk ∈Zk

l=1 −1

p ˆ = I − ΓΨ(ˆ z)

ΓN(ˆ z) .

Proof. This is a consequence of Theorem 4.5.

(5.6)

104

Matrix-Based SINR Balancing and Algorithmic Solutions

5.3

Fixed-point iteration

The fixed point iteration (4.10) converges for any interference function fulfilling A1–A4. This follows from Theorem 4.3. Thus, it can also be used for the special function (5.2). Since (5.2) includes the optimization of the parameter z, we have to adjust z in each iteration step. This modified iteration, which was already used in the context of downlink beamforming [50, 78], can be summarized as follows. (1) for given power allocation p ¯ (n) , compute h (n) i (n) zk = arg min G(z) p¯ 1 , k ∈ {1, . . . , K} .

(5.7)

(2) for given receivers z (n) , compute p ¯ (n+1) = Γ Ψ(z (n) )¯ p(n) + N(z (n) ) .

(5.8)

k

zk

Since this is a special case of the generic fixed-point iteration (4.10), this algorithm inherits all the properties described in Section 4.4. Lemma 5.2. Let p(0) ∈ P(Γ) be an arbitrary initialization, then all p ¯ (n) are effectively achievable and belong to P(Γ). Proof. Let p(0) ∈ P(Γ) be arbitrary. Since p(0) is effectively achievable, we have p ¯ (0) ≥ ΓI(p(0) ) = p ¯ (1) .

(5.9)

Suppose that p ¯ (n) is effectively achievable, i.e., p ¯ (n) ≥ ΓI(¯ p(n) ) = p ¯ (n+1) . With property A3 (monotonicity) this implies ΓI(¯ p(n+1) ) ≤ ΓI(¯ p(n) ) = p ¯ (n+1)

(5.10)

thus p ¯ (n+1) is effectively achievable as well. Starting with (5.9) we can show p ¯ (n) ∈ P(Γ) for every n.

5.4

Matrix-based iteration

One advantage of the generic fixed-point iteration (4.10) is its generality. It can be applied to any interference function satisfying the axioms

5.4. Matrix-based iteration

105

A1–A4. However, most practical interference scenarios can be modeled by the matrix-based function (5.2), in which case the fixed-point iteration has the form (5.8). If the interference Ψ(z (n) ) and the noise N(z (n) ) are known, then a “better” power update can be found. Here, better means that the allocation should perform well with respect to the power minimization goal (5.3). This will be specified in the following. Lemma 5.3. then

Let z 0 be a receive strategy such that ρ ΓΨ(z 0 ) < 1, −1 p0 = I − ΓΨ(z 0 ) Γn(z 0 ) ≤ p

(5.11)

for all p > 0 which fulfill p ≥ ΓΨ(z 0 )p + Γn(z 0 ). That is, p0 achieves the targets Γ with (component-wise) minimal power. Proof. The vector p0 is the fixed-point which fulfills p0 = ΓΨ(z 0 )p0 + Γn(z 0 ). From Theorems 4.4 and 4.5 we know that p0 is the unique solution that achieves targets Γ with minimal total power. If the set P(Γ) is non-empty, then the optimum (5.4) can be approached up to a desired accuracy by repeating the following steps until convergence (superscript n denotes the nth iteration). The initialization p(0) with total power P (0) = kp(0) k1 must be contained in P(Γ). (1) for a given power allocation p(n) , compute h (n) i (n) zk = arg min G(z) p 1 , k ∈ {1, . . . , K} .

(5.12)

(2) for a given receive strategy z (n) , compute −1 p(n+1) = I − ΓΨ(z (n) ) ΓN(z (n) ) .

(5.13)

zk ∈Zk

k

Note, that if the receive strategy z is fixed, then the algorithm converges in a single step. Then, the optimal power allocation which minimizes the total power is given simply as the solution of a system of linear equations. This is a well-known result from power control theory (see

106

Matrix-Based SINR Balancing and Algorithmic Solutions

e.g. [96]). If the receive strategies are adapted to the power allocation, then the interference coupling may change from step to step. We will now discuss properties of this iterative approach. Theorem 5.4. Let p(0) ∈ P(Γ) be an arbitrary initialization. Then, the sequence p(n) , as defined in (5.13), is component-wise monotonically decreasing p(n+1) ≤ p(n) .

(5.14)

(0)

Proof. Achievability of p(0) implies pk ≥ γk Jk (p(0) ), thus ! X (0) (0) pk ≥ γk Ψkl (z (0) ) pl + Nk (z (0) ) ∀k .

(5.15)

l

Now step (5.13) is carried out for given z (1) . With Lemma 5.3, the (1) optimizer pk fulfills (1)

(0)

p k ≤ pk ,

1≤k≤K.

(5.16)

(1)

We also have pk = [ΓG(z (0) )p(1) ]k ≥ minz∈Z [ΓG(z)p(1) ]k = γk Jk (p(1) ), thus, p(1) ∈ P(Γ). This can be used to show the result for step n = 2 and all following steps. In the next section, we will use this monotonicity result to show global convergence to the unique optimum. To this end, we will compare the proposed iteration with the fixed-point iteration.

5.5

Convergence and comparison with the fixed-point iteration

We now compare the sequence p(n) , as defined in (5.13), with the sequence p ¯ (n+1) = ΓJ (¯ p(n) ),

p ¯ (0) ∈ P(Γ) ,

(5.17)

where the vector J (¯ p) = [J1 (¯ p), . . . , JK (¯ p)]T contains the matrix-based interference functions defined in (5.2). Note, that this is a special

5.5. Convergence and comparison with the fixed-point iteration

107

case of the iteration (4.10), which is defined for arbitrary interference functions. Applying the iteration (5.17) l times to a vector p ∈ P(Γ), we obtain f (l) (p) = ΓJ . . . (ΓJ ( p)) . | {z } l times

It is known from Lemma 5.2 that the power allocation f (l) (p) is also contained in P(Γ). The following theorem shows that the proposed iteration p(n) , as defined in (5.13) is step-wise better than the fixed-point iteration (5.17). This result is illustrated in Fig. 5.1 and will also be shown by numerical simulations in Section 5.7 for the beamforming example. Theorem 5.5. Let p(0) ∈ P(Γ) be the initialization for both algorithms (5.13) and (5.17). For all n ≥ 1, we have p ¯ (n) ≥ f (n−1) (p(1) ) ≥ f (n−2) (p(2) ) ≥ · · · ≥ ΓI(p(n−1) ) ≥ p(n) . (n)

(5.18)

(n)

thus p¯k ≥ pk , ∀k. In each step, the proposed iteration p(n) is better than the fixed-point iteration p ¯ (n) (see Fig. 5.1).

Fig. 5.1 Illustration of Theorem 5.5 – Comparison between iterations (4.8) and (5.13)

108

Matrix-Based SINR Balancing and Algorithmic Solutions

Proof. For given z (0) , the vectors p(1) and p ¯ (1) are obtained from (5.13) and (5.17), respectively. We have p ¯ (n) , p(n) ∈ P(Γ) for all n, thus Lemma 5.3 implies p ¯ (1) ≥ p(1) .

(5.19)

Similarly, we can use Lemma 5.3 to show that for step n, with receive strategy z (n) , we have ΓI(p(n) ) = ΓΨ(z (n) )p(n) + Γn(z (n) ) ≥ ΓΨ(z (n) )p(n+1) + Γn(z (n) ) = p(n+1) .

(5.20)

Suppose that for some n we have p ¯ (n) ≥ f (n−1) (p(1) ) ≥ · · · ≥ f (1) (p(n−1) ) ≥ p(n) , then property A3 implies p ¯ (n+1) ≥ f (n) (p(1) ) ≥ · · · ≥ f (2) (p(n−1) ) ≥ ΓI(p(n) ) . Applying this principle to (5.19), and using (5.20) we have for n = 2: p ¯ (2) = ΓI(¯ p(1) ) ≥ ΓI(p(1) ) ≥ p(2) .

(5.21)

This can be continued for all iteration steps n.

Theorem 5.6. The sequence p(n) , as defined in (5.13), converges to the optimizer p ˆ of the power minimization problem (5.3), i.e., (n) limn→∞ pk = pˆk . Proof. From (5.18) in Theorem 5.5 we known that p ¯ (n) ≥ p(n) . That is, (n) the proposed iteration p is upper-bounded by the fixed-point iter(n) ation p ¯ . Both sequences are lower-bounded by the global optimizer ∗ p ˆ , i.e., p∗ ≤ p(n) ≤ p ¯ (n) . From Theorem 4.3 we know that p ¯ (n) converges to the optimizer p∗ . This was shown in [91] and an alternative proof is given in the Appendix A.5. Thus, we can conclude that also p(n) converges to p∗ .

5.5. Convergence and comparison with the fixed-point iteration

5.5.1

109

Sampling property

Next, consider the sequence p(n) , as defined in (5.13), with an effectively achievable initialization. It was shown that p(n) is componentwise monotonic decreasing. The total power associated with the nth step is −1 P (n) := 1T p(n) = 1T I − ΓΨ(z (n) ) ΓN(z (n) ) . (5.22) The sequence P (n) is monotonically decreasing as long as p(n) is not an optimizer of (4.8). For an arbitrary parameter z ∈ Z, with spectral radius ρ(ΓΨ(z)) < 1, the minimum total power is −1 P (z) = 1T I − ΓΨ(z) ΓN(z) . (5.23) where 1 is the all-one vector. This power level depends on the receive strategy, so the power minimization problem can also be regarded as a minimization of P (z) over the set of possible z, i.e., Pmin (Γ) = minz∈Z P (z). The sequence P (n) , as defined in (5.22), “samples” the continuous function P (z). We have limn→∞ P (n) = Pmin (Γ). That is, P (n) is strictly monotonic decreasing and converges to the global optimum Pmin (Γ). 5.5.2

Implementation aspects

A feasible initialization p(0) ∈ P(Γ) is not required for the fixed-point iteration (5.8), but for the iteration (5.13). If the starting point is infeasible, then the optimization (5.13) yields a power vector with negative entries or no solution at all. Thus, the algorithm would not converge, even if the targets Γ were feasible. However, this is no drawback. In Section 5.6.3 it will be shown how a feasible initialization (if existent) can be found by a modified version of the above algorithm. If the targets are found to be infeasible, then the iteration can be stopped. Whereas the fixed-point iteration (4.10) will diverge without any sign of abnormality in the iterates. Another advantage of the proposed iteration is that, after each power allocation step, feasible targets γk are achieved exactly. This may change, though, with the following update of the receive strategy.

110

Matrix-Based SINR Balancing and Algorithmic Solutions

But with the next power allocation step, the targets are achieved again. These power allocations are suboptimal as long as the receive strategy achieves an improvement, but whenever the algorithm is stopped, SINRk (p) = γk , ∀k, is fulfilled. This behavior is unlike the one of the fixed-point iteration (4.10), which approaches the targets γk asymptotically. It should be noted that in order to assess the actual implementation complexity, one might need to consider additional aspects, like the numerical complexity of each iteration step itself. The matrix-based iteration requires a matrix inversion, which can add to the overall complexity. But if the powers are optimized jointly with the receivers, then the main computational burden will be due to the receiver update anyway, which is the same for both iterations. Other aspects, like the suitability for decentralized implementations might be considered as well. This also depends on the specific scenario under consideration. For instance, global channel information might be required for the update of the receive strategy. In this case, both iterations can only be implemented in a centralized way.

5.6

Relationship with spectral radius optimization

In Section 4.5 it was shown for boundary points, that the power minimization problem (5.4) is equivalent to an SINR balancing problem. Next, we show that both problems are equivalent to the problem of optimizing the spectral radius of an extended coupling matrix. The results stand in interesting relationship to the results on SIR balancing in Section 3. It was shown that SIR balancing and spectral radius optimization are generally not equivalent in terms of optimizers, except if the coupling matrix is irreducible or block-irreducible. This is the reason why irreducibility was always assumed in the context of SIR balancing [29, 45]. In this section, we do not need the assumption of irreducibility. This is because of axiom A4, which ensures that the users are always coupled by the sum-power constraint. In this case, equivalence between SINR balancing and spectral radius optimization always holds, even for interference-free systems.

5.6. Relationship with spectral radius optimization

5.6.1

111

Spectral radius optimization

It was already shown in Section 4.5 that the power minimization problem (4.13) and the min-max balancing problem (4.14) are equivalent for boundary points. Thus far, we have studied the problem from a powerminimization point of view. Now, consider the min-max problem for the matrix-based model, which can be written as K X [ΓG(z)p]k C(Γ, P ) = inf max s.t. pk ≤ P . (5.24) p>0 1≤k≤K pk z∈Z k=1

If C(Γ, P ) = 1, then Γ lies on the boundary of the power constrained SINR region, and (5.24) is equivalent to the power minimization problem (5.4). We know from Theorem 4.4 that (5.24) has a unique optimizer p ˆ , Pˆ := kˆ pk1 , and a balanced optimum Cˆ := C(Γ, Pˆ ). It follows from Theorem 4.5 that Cˆ · pˆk = γk Jk (ˆ p),

1≤k≤K.

(5.25)

Assume that zˆ is an optimal receive strategy associated with p ˆ according to (5.5). With zˆ, we can rewrite (5.25) in matrix notation as h i p ˆ · Cˆ = ΓG(ˆ z ) pˆ1 . (5.26) The total power is Pˆ = 1T p ˆ . With (5.26) we have h i Cˆ = 1ˆ 1T ΓG(ˆ z ) pˆ1 . P

(5.27)

It was observed in [89] that the K + 1 equations (5.26) and (5.27) can be combined in an eigensystem h i h i ΓG(z) p ˆ p ˆ ˆ ˆ . (5.28) Φ(ˆ z, P ) · 1 = C · 1 where Φ(z, P ) = 1 T P · 1 ΓG(z) The last row of the system of equations (5.28) links the power allocation p ˆ to the total power level P , whereas the first K rows ensure SINRk (ˆ z, p ˆ ) = γk , ∀k. The power allocation pˆ1 is an eigenvector of the extended coupling matrix Φ(z, P ). But which eigenvector should be chosen? The following theorem shows that such a balanced solution, which exists for any receive strategy z, is always connected with the principal right eigenvector.

112

Matrix-Based SINR Balancing and Algorithmic Solutions

Theorem 5.7. For any z and P , the matrix Φ(z, P ) has a maxi mum eigenvalue equaling the spectral radius ρ Φ(z, P ) . The associated right-hand eigenvector is strictly positive. All other eigenvectors have at least one negative component. Proof. The matrix Φ(z, P ) is nonnegative, with Φ(z, P ) 6= 0, thus there exists a non-trivial eigenvalue that equals the spectral radius ρ Φ(z, P ) and the associated eigenvector v 6= 0 is non-negative [41]. First, we show that each v associated with the spectral radius is strictly positive. We start with the last component vK+1 . It can ˆ be observed from the last row of the system Φ(z, P )v = Cv, that vK+1 = 0 would imply ΓG(z) · v = 0, and together with the first K rows, this would lead to the trivial solution v = 0. Thus, vK+1 6= 0 and we can assume v = v˜1 without loss of generality. Thus, the ˆ can be rewritten first K equations of the system Φ(z, P )v = Cv ˆ as C˜ v = ΓΨ(z)˜ v + ΓN(z). Since ΓN(z) > 0, we can conclude that v > 0. The existence of another strictly positive eigenvector can be ruled out, since we know from Theorems. 4.4 and 4.5 that the power allocation that balances the relative SINR is unique for any interference function fulfilling the axiomatic framework. So this property as well holds for an arbitrary interference function based on a fixed matrix Ψ(z). Theorem 5.7 shows that the special structure of Φ(z, P ), together with the assumption of a strict noise component, leads to similar properties as the ones shown in Section 3 for irreducible matrices. However, Φ(z, P ) is generally not irreducible. Positivity is ensured by the noise component and the last column of G(z), which is strictly positive. With Theorem 5.7, we know that the min-max balancing optimum C(Γ, P ) is equivalently achieved by optimizing the spectral radius ρ Φ(z) over the set of possible transmit strategies Z, i.e., C(Γ, P ) = min ρ Φ(z, P ) . (5.29) z∈Z

Problem (5.29) is equivalent to (5.24). Assuming that P is chosen such that C(Γ, P ) = 1, (5.29) is also equivalent to (5.3) and (5.4).

5.6. Relationship with spectral radius optimization

113

To conclude, we have the following properties: • The SINR balancing problem (5.24) and the eigenvalue optimization problem (5.29) provide the same optimum C(Γ, P ), thus they can be equivalently used to describe the sum-power constrained SINR region • Let p ˆ be the optimal power allocation of the power minimization problem (5.4), then the associated optimal receive strategy zˆ can be found by solving the eigenvalue minimization problem (5.29) for a given sum-power P = kˆ pk1 . Equivalently, zˆ is given by (5.5). • Let zˆ be the optimizer of the eigenvalue minimization problem (5.29) for given P , then the min-max optimal power allocation p ˆ is obtained by the power minimization prob lem (5.4) for given targets Γ/ρ Φ(ˆ z , P ) . Equivalently, p ˆ is obtained by eigenvalue decomposition (5.28), as the first K components of the principal eigenvector. These “transformation laws” between the optimizers zˆ and p ˆ are based on the strict monotonicity of Jk (p) with respect to the positive noise component. It was already shown in Section 3.1.5 that this cannot be generalized to models without noise. 5.6.2

Optimality of receive strategy

The solution of the power minimization problem (5.4) was already characterized by Theorem 5.1. We now have an alternative way of characterizing the optimal receive strategy by means of the spectral radius of the extended coupling matrix Φ. Suppose that Γ is a boundary point of the region limited by the total power P , then the set of optimal receive strategies is Z(Γ) = {z : ρ Φ(z, P ) = 1} . (5.30)

Theorem 5.8. Let Γ be a boundary point, i.e., C(Γ, P ) = 1, then zˆ ∈ Z(Γ) if and only if the following statements are jointly fulfilled.

114

Matrix-Based SINR Balancing and Algorithmic Solutions

(1) there exists a p > 0 such that Φ(ˆ z, P ) · p = p (2) min Φ(z, P )p k = Φ(ˆ z , P )p k , 1 ≤ k ≤ K . zk ∈Zk

Proof. If zˆ is optimal, then there exists a power allocation p ˆ , with P = kˆ pk1 and p = pˆ1 , such that the boundary point Γ is achieved with equality, i.e., 1) is fulfilled. Also 2) must be fulfilled, otherwise it would be possible to reduce the spectral radius, thus C(Γ, P ) < 1, in which case Γ would not be a boundary point. Conversely, suppose that 1) and 2) are fulfilled. This implies that the targets Γ are achieved with equality and no improvement is possible. We have C(Γ, P ) = 1 and thus zˆ ∈ Z(Γ). Note, that a receive strategy zˆ ∈ Z(Γ) need not be unique. Different parameters may result in different coupling matrices. Nevertheless, Theorem 4.4 shows that there is only one optimal power allocation. That is, if z (1) , z (2) ∈ Z(Γ), then Φ(z (1) , P ) and Φ(z (2) , P ) have the same principal right eigenvector, scaled with respect to the last component. 5.6.3

Max-min SINR balancing algorithm

We now propose an iterative algorithm for solving the SINR balancing problem (5.24). (n)

(1) for given p(n−1) , compute zk

= arg min [Φ(z, P ) · p(n−1) ]k , zk ∈Zk

1 ≤ k ≤ K. (2) for given z (n) , compute p(n) as the principal right eigenvector of Φ(z (n) , P ), normalized such that the last component equals one. For the nth iteration step, the eigenvector p(n) is associated with an eigenvalue ρ(n) , as in (5.28). In analogy to the proof in [57], the sequence ρ(n) can be shown to be monotonically decreasing, and it converges to the global optimum of the min-max balancing problem (4.14). The achievable level can be controlled with the parameter P .

5.6. Relationship with spectral radius optimization

115

If P = Pmin (Γ), as defined in (5.3), then the above iteration solves the power minimization problem. The max-min iteration is important since the spectral radius ρ Φ(z (n) , P ) is an indicator for feasibility under a total power maxi mum P . If ρ Φ(z (n) , P ) ≤ 1, then we know that −1 p(n) = I − ΓΨ(z (n) ) ΓN(z (n) )

(5.31)

is strictly positive and fulfills the sum-power constraint. Thus, we can replace the eigenvalue computation by (5.31), which means that the algorithm will converge towards the power minimum (5.3). Otherwise it will converge towards the max-min optimum (5.24). It is also possible to start the algorithm with the min-max iteration. If feasibility is ensured, i.e., if ρ Φ(z (n) , P ) ≤ 1, then the power allocation policy is replaced by (5.31), and the iteration converges towards the total power minimum. If Γ is a boundary point, then the algorithm will converge towards a solution limn→∞ ρ Φ(z (n) , P ) = 1. In this case, both strategies are equivalent.

5.6.4

Duality

In Section 5 we made the assumption that the kth row of Ψ(z) only depends on zk . This was necessary in order to ensure that the receivers can be optimized independently. The optimization framework can be extended to the case when the kth column of Ψ(z) depends on zk . Then, we exploit that this channel achieves the same spectral radius ρ φ(Γ, P ) as the “transpose channel” Ψ(z)T . That is, the same SINR targets can be achieved by the same total power. Thus, by performing the optimization with respect to Ψ(z)T , we can restore the desired property of separable receive strategies. The proposed iterations yield an optimizer z, which is optimal with respect to the original channel Ψ(z). It remains to adjust the powers according to the “true” channel Ψ(z). This “duality”, was first observed in [95] and later used in [50, 78], where a “virtual uplink channel” was used to solve a downlink beamforming problem. It was formalized and further developed in [57, 80].

116

Matrix-Based SINR Balancing and Algorithmic Solutions

These results can be extended to the parameter-dependent model Ψ(z) used in this section.

5.7

Application example: Beamforming

The beamforming example, which was already discussed in Section 1.2, is a special case of the matrix-based model. By combining the outputs of an M -element antenna array by a filtering matrix U = [u1 , . . . , uK ] ∈ CM ×K , we have an interference function Jk (p) =

min

uH k

uk :kuk k=1

P

l6=k pl Rl + uH k Rk uk

σ 2 I uk

,

(5.32)

where R1 , . . . , RK ∈ CM ×M are Hermitian and positive semidefinite spatial covariance matrices. The interference function (5.32) fulfills the axioms A1–A4, thus all the properties shown in Section 4 also apply to this special case. For details, see [50, 78, 6, 57]. It was mentioned in Section 5.1 that the optimum receive strategy need not be unique. For the beamforming example, this can be seen when rewriting the optimality condition pk = γk Jk (p), ∀k, as u = 0, where u ˆ k is the optimizer for given p and Bk (p) := u ˆH k Bk (p)ˆ P k 1 σ2I + K p R − p R p) is positive semidefinite, the l6=k l l γk k k . Since Bk (ˆ optimal u ˆ k lies in the nullspace of Bk (ˆ p). Moreover, every vector from the nullspace fulfills the optimality condition. Thus, the power allocation problem can be seen as the search for zeros of the polynomials det(Bk (p)) = 0, ∀k. For more details, see [11].

5.7.1

Numerical simulations

In Fig. 5.2 and Fig. 5.3, the convergence of the new algorithm is compared with the fixed-point iteration for the beamforming model (5.32). We use a randomly chosen exemplary channel " H=

−0.51−0.61i 0.42−1.34i 0.29+0.29i 0.77−0.58i −1.65+0.31i 0.23+0.69i 1.19+0.48i 0.83−0.14i 1.31−0.90i −0.99−2.03i −0.60+0.02i 0.77−1.63i −0.01−1.13i 1.23+0.25i 0.69+0.53i 0.02+1.06i −2.64−1.44i 0.86−0.29i 0.96−1.49i −0.97+0.34i

#

5.7. Application example: Beamforming

117

Fig. 5.2 Convergence behavior of the proposed algorithm compared by the fixed point iteration [91]. Each curve is associated with the power of one user. They converge to the optimal allocation which fulfill SINR targets with minimum power.

for K = 5 users and M = 4 antennas. The noise is σ 2 = 0.01 and the iteration is stopped when a relative error of 1E − 6 is achieved. The targets Γ are chosen such that the minimum spectral radius varies between 0 and 1 (near-infeasible system). The first simulation in Fig. 5.2 illustrates the convergence of the individual transmission powers to the optimal level, for a minimum spectral radius 0.53. Starting with a joint feasible initialization, both algorithms converge to the optimal power allocation. The dependency of the convergence speed on the spectral radius is depicted in Fig. 5.3. It can be observed that the convergence behavior of the fixed-point iteration depends strongly on the spectral radius. For the near-infeasible scenario, the number of required iterations is very large. For the proposed iteration, the number of iterations is relatively constant. The small variations are due to the chosen initialization. 5.7.2

Beamforming-related interference functions

The interference function (5.32) is one example for a practical interference function which fit into the proposed framework. In the following we provide more examples.

118

Matrix-Based SINR Balancing and Algorithmic Solutions

Fig. 5.3 Required number of iterations vs. spectral radius (system load). The small differences in the iterations of the proposed algorithm are due to the chosen initialization (found by the SIR balancing algorithm described in Section 3.5.3), which favors the fully-loaded scenario.

Example 5.9. (MMSE beamforming) If the performance measure is linear MMSE instead of SINR, then we can use the relation M M SEk = 1/(1 + SIN Rk ). That is, MMSE targets 1 , . . . , K translate to SINR targets γk = 1/k − 1. The vector-valued MMSE estimator of the kth user can be written as uk βk , where uk is the unity-norm beamformer, which maximizes the SINR, and βk is a scalar MMSE estimator. This way, the receivers uk can be optimized jointly with the power allocation p, using the proposed framework. For example, the algorithm in Section 5.4 provides powers and receivers which are optimal with respect to the given MMSE targets k (see e.g. [62, 59]).

Example 5.10. (zeroforcing beamforming) Assume that h1 , . . . , hK are the vector channels associated with the K links. The kth user transmits over an effective channel uH k hk . Since the SINR is invariant with respect to a scaling of uk , we can set uH k hk = 1. Then, the

5.7. Application example: Beamforming

interference function becomes   X 2 2 . Jk (p) = min  pl |uH k hl | + σ kuk k2 uk :uH k hk =1

119

(5.33)

l6=k

If Rk = hk hH k , then the optimal beamformer of (5.32) and the optimal beamformer of (5.33) are identical up to a scaling. For a given p, the optimizer uk maximizes the SINR. Another common design criterion is zeroforcing [76]. While the maximum SINR beamformer can be chosen from the closed and bounded set of vectors satisfying uH k hk = 1, the zeroforcing receiver is further constrained to satisfy uH h k l = 0, l 6= k. Assuming that K is not too large, it can be observed from (5.33) that this leads to a complete elimination of the interference, and only the effective noise term remains. The interference function (5.33) can be rewritten as Jk (p) =

min

H uk :uH k hk =1,uk hl =0,l6=k

σ 2 kuk k2 .

(5.34)

That is, among the closed and bounded set of beamformers fulfilling the constraints, we are looking for the unique solution which minimizes the effective noise being proportional to kuk k2 . Based on the knowledge of H = [h1 , . . . , hK ], these beamformers can be computed independently of one another. The kth optimal beamformer is given as the kth row of the pseudo-inverse H† . This solution can be shown to be optimal with respect to the optimization (5.34). It can be observed that (5.34) fulfills the axioms A1–A4, so it is a valid interference function, for which all the shown results hold. Since the optimal receiver does not depend on the power allocation, the algorithm in Section 5.4 only requires a single step. By constraining the set of possible receive strategies to a subset, we obtain a result which is generally suboptimal with respect to the achievable SINR (or related criteria like MMSE, BER, or capacity). However, there are other criteria, like robustness or diversity, which motivate such a restriction (see e.g. [52]).

120

Matrix-Based SINR Balancing and Algorithmic Solutions

Example 5.11. (interference cancellation) Known interference can be subtracted from the received compound signal. Assuming a fixed decoding order 1, 2, . . . , K, and neglecting error propagation, this results in a modified interference function ! K X H 2 2 Jk (p) = min pl |uk hl | + σ kuk k2 . uk :uH k hk =1

l=k+1

The kth user is only interfered by users k + 1, . . . , K. This interference function also fulfills the axioms A1–A4, and the optimal receivers uk can be computed independently. Thus, the algorithm in Section 5.4 can be used to minimize the total power required to achieve SINR targets γ1 , . . . , γK . This problem was studied in [58], where it was shown that although the powers and beamformers are mutually interdependent, an iteration is not required. The optimal power allocation can be computed directly, by exploiting the special triangular interference structure of the effective channel [58]. A good decoding order can be derived from the channel state information [86, 24]. However, the choice of the decoding order has impact on all interference functions and thus on the power allocation. Finding a decoding order which is optimal with respect to the sum power minimization problem (5.3) would require a joint optimization with the power allocation. No efficient techniques are known for this problem. Example 5.12. (base station assignment) The parameter z need not be continuous. By optimizing over a discrete set, problems related to channel assignment or scheduling can be solved. As an example, consider the base station assignment problem studied, e.g. in [90, 50, 32, 5]. The basic idea is to choose from a set of possible receivers (base stations) the one with the best link quality. Consider an uplink system with receiving base stations from a set A. For the kth user, the system can choose an assignment ak ∈ Ak . Since the choice of the receiving base station does not influence the interference of other users, we have X (a ) Jk (p) = min pl hl k + σ 2 , (5.35) ak ∈Ak

l6=k

5.8. Summary

121

(a )

where hl k is the channel between the lth transmitting mobile and the base station ak . It can be verified that the axioms A1–A4 hold for the special interference function (5.35). All the results derived in this text apply. A jointly optimal assignment and power allocation can be computed with the iterative algorithm proposed in Section 5.4. The interference function (5.32) can be further extended, e.g. by beamforming. ! P (ak ) uH + σ 2 I uk l6=k pl Rl k Jk (p) = min min . (ak ) ak ∈Ak uk :kuk k=1 uH k Rk uk Also this interference function fulfills axioms A1–A4. It incorporates beamforming and base station assignment, as proposed in [90, 50, 32, 5]. With the algorithm proposed in Section 5.4, we can jointly optimize powers, assignment, and beamforming.

5.8

Summary

This section further extends the previous models by introducing matrixbased interference functions, which include a strictly positive noise component. This model fulfills the properties A1–A4, thus all the results shown in Section 4 apply. In particular, the fixed-point iteration can be reformulated as an alternating optimization of powers and receive strategies z. Such alternating algorithms are already known in the context of multiuser beamforming [50, 78]. The generalized model considered here can by applied to any receive strategy which fulfills the basic assumptions discussed in Section 3.1.1. Thus, the results are potentially useful to a wide range of practical problems, including multiuser interference filtering, adaptive channel assignment and others. While the matrix-based fixed-point iteration is a direct consequence of the axiomatic approach, more dedicated algorithms can be derived by exploiting the special special matrix structure, as shown in Section 5.4. As the fixed-point iteration, the proposed iteration also converges to the global optimum of the power minimization problem. But both iteration differ in their convergence behavior. The convergence analysis in Section 5.5 reveals that the dedicated algorithm is upper-bounded

122

Matrix-Based SINR Balancing and Algorithmic Solutions

by the fixed-point iteration, so it performs better in each step. The convergence proof mainly relies on the properties A1–A4, no convexity properties are required. In Section 5.6 an iteration for power-constrained min-max balancing is proposed. As shown in the previous section, the min-max balancing problem is closely connected to the power minimization problem. The only difference is the way the powers are updated. The min-max power allocation is computed as the principal scaled eigenvector of a generalized coupling matrix. Finally, we discuss the role of the transpose channel in finding on optimum transmit strategy. Unlike the receive strategy, the transmit strategy couples the rows of the coupling matrix Ψ, but the columns can be optimized separately. This allows to find a jointly optimum transmit strategy indirectly, by optimizing the transpose channel. In this way, the proposed model can be applied to transmitter optimization. In the literature this is referred to as “duality”. However, this optimization framework cannot be applied directly to the joint optimization of transmitters and receivers, where the rows are coupled by the transmit strategy and the columns are coupled by the receive strategy.

6 Geometrical Properties for Log-Convex Interference Functions

In this section we provide conditions under which the QoS region Q introduced in Section 1.1.2 is a convex set. Convexity is a desirable property, which facilitates efficient optimization over the boundary of the region. This allows for the development of efficient algorithms for utility-based resource allocation (see e.g. [67, 83, 66, 65]). The actual structure of the QoS region depends very much on the functions φ and Ik . The QoS can be modeled as a function of the SINR, as discussed in Section 1.1.2, where a one-to-one mapping QoSk = φ(SINRk ) was assumed, with the inverse mapping SINRk = γ(QoSk ). A special class of mappings γ(x) are log-convex mappings (for a definition see the Appendix A.1). It was shown in [19, 16, 17, 68] that for a log-convex inverse mapping γ(x), and a matrix-based interference function Ik (p) = Ψp, with Ψ ≥ 0, the resulting min-max optimum C(Γ) is log-convex, and hence the QoS region is convex. An example for a log-convex QoS mapping is γ(x) = exp(x), which is associated with QoSk = log(SIRk ). This means that the log-SIR region is convex. Practical examples for log-convex mapping are: • Capacity C(SINRk ) in the high SNR regime, i.e. C(SINRk ) ≈ log(SINRk ). The inverse function γ(x) = exp(x) is log-convex on R. 123

124

Geometrical Properties for Log-Convex Interference Functions

• Delay (average customer time) D(SINR) for an M/M/1 queuing system in the low-SNR regime. Given an arrival rate λ and a service rate ν, the delay is D(SINR) = 1/(ν − λ) [8]. For low SNR, we can approximate ν = log(1 + SINRk ) ≈ SINRk , so D(SINR) ≈ 1/SINR for small λ. The inverse function γ(x) = 1/x is log-convex on R++ . In the remainder of this section, we will restrict the discussion to QoS functions with a log-convex inverse mapping γ(x). The convexity of the QoS region is not limited to the linear function Ik (p) = Ψp. It was shown in [15] that every log-convex interference function Jk (es ), characterized by A1–A3, leads to a convex QoS region. Here we have substituted p := es for the power vector. This means that the convexity result applies to a wide range of log-convex interference functions, including the adaptive worst-case design, which will be studied later in Section 6.2. We start by reviewing the basic linear design in the following section.

6.1

Log-convexity of linear interference functions

An interference function is linear if it can be written in the form Ψp + C, where C is a constant, which usually models noise, and Ψ ≥ 0 is the coupling coefficient matrix. This model holds for a wide range of practically relevant system models, like the zeroforcing or matched filter receiver discussed in Section 5.7, where the coupling matrix is fixed. For this class of interference functions, log-convexity with respect to the transformed power allocation s can be shown (the substitution p = exp{s} is assumed). Theorem 6.1. All linear interference functions of the form Jk (exp{s}) =

K X l=1

are log-convex.

Ψkl pl + C,

Ψkl ≥ 0, C ≥ 0

(6.1)

125

6.1. Log-convexity of linear interference functions

Proof. Defining the extended coupling matrix G = Ψ | 1 , the function (6.1) can be rewritten as Jk (exp{s}) =

K+1 X

∀k,

Gkl pl ,

(6.2)

l=1

where p = Cp is the extended power allocation, which includes the noise power C. Now, consider two arbitrary power allocations p(1) = exp{s(1) } and p(2) = exp{s(2) }, and s(λ) = λs(1) + (1 − λ)s(2) , then Jk exp{s(λ)} =

K+1 X

(1)

(2)

Ψkl · (pl )λ · (pl )1−λ

l=1

=

K+1 X

(1)

(2)

(Ψkl )1/m (pl )λ · (Ψkl )1/n (pl )1−λ

with

1 n

+

1 m

=1

l=1 (a)

≤

K+1 X

!1/m (1) Ψkl (pl )λm

·

l=1 (b)

=

K+1 X l=1

K+1 X

!1/n (2) Ψkl (pl )(1−λ)n

l=1

!λ (1) Ψkl (pl )

·

K+1 X

!1−λ (2) Ψkl (pl )

(6.3)

l=1

where (a) follows from H¨older’s inequality (Theorem A.3 in the appendix), and (b) follows from choosing m = 1/λ and n = 1/(1 − λ). It is shown in the Appendix A.1 that (6.3) implies that Jk exp{s(λ)} is log-convex. An even stronger result can be shown if the off-diagonal entries of Ψ are strictly positive. Theorem 6.2. Let K ≥ 3, and Ψkl > 0, k 6= l. For the kth user, the interference function (6.1) is strictly log-convex for all p(1) , p(2) > 0 (1) (2) with pl 6= δpl , l 6= k, δ > 0.

126

Geometrical Properties for Log-Convex Interference Functions

Fig. 6.1 Schematic illustration of the proof of Theorem 6.2. – Strict inequality of (6.3) only needs to be shown for λ = 1/2. This implies that all other points are strictly below the interconnecting line. This is because (6.3) shows that all points are less or equal the dashed connections.

Proof. Consider two arbitrary power allocations p(1) = exp{s(1) } and (1) (2) p(2) = exp{s(2) }, with pl 6= δpl , l 6= k. Defining s(λ) = λs(1) + (1 − λ)s(2) , it can be reasoned (see Fig. 6.1) that Jk (p), as defined in (6.2), is strictly log-convex if and only if 1 1 2 2 (1) (2) 1 Jk exp{s( 2 )} < Jk (p ) Jk (p ) . (6.4) Rewriting (6.4) in matrix form, it can be observed that this is the Cauchy-Schwarz inequality. Because of the assumption Ψkl > 0, k 6= l, (1) we can conclude that (6.4) is fulfilled with equality if and only if pl = (2) δpl , l 6= k, which contradicts the assumption, thus implying strict logconvexity.

Remark 6.3. This result does not hold for K = 2, in which case J1 (exp{s2 }) = Ψ12 exp{s2 }. Thus the function is only log-convex (not strictly).

6.2

Worst-case interference functions

Having shown log-convexity for the linear model (6.1), we now consider the more general class of interference functions Jk (p) = max fk (p, c) ,

(6.5)

fk (p, c) = [Ψ(c)p + N(c)]k

(6.6)

c∈C

where the interference

6.3. Convexity of the QoS feasible region

127

depends on a parameter c, chosen from a compact set C. If the parameter c stands for interference uncertainties, then the function (6.6) can be regarded as the worst-case interference. By optimizing with respect to these worst-case interference functions, a certain degree of robustness is obtained (see e.g. the related concepts in [23, 81]). In this respect, it differs from the concept of the receive strategy z, which aims at minimizing the interference. Theorem 6.4. The worst-case interference functions Jk (es ), as defined in (6.5), are log-convex on RK + , i.e., log Jk (p(λ)) ≤ λ log Jk (p(1) ) + (1 − λ) log Jk (p(2) ) .

(6.7)

Proof. As in the proof of Theorem 6.1 we can incorporate the noise component in an extended coupling matrix, thus the result only needs to be shown for the function fk (p, c) = [Ψ(c)p]k . We define (1) (2) (1) (2) pk (λ) = exp{λsk + (1 − λ)sk } = (pk )λ · (pk )1−λ . Theorem 6.2 (log-convexity) implies log[Ψ(c)p(λ)]k ≤ λ log[Ψ(c)p(1) ]k + (1 − λ) log[Ψ(c)p(2) ]k . This inequality still holds when taking the maximum over c on both sides, i.e., max log fk (p(λ), c) ≤ λ max log fk (p(1) , c) + (1 − λ) max log fk (p(2) , c) . c∈C

c∈C

c∈C

Since the max and log operations are interchangeable, we obtain (6.7).

This log-convexity property will be exploited in the following section. It will be shown that under certain conditions the resulting QoS region is a convex set.

6.3

Convexity of the QoS feasible region

The QoS was defined in (1.2) as a monotonic function QoSk (p) = φ SIRk (p) . In this section we will focus on a special class of mappings

128

Geometrical Properties for Log-Convex Interference Functions

with a log-convex inverse function γ = φ[−1] . Examples have already been discussed at the beginning of this section. The QoS region Q discussed in Section 1.1.2 was defined for unconstrained powers p ∈ RK . Now, consider the region Q(Pmax ), which is the set of all QoS which can be jointly achieved under a sum power constraint kpk1 ≤ Pmax . Clearly, by constraining the power set, we constrain the region, so Q(Pmax ) ⊆ Q. The sum-power constrained region Q(Pmax ) can be defined with the function popt (Q), which is the optimizer of the power minimization problem (5.3), with target SINR’s γ(Qk ), 1 ≤ k ≤ K. The QoS region under a total power constraint is defined as Q(Pmax ) = {Q : kpopt (Q)k1 ≤ Pmax } .

(6.8)

The allocation popt (Q) achieves the targets Q not only with minimum total power, but also with individually minimum powers, as shown in [91] (see also Section 4). Thus, we can use the function popt (Q) to define the QoS region under individual power constraints pmax = [pmax , . . . , pmax 1 K ]: Q(pmax ) = {Q : popt (Q) ≤ pmax } .

(6.9)

We will now show that both regions are convex for the scenario under consideration. That is, Jk (es ) is log-convex and the inverse QoS mapping γ(x) is log-convex as well. We start by considering the min-max optimum γ(Qk )Jk (p) Cγ (Q) = inf max . (6.10) p>0 1≤k≤K pk Theorem 6.5. For log-convex interference functions and log-convex mappings γ, the min-max optimum Cγ (Q), as defined in (6.10), is logconvex with respect to Q. Proof. Let Q(λ) = (1 − λ)Q(1) + λQ(2) , λ ∈ [0, 1], where Q(1) , Q(2) ∈ (l) (l) Q. Also, γ(λ) := γ(Qk (λ)) and γk = γ(Qk ), l = 1, 2. There exists an

6.3. Convexity of the QoS feasible region (1)

129

(2)

> 0 and vectors p , and p , such that (l)

max log

(l)

γk Jk (p )

1≤k≤K

(l)

[p ]k (l)

≤ log Cγ Q(l) + ,

(l)

l = 1, 2 . (1)

(6.11) (2)

Substituting s = log p , we define s(λ) = (1 − λ)s + λs p(λ) = es(λ) . It can be shown that ! Jk es(λ) log γk (λ) s(λ) [e ]k

and

≤ (1 − λ) log Cγ Q(1) + λ log Cγ Q(2) + for all k ∈ {1, 2, . . . , K}. Here we have used (6.11) and the assumption that log γ(Qk ) is convex with respect to Qk and Jk es /[es ]k is logconvex with respect to s. It follows that ! γk (λ)Jk es(λ) log Cγ Q(λ) = inf max 1≤k≤K es(λ) k s∈RK + ≤ (1 − λ) log Cγ (Q(1) ) + λ log Cγ (Q(2) ) + .

(6.12)

This holds for any > 0 and the left-hand side of (6.12) does not depend on . Thus Cγ (Q) is log-convex. Moreover, it can be shown that (1) If γ(Q) is strictly log-convex, then Cγ (Q) is strictly logconvex. (2) If the functions Jk (p(λ)), with p(λ) = es(λ) , s(λ) = (1 − λ)s(0) + λs(1) , s(0) 6= s(1) , are strictly log-convex, then Cγ (Q) is strictly log-convex. The log-convexity of the function Cγ (Q) will be used later to show convexity of the resulting QoS region. But first, we show that the functions popt (Q) are also log-convex with respect to Q. Theorem 6.6. Let popt (Q) be the optimizer of the power minimization problem (5.3) with target SINR’s γ(Qk ), 1 ≤ k ≤ K, where γ(Qk )

130

Geometrical Properties for Log-Convex Interference Functions

is log-convex, then the functions popt k (Q), 1 ≤ k ≤ K, are log-convex with respect to Q. Proof. Let Q(0) and Q(1) be feasible points. From Theorem 6.5 it is clear that 1 ≥ Cγ Q(λ) , thus, all Q(λ) are feasible and achieved by optimal power allocations p(λ) := popt (Q(λ)) characterized by pk (λ) = γk (λ)Jk p(λ) , 1 ≤ k ≤ K. Let γk (λ) := γ Qk (λ) . Exploiting the log-convexity of γ and Jk (p) we have pk (λ) = γk (λ)Jk p(λ) (1−λ) λ (1−λ) λ ≤ γk (0) γk (1) Jk p(0) Jk p(1) (1−λ) λ γk (1)Jk p(1) = γk (0)Jk p(0) (1−λ) λ = pk (0) pk (1) , and thus log pk (λ) ≤ (1 − λ) log pk (0) + λ log pk (1). A similar result can be shown for the sum-power minimum. Theorem 6.7. The minimum total power Pmin (Q), as defined in (5.3), is log-convex with respect to Q. Proof. Let Q(0) and Q(1) be feasible points and let Q(λ) and the associated optimizers p(λ) be defined as before. Consider vectors p0 (λ) which fulfill log p0k (λ) = (1 − λ) log pk (0) + λ log pk (1). We have P Pmin Q(λ) = k pk (λ), thus X X 0 (1−λ) λ Pmin Q(λ) ≤ pk (λ) = pk (0) pk (1) k

k

!(1−λ) ≤

X k

pk (0)

!λ X

pk (1)

,

k

where the last step follows from the H¨older inequality. Thus, log Pmin Q(λ) ≤ (1 − λ) log Pmin (Q(0) ) + λ log Pmin (Q(1) ) .

6.3. Convexity of the QoS feasible region

131

In [17] it was shown that for functions γ(Q) = eQ and γ(Q) = 1/Q, the inequality is strict. With the above results, we are now in the position to prove the convexity of the QoS region. Theorem 6.8. The feasibility region Q(pmax ), as defined in (6.9), and the region Q(Pmax ), as defined in (6.8), are both convex for logconvex interference functions and log-convex mappings φ. Proof. We need to show that if Q(1) and Q(2) are boundary points of the QoS feasibility region, then all points on the interconnecting line Q(λ) = (1 − λ)Q(1) + λQ(2) lie in the interior of the region. To this end, assume that the boundary points have a total power Pmax , thus log-convexity of Pmin (Q) implies 1−λ λ Pmin Q(λ) ≤ Pmin (Q(1) ) · Pmin (Q(2) ) = (Pmax )1−λ · (Pmax )λ = Pmax .

(6.13)

Thus, any point on the interconnecting line can be achieved with power Pmin Q(λ) ≤ Pmax , which means that it belongs to the feasible region limited by Pmax . This is illustrated in Fig. 6.2. The convexity of the region with individual constraints can be shown in analogy.

Fig. 6.2 The QoS region is convex for log-convex mappings SIN Rk = φ(QoSk ) and logconvex interference functions. Thus, points on the interconnection between two arbitrary boundary points belong to the region.

132

Geometrical Properties for Log-Convex Interference Functions

6.4

Resource allocation by weighted QoS optimization

In this section we consider another class of QoS functions. We assume that the SINR is related to the QoS by a function φ(x) = g(1/x), thus QoS = g(1/SINR) . The function g is assumed to be monotonically increasing and g(ex ) is convex with respect to x. Examples for such functions are g(x) = x or g(x) = log x. Thus, the QoS is proportional to the inverse SINR. This can be interpreted, e.g. as a first-order approximation for the BER. We are interested in the solution of the following optimization problem: min

s∈RK

K X

αk g Jk (es )/esk

s.t. kes k1 ≤ Pmax ,

(6.14)

k=1

where Jk (es ) is a log-convex interference function. The minimization of an aggregate cost function is a common problem in network resource allocation. In (6.14) the weights α = [α1 , . . . , αK ] can model individual user requirements and possibly depend on system parameters like priorities, queue lengths, etc. By appropriately choosing α it is possible to trade off throughput against fairness (illustrated in Fig. 6.3). The problem (6.14) can be shown to be convex [18].

Fig. 6.3 The resource allocation problem: weighted minimization over the boundary of the QoS achievable region

6.5. Summary

133

Theorem 6.9. The problem (6.14) is convex if and only if g(ex ) is convex with respect to x. Note, that the optimization is over the non-compact set RK , thus even if the problem is convex, it is not obvious that the optimum is achieved (e.g. s → −∞ might be necessary to achieve a valid QoS point). However, this case is excluded by axiom A4 and the fact that σn2 > 0. For a practical system with receiver noise σn2 > 0, we always have strictly positive interference J (p) > 0. Thus, esk → 0 can be ruled out, since otherwise the objective would tend to infinity, away from the minimum. A problem formulation of the form (6.14) is desirable for systems, where all users are active at the same time. Then, (6.14) could be used to control certain performance aspects, like bit error rates. For any choice of parameters α, the optimization problem (6.14) can be solved by standard convex optimization techniques. The optimization of weighted sum QoS functionals is an important problem in resource allocation. Note, that the optimum always lies on the boundary of the region, as illustrated in Fig. 6.3. Sometimes, it is possible to achieve the optimum with the SIR balancing strategy studied in this text. It was shown in [12] for a special case, how to adjust the weights αk such that both problems are equivalent. Another example has been provided in this section, where we have studied logconvex interference functions, like the nonlinear worst-case function (6.5). For this case, the QoS region has been shown to be convex, thus standard optimization strategies can be applied in order to find the unique optimum. An extension of more general cases is desirable and will be the subject of future work.

6.5

Summary

In this section we have studied the class of log-convex interference functions. The first result shows that all linear interference functions of the form (6.1) are log-convex. This model holds for many practical designs, e.g. single-user receive strategies, for which the parameter zk does not depend on the power allocation.

134

Geometrical Properties for Log-Convex Interference Functions

Log-convexity has some interesting consequences. For log-convex mappings SIRk = γ(QoSk ), it is shown in Section 6.3 that the resulting QoS feasible region is convex. This is a useful property which can be exploited for the development of efficient algorithmic solutions, like the projection algorithm proposed in [67]. So for some performance criteria, like the capacity in the high SNR regime, or the delay approximation discussed at the beginning, the feasible region is a convex set. Log-convexity also holds for worst-case interference functions of the form (6.5). This result is useful, e.g. for the development of robust power allocation algorithms. However, log-convexity does not hold for adaptive receive strategies z, as discussed in Section 3.1.2. Even though a specific choice of z leads to a log-convex form (6.1), thus implying a convex region, the union over all possible strategies z ∈ Z (see the illustration in Fig. 3.1) need not be convex.

Acknowledgements

This work was supported in part by the Bundesministerium f¨ ur Bildung und Forschung (BMBF) under grants 01BU150 (Hyeff) and 01BU350 (3GET). The authors also acknowledge support from Alcatel SEL Forschungszentrum in Stuttgart, and Siemens ICM in M¨ unchen, as well as valuable suggestions and comments from reviewers and colleagues.

“Wir, so gut es gelang, haben das Unsre (vorerst)1 getan.” Friedrich H¨ olderlin, “Der Gang aufs Land”, 1800.

1 After

the text was finished, new results were found. They will be incorporated in a new book project [55].

135

Appendix

A.1

Some definitions and results

Definition A.1. (log-convex function) Let D be a convex nonempty set. A function f : D 7→ R++ is called log-convex if log f is convex, i.e., log f ((1 − µ)ˆ x + µˇ x) ≤ (1 − µ) log f (ˆ x) + µ log(f (ˇ x))

(A.15)

for all µ ∈ (0, 1) and x ˇ, x ˆ ∈ D. If (A.15) is fulfilled with strict inequality, then we say that f (x) is strictly log-convex. The following lemma is an immediate consequence of property (A.15). Lemma A.2. A positive function f : D 7→ R++ is log-convex on D if and only if f (x(µ)) ≤ f (ˆ x)1−µ f (ˇ x)µ for all µ ∈ (0, 1) and x ˇ, x ˆ ∈ D. 137

138

Appendix

Log-convex functions can be shown to have the following properties: • the product of log-convex functions is log-convex • the sum of log-convex functions is log-convex Note, that the same properties need not hold for log-concave functions. Also, log-convexity is stronger than convexity since each log-convex function is convex, but the converse statement is not true. Theorem A.3. p, q > 1, then

(H¨ older’s inequality) Let 1/p + 1/q = 1, with !1/p

X k

A.2

p

|xk |

!1/q X k

q

|yk |

≥

X

|xk yk | .

k

Proof of Theorem 2.9

From Theorem 2.7 we know that there always exists a p ≥ 0 such that (2.26) is fulfilled. If there exists a k0 such that pk0 = 0, then it follows from Theorem 2.8 that the vector p has at least two zero entries. For K = 2, we know that I1 (p) and I2 (p) are reduced to (2.13) and (2.14), respectively. Thus, there exists exactly one vector p ≥ 0 such that C(Γ)pk = γk Ik (p), k = 1, 2, and this vector is strictly positive, i.e., p > 0. For K = 3, each vector p satisfying C(Γ)pk = γk Ik (p), ∀k, is strictly positive, i.e., p > 0. The reason is Theorem 2.8, which shows that only exactly two components can be zero (excluding the trivial all-zero vector). Without loss of generality, assume p = [0, 0, p3 ], p3 > 0. Because of the assumption of no self-interference, we have C(Γ)p3 = γ3 I3 (p) = γ3 I3 ([0, 0, p3 ]) = 0 , which leads to the contradiction p3 = 0. Thus, all components are strictly positive. It remains to show uniqueness. The proof is by contradiction. Suppose that there exist p(1) , p(2) > 0. Without loss of generality, we can (1) (2) (1) (2) (1) (2) assume that p(1) ≤ p(2) and p1 = p1 . If p2 < p2 and p3 < p3 ,

A.3. Proof of Theorem 2.22 (1)

(2)

then there exists a λ > 1 such that λp2 < p2 thus (1)

(1)

139

(2)

and λp3 < p3 , and

(1)

I1 (λp(1) ) = λI1 (p2 , p3 ) ≤ I1 (p(2) ) . We can conclude that I1 (p(1) ) < I1 (p(2) ) and thus C(Γ) =

γ1 I1 (p(1) ) (1)

=

γ1 I1 (p(1) ) (2)

p1

<

p1

γ1 I1 (p(2) ) (2)

= C(Γ)

p1

which contradicts the existence of two different components. It remains to contradict the existence of one different component. (1) (2) Without loss of generality, assume that p3 < p3 , while the first two components are equal. This implies I3 (p(1) ) = I3 (p(2) ) and thus C(Γ) =

γ3 I3 (p(1) ) (1)

=

γ3 I3 (p(2) ) (1)

p3

p3

>

γ3 I3 (p(2) ) (2)

= C(Γ)

p3

which is a contradiction and shows that p(1) = p(2) for all components.

A.3

Proof of Theorem 2.22

Because of the definition (2.2), there exists a p ¯ () > 0, for every > 0, such that γk Ik (¯ p() ) ()

≤ C(Γ) + ,

∀k ∈ {1, 2, . . . , K} .

(A.16)

p ¯k

Definition (2.42) implies the existence of a p() > 0, for every > 0, such that γk Ik (p() ) ()

≥ c(Γ) − ,

∀k ∈ {1, 2, . . . , K} .

(A.17)

pk

Since SIRk (p) is invariant to a scaling of p, we can assume ()

, p¯k ≥ p() k

∀k ∈ {1, 2, . . . , K} ,

(A.18)

140

Appendix ()

()

and there exists an index k0 such that p¯k0 = pk0 . Thus, γk Ik (¯ p() )

C(Γ) + ≥ max

()

1≤k≤K

≥

p ¯k

γk0 Ik0 (¯ p() ) ()

=

γk0 Ik0 (¯ p() ) ()

p ¯ k0

.

pk0

From (A.18) and A3 we know that Ik (¯ p() ) ≥ Ik (p() ), ∀k, and thus C(Γ) + ≥

γk0 Ik0 (p() ) ()

≥ min

γk Ik (p() )

1≤k≤K

pk0

()

≥ c(Γ) − ,

pk

which concludes the proof.

A.4

Proof of Theorem 3.2

Since Ik is designed to minimize the interference, we have for every z ∈ Z, [ΓΨ(z)p]k γk Ik (p) ≤ max . 1≤k≤K 1≤k≤K pk pk max

Taking the infimum over p > 0 on both sides and using (2.42) and (3.2), we have C 0 (Γ) ≤ C(Γ, z) for any z, and thus C 0 (Γ) ≤ inf C(Γ, z) . z∈Z

(A.19)

Conversely, assume that we have an arbitrary > 0, then it can be seen from (2.42) that there exists a p() > 0 such that γk Ik p() max ≤ C 0 (Γ) + . () 1≤k≤K pk This inequality even holds for all indices k. There exists a z () such that Ik (p() ) = [Ψ(z () )p() ]k , k ∈ {1, 2, . . . , K}. Thus, max

1≤k≤K

γk [Ψ(z () )p() ]k () pk

≤ C 0 (Γ) + .

A.5. Proof of Theorem 4.3

141

Consequently, inf

p>0

γk [Ψ(z () )p]k ≤ C 0 (Γ) + . 1≤k≤K pk max

(A.20)

Combining (3.2) and (A.20), we have C(Γ, z () ) ≤ C 0 (Γ) + , and thus inf C(Γ, z) ≤ C 0 (Γ) + .

z∈Z

This holds for all > 0, thus inf C(Γ, z) ≤ C 0 (Γ) .

z∈Z

Comparison with (A.19) yields the desired result.

A.5

Proof of Theorem 4.3

First, monotonicity is proven by complete induction. For convenience, we assume an initialization p(0) = 0. Since Jk (p) ≥ 0 (axiom A1), the power update step yields p(1) ≥ p(0) and therefore p(1) ≥ p(0) . With axiom A3 this implies Jk (p(1) ) ≥ Jk (p(0) ), ∀k ∈ {1, 2, . . . , K} and thus p(2) = ΓJ (p(1) ) ≥ ΓJ (p(0) ) = p(1) . (n)

(n−1)

(A.21)

Suppose that pk ≥ pk for some iteration n, then it follows from (n+1) (n) axiom A3 that p ≥ p . Together with (A.21) this shows that the sequence is monotonically increasing. Next, we show that the sequence is bounded. Let popt denote the P opt opt optimizer of (4.8). We have popt k pk = Pmin . The k = γk Jk (p ) and (1) (0) opt iteration yields p = ΓJ (p ). We also have p = ΓJ (popt ). Since (0) (1) ≤ popt . Now assume pk ≤ popt k and with axiom A3 it follows that p that the nth iteration yields p(n) ≤ popt . Then, axiom A3 can be used to show p(n+1) ≤ popt . By complete induction, it can be concluded that the sequence p(n) is bounded and monotonically increasing. There exists a vector p0 such that p0 = lim p(n) . n→∞

142

Appendix

Continuity of the interference function implies p0 = lim p(n+1) = lim ΓJ (p(n) ) n→∞

n→∞

0

= ΓJ (p ) .

(A.22)

Thus, p0 ≤ popt is an optimizer of (4.8). Moreover, it can be concluded that p0 = popt , i.e., popt is unique.

References

[1] J. M. Aein, “Power balancing in systems employing frequency reuse,” COMSAT Tech. Rev., vol. 3, no. 2, pp. 277–300, 2002. [2] H. Alavi and R. Nettleton, “Downstream power control for a spread spectrum cellular mobile radio system,” in Proc. IEEE Globecom, pp. 84–88, 1982. [3] M. Andersin, Z. Rosberg, and J. Zander, “Gradual removals in cellular PCS with constrained power control and noise,” ACM/Baltzer Wireless Networks, vol. 2, no. 1, pp. 27–43, 1996. [4] N. Bambos, S. C. Chen, and G. J. Pottie, “Radio link admission algorithms for wireless networks with power control and active link quality protection,” in INFOCOM (1), pp. 97–104, 1995. [5] M. Bengtsson, “Jointly optimal downlink beamforming and base station assignment,” in Proc. IEEE Internat. Conf. on Acoustics, Speech, and Signal Proc. (ICASSP), May 2001. [6] M. Bengtsson and B. Ottersten, Handbook of Antennas in Wireless Communications. CRC press, August 2001. ch. 18: Optimal and Suboptimal Transmit Beamforming. [7] F. Berggren, R. J¨ antti, and S.-L. Kim, “A generalized algorithm for constrained power control with capability of temporary removal,” IEEE Trans. on Vehicular Technology, vol. 50, no. 6, pp. 1604–1612, November 2001. [8] D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: PrenticeHall, 1992. [9] H. Boche and M. Schubert, “Duality theory for uplink downlink multiuser beamforming,” in Smart Antennas – State-of-the-Art. EURASIP, Hindawi Publishing Corp., 2006. [Online]. Available: www.hindawi.com/books/spc/ volume-3/index.html. 143

144

References

[10] H. Boche and M. Schubert, “A unifying theory for uplink and downlink multiuser beamforming,” in Proc. IEEE Intern., (Zurich Seminar, Switzerland), February 2002. [11] H. Boche and M. Schubert, “A semialgebraic approach to multiuser beamforming and power control,” in Proc. IEEE Int. Symp. on Inf. Theory (ISIT), (Chicago, USA), June 2004. [12] H. Boche and M. Schubert, “Resource allocation in multi-antenna systems – achieving max-min fairness by optimizing a sum of inverse SIR,” IEEE Trans. Signal Processing, vol. 54, no. 6, June 2006. [13] H. Boche and M. Schubert, “Optimal multi-user interference balancing using transmit beamforming,” Wireless Personal Communications, vol. 26, no. 4, pp. 305–324, September 2003. [14] H. Boche, M. Schubert, and S. Sta´ nczak, “A unifying approach to multiuser receiver design under QoS constraints,” in Proc. IEEE Vehicular Techn. Conf. (VTC), (Stockholm, Sweden), May 2005. [15] H. Boche, M. Schubert, S. Sta´ nczak, and M. Wiczanowski, “An axiomatic approach to resource allocation and interference balancing,” in Proc. IEEE Internat. Conf. on Acoustics, Speech, and Signal Proc. (ICASSP), Philadelphia, USA, March 2005. [16] H. Boche and S. Sta´ nczak, “Convexity of some feasible QoS regions and asymptotic behavior of the minimum total power in CDMA systems,” IEEE Trans. Commun., vol. 52, no. 12, pp. 2190–2197, December 2004. [17] H. Boche and S. Sta´ nczak, “Log-convexity of the minimum total power in CDMA systems with certain quality-of-service guaranteed,” IEEE Trans. Inform. Theory, vol. 51, no. 1, pp. 374–381, January 2005. [18] H. Boche, M. Wiczanowski, and S. Sta´ nczak, “Characterization of optimal resource allocation in cellular networks,” in Proc. IEEE Workshop SPAWC, (Lisboa, Portugal), 2004. [19] D. Catrein, L. Imhof, and R. Mathar, “Power control, capacity, and duality of up- and downlink in cellular CDMA systems,” IEEE Trans. Commun., vol. 52, no. 10, pp. 1777–1785, 2004. [20] R. Choi and R. Murch, “MIMO transmit optimization for wireless communication systems,” in DELTA’02, 2002. [21] C. Farsakh and J. A. Nossek, “Channel allocation and downlink beamforming in an SDMA mobile radio system,” in Proc. Int. Symp. on Personal, Indoor and Mobile Radio Comm. (PIMRC), (Toronto, Canada), pp. 687–691, 1995. [22] C. Farsakh and J. A. Nossek, “Spatial covariance based downlink beamforming in an SDMA mobile radio system,” IEEE Trans. Commun., vol. 46, no. 11, pp. 1497–1506, November 1998. [23] G. Fettweis, M. L¨ ohning, D. Petrovic, M. Windisch, P. Zillmann, and W. Rave, “Dirty RF: A new paradigm,” in Proc. 16th IEEE Intern. Symposium on Personal, Indoor and Mobile Radio Commun. (PIMRC), (Berlin, Germany), September 2005. [24] G. Foschini, G. Golden, R. Valenzuela, and P. Wolniansky, “Simplified processing for wireless communication at high spectral efficiency,” IEEEjsac, vol. 17, no. 11, pp. 1841–1852, November 1999.

References

145

[25] G. J. Foschini and M. J. Gans, “On limits of wireless communications in a fading environment when using multiple antennas,” Signal Processing (Elsevier Science), vol. 6, pp. 311–335, 1999. [26] G. J. Foschini and Z. Miljanic, “A simple distributed autonomous power control algorithm and its convergence,” IEEE Trans. on Vehicular Technology, vol. 42, no. 4, pp. 541–646, November 1993. [27] F. R. Gantmacher, The Theory of Matrices. Vol. 2, New York: Chelsea Publishing Comp., 1959. [28] D. Gerlach and A. Paulraj, “Adaptive transmitting antenna methods for multipath environments,” in Proc. IEEE Globecom, (San Francisco, CA), pp. 425– 492, November 1994. [29] D. Gerlach and A. Paulraj, “Base station transmitting antenna arrays for multipath environments,” Signal Processing (Elsevier Science), vol. 54, pp. 59–73, 1996. [30] J. Goldberg and J. R. Fonollosa, “Downlink beamforming for cellular mobile communications,” in Proc. IEEE Vehicular Techn. Conf. (VTC), pp. 632–636, 1997. [31] S. A. Grandhi, R. Vijayan, and D. J. Goodman, “Distributed power control in cellular radio systems,” IEEE Trans. Commun., vol. 42, pp. 226–228, 1994. [32] S. Hanly, “An algorithm for combined cell-site selection and power control to maximize cellular spread spectrum capacity,” IEEE Journal on Selected Areas in Communications, vol. 13, no. 7, pp. 1332–1340, September 1995. [33] B. He, M. Wang, and E. Li, “A new distributed power balancing algorithm for CDMA cellular systems,” in Proc. IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1768–1771, 1997. [34] W. Hongyu, H. Aiging, H. Rong, and G. Weikang, “Balanced distributed power control,” in IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), pp. 1415–1419, 2000. [35] R. A. Horn and C. R. Johnson, Matrix Analysis. MA: Cambridge University Press, 1985. [36] M. Joham, K. Kusume, M. H. Gzara, W. Utschick, and J. A. Nossek, “Transmit Wiener filter for the downlink of TDD DS-CDMA systems,” in Symp. on Spread-Spectrum Tech. and Appli., (Prague, Czech Republic), September 2002. [37] M. Joham, W. Utschick, and J. A. Nossek, “Linear transmit processing in MIMO communications systems,” IEEE Trans. Signal Processing, vol. 53, no. 8, pp. 2700–2712, August 2005. [38] S. Koskie and Z. Gajic, “Sir-based power control algorithms wireless CDMA networks: An overview,” in International Conference on Dynamics of Continuous, Discrete and Impulsive Systems, (Guelph, Ontario), May 2003. [39] K. K. Leung, C. W. Sung, W. S. Wong, and T. Lok, “Convergence theorem for a general class of power-control algorithms,” IEEE Trans. Commun., vol. 52, no. 9, pp. 1566–1574, September 2004. [40] J. C. Liberti and T. S. Rappaport, Smart Antennas for Wireless Communications. Upper Saddle River, NJ: Prentice Hall, 1999. [41] C. D. Meyer, Matrix Analysis and Applied Linear Algebra. SIAM, 2000.

146

References

[42] H. J. Meyerhoff, “Method for computing the optimum power balance in multibeam satellites,” COMSAT Tech. Rev., vol. 4, no. 1, pp. 139–146, 1974. [43] D. Mitra, “An asynchronous distributed algorithm for power control in cellular radio systems,” in Wireless and Mobile Communications, pp. 177–186, Kluwer, 1994. [44] G. Montalbano, I. Ghauri, and D. T. M. Slock, “Spatio-temporal array processing for DS-CDMA downlink transmission,” in Proc. Asilomar Conf. on Signals, Systems and Computers, (Monterey), 2000. [45] G. Montalbano and D. T. M. Slock, “Matched filter bound optimization for multiuser downlink transmit beamforming,” in Proc. IEEE Internat. Conf. on Universal Personal Communications (ICUPC), (Florence, Italy), October 1998. [46] R. Nettleton and H. Alavi, “Power control for a spread spectrum cellular mobile radio system,” in Proc. IEEE Vehicular Techn. Conf. (VTC), pp. 242–246, 1983. [47] D. P. Palomar, J. M. Cioffi, and M. A. Lagunas, “Joint Tx-Rx beamforming design for multicarrier MIMO channels: A unified framework for convex optimization,” IEEE Trans. Signal Processing, vol. 51, no. 9, pp. 2381–2401, September 2003. [48] S. U. Pillai, Array Signal Processing. NY: Springer, 1989. [49] J. G. Proakis, Digital Communications. McGraw Hill, 1989. [50] F. Rashid-Farrokhi, L. Tassiulas, and K. J. Liu, “Joint optimal power control and beamforming in wireless networks using antenna arrays,” IEEE Trans. Commun., vol. 46, no. 10, pp. 1313–1323, October 1998. [51] H. Sampath, P. Stoica, and A. Paulraj, “Generalized linear precoder and decoder design for MIMO channels using the weighted MMSE criterion,” IEEE Trans. Signal Processing, vol. 49, no. 12, pp. 2198–2206, December 2001. [52] D. Samuelsson, M. Bengtsson, and B. Ottersten, “An efficient algorithm for solving the downlink beamforming problem with indefinite constraints,” in Proc. IEEE Internat. Conf. on Acoustics, Speech, and Signal Proc. (ICASSP), Philadelphia, USA, March 2005. [53] A. Scaglione, G. B. Giannakis, and S. Barbarossa, “Redundant filterbank precoders and equalizers, parts i and ii,” IEEE Trans. Signal Processing, vol. 47, pp. 1988–2002, July 1999. [54] A. Scaglione, P. Stoica, S. Barbarossa, G. B. Giannakis, and H. Sampath, “Optimal designs for space-time linear precoders and decoders,” IEEE Trans. Signal Processing, vol. 50, no. 5, pp. 1051–1064, May 2002. [55] M. Schubert and H. Boche Advanced Interference Function Calculus. [56] M. Schubert and H. Boche, “Comparison of infinity-norm and 1-norm optimization criteria for SIR-balanced beamforming,” Signal Processing (Elsevier Science), vol. 84, no. 2, pp. 367–368, February 2004. [57] M. Schubert and H. Boche, “Solution of the multi-user downlink beamforming problem with individual SINR constraints,” IEEE Trans. Veh. Technol., vol. 53, no. 1, pp. 18–28, January 2004. [58] M. Schubert and H. Boche, “Iterative multiuser uplink and downlink beamforming under SINR constraints,” IEEE Trans. Signal Processing, vol. 53, no. 7, pp. 2324–2334, July 2005.

References

147

[59] M. Schubert, S. Shi, E. A. Jorswieck, and H. Boche, “Downlink sum-MSE transceiver optimization for linear multi-user MIMO systems,” in Proc. Asilomar Conf. on Signals, Systems and Computers, (Monterey, CA), September 2005. [60] E. Seneta, Non-Negative Matrices and Markov Chains. Springer, 1981. [61] S. Serbetli and A. Yener, “Transceiver optimization for multiuser MIMO systems,” IEEE Trans. Signal Processing, vol. 52, no. 1, pp. 214–226, January 2004. [62] S. Shi and M. Schubert, “MMSE transmit optimization for multiuser multiantenna systems,” in Proc. IEEE Internat. Conf. on Acoustics, Speech, and Signal Proc. (ICASSP), (Philadelphia, USA), March 2005. [63] S. Stanczak and H. Boche, “Information theoretic approach to the Perron root of nonnegative irreducible matrices,” in Proc. of 2004 Information Theory Workshop (ITW), (San Antonio, Texas, USA), pp. 24–29, October 2004. [64] S. Stanczak and H. Boche, “The infeasible SIR region is not a convex set,” IEEE Trans. Commun., Accepted, November 2005. [65] S. Stanczak and M. Wiczanowski, “Distributed fair power control for wireless networks: Objectives and algorithms,” in Proc. the 43rd Annual Allerton Conference on Communications, Control, and Computing, pp. 28–30, September 2005. Invited. [66] S. Stanczak, M. Wiczanowski, and H. Boche, “Distributed power control for optimizing a weighted sum of QoS parameter values,” in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), (St. Louis, MO, USA), November 25–December 2 2005. [67] S. Stanczak, M. Wiczanowski, and H. Boche, Theory and Algorithms for Resource Allocation in Wireless Networks. Springer-Verlag, 2006. ser. Lecture Notes in Computer Science (LNCS). [68] C. W. Sung, “Log-convexity property of the feasible SIR region in powercontrolled cellular systems,” IEEE Communications Letters, vol. 6, no. 6, pp. 248–249, June 2002. [69] E. Telatar, “Capacity of multiple-antenna Gaussian channels,” European Trans. Telecommun., vol. 10, pp. 585–595, November 1999. [70] M. Torlak, G. Xu, B. L. Evans, and H. Liu, “Estimation of optimal weight vectors for spatial broadcast channels,” in Proc. IEEE Internat. Conf. on Acoustics, Speech, and Signal Proc. (ICASSP), p. 4009, 1997. [71] S. Ulukus and R. Yates, “Adaptive power control and MMSE interference suppression,” ACM Wireless Networks, vol. 4, no. 6, pp. 489–496, 1998. [72] S. Ulukus and A. Yener, “Iterative transmitter and receiver optimization for CDMA networks,” IEEE Trans. Wireless Commun., vol. 3, no. 6, pp. 1879– 1884, November 2004. [73] W. Utschick and J. A. Nossek, “Downlink beamforming for FDD mobile radio systems based on spatial covariances,” in Proc. European Wireless 99, (Munich, Germany), pp. 65–68, October 1999. [74] M. K. Varanasi and T. Guess, “Achieving vertices of the capacity region of the Gaussian correlated-waveform multiple-access channel with decision feedback

148

[75]

[76] [77]

[78]

[79]

[80]

[81]

[82]

[83]

[84]

[85]

[86]

[87]

References receivers,” in Proc. IEEE Int. Symp. on Inf. Theory (ISIT), (Ulm, Germany), p. 270, June 1997. M. K. Varanasi and T. Guess, “Optimum decision feedback multiuser equalization with successive decoding achieves the total capacity of the Gaussian multiple-access channel,” in Proc. Asilomar Conf. on Signals, Systems and Computers, Monterey, pp. 1405–1409, November 1997. S. Verdu, Multiuser Detection. Cambridge, UK: Cambridge University Press, 1998. S. Vishwanath, N. Jindal, and A. Goldsmith, “Duality, achievable rates, and sum-rate capacity of Gaussian MIMO broadcast channels,” IEEE Trans. Inform. Theory, vol. 49, no. 10, pp. 2658–2668, October 2003. E. Visotsky and U. Madhow, “Optimum beamforming using transmit antenna array,” in Proc. IEEE Vehicular Techn. Conf. (VTC) spring, (Houston, Texas), pp. 851–856, May 1999. P. Viswanath, V. Anantharam, and D. Tse, “Optimal sequences, power control and capacity of synchronous CDMA systems with linear MMSE multiuser receivers,” IEEE Trans. Inform. Theory, vol. 45, no. 6, pp. 1968–1993, September 1999. P. Viswanath and D. Tse, “Sum capacity of the vector Gaussian broadcast channel and uplink-downlink duality,” IEEE Trans. Inform. Theory, vol. 49, no. 8, pp. 1912–1991, August 2003. S. Vorobyov, A. Gershman, and Z.-Q. Luo, “Robust adaptive beamforming using worst-case performance optimization: a solution to the signal mismatch problem,” IEEE Trans. Signal Processing, vol. 51, no. 2, pp. 313–324, February 2003. H. Weingarten, Y. Steinberg, and S. Shamai (Shitz), “The capacity region of the Gaussian MIMO broadcast channel,” IEEE Trans. Inform. Theory, Submitted, 2004. M. Wiczanowski, H. Boche, and S. Sta´ nczak, “Characterization of optimal resource allocation in cellular networks – optimization theoretic view and algorithmic solutions,” in Internat. Teletraffic Congress (ITC), (Bejing, China), September 2005. H. Wielandt, “Unzerlegbare, nicht negative Matrizen,” in Math. Z., pp. 642– 648, 1950. and Mathematische Werke/Mathematical Works, vol. 2, 100-106 de Gruyter, Berlin, 1996. A. Wiesel, Y. C. Eldar, and S. Shamai, “Linear precoding via conic optimization for fixed MIMO receivers,” IEEE Trans. Signal Processing, vol. 54, no. 1, pp. 161–176, 2006. P. Wolniansky, G. Foschini, G. Golden, and R. Valenzuela, “V-BLAST: an architecture for realizing very high data rates over the rich-scattering wireless channel,” in Proc. URSI Intern. Symp. on Signals, Systems, and Electronics., (New York, NY, USA), pp. 295–300, 1998. C. Wu and D. Bertsekas, “Distributed power control algorithms for wireless networks,” IEEE Trans. on Vehicular Technology, vol. 50, no. 2, pp. 504–514, March 2001.

References

149

[88] J. Yang and S. Roy, “On joint transmitter and receiver optimization for multiple-input-multiple-output (MIMO) transmission systems,” IEEE Trans. Commun., vol. 42, no. 12, pp. 3221–3231, December 1994. [89] W. Yang and G. Xu, “Optimal downlink power assignment for smart antenna systems,” in Proc. IEEE Internat. Conf. on Acoustics, Speech, and Signal Proc. (ICASSP), May 1998. [90] R. Yates and H. Ching-Yao, “Integrated power control and base station assignment,” IEEE Trans. on Vehicular Technology, vol. 44, no. 3, pp. 638–644, August 1995. [91] R. D. Yates, “A framework for uplink power control in cellular radio systems,” IEEE J. Select. Areas Commun., vol. 13, no. 7, pp. 1341–1348, September 1995. [92] W. Yu and J. M. Cioffi, “Sum capacity of Gaussian vector broadcast channels,” IEEE Trans. Inform. Theory, vol. 50, no. 9, pp. 1875–1892, 2004. [93] J. Zander, “Distributed cochannel interference control in cellular radio systems,” IEEE Trans. on Vehicular Technology, vol. 41, no. 3, pp. 305–311, August 1992. [94] J. Zander, “Performance of optimum transmitter power control in cellular radio systems,” IEEE Trans. on Vehicular Technology, vol. 41, no. 1, pp. 57–62, February 1992. [95] J. Zander and M. Frodigh, “Comment on performance of optimum transmitter power control in cellular radio systems,” IEEE Trans. on Vehicular Technology, vol. 43, no. 3, p. 636, August 1994. [96] J. Zander and S.-L. Kim, Radio Resource Management for Wireless Networks. Boston, London: Artech House, 2001. [97] P. Zetterberg and B. Ottersten, “The spectrum efficiency of a base station antenna array system for spatially selective transmission,” in Proc. IEEE Vehicular Techn. Conf. (VTC) fall, 1995.

QoS-Based Resource Allocation and Transceiver Optimization (Foundations and Trends in Communications and Information Theory)

Information Combining (Foundations and Trends in Communications and Information Theory)

MIMO Transceiver Design via Majorization Theory (Foundations and Trends in Communications and Information Theory)

Recent Trends in Optimization Theory and Applications

Toeplitz and Circulant Matrices: A review (Foundations and Trends in Communications and Information The)

Trends in Network and Communications

Algebraic Number Theory and Code Design for Rayleigh Fading Channels (Foundations and Trends in Communications and Information Theory)

Wireless Resource Allocation: Auctions, Games and Optimization Ph.D Thesis

Fundamentals of Resource Allocation in Wireless Networks: Theory and Algorithms

Resource Allocation in Wireless Networks.. Theory and Algorithms

Geometric Programming for Communication Systems (Foundations and Trends in Communications and Information The)

Optimization: Foundations and Applications

Algebraic Number Theory And Code Design For Rayleigh Fading Channels (Foundations and Trends in Communications and Information The)

Information and Communications Security

Music Retrieval (Foundations and Trends in Information Retrieval)

Music Retrieval (Foundations and Trends in Information Retrieval)

Resource Allocation in the Grid

Cyclic Division Algebras: A Tool for Space-Time Coding (Foundations and Trends in Communications and Information Theory)

Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial (Foundations and Trends in Communications and Information Theory)

Resource Allocation in Project Management

Convex Optimization in Signal Processing and Communications

Entrepreneurship Research (Foundations and Trends in Entrepreneurship)

Entanglement and Decoherence: Foundations and Modern Trends

Recent Trends in Information Reuse and Integration

Monotonicity in Markov Reward and Decision Chains: Theory and Applications (Foundations and Trends in Stochastic Systems)

Uncertainty and Information: Foundations of Generalized Information Theory

From Filing and Fitting to Flexible Manufacturing (Foundations and Trends in Technology, Information and Operations Management)

Uncertainty and Information: Foundations of Generalized Information Theory

Uncertainty And Information: Foundations of Generalized Information Theory

Information Dynamics: Foundations and Applications

Sliding Modes in Control and Optimization (Communications and Control Engineering)

QoS-Based Resource Allocation and Transceiver Optimization (Foundations and Trends in Communications and Information Theory)

Information Combining (Foundations and Trends in Communications and Information Theory)

MIMO Transceiver Design via Majorization Theory (Foundations and Trends in Communications and Information Theory)

Recent Trends in Optimization Theory and Applications

Toeplitz and Circulant Matrices: A review (Foundations and Trends in Communications and Information The)

Trends in Network and Communications

Algebraic Number Theory and Code Design for Rayleigh Fading Channels (Foundations and Trends in Communications and Information Theory)

Wireless Resource Allocation: Auctions, Games and Optimization Ph.D Thesis

Fundamentals of Resource Allocation in Wireless Networks: Theory and Algorithms

Resource Allocation in Wireless Networks.. Theory and Algorithms

Geometric Programming for Communication Systems (Foundations and Trends in Communications and Information The)

Optimization: Foundations and Applications

Algebraic Number Theory And Code Design For Rayleigh Fading Channels (Foundations and Trends in Communications and Information The)

Information and Communications Security

Music Retrieval (Foundations and Trends in Information Retrieval)

Music Retrieval (Foundations and Trends in Information Retrieval)

Resource Allocation in the Grid

Cyclic Division Algebras: A Tool for Space-Time Coding (Foundations and Trends in Communications and Information Theory)

Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial (Foundations and Trends in Communications and Information Theory)

Resource Allocation in Project Management

Convex Optimization in Signal Processing and Communications

Entrepreneurship Research (Foundations and Trends in Entrepreneurship)

Entanglement and Decoherence: Foundations and Modern Trends

Recent Trends in Information Reuse and Integration

Monotonicity in Markov Reward and Decision Chains: Theory and Applications (Foundations and Trends in Stochastic Systems)

Uncertainty and Information: Foundations of Generalized Information Theory

From Filing and Fitting to Flexible Manufacturing (Foundations and Trends in Technology, Information and Operations Management)

Uncertainty and Information: Foundations of Generalized Information Theory

Uncertainty And Information: Foundations of Generalized Information Theory

Information Dynamics: Foundations and Applications

Sliding Modes in Control and Optimization (Communications and Control Engineering)

Recommend Documents