Amel Tibhirt
email: amel.tibhirt@orange.com

Dirk Slock
email: dirk.slock@eurecom.fr

Yi Yuan-Wu

Interference Mitigation in Dynamic TDD MIMO Interference Channels

Keywords: Dynamic TDD, MIMO, rank deficient, interference alignment, Degree of Freedom

Dynamic Time Division Duplexing (DynTDD) is one of the key features that enable the dynamic or flexible uplink and downlink transmission and reception for a specific sub-frame in 5G mobile networks. However, the advantages of the DynTDD system are difficult to fully utilize due to the cross-link interference (CLI) arising from neighboring cells using different transmission directions on the same or partially-overlapping time-frequency resources. There are two types of cross-link interference; between the Base Stations (BS), which is known as BS-to-BS or DL-to-UL interference, and between User Equipment (UE) which is known as UEto-UE or UL-to-DL interference. Rank deficiency of channel matrices is an important aspect of Multi-Input Multi-Output (MIMO) wireless systems. Poor scattering and the presence of single or very few direct paths are some reasons for rank deficiency in wireless channels. While the implications of rank deficient channels are well understood for the single user (SU) point-to-point setting, less is known for interference networks. In this paper, we give a sufficient condition for a full rank MIMO interfering channel, that outperforms the current state of the art, we provide also tighter necessary conditions for Interference Alignment (IA) feasibility, that are very close to the necessary and sufficient condition, which gives all the feasible cases. Then we extend a MIMO Interference Alignment (IA) feasibility framework to rank deficient channels, by investigating our published theorem for the necessary and sufficient condition in this case.

I. INTRODUCTION

Beside the potential to significantly improve the overall resource utilization [START_REF] Jayasinghe | Bi-directional signaling strategies for dynamic TDD networks[END_REF] and considerately reduce the latency [START_REF] Yang | Packet Throughput Analysis of Static and Dynamic TDD in Small Cell Networks[END_REF], Dynamic Time Division Duplexing (DynTDD), brings some new challenges because of the introduction of crosslink interference (CLI), including DL-to-UL and UL-to-DL interference.

Studies focusing on resolving the BS-to-BS interference problem rather than the UE-to-UE interference have been much more prevalent. The reason for this is that during an UL transmission, DL to UL interference may cause substantial performance degradation, contrarily to the DL transmission where the DynTDD is only used in favor of it [START_REF] Jalal | Interference Analysis in Dynamic TDD System Combined or Not with Cell Clustering Scheme[END_REF]. But according to [START_REF] Han | A Novel Inter-Cell Interference Coordination Scheme Based on Dynamic Resource Allocation in LTE-TDD Systems[END_REF], the UE-to-UE interference power level is low for the UEs in the center of the cell region but very high for the cell-edge UEs. Moreover, for network stability, it is also very important to handle the UE-to-UE interference of edge UEs. Thus, to further improve network capacity significantly, we have to resort to concurrent transmissions. Multiple concurrent transmission techniques (e.g., Zero Forcing (ZF), Interference Alignment (IA), and distributed MIMO) are proposed in which multiple senders jointly encode signals to multiple receivers so that interference is aligned or canceled and each receiver is able to decode its desired information.

The feasibility conditions of IA have been analyzed in [START_REF] Liu | On the Feasibility of Linear Interference Alignment for MIMO Interference Broadcast Channels With Constant Coefficients[END_REF]- [START_REF] Jeon | The Feasibility of Interference Alignment for MIMO Interfering Broadcast-Multiple-Access Channels[END_REF]. [START_REF] Ko | Distributed Interference Alignment for Multi-Antenna Cellular Networks With Dynamic Time Division Duplex[END_REF] also mathematically characterizes the achievable Degrees-of-Freedom (DoF) of their proposed DIA technique for a given number of antennas at BS/MS. In [START_REF] Liu | On the Feasibility of Linear Interference Alignment for MIMO Interference Broadcast Channels With Constant Coefficients[END_REF] the authors show that for the MIMO Interfering Broadcast Channel (IBC) where each user has one desired data stream, a proper system is feasible. For the symmetric (which we call here uniform) MIMO Interfering Broadcast Channel (IBC), they provide a proper but infeasible region of antenna configurations by analyzing the difference between the necessary conditions and the sufficient conditions of linear IA feasibility. [START_REF] Jeon | The Feasibility of Interference Alignment for MIMO Interfering Broadcast-Multiple-Access Channels[END_REF] established a necessary and sufficient condition on IA feasibility for the (full rank) MIMO Interfering Broadcast Multiple Access Channel (IBMAC), which characterizes the optimal sum DoF for various practical network configurations.

The main contributions of this paper are summarized as follows: the work reported in this paper comes to go beyond our study in [START_REF] Tibhirt | Distributed Beamforming Design in Reduced-Rank MIMO Interference Channels and Application to Dynamic TDD[END_REF] and [START_REF]Interference Alignment in Reduced-Rank MIMO Networks with Application to Dynamic TDD[END_REF]. We start by reporting the proper conditions considering centralized design for IA feasibility. Then we give a sufficient condition in a full rank MIMO IC, which is written in terms of the problem dimension (number of UEs, number of antennas, and the number of streams). After that, we propose tighter necessary conditions that show motivating numerical results since it is very close to the sufficient and necessary condition for IA feasibility. In the end, we give the numerical result that shows the gap between our sufficient condition, the sufficient and necessary condition, and the existing sufficient condition in the current state of the art. We highlight also the gap between our different proposed conjectures and the sufficient and necessary condition. In addition, for the reduced Rank MIMO IBMAC-IC we establish for a given system a comparative table between our previous IA methods in [START_REF] Tibhirt | Distributed Beamforming Design in Reduced-Rank MIMO Interference Channels and Application to Dynamic TDD[END_REF] and the necessary and sufficient condition in [START_REF]Interference Alignment in Reduced-Rank MIMO Networks with Application to Dynamic TDD[END_REF], to confirm the conclusion about the choice of the IA method, based on the rank of the interfering channel, that increase the feasible DoF.

II. DYNAMIC TDD SYSTEM MODEL

We consider a MIMO system with two cells, one operating in DL and the other one in UL. Each cell has one BS of M antennas, with K ul and K dl interfering/interfered users in the UL and DL cell respectively. The kth DL UE and the lth UL UE have N dl,k and N ul,l antennas respectively. This scenario brings the two types of interference, the BSto-BS interference, and the UE-to-UE interference between the UEs that are particularly on the edge of the two cells as shown in Fig 1 . The channel between the lth user in the UL cell and the kth user in the DL cell is denoted as H k,l ∈ C N dl,k ×N ul,l with k ∈ [1, ..., K dl ] and l ∈ [1, ..., K ul ]. Denote d dl,k and d ul,l as the number of data streams from the DL BS to the kth DL UE and from the lth UL UE to the UL BS respectively. We denote the rank of the UE-to-UE interference channel (IC) as r k,l . We have r k,l distinguishable significant paths contribute to H k,l , where distinguishable means with linearly independent antenna array responses from other paths, at both the Tx side and the Rx side. Then we can factorize H k,l as:

H k,l = B k,l A H k,l (1)
with B k,l ∈ C N dl,k ×r k,l and A k,l ∈ C N ul,l ×r k,l are full rank matrices. To analyze the UE-to-UE interference, we have both the DL and UL UEs will contribute to cancel each link of interference between them. We consider F k ∈ C N dl,k ×d dl,k and G l ∈ C N ul,l ×d ul,l as the Rx/Tx beamforming (BF) matrices at the kth DL and the lth UL users respectively. ZF from UL UE l to the DL UE k requires:

F H k H k,l G l = 0, ∀k ∈ {1, ..., K dl }, ∀l ∈ {1, ..., K ul } . (2)
Our system of Fig. 1 is also called IBMAC (Interfering Broadcast-Multiple Access Channel) in [START_REF] Jeon | The Feasibility of Interference Alignment for MIMO Interfering Broadcast-Multiple-Access Channels[END_REF] which corresponds to a two cells system with one cell being in DL (BC) and another in UL (MAC) and with interference between the two cells.

In our study, we suppose that the number of base station antennas is large enough so that all UL or DL UE streams can be supported, and that the BS-to-BS interference can be mitigated by exploiting a limited rank BS-to-BS channel [START_REF] Ko | Distributed Interference Alignment for Multi-Antenna Cellular Networks With Dynamic Time Division Duplex[END_REF]. Hence the IBMAC problem is then limited to the interference from UL users to DL users, which we may call IBMAC-IC (IBMAC Interference Channel). We assume:

d dl,k ≥ 1 and d ul,l ≥ 1. (3)

III. IA FEASIBILITY CONDITIONS FOR DYNTDD UE-TO-UE GENERIC RANK MIMO IBMAC

In this section we analyze the overall UL UE to DL UE interference, considering generic rank MIMO channels.

A. Proper Conditions

In [START_REF] Tibhirt | Distributed Beamforming Design in Reduced-Rank MIMO Interference Channels and Application to Dynamic TDD[END_REF] we have established the proper conditions, where the global proper conditions are given by [13, eq.( 6)].

Note that this condition subsumes the SU MIMO conditions d ul,l ≤ N ul,l , d dl,k ≤ N dl,k so that the number of variables on the LHS is non-negative. Apart from this proper condition for the overall system, we get an overall set of proper conditions by considering all subsystems also.

Theorem 1. Overall Proper Conditions for IA Feasibility in generic rank MIMO IBMAC-IC

The conditions in [13, eq.( 6)] should be satisfied also by any subsystem, i.e. the IBMAC-IC formed by any subset of the UL users and any subset of the DL users, such that:

l∈U ul d ul,l (N ul,l -d ul,l ) + k∈U dl d dl,k (N dl,k -d dl,k ) ≥ k∈U dl k∈U dl min(r k,l d dl,k , r k,l d ul,l , d ul,l d dl,k ) . ∀ U ul ⊆ [ 1, ..., K ul ] and ∀ U dl ⊆ [ 1, ..., K dl ] (4)

B. Necessary and sufficient Conditions

In our previous work [START_REF]Interference Alignment in Reduced-Rank MIMO Networks with Application to Dynamic TDD[END_REF] we have revisited the feasibility analysis framework of [START_REF] Razaviyayn | On the Degrees of Freedom Achievable Through Interference Alignment in a MIMO Interference Channel[END_REF], [START_REF] Óscar González | A Feasibility Test for Linear Interference Alignment in MIMO Channels With Constant Coefficients[END_REF] and [START_REF] Liu | On the Feasibility of Linear Interference Alignment for MIMO Interference Broadcast Channels With Constant Coefficients[END_REF]. Thus we have provided a detailed analysis of the UE-to-UE interference by shedding light on the channel matrices and the beamformers at Tx and Rx, which was of huge use to provide the necessary and sufficient condition for IA feasibility in a Reduced Rank MIMO IBMAC-IC. To better understand the following theorems and conjectures, we report here the representation of Jacobian matrices J and J H that include all the UE-to-UE interference channels of our system model, where the details to obtain these matrices are given in [START_REF]Interference Alignment in Reduced-Rank MIMO Networks with Application to Dynamic TDD[END_REF]:

J =                                         I d ul,1 ⊗H (2) 11 0 (H (3) 11 ) T ⊗I d dl,1 0 . . . . . . . . . . . . 0 I d ul,K ul ⊗H (2) 1K ul (H (3) 1K ul ) T ⊗I d dl,1 0 . . . . . . . . . . . . I d ul,1 ⊗H (2) K dl 1 0 0 (H (3) K dl 1 ) T ⊗I d dl,K dl . . . . . . . . . . . . 0 I d ul,K ul ⊗H (2) K dl K ul 0 (H (3) K dl K ul ) T ⊗I d dl,K dl                                         (5) J G J F
The block

I d ul,l ⊗H (2) kl in J G has dimensions d ul,l d dl,k × d ul,l (N ul,l -d ul,l ), the block (H (3) kl ) T ⊗ I d dl,k in J F has dimensions d ul,l d dl,k × (N dl,k -d dl,k )d dl,k .
The dimensions are for matrix J G :

K ul l=1 K dl k=1 d ul,l d dl,k × K ul l=1 (N ul,l -d ul,l ) d ul,l ,
for matrix J F :

K ul l=1 K dl k=1 d ul,l d dl,k × K dl k=1 (N dl,k -d dl,k ) d dl,k . A H kl = A (1) kl A (2) kl , B H kl = B (1) kl B (2) kl . (6)
The matrix blocks A

kl and B

(1

)
kl have dimensions r kl × d ul,l and r kl × d dl,k respectively.

J H =            (I d ul,1 ⊗B (1)H 11 ) 0 (A (1)
0 (I d ul,K ul ⊗B (1)H K dl K ul ) 0 (A (1)T K dl K ul ⊗I d dl,K dl )            (7) J B J A
The necessary and sufficient condition for IA feasibility in a regular MIMO IBMAC-IC is given in the following Theorem: And the necessary and sufficient condition for IA feasibility in a reduced rank MIMO IBMAC-IC is provided and proved in [START_REF]Interference Alignment in Reduced-Rank MIMO Networks with Application to Dynamic TDD[END_REF], this condition is given by the following Theorem: Theorem 3. Necessary and Sufficient Condition for IA Feasibility in Reduced Rank MIMO IBMAC-IC For a deficient rank MIMO IBMAC-IC, the DoF (d ul,1 , ..., d ul,K ul , d dl,1 , ..., d ul,K dl ) are feasible almost surely if and only if:

rank(J) = rank(J J ) = rank([J J H ]) (8)
i.e., the column space of J H in (7) should be contained in the column space of J in (5).

IV. IA FEASIBILITY CONDITIONS FOR DYNTDD UE-TO-UE FULL RANK MIMO IBMAC In this section, we focus on the sufficient condition of IA feasibility in a full rank MIMO IBMAC-IC.The aim here is to give an easy formulation of a sufficient condition, in terms of the problem dimensions: the number of antennas at UL and DL UEs, the number of data stream and the number of users that are included in the UE-to-UE interference, rather than the sufficient and necessary condition in Theorem 2 given by a Jacobian matrix row rank. [START_REF] Jeon | The Feasibility of Interference Alignment for MIMO Interfering Broadcast-Multiple-Access Channels[END_REF] finds sufficiency in the limited scenario in which all DL UEs and UL UEs have the same number of data streams d dl,k = d dl , d ul,l = d ul , for this assumption the number of antennas at DL N dl,k and at UL N ul,l must satisfy mod(N dl,k -d dl , d ul ) = mod(N ul,l -d ul , d dl ) = 0 so the IA is feasible. Within this scope, we establish a sufficient condition for IA feasibility given by our following Theorem 4, which gives a much greater DoF than the recent work in [START_REF] Jeon | The Feasibility of Interference Alignment for MIMO Interfering Broadcast-Multiple-Access Channels[END_REF]. Theorem 4. Sufficient Condition for IA Feasibility in a Regular MIMO IBMAC-IC For a full rank MIMO IBMAC-IC, respecting the proper condition of Theorem 1, and if:

∀k, l : (N ul,l -d ul,l ) ≥ d dl,k and (N dl,k -d dl,k ) ≥ d ul,l (9) then (d ul,1 , ..., d ul,K ul , d dl,1 , ..., d ul,K dl ) is feasible.
The equation in [START_REF] Negro | Interference Alignment Limits for K-user Frequency-Flat MIMO Interference Channels[END_REF] means that both the block matrix

I d ul,l ⊗ H (2)
kl in J G and the block matrix (H

(3) kl ) T ⊗ I d dl,k in J F should be full row rank.
For the proof, see the Appendix.

In the following, we introduce three conjectures that represents another sufficient condition, and two tighter necessary conditions for IA feasibility in regular MIMO IBMAC-IC. Conjecture 1. Sufficient Condition for IA Feasibility in a Regular MIMO IBMAC-IC For a full rank MIMO IBMAC-IC, respecting the proper condition of Theorem 1, and if: [START_REF] Negro | Interference Alignment Feasibility in Constant Coefficient MIMO Interference Channels[END_REF] and:

∀k, l : (N ul,l -d ul,l ) ≥ d dl,k or (N dl,k -d dl,k ) ≥ d ul,l
K dl k=1 d dl,k min(N dl,k -d dl,k , l d ul,l -max i (d ul,i ))+ K ul l=1 d ul,l min(N ul,l -d u,l , k d dl,k -max i (d dl,i )) ≥ K dl k=1 K ul l=1 d dl,k d ul,l (11)
then (d ul,1 , ..., d ul,K ul , d dl,1 , ..., d ul,K dl ) is feasible.

The equation in [START_REF] Negro | Interference Alignment Feasibility in Constant Coefficient MIMO Interference Channels[END_REF]

K dl k=1 d dl,k min(N dl,k -d dl,k , max l (d ul,l ))+ K ul l=1 d ul,l min(N ul,l -d ul,l , max k (d dl,k )) ≥ K ul l=1 K dl k=1 d ul,l d dl,k (12)
The LHS of equation ( 12) represents the number of non zero columns of the Jacobian matrix J in equation ( 5), and the RHS is the number of rows of J . Conjecture 3. Tighter Necessary Condition for IA Feasibility in a Regular MIMO IBMAC-IC For full rank MIMO channels, if the tuple of DoF (d ul,1 , ..., d ul,K ul , d dl,1 , ..., d ul,K dl ) respects the proper condition of Theorem 1 and is feasible, then it may satisfy the following necessary condition:

∀k, l : (N ul,l -d ul,l ) ≥ d dl,k or ∀k, l : (N dl,k -d dl,k ) ≥ d ul,l (13)
The conjecture 3 means that either J G or J F is full row rank.

V. RESULTS AND DISCUSSION

For the evaluation of the different given conditions for the IA feasibility, we give the numerical results in Table I. Thus we compare the number of combinations (a combination is a given number of data streams at each UL and DL UE) for different sum DoF, when considering the proper condition in Theorem 1, the necessary and sufficient condition in Theorem 2, our sufficient condition in Theorem 4, and the sufficient condition in [START_REF] Jeon | The Feasibility of Interference Alignment for MIMO Interfering Broadcast-Multiple-Access Channels[END_REF]Theorem 3]. We choose as an example K ul = 2 and K dl = 3, for the following three systems:

• System 1: N ul,1 = 3, N ul,2 = 7, N dl,1 = 2, N dl,2 = 3 and N dl,3 = 8, which is the system that has been chosen in [START_REF] Jeon | The Feasibility of Interference Alignment for MIMO Interfering Broadcast-Multiple-Access Channels[END_REF],

• System 2: N ul,1 = 4, N ul,2 = 7, N dl,1 = 4, N dl,2 = 5 and N dl,3 = 6, • System 3: N ul,1 = 7, N ul,2 = 7, N dl,1 = 6, N dl,2 = 5 and N dl,3 = 6.

We get the following numerical results by doing an exhaustive search for all the possible combinations that satisfies each given theorem in Table I, and this process is repeated for different sum DoF. We give here a example to better understand the meaning of a combination, for System 1 when SumDoF = 6, the different possible combinations that respect the proper condition in Theorem 1 are:

d ul,1 = 2, d ul,2 = 1, d dl,1 = 1, d dl,2 = 1 and d dl,3 = 1 d ul,1 = 1, d ul,2 = 2, d dl,1 = 1, d dl,2 = 1 and d dl,3 = 1 d ul,1 = 1, d ul,2 = 1, d dl,1 = 2, d dl,2 = 1 and d dl,3 = 1 d ul,1 = 1, d ul,2 = 1, d dl,1 = 1, d dl,2 = 2 and d dl,3 = 1 d ul,1 = 1, d ul,2 = 1, d dl,1 = 1, d dl,2 = 1 and d dl,3 = 2
From these results, we can conclude that:

• The gap in term of the number of combinations between the proper (Theorem 1) and the necessary and sufficient condition (Theorem 2) is not negligible, and it is proportional to the number of antennas. Thus a feasible Sum DoF needs to be associated to feasible combinations (distribution of the DoF at UL and DL UE), so the IA is feasible, • All the feasible cases are given by the necessary and sufficient condition (Theorem 2), our sufficient condition (Theorem 4) comes to cover a subset of these feasible cases, the size of this subset is quite interesting, since Theorem 4 is written in term of the problem dimension, and does not need the full row rank test on J . • When considering our sufficient condition (Theorem 4)

with the sufficient condition mentioned before in the state of the art [11, Theorem 3], we notice how much our sufficient condition outperforms and improves the available state of the art. In Table II we give some numerical results for the three systems mentioned before, to evaluate the gap between the given conjectures and the necessary and sufficient condition in Theorem 2. : the given condition gives some combinations that are proper but not feasible. (Feasible = Theorem 2 is satisfied). From these results, we can notice that:

• Conjecture 1 is another sufficient condition for IA feasibility that gives more feasible combinations comparing to Theorem 4, from our observation, Conjecture 1 can find some combinations which are not found by Theorem 4, so Conjecture 1 and Theorem 4 can be complementary, • Conjecture 2 and Conjecture 3 are very close to the necessary and sufficient conditions in Theorem 2, but at some DoF these conditions gives some combinations (at most two combinations) that are proper but not feasible, it is for this reason that these conditions are mentioned as a tighter necessary condition. In Table III we move to a reduced rank MIMO IBMAC-IC, and we evaluate the DoF of uniform system (N ul,l = N ul , N dl,k = N dl , d ul,l = d ul , d dl,k = d dl , r kl = r) with N dl = 4, N ul = 5, K dl = 4 and K ul = 2, for the different conditions established in [START_REF] Tibhirt | Distributed Beamforming Design in Reduced-Rank MIMO Interference Channels and Application to Dynamic TDD[END_REF] and the proper and sufficient conditions given by Theorem 3. In Table III we give different example than [START_REF]Interference Alignment in Reduced-Rank MIMO Networks with Application to Dynamic TDD[END_REF] in order to show that the previous conclusion mentioned in [START_REF]Interference Alignment in Reduced-Rank MIMO Networks with Application to Dynamic TDD[END_REF] are also true at different number of antennas. In the following we give the description of each element in Table III

(n F,d ,n G,d ) (1,2) (1,2) (2,0) (1,2) (2,0) (d c,dl ,d c,ul ,dc,tot) (5,4,28) (4,2,20) (3,1,14) (3,1,14) (3,1,14) (n F,c ,n G,c ) (1,2) (1,2) (2,0) (2,0) (2,0) (d r,dl , d r,ul , dr,tot) (5

VI. CONCLUSIONS

In this paper we address the IA feasibility in MIMO IBMAC-IC, thus by considering a full rank interference channel, we establish a sufficient condition for IA feasibility, that is written in terms of the problem dimension (number of UEs, number of antennas, and number of streams). This condition outperform the existing sufficient condition in [START_REF] Jeon | The Feasibility of Interference Alignment for MIMO Interfering Broadcast-Multiple-Access Channels[END_REF] in term of the feasible DoF region (combinations), to highlight this we provide a comparative table between our and the existing sufficient condition in the state of the art for IA feasibility in full rank MIMO IC. We propose also two conjectures, written in terms of the problem dimension, as a tighter necessary conditions for IA feasibility, and by numerical results, we show how much these conjectures are interesting since their results are very close to the necessary and sufficient condition given in Theorem 2. For the rank deficient MIMO IC we evaluate the DoF for a number of dimensions and compare the results between the proper conditions mentioned before in our previous work [START_REF] Tibhirt | Distributed Beamforming Design in Reduced-Rank MIMO Interference Channels and Application to Dynamic TDD[END_REF] including the centralized and distributed design, the zeroforcing in shared fashion or only considering Tx or Rx, and our sufficient condition given by Theorem 3, here we take another number of dimension than the one taken in [START_REF]Interference Alignment in Reduced-Rank MIMO Networks with Application to Dynamic TDD[END_REF] to confirm the observations given before in [START_REF]Interference Alignment in Reduced-Rank MIMO Networks with Application to Dynamic TDD[END_REF] regarding the rank of the MIMO IC for which the distributed method is interesting to be applied for the IA. The byproduct of our results is that the IA feasibility conditions that we provide are applicable to any MIMO interference network, for our system model as an example we consider the DynTDD interference network.

APPENDIX

Proof of Theorem 4: Diagonal Shift method For the ease of understanding of the following proof, we can divide J F and J G into sub-matrices J F k and J G k respectively, regarding the k th receiver, such as:

J =            J G1 J F1 0 0 0 J G2 0 J F2 0 0 . . . . . . . . . . . . J G K dl 0 0 0 J F K dl            (14)
For each receiver k ∈ [1, . . , K dl ], the matrices J F k and J G k are given by ( 15) and ( 16) respectively:

J F = T F k1 J T F k2 . . . J T F kK ul   T (15)
J G k =             J G k1 0 . . . 0

Fig. 1 :

 1 Fig. 1: DynTDD system model.

Theorem 2 .

 2 Necessary and Sufficient Condition for IA Feasibility in a Regular MIMO IBMAC-IC For a full rank MIMO IBMAC-IC, the DoF tuple (d ul,1 , ..., d ul,K ul , d dl,1 , ..., d ul,K dl ) is feasible almost surely if and only if J has full row rank.

  Number of combinations for different Sum DoF in a full rank interference channel, K ul = 2 and K dl = 3

, 4 ,

 4 28) (3,4,20) (3,1,14) (3,1,14) (3,1,14) (d t,dl , d t,ul , dt,tot) (5,4,28) (5,0,20) ( * * ) (5,0,20) ( * * ) (5,0,20) ( * * ) (5,0,20) ( * * ) (d T 3,dl , d T 3,ul , d T 3,tot ) (5,4,28) (4,2,20) (3,2,16) (3,1,14) (3,1,14)

  means that either the block matrix I d ul,l ⊗H ⊗I d dl,k in J F should be full row rank. The equation in (11) represents the tighter necessary version of the proper condition in (4). Conjecture 2. Tighter Necessary Condition for IA Feasibility in a Regular MIMO IBMAC-IC For full rank MIMO channels, if the tuple of DoF (d ul,1 , ..., d ul,K ul , d dl,1 , ..., d ul,K dl ) respects the proper condition of Theorem 1 and is feasible, then it may satisfy the following necessary condition:

	(2) kl in J G or the block matrix (H kl ) T (3)

TABLE II :

 II Number of combinations for different Sum DoF in a full rank interference channel, K ul = 2 and K dl = 3 ( * )

  , where a generic tuple (d dl , d ul , d tot ) denotes the uniform DoF of a DL UE, an UL UE, and the overall UL and DL sum DoF: • (d p,dl , d p,ul , d p,tot ) considering Theorem 2 in the centralized case, • (d d,dl , d d,ul , d d,tot ) considering the distributed method, with DL UE DoF as in [13, eq. (31a)], UL UE DoF as in [13, eq. (31b)] (with n F , n G in Table III optimized as n F d , n G d ), • (d c,dl , d c,ul , d c,tot ) considering the combined method, with DL UE DoF as in [13, eq. (26)], the UL UE as in [13, eq. (27)] (with n F , n G in Table III optimized as n Fc , n Gc ), • (d r,dl , d r,ul , d r,tot ) considering Rx side ZF only as in [13, eq. (26)] with n F = K ul , • (d t,dl , d t,ul , d t,tot ) considering Tx side ZF only as in [13, eq. (27)] with n G = K dl , • (d T 3,dl , d T 3,ul , d T 3,tot ) considering Theorem 3.

	r	0	1	2	3	4
	(d p,dl ,d p,ul ,dp,tot)	(5,4,28) (4,2,20)	(4,1,18) (3,1,14) (3,1,14)
			or
			(3,4,20)
	(d d,dl ,d d,ul ,d d,tot )	(5,4,28) (4,2,20) (1,4,12) (2,0,8) ( * * ) (0,4,8) ( * * )

TABLE III :

 III DoF per user as a function of the rank of any cross link channel with N ul = 4, N dl = 5, K ul = 2 and K dl = 4.

	( * * ) : the given DoF does not satisfy the conditions in (3).
	If negative DoF results from a formula, this DoF will be
	set to zero logically.
	The observations in [14, Table I] are always true in this
	case.

IEEE 27th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD)

ACKNOWLEDGEMENTS

EURECOM's research is partially supported by its industrial members: ORANGE, BMW, SAP, iABG, Norton LifeLock, and by the projects EEMW4FIX, CellFree6G (French ANR).

With l ∈ [1, . . . , K ul ], we have:

We prove here that for any system (N dl,k , N ul,l , d dl,k , d ul,l ) satisfying Theorem 4, the associated matrix J to this system can be transformed to a permutation matrix with a rank equal to the number of rows of J , i.e. J is a full row matrix, thus the IA is feasible. This transformation can be done following the coming steps acting on J F then on J G side, we call this proof as Diagonal Shift method:

• Building Diagonals on J F :

-First diagonal: On the given matrix J at J F , we choose the longest diagonal * * * from the 1 st element of J F1 and we put to zero the other elements in the rows including this diagonal, we note the number of elements of this diagonal as n 1 .

If n 1 is equal or smaller than the number of rows of J F1 , we set the variable sh to 0 or 1 respectively, -Second diagonal: We choose the longest diagonal from the element at the 1 st column and the (sh × d dl,2 + 1) th row of J F2 , i.e. the diagonal is shift down by sh × d dl,2 elements. We put to zero the other elements in the rows including this diagonal. We note the number of elements of this diagonal as n 2 . If n 2 is equal or smaller than the number of rows of J F2 , we don't increment sh or we increment by 1 respectively, . . .

-K th dl diagonal: We choose the longest diagonal from the element at the 1 st column and the (sh × d dl,K dl + 1) th row of J F K dl , i.e. the diagonal is shift down by sh d dl,K dl elements.We put to zero the other elements in the rows including diagonal.

• Choosing elements from J G :

The following process is done for each k ∈ [1, . . . , K dl ]:

is smaller than the number of rows of J F k noted as m k , we work on the m k -n k remaining rows of J that don't include element from the previous chosen diagonals on J F k .

For those rows, we choose m k -n k elements from J G k . The column and row of each chosen element should be different from each other and also different from the previously selected element in J G1 , . . . , J G k-1 . * * * : Our longest diagonal should take n elements for a matrix A ∈ (m × n) with m ≥ n, it begins always at the 1 st column of A:

• If the diagonal begins at the i th row with i ≤ (mn + 1), the diagonal will end at the n th column and the (i + n -1) th row; • If the diagonal begins at i th row with i > (m-n+1); the diagonal will be stopped at the (m-i+1) th column and the m th row and goes forward from (m -i + 2) th column and the 1 st row.


Pierre Zembri

CONNECTION MANAGEMENT BETWEEN NEW HIGH-SPEED RAIL SYSTEM AND EXISTING RAILWAYS IN EUROPE : THE FRENCH EXCEPTION

Introduction

The main event concerning the european railways for the 15 last years has been the emergence of high speed trains, mainly running on a new and specialized infrastructure, but compatible with the pre-existing railway lines. Initially designed as a technical solution for situations of congestion, high speed had furthermore influence upon the purpose, the use, and the image of railways in an unfavourable context. Moreover, high speed train impact is not only limited to the railways network : it changes relationship between network and territory. It is supposed to produce structuring effects that place high speed transportation in the heart of several town, regional and national planning policies. Stations become again a major centre of interest for urban designers.

This paper focuses on the different ways of management of the interface between the new lines, the "old" railways, the other modes of transport and the territory. The French case singularity is the juxtaposition of numerous more or less outstanding solutions, that can now be compared with connection policies runned in other european countries.

From line to network

High speed rail in Europe is the fruit of many years of struggle against competing modes, and especially against domestic airlines. As people mobility was constinuously increasing, producing more potential customers, railway companies were paradoxically focusing their commercial investment on businessmen fond of high performance in the best conditions : high speed, a little number of stops, etc. An example of this commercial policy is the "Trans Europ Express" (TEE) network, created in 1957, and joining between them all the main towns without any stop at the border-crossing points.

However, existing lines couldn't afford more traffic, and creating new inter-city trains was only possible if other trains were cancelled. A coexistence problem emerged between trains running at very heterogeneous speeds, from freight trains (80 km per hour) to TEE and intercity fast trains (up to 200 km per hour). It appeared that building new lines devoted to high speed passenger trains was necessary. It also appeared that a new rolling stock, fitted to more favourable routes, had to be designed.

The european solution, very different from the japanese one, is a perfect technical compability between existing and new lines, in order to avoid the building of new infrastructures in an urban context. Existing electrified lines can also be used beyond the new lines.

French "TGV" has been designed in 1967 by the SNCF Research Department under the project name "C03". Its main purpose was to relieve the pressure on the Paris -Lyon line, hardly perfectible and enduring a heavy traffic. At this time, no one was thinking about any new network : the TGV would be a fast intercity shuttle. Governmental approbation has been given only in 1974, provided that the operator put up the money for the whole project. This bet on the future became a huge commercial success (the investment has been paid back by additional receipts in ten years !).

The undeniable success of the first high-speed train line, profitable, attracting new customers formerly airlines users or car users, developing mobility on the axis Paris -Lyon ( 1) , led in 1984 to substantial changes in the TGV approach :

-new operating methods : the fast intercity shuttle gives place to a real network based ont the new line, covering the southeastern part of France, in order to generalize the high-speed effects to a large number of towns (including little ones like Montélimar or Montbard)(fig. 1). Compatibility of the high-speed trains with classical infrastructures is a great advantage ; -construction of two others new lines is decided : the "Atlantic" line to the western and southwestern parts of France and the "North-Europe" line to Belgium and Great-Britain (through the Channel Tunnel). There is a willingness to cover the most important part of the territory ; -junction (2) of the three new lines by a short link crossing the eastern part of the parisian region, and serving peripheral polarizations like Charles de Gaulle Airport or Disneyland Paris.

The State plays a major role in the network development, financing even 30% of the "Atlantic" new line. In fact, TGV is progressively considered and used as a planning tool. This evolution results in the adoption of a national plan for new high-speed train infrastructures (3) (fig. 2). 11 lines departing from Paris and two cross-country lines (Rhine-Rhone and Bordeaux-Narbonne) would be built. In fact, the 21 metropolitan regions would be concerned, following territorial equity rules, provided that the financing is possible.

At the same time, as other high-speed train projects appear in other countries (Italy, Germany, Spain, etc.), the European Community brings out its own plan, laying stress on desirable connections between neighbouring networks (the "missing links"). International agreements are signed for the first international new lines (Paris-London / Brussels, Lyon -Torino, Montpellier -Barcelona, etc.). The favourable geographic position of France in Europe confers a major role in international connections.

High-speed tends to become the reference level in train services in Europe. As the new lines change seriously accessibility conditions along the axis served, the other regions, considering that they comparatively suffer from their situation, demand other news lines, as they use to demand new motorways since decades, in order to be "opened up".

French high-speed train, a misused planning tool ?

Is it possible to make the development of fast and direct intercity train services compatible with the servicing of intermediary areas, which formerly enjoyed a classical train service ? It depends on the willingness of different actants and on the outcome of the inevitable balance of power between them :

-The operator argues about financial aspects : customers travelling on the longest distances

(1 ) -The number of train users between Paris and Lyon has been multiplied by 2,9 between 1980 and 1990 (Beauvais, 1992).

(2) -And not "interconnection", so called by numerous authors, following the initial terminology of SNCF (which talks about "TGV-Junction" since 1993) : only one operator is concerned.

(3) -"Schéma directeur national des infrastructures ferroviaires à grande vitesse". are more profitable. So they have to be favoured, to the detriment of users living in intermediary areas. Maintaining a double-oriented supply (TGV + classical trains) is too costly, and high-speed trains cannot stop as frequently as other trains ; -The State stands up for a territorial equity principle : the new network has to be profitable for the whole country, and all the network users. This principle justifies significant subsidies for numerous lines in deficit. Moreover, regions intervene in public transport services financing beside the State (in France, Italy, Germany and Spain) ; -The users (frequently defended by their local elected representatives) ask anyway for the preservation of the previous supply (considered as an "acquired right").

In the French case, the State stayed back, only worrying about the new infrastructures layout, and letting SNCF do its own way. So, the operator manages the TGV in a pure commercial way, since it has opened the first line. On Paris -Lyon, priority has been given to travels from one end to one other, and the only two intermediary stations stem from a "compromise solution between the operator's logic and the concerned local communities" (4) . Later, the same conception prevailed, connections being limited to the bare minimum.

The effects of this policy have been negative for three kinds of lines :

-the previous main lines, followed by a new high-speed infrastructure (Paris -Dijon, Paris -Le Mans, Paris -Tours, Paris -Lille) : most of the long-distance trains enjoyed by the intermediary areas inhabitants have been replaced by direct TGV. The average travel duration to Paris and the service quality have been debased for some towns like Chartres or Amiens ; -some lines, not parallel to a new infrastructure, but suffering from the competition with a combination of two high-speed train lines via Paris area. Long-distance traffic is captured by TGV using different and longer routes, but saving time compared with classical trains using the shortest route (fig. 3). Are in this situation some cross-country lines like Lyon -Tours -Nantes (TGV use successively the South-East and the Atlantic new lines, saving one hour (5) ) but also radial lines like Paris -Brive -Toulouse (TGV use Atlantic new line and go through Bordeaux), or Paris -Amiens -Calais (TGV use North-Europe new line and go through Lille). All these lines are disadvantaged by the loss of an important part of their traffic. Moreover, long-distance trains cancelled are not replaced by other services for evident financial reasons.

-the classical lines used by TGV in continuation of the new high-speed infrastructure suffer from the cancellation of numerous stops, in order to save time for long-distance travels. Passengers formerly using long-distance trains for short intercity journeys (they had no choice) are disadvantaged. In other words, TGV replace previous classical trains without servicing all intermediary towns with the same quality. There has been lots of demonstrations at the beginning of TGV-Atlantic services, especially along the two main lines of Brittany (Rennes -Brest and Rennes -Quimper), where numerous little towns had (4) -"compromis entre la logique de l'exploitant et celle des collectivités concernées", BEAUCIRE & EMENGARD, 1985.

(5) -The cost of the hour saved is high : travellers pay the priced based on the real mileage (200 additional kilometers) lost up to the half of the previous servicing ! Inhabitants and local elected representatives forced TGV to stop at the neglected stations, occupying every day the tracks. In some cases, the operator had to restore some stops.

Being free to organize the servicing in the most convenient way for itself, the SNCF took without any control decisions having significant repercussions on territories accessibility. And these outcomes are not positives in all cases : the "reducing effect" (effet réducteur) linked to high-speed train is only perceptible between large geographical centres of attraction. There will be by comparison a "distancing effect" (effet distanciateur) for little or mid-sized towns playing a local or regional role, and situated in the sphere of influence of large cities (7) . Giving greater importance to certain kinds of trips, and refusing to extend TGV effect to the largest area, the SNCF favoured a few large towns, and penalized a large number of the other cities.

Some dissimilar options of connection

Coexistence between TGV and "old" railways becomes problematical. The main reason why is that the increase in the number of new high-speed infrastructures tends to make TGV more and more autonomous vis-à-vis the classical network. Management of the relationship between them reveals the initial bias concerning the purposes of high-speed train network : is it considered as a revitalization tool for the whole train network (including high-speed and normal speed lines) or a new network developed to the detriment of the existing one ?

Countries as Germany or Italy have chosen the first option : the overlapping of the two kinds of infrastructures is complete. New infrastructures admit high-speed trains and other ones : intercity trains (up to 200 km per hour), and even freight trains during the night can also save time, even for a short mileage (there is an interchange every 40-50 km in average). Symmetrically, high-speed trains (the ICE in Germany, the "Pendolino" in Italy) can leave temporarily their specific line in order to serve intermediary-located towns. In short, highspeed effects are generalized to the maximum number of links, even those using very partly the new lines.

The French way is very different : new lines are rarely connected to the classical railway network, even if the two infrastructures are parallel one to the other. Connecting services depart only from large towns, provided that high-speed trains don't stop at a peripheral station only accessible by car. New infrastructures are completely dedicated to the TGV, and there are a very few interchanges between the two networks. French railways think that leaving the new lines in order to serve the central stations induce an unacceptable loss of time, provoking (according to the company) a loss of customers. Creating new peripheral stations on the new infrastructures limit the waste of time, and don't discourage long-distance travellers (the most lucrative ones).

Stations built on the new infrastructures in France can be allocated among three categories : 4.1. "Gares-bis" (paripheral stations dedicated to the TGV) : these stations located near midsized towns, are served a few times a day. The low level of service (provoking a alow level of use) don't permit the building of a public transport link between the new peripheral and the central stations. There are now 13 peripheral stations planned along the different new lines to be built (fig. 4), and a "gare-bis" runs since 1982 in Mâcon-Loché, with a very weak success.

"

Opening-up stations" (Gares de désenclavement) : This kind of new stations is justified by a poor-quality (even impossible) previous service, the TGV route offering a new opportunity (it doesn't follow every times the habitual corridors). For instance, the new line joining Paris to Lyon, taking the quickest way across the Morvan massif, offers to the Creusot-Montchanin-Montceau les Mines conurbation (110 000 inhabitants) a significant opportunity (now 1 hour from Paris, 4 hours before the building of the new line), coming at the right moment (a huge crisis of local traditional activities). Another interesting example is the new station of Vendôme, on the Atlantic new line. Vendôme is a little town located between the Paris -Orléans -Tours and the Paris -Brittany axis, not so far from Paris (120 km) but with a very weak level of train service (it takes 2 hours to reach Vendôme from Paris by classical train). The travel duration is now 40 minutes since the opening of the TGV line. Other "opening-up" stations are planned along the future East and Mediterranean lines, but, that is new and... strange, in rural areas (8) 4.3. New stations as exchange nodes : Established in the peripheral areas of the two most important cities, Paris and Lyon, their purpose is to connect the high-speed train network with other transport modes operated at different scales (regional train networks, intercontinental airlines), and sometimes with large scale amenities generating mass mobility. Each exchange node have to energize and to structure his neighbourhood in order to confer to this area a kind of autonomy vis-à-vis of the central part of the town. These stations are located on high-speed junction links ; therefore they will play in the future a significant role in the emergence of an autonomous high-speed network. In the particular case of the Île-de-France (the Parisian region), they will permit the generalization of the TGV-effects to the whole regional territory, and they will offer (provided that there will be a high-level of service) a clever alternative to the transit through the central stations, which are saturated. Five of the six planned stations will be in the Parisian region : Massy-Palaiseau, Roissy Charles de Gaulle Airport, Chessy-Disneyland Paris (all of these three stations are now in operation), Cergy-Pontoise and Melun-Sénart (only planned). The three last stations are (or will be) located in new towns, in order to give them some more attractivity. The sixth station, Lyon-Satolas Airport, opened in 1993. A seventh exchange node could be created in the business pericentral pole of La Défense.

The connection process between TGV and airlines has been outstandingly fast : there was in the interest of the airport managers, the French Railways and the French national airlines (Air France), in a highly-competitive context, to reach an agreement in order to raise the level of attractivity of the two airports, directly connected to an european high-speed train network. The adoption of a Global Distribution System (called "Socrate") derived from American Airlines one, and perfectly compatible with the major ones, can be linked with this process of connection.

(8) -Jean VARLET detects in this evolution a third phase in the localization of new TGV stations, after the "TGV in the heart of the town" and the "TGV in urban peripheral areas". There is now a "rural TGV". "La ligne nouvelle évite tout contact urbain, passant loin des têtes de ligne, au point que des bretelles de raccordement sont nécessaires pour atteindre Amiens, St-Quentin, Reims, Metz, Nancy et même Strasbourg. À ces embranchements en plein milieu rural seront installées des garres TGV affublées du titre trompeur de «gare régionale» («Champagne-Ardennes», «Alsace», «Lorraine»)". (Varlet, 1992)

Conclusion

As connections between high-speed train services, other train services and other transport modes are well-organized in the towns, provided that they are served by central stations or peripheral exchange nodes, the quality of the networks/territory interface in the intermediary areas is more irregular. This is shown by the attached typology (fig. 5), worked out at the European level, and presenting the different ways to serve a town localized along a new high-speed line.

(7) -"L'«effet réducteur» lié au TGV n'intervient qu'entre grands pôles géographiques. Il sera aussi par comparaison effet distanciateur pour les villes locales ou régionales, parfois importantes, situées dans l'aire d'influence des grands pôles urbains", Francis BEAUCIRE, 1992.


Abel A Silva

Ground-based total ozone column measurements and their diurnal variability

Three Brewer spectrophotometers were set up in three tropical sites of South America (in the Bolivian Altiplano and seashore and biomass burning areas of Brazil) to measure the total ozone column (TOC). Only TOC measurements with uncertainties ≤1% (1σ) were considered. Typically, the standard deviation for the diurnal sets of measurements was predominantly ≤1% for two of these sites. The average variability in TOC ranged from 6.3 Dobson units (DU) to 16.8 DU, and the largest variability reached 54.3 DU. Comparisons between ground-based and satellite (Total Ozone Mapping Spectrometer (TOMS)) data showed good agreement with coefficients of determination ≤0.83. However, the quality of the ground-based measurements was affected by the weather condition, especially for one of the sites. Visual observation of the sky from the ground during the measurements with one of the Brewers added to the satellite data of reflectivity and aerosol index supports that statement.

Introduction

[2] The ozone in the Earth's atmosphere results from the balance between production and destruction in photochemical mechanisms fed by the solar radiation. The dynamics of the air masses contribute to the varying amounts of ozone in the atmosphere, and the interannual and seasonal variations of this gas follow patterns with latitudinal dependence [START_REF] Whitten | Ozone in the Free Atmosphere[END_REF]. The potential effects of the anthropogenic action on the atmospheric ozone have stimulated the research on ozone in the last 50 years. Measurements of the total ozone column (TOC) have been analyzed in many studies [START_REF] Silva | A quarter century of TOMS total column ozone measurements over Brazil[END_REF][START_REF] Fioletov | An assessment of the world ground-based total ozone network performance from the comparison with satellite data[END_REF].

[3] The investigation into the diurnal variability in TOC (TOC var , or the difference between the maximum and the minimum values of TOC in the period) has been made by several studies depicted in Table 1. Diurnal changes of up to ≈40 Dobson units (DU) were reported for different environments in the Northern Hemisphere. A few percent of variability in TOC (≈1%) in the diurnal period has been reported in general [START_REF] Whitten | Ozone in the Free Atmosphere[END_REF]. However, the influence of clouds and aerosols on TOC measurements leads to lower quality results and higher values of TOC var [START_REF] Brogniez | Ozone column retrieval from solar UV measurements at ground level: Effects of clouds and results from six European sites[END_REF].

[4] In this work, a monthlong campaign was conducted in three different environments in South America using three Brewer spectrophotometers simultaneously: one in central Brazil during the biomass burning season, another in the northeast coast (seashore) of Brazil, and another in the Bolivian Altiplano. One of the goals of the campaign was to measure the TOC var within the diurnal period. TOC data from Brewers and the Total Ozone Mapping Spectrometer (TOMS) were compared. In addition, TOMS data of reflectivity (R PC ) and aerosol index (AI) were used in the analysis of the influence of the weather condition on ground-based TOC measurements. The visual inspection of the sky was conducted in one of the sites in order to support the analysis.

Sites and Instruments

Site Description

[5] Ground-based measurements using Brewers were held simultaneously in Campo Grande (CG, 20.44°S, 54.65°W, 532 m above sea level (asl), 8093 km 2 , Brazil), Natal (Na, 5.79°S, 35.21°W, 30 m asl, 167 km 2 , Brazil), and La Paz (LP, 16.49°S, 68.15°W, 3640 m asl, 3240 km 2 , Bolivia). These three cities are capitals (state or national) with about 850,000 inhabitants. CG's economy is devoted to the rural activities of the agro-business in central Brazil. Its rainy and dry seasons extend from November to March and from May to September, respectively. The dry season is marked by biomass burning episodes where huge amounts of aerosols and gases are released to the atmosphere by the fire in the dry vegetation. Na is located in the Northeast coast of Brazil, where tourism represents one of the main economic activities. The breeze from the Atlantic Ocean (the Alisios winds) blows over the region and represents a source of clean air with marine aerosols. Rainy and dry seasons in Na extend from February to August and from September to January, respectively. LP is the capital of Bolivia and is located in a valley in the Andes within the region called the Altiplano. Despite its location in the equatorial zone, LP has a subtropical climate of altitude caused by the altitude of the Altiplano. Snowy mountains are seen constantly across

The Brewer Spectrophotometer

[6] The Brewer spectrophotometer (SCI-TEC Instruments Inc., Saskatoon, Canada) uses the sunbeam in a direct Sun (DS) measurement to obtain the amount of TOC. The solar radiation is admitted into the instrument's foreoptics (field of view of nearly 2°) composed of collimators, shutters, neutral density filters, focal lens, and a grating of 1200 lines/mm that selects five wavelengths (with resolution of 0.6 nm full width at half maximum) in the ultraviolet B (UVB) range to be counted by a photomultiplier tube. A routine setup in a personal computer controls the instrument's operation and processes the UVB counts to determine the TOC measurement. This value is the average of five TOC values obtained in five consecutive DS measurements (which take about 3.5 min to be completed) followed by the corresponding standard deviation (herein just called the uncertainty of TOC). The accuracy and precision of each TOC value from one DS measurement are estimated to be ±2.5% and ±0.25%, respectively [START_REF] Kerr | Total ozone measurements made with the Brewer ozone spectrophotometer during STOIC 1989[END_REF]. The TOC measurement depends on the consideration of a representative temperature for the atmosphere, which defines the effective ozone absorption coefficients of UVB radiation to be input in the Brewer's routine to obtain the amount of TOC in the atmosphere. An annual calibration based on certified UVB sources and daily procedures to check the calibration and operation of the instrument must be assured. In general, TOC measurements from Brewers are assumed to be of good quality if their uncertainties are ≤1% (1σ) [START_REF] Fioletov | An assessment of the world ground-based total ozone network performance from the comparison with satellite data[END_REF].

The TOMS Instrument

[7] The Total Ozone Mapping Spectrometer (TOMS) was an instrument carried by three satellites (Nimbus 7, Meteor 3, and Earth Probe) sponsored by the National Aeronautics and Space Administration (NASA) from 1978 to 2004. Each satellite provided TOMS with 13-14 synchronous polar orbits around the Earth daily. Measurements (35 times every 8 s by scanning in the perpendicular direction to the satellite orbit) of the solar radiation backscattered by Earth (surface and atmosphere) at wavelengths from 310 nm to 380 nm were obtained. Wavelengths at 317 nm and 331 nm were input into the TOMS routine (Version 8) to produce daily TOC values averaged within 1°× 1.25°grids (latitude × longitude, area of ≈12,500 km 2 at low latitudes). TOMS also used wavelengths in the range of 330-380 nm to produce other atmospheric parameters like R PC and AI [START_REF] Herman | UV 380 nm reflectivity of the Earth's surface, clouds and aerosols[END_REF][START_REF] Hsu | Comparisons of the TOMS aerosol index with Sun-photometer aerosol optical thickness: Results and applications[END_REF].

Methods

[8] Three Brewer spectrophotometers were set up in three South American sites to operate simultaneously in a campaign from 28 July to 25 August 1999. The campaign was sponsored by the Laboratório de Ozônio of the Instituto Nacional de Pesquisas Espaciais [START_REF] Silva | A espessura óptica de aerossóis na banda do UV-B[END_REF][START_REF] Silva | Calmness of the aerosol layer in the atmosphere during biomass burning episodes[END_REF]. Brewers were set up as follows: Brewer MKII #056 in CG, Brewer MKIV #073 in Na, and Brewer MKIV #110 in LP. The same schedule was arranged for the three instruments to provide TOC values through DS measurements at solar zenith angles (SZA) ≤60°( air masses ≤2). At noon time (≈11:00-13:00 local time), the instruments were scheduled to take other types of measurements. The diurnal set of measurements of TOC and its variability (TOC var ) were analyzed individually and in comparisons using data from the sites and TOMS. Mercury lamp calibration tests were made routinely for each Brewer during the campaign to ensure the correct alignment of the instrument's foreoptics.

[9] According to [START_REF] Herman | UV 380 nm reflectivity of the Earth's surface, clouds and aerosols[END_REF], the parameter R PC is drawn from the Lambert Equivalent Reflectivity (LER) that combines the fraction of sky covered by clouds, the optical depth of clouds, and their height to be associated with the solar energy reflected to the space. Typically, R PC is in the range of 2%-8% for land covered by green vegetation, urban constructions, and sand or water reservoirs (lakes, seas, and oceans). Above that limit and up to about 80%, R PC is proportional to the cloud cover. However, large areas covered by desert sand and snow can augment this parameter significantly, representing a false estimation of cloud cover. Another interesting parameter is the AI defined by [START_REF] Hsu | Comparisons of the TOMS aerosol index with Sun-photometer aerosol optical thickness: Results and applications[END_REF] as a measure of the reduction in the Rayleigh scattered radiation in the atmosphere from the attenuation by aerosols in relation to the amount that would be scattered in a pure atmosphere. Absorbing and nonabsorbing aerosols yield positive and negative values of AI, respectively. However, absorbing aerosols within the boundary layer can lead to negative values due to the prevalence of the Mie scattering over the Rayleigh one in this region. Both parameters, R PC and AI, were used in the analysis of TOC measurements from Brewers to provide information on the weather condition during the campaign. In addition, visual observations of the sky were conducted in CG for the DS measurements to guide the analysis of the TOC measurements.

Results and Discussion

Weather Observation in CG

[10] According to [START_REF] Brogniez | Ozone column retrieval from solar UV measurements at ground level: Effects of clouds and results from six European sites[END_REF], clouds affect the value and the uncertainty of TOC measurements. Therefore, the observation of the weather condition (or the sky) during DS measurements represents a crucial point to understand the obtained values of TOC. In general, a successful DS measurement is obtained through a direct sunbeam free of clouds. However, the presence of clouds in the sky can affect the measurements even if the clouds are not blocking the sunbeam reaching the instrument on the ground. The observation of the sky in the 1999 campaign was provided for each and every DS measurement in CG, where the sky was described in terms of both clouds blocking the sunbeam reaching the Brewer and clouds in other parts of the sky. The presence of smoke and aerosols in the atmosphere of CG was also reported.

[11] Table 2 shows for each site the number of days of campaign (ND), the total number of TOC measurements (MDS), and the number of these measurements that resulted in TOC values with uncertainties ≤1% (MDS 1% ). For CG, 88% of the MDS were MDS 1% , where 435 measurements had occurred under cloudless skies and 370 under cloudy ones. From the latter, 103 measurements had clouds blocking the sunbeam that were generally optically thin and tiny clouds of the genera cirrus and altocumulus or the fractus form type. On the other hand, 16 measurements among the 105 ones with uncertainties > 1% occurred under cloudless skies. These numbers are summarized in Figure 1 in terms of the distribution of cloud genera during TOC measurements in CG. They are not only evidence of the interference of clouds in the measurements but also proof of the complexity of the matter. A link between TOC measurements of uncertainties ≤1% (good quality) and cloudless scenarios was also found by [START_REF] Silva | Total ozone column measurements for an urban, tropical site in the Southern Hemisphere with a Microtops II[END_REF] using a handheld ozone monitor Microtops II (MII, Solar Light Co., Inc., Glenside, U.S.). It seems that the presence of clouds can introduce variations in the amount of UVB radiation admitted into the instrument's foreoptics.

[12] There was no observation of the sky for the two other sites during the campaign. However, we can use the observations in CG as a guide in the interpretation of the data from those sites. Na had 49% of its measurements as MDS 1% , and LP made a higher amount of 75%. It was dry season for LP and CG, while Na was in the final stages of its annual rainy period. Therefore, it is reasonable to expect a higher occurrence of clouds at Na than at LP. The TOMS data of AI and R PC can help in the analysis. Figure 2 shows the daily values of AI and R PC . The AI had similar average values for CG (0.49 ± 0.57) and Na (0.47 ± 0.22), but a lower value was obtained for LP (0.15 ± 0.15). The similarity between the values for CG and Na comes out probably from the preponderant presence of aerosols in these sites in that period: CG was in the middle of the biomass burning season in central Brazil [START_REF] Silva | Calmness of the aerosol layer in the atmosphere during biomass burning episodes[END_REF][START_REF] Reid | Physical and optical properties of young smoke from individual biomass fires in Brazil[END_REF]], while Na is a seashore site in the equatorial zone where the atmosphere is abundantly fed with marine aerosols brought by the ocean breeze. On the contrary, LP is in the limits of the boundary layer tending to present a cleaner atmosphere that explains the smaller values of AI. The average R PC was smaller than 8% for CG (6.2 ± 4.2%), where many days of cloudless skies had been observed, while similar values were obtained between Na (15.6 ± 9.2%) and LP (14.2 ± 9.9%). This suggests the occurrence of similar amounts of cloud cover in that period at both Na and LP. However, there are two facts that must be taken into consideration: (i) The Bolivian Altiplano is thousands of meters above sea level; thereby, peaks and mountains surrounding the valley where LP is located can be constantly snowy, especially in the winter months of the campaign. (ii) The grid of TOMS data represents a large area (a radius of ≈63 km would be obtained if the grid were taken as a circle), and many snow-covered areas can be included within the grid referring to LP. In this case, the average R PC of 15.6% for LP is likely to be an augmented value contaminated by the presence of these areas around the site. Then, the correct value of R PC is likely to be lower than the obtained one. This argument supports the 75% of MDS 1% for LP in relation to the 49% for Na.

The TOC Values From the Campaign

[13] Only TOC values considered as good quality measurements (uncertainties ≤1%) were adopted for the analysis herein. Figure 2 shows the daily average values of TOC for the sites, while Table 2 shows the average values of TOC for the whole period of the campaign. These values and their day-to-day variability are regular and typical [START_REF] Silva | A quarter century of TOMS total column ozone measurements over Brazil[END_REF][START_REF] Whitten | Ozone in the Free Atmosphere[END_REF]. The average TOC for LP is about 6% lower than the values for CG and Na. This difference is explained by the higher altitude of LP in relation to the two other sites.

[14] Figure 3 shows some sets of TOC measurements that were selected by taking into consideration the association between a lower standard deviation (in percentage, TOC sd% ) for the diurnal average TOC and a significant amount of MDS 1% . The values of TOC var for these cases were 1.2% (3.2 DU) in 27 MDS 1% for CG, 0.9% (2.4 DU) in 7 MDS 1% for Na, and 1.9% (5 DU) in 30 MDS 1% for LP. Note that the low number of MDS 1% for Na reflects the likely influence of clouds yielding poorer results, since the number of good quality measurements per day depends on the weather condition. TOC measurements for day of year (DOY) 218 in CG had cloudless skies in the morning and cloudy skies in the afternoon with predominance of cumulus. This scenario probably yielded the larger uncertainties indicated by the error bars in the afternoon measurements. In addition, the turbidity seen in the skies was an evidence of an atmosphere burdened by aerosols from the biomass burning fires in the region, which can also add some influence through the increase of stray light in the DS measurements [START_REF] Silva | Aerosol optical thickness from Brewer spectrophotometers and an investigation into the stray-light effect[END_REF]. However, further investigations must be conducted in relation to the effective influence of aerosols on TOC, especially because that influence can depend on parameters like the aerosol optical depth and the aerosol composition and can overlap with effects caused by clouds [START_REF] Silva | Total ozone column measurements for an urban, tropical site in the Southern Hemisphere with a Microtops II[END_REF][START_REF] Silva | Calmness of the aerosol layer in the atmosphere during biomass burning episodes[END_REF].

[15] The average period for the realization of the measurements varied from 6.5 to 7.5 h, with an interval of about 2 h at noontime. This is shorter than the elapsed time for the measurements in the works of Table 1, but it represents a significant part of the diurnal period. TOC var and TOC sd% for the sites are shown in Figure 4. TOC sd% for CG and LP was typically under 1% or the same amount as the uncertainties for good quality measurements of TOC. Therefore, it is not possible in these cases to identify whether the diurnal variability in TOC was real or simply reflected the uncertainty of the measurements. However, sets of measurements with TOC sd% > 1% occurred for two DOYs (224 and 236) for LP and six DOYs (209, 224, 226, 230, 233, and 234) for CG. On the other hand, Na had all sets of measurements with TOC sd% > 1% (the only exception was DOY 232), which represent a significant variation in TOC. TOC var ranged from 2.7 DU to 54.3 DU with an average of 9.3 ± 10.9 DU for CG, from 2.4 DU to 40.4 DU with an average of 16.8 ± 7.7 DU for Na, and from 3.4 DU to 10.3 DU with an average of 6.3 ± 1.5 DU for LP. The 54.3 DU value is higher than the values found in Table 1 and corresponds to ≈20% of the average TOC value for that DOY in CG. However, the average TOC var for LP is similar to the one obtained by [START_REF] Kerr | Total ozone measurements made with the Brewer ozone spectrophotometer during STOIC 1989[END_REF] (6.6 ± 2.4 DU) in Table Mountain, which is also a high altitude site like LP.

[16] The weather condition, or the presence of clouds in terms of cloud cover, seems to be the main aspect modulating the amounts of MDS 1% , which are shown for each set of measurements for each site in Figure 4 (top). The average values for the amounts of MDS 1% were 28 for CG, 14 for Na, and 22 for LP. These numbers support the assumption of lower amounts of cloud cover for CG and LP in relation to Na. The influence of plumes of smoke and aerosols in the measurements is a likely effect, although no direct evidence of it had been observed in CG. However, the occurrence of the 16 TOC measurements with uncertainty > 1% under cloudless skies could result from the influence of aerosols. In addition, the largest values of TOC var in CG on DOYs 209, 224, and 234 were reported with lower values of cloud cover (or no cloud cover at all) and a significant amount of smoke and aerosols in the atmosphere from biomass burning fires.

[17] In addition to many sets of measurements having TOC var similar to the uncertainties of good quality measurements, there was also no trend apparent in the variation of TOC along the day (from morning to afternoon) for CG and LP. The only significant variations were found for the three highest TOC var for CG. On the other hand, 47% of the sets of measurements for Na showed significant diurnal increases in TOC.

Comparing TOC Measurements From Brewers and TOMS

[18] The daily TOC values from TOMS (TOC T ) were compared with the diurnal average TOC values from Brewers (TOC B ) using linear fittings. The results are depicted in Table 3. There was good agreement between CG and LP with coefficients of determination (r 2 ) of fair (0.68) and very good (0.83) values, respectively, in addition to the relatively low values of ≈13% for the percentage scattering of points (SD%). These parameters reflect linear fittings (TOC T = a + bTOC B ) of good quality with coefficients a and b close to 0 and 1, respectively. On the other hand, the linear fitting for Na was of very poor quality, with low r 2 , large SD%, and values of a and b quite disconnected from the good pattern. The main reason for this is the likely influence of clouds on Brewer #073's measurements, which is supported by the low percentage (49%) of MDS 1% for the site.

Conclusions

[19] TOC measurements from Brewer spectrophotometers were obtained simultaneously at three South American sites in the tropics. Their diurnal variability was investigated taking into consideration the presence of clouds and aerosols. The most elevated site (LP) showed the lowest diurnal values of variability, with a maximum TOC var of 10.3 DU and an average of 6.3 ± 1.5 DU (1σ) for an average TOC value of 256.9 ± 6.8 DU. The site in the biomass burning area (CG) presented a TOC var of up to 54.3 DU, with an average of 9.3 ± 10.9 DU and an average TOC value of 274.1 ± 7.2 DU. The site in the seashore (Na) showed a TOC var of up to 40.4 DU, with an average TOC var of 16.8 ± 7.7 DU (the highest one) and an average TOC of 271.7 ± 5.5 DU. In general, the standard deviation associated with the diurnal variability in TOC was less than 1% for LP and CG.

[20] Apparently, clouds affect the ground-based measurements, lowering the quality of measurements, since the higher the presence of clouds, the lower the number of MDS 1% measurements. CG and LP, which were in the dry season, had 88% and 75% of MDS 1% , respectively, while Na in the rainy season had only 49% of measurements with such a status. In addition, data for LP and CG matched quite well with satellite data, while for Na, poor results were obtained in the same comparison. The advantage of obtaining TOC measurements from the ground under cloudless scenarios was evident. On the other hand, the data in this work do not provide a conclusive evidence of the influence of aerosols on the ground-based measurements of TOC, although the highest value of TOC var = 54.3 DU had been obtained in the biomass burning site, which suggests the need for a more detailed investigation.

[21] Acknowledgments. This study was financially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, grant 471159/2004-2 and other grants), Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG, CRA APQ 0848-5.02/07), and Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP), and received logistic support from PUC Minas.

Figure 1 .

 1 Figure1. Occurrence of TOC measurements with uncertainty ≤1% (MDS 1% ) and uncertainty > 1% (MDS À MDS 1% ) in CG and the corresponding status of the measurements regarding the Sun as blocked or unblocked by clouds, and the presence of clouds in the sky (cloudless and cloud genera of cumulus (Cu), cirrus (Ci), altocumulus (Ac), and fractus forms).

Figure 2 .

 2 Figure 2. Daily average values for (top) TOC ± 1σ, (middle) AI, and (bottom) R PC for the three sites in the campaign.

Figure 3 .

 3 Figure 3. Sets of TOC measurements for CG, Na, and LP. Figures beside each set of data are the diurnal average of TOC and the day of year (DOY). Uncertainties are 1σ.

Figure 4 .

 4 Figure 4. (top) TOC var for the 1999 campaign. Figures at the top of the columns refer to the number of MDS 1% . (bottom) Percentage standard deviation for the average TOC.

Table 1 .

 1 Studies on TOC var

		a
	Work	Site	Coordinates	Date	Instrument	Time	TOC var (DU)
	Subbaraya et al. [1994]	Thumba	8.52°N, 76.85°E, sea level	10/3-23/5 of 1990	Brewer	7:30-17:30 LT	4-12
	Kerr and McElroy [1995] Table Mountain 34.38°N, 117.70°W, 2286 m asl 20/7-1/8 of 1989	Brewer	7:30-18:30 LT	≈5-14
	Raj et al. [2004]	Pune	18.53°N, 73.85°E, 559 m asl	5/1998-5/2003	Microtops II	7:30-17:30 LT	≈10-18
	Ganguly et al. [2006]	Rajkot	22.30°N, 70.80°E, sea level	6/2004-6/2005	Microtops II	10:30-16:30 LT	≈20-40
	Aculinin [2006]	Chisinau	47.00°N, 28.82°E, 205 m asl	7/2003-8/2005	Microtops II	6:00-15:00 UT	15-20
	Antón et al. [2010]	Madrid	40.45°N, 3.72°W, 680 m asl	1/1999-12/2003 Brewer MKIV #070 7:00-17:00 UT	10-20
	Petkov et al. [2012]	Ny-Alesund	78.92°N, 11.93°E, sea level	31/5-6/6 of 2009	Brewer #050	Diurnal	≈40

a LT and UT stand for local and universal time, respectively.

Table 2 .

 2 Average Values of TOC ± 1σ and TOC var ± 1σ, ND, MDS, and MDS 1%

	Site	Ave. TOC (DU)	Ave. TOC var (DU)	ND	MDS	MDS 1%
	CG	274.1 ± 7.2	9.3 ± 10.9	29	910	805
	Na	271.7 ± 5.5	16.8 ± 7.7	29	840	410
	LP	256.9 ± 6.8	6.3 ± 1.5	25	749	559

Table 3 .

 3 Comparison Between TOC Measurements From TOMS (TOC T ) and Brewers (TOC B ) a Site, linear fitting equation, coefficient of determination, percentage scattering of points, and number of data points are also shown. Uncertainties are 1σ.

	Site	Linear Fit Equation	r 2	SD%	N
	CG	TOC T = (23 ± 35) + (0.91 ± 0.13) TOC B	0.68	13.0	26
	Na	TOC T = (193 ± 32) + (0.30 ± 0.12) TOC B	0.22	22.4	25
	LP	TOC T = (À12 ± 27) + (1.04 ± 0.11) TOC B	0.83	13.1	22

a


Dirk Slock
email: dirk.slock@eurecom.fr

Convergent Approximate Message Passing by Alternating Constrained Minimization of Bethe Free Energy

Approximate Message Passing (AMP) allows for Bayesian inference in linear models with non identically independently distributed (n.i.i.d.) Gaussian priors and measurements of the linear mixture outputs with n.i.i.d. Gaussian noise. It represents an efficient technique for approximate inference which becomes accurate when both rows and columns of the measurement matrix can be treated as sets of independent vectors and both dimensions become large. It has been shown that the fixed points of AMP correspond to extrema of a large system limit of the Bethe Free Energy (LSL-BFE), which represents a meaningful approximation optimization criterion regardless of whether the measurement matrix exhibits the independence properties. However, the convergence of AMP can be notoriously problematic for certain measurement matrices and the only sure fix so far is damping (by a difficult to determine amount). In this paper we revisit the AMP algorithm by rigorously applying an alternating constrained minimization strategy to an appropriately reparameterized LSL-BFE with matched variable and constraint partitioning. This guarantees convergence, and due to convexity in the Gaussian case, to the global optimum. We show that the AMP estimates converge to the Linear Minimum Mean Squared Error (LMMSE) estimates, regardless of the behavior of the variances. In the LSL, the variances also converge to the LMMSE values, and hence to the correct values.

I. INTRODUCTION

In the Gaussian case, the signal model for the recovery of a sparse signal vector x can be formulated as, z = Ax, y = z + v, where y are the observations or data, A is called the measurement or the sensing matrix which is known and is of dimension M × N with typically M < N . In the sparse model case, x contains only K non-zero (or significant) entries, with K < M < N . In Bayesian inference, the Sparse Bayesian Learning (SBL) algorithm was first proposed by [START_REF] Tipping | Sparse Bayesian Learning and the Relevance Vector Machine[END_REF], [START_REF] Wipf | Sparse Bayesian Learning for Basis Selection[END_REF]. SBL is based on a two or three layer hierarchical prior on the sparse coefficients x. The priors for the hyperparameters (precision parameters) are chosen such that the marginal prior for x induces sparsity, allowing the majority of the coefficients to tend towards zero. It is worth mentioning that [START_REF] Giri | Type I and type II bayesian methods for sparse signal recovery using scale mixtures[END_REF] provides a detailed overview of the various sparse signal recovery algorithms which fall under l 1 or l 2 norm minimization approaches such as Basis Pursuit, LASSO etc and SBL methods. The authors justify the superior recovery performance of SBL compared to the above mentioned conventional methods. Nevertheless, the matrix inversion involved in the Linear Minimum Mean Squared Error (LMMSE) step in SBL at each iteration makes it computationally complex even for moderately large data sets. This complexity is the motivation behind approximate inference methods. Belief Propagation (BP) based SBL algorithms [START_REF] Tan | Computationally Efficient Sparse Bayesian Learning via Belief Propagation[END_REF] are computationally more efficient. A more detailed discussion on the various approximate inference methods for SBL appears in [START_REF] Thomas | Low Complexity Static and Dynamic Sparse Bayesian Learning Combining BP, VB and EP Message Passing[END_REF]. Various studies on the convergence analysis of Gaussian BP (GaBP) can be found in [START_REF] Du | Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation[END_REF]- [START_REF] Cseke | Properties of Bethe Free Energies and Message Passing in Gaussian Models[END_REF]. Although BP achieves great empirical success [START_REF] Murphy | Loopy belief propagation for approximate inference: an empirical study[END_REF], not enough rigorous work exists to characterize the convergence behavior of BP in loopy networks. In [START_REF] Malioutov | Walk-Sums and Belief Propagation in Gaussian Graphical Models[END_REF] a convergence condition for GaBP is provided which requires the underlying distribution to be walk-summable. Their convergence analysis is based on the Gaussian Markov random field (GMRF) based decomposition, in which the underlying distribution is expressed in terms of the pairwise connections between the variables. The Approximate Message Passing (AMP) algorithm has been introduced to further reduce complexity of GaBP. In Generalized AMP (GAMP), the vector x can have non-Gaussian priors and the measurement process can be more general than with additive Gaussian noise. However, the convergence of AMP can be problematic for certain measurement matrices A. Many variations have been introduced to help AMP converge, such as adding ADMM, exploiting part of the singular value decomposition of the measurement matrix in Vector AMP (VAMP) (but which does not allow to handle n.i.i.d. priors conveniently), sequential updating in Swept AMP (SwAMP) which works almost always, and especially by introducing damping with typically difficult to determine damping requirements.

A. Contributions of this paper

• We propose a version of AMP with guaranteed convergence, by rigorously applying an alternating constrained minimization strategy with matched variable and constraint partitioning. We apply this strategy to an appropriately augmented Lagrangian of the constrained Large System Limit of the Bethe Free Energy.

(y|z) = M k=1 p y k |z k (y k |z k ).
In Bayesian estimation we are interested in the posterior, which is given by p x,z|y (x, z|y) = p x (x) p y|z (y|z) 1 {z=Ax} / p y (y)

= 1 Z(y) e -N i=1 fx i (xi)-M fz k (z k ) 1 {z=Ax} (2)
where we have the negative loglikelihoods for prior and measurements

f xi (x i ) = -ln p xi (x i ) , f z k (z k ) = -ln p y k |z k (y k |z k ) (3)
where the equality in case of f z k (z k ) is up to constants that may depend on y (and which are absorbed in the normalization constant Z(y)). We shall consider here the Gaussian case, with n.i.i.d. Gaussian p x (x) and p y|z (y|z) = p v (y-z), so we have (neglecting constants)

f xi (x i ) = x 2 i 2σ 2 xi , f z k (z k ) = (z k -y k ) 2 2σ 2 v k . (4)
We shall need below the vectors

σ 2 x = [σ 2 x1 • • • σ 2 x N ] T , σ 2 v = [σ 2 v1 • • • σ 2 v M ] T .
The problem in Bayesian estimation is the computation of the constant Z(y) in (2) and of the posterior means and variances. Belief propagation is a message passing technique that allows to compute the posterior marginals. However, due to loops in the factor graph, loopy belief propagation may have convergences issues and is furthermore still relatively complex. AMP is an approximate belief propagation technique which is motivated by asymptotic considerations in which the rows and columns of the measurement matrix A are considered as random and independent, in which case AMP can actually produce the correct posterior marginals. In any case, AMP computes a separable approximate posterior of the form

q x,z (x, z) = q x (x) q z (z) = N i=1 q xi (x i ) M k=1 q z k (z k ) (5) Algorithm 1 AMP Require: y, A, S = A.A, f x (x), f z (z) 1: Initialize: t = 0, x t , τ t x , s t-1 = 0 2: repeat 3: [Output node update] 4: τ t p = S τ t x 5: p t = A x t -s t-1 .τ t p 6: z t = p t .σ 2 v ./(σ 2 v + τ t p ) + y.τ t p ./(σ 2 v + τ t p ) 7: τ t z = σ 2 v .τ t p ./(σ 2 v + τ t p )
8:

s t = ( z t -p t )./τ t p 9:
τ t s = (1 -τ t z ./τ t p )./τ t p 10:

[Input node update] 11:

τ t r = 1./(S T τ t s )
12:

r t = x t + τ t r .A T s t 13:
x t+1 = r t .σ 2 x ./(σ 2

x + τ t r )

14:

τ t x = τ t r .σ 2 x ./(σ 2 x + τ t r ) 15:
until Convergence in which the dependence on y has been omitted. Note that as in Expectation Propagation, these posterior marginal (approximations) will be of the form

q xi (x i ) = m xi (x i ) p xi (x i ) , q z k (z k ) = m z k (z k ) p y k |z k (y k |z k ) (6)
where not all dependence on y is shown explicitly. The factors m xi (x i ), m z k (z k ) are the extrinsic informations on the respective variables. The AMP algorithm [START_REF] Rangan | Generalized Approximate Message Passing for Estimation with Random Linear Mixing[END_REF], [START_REF] Rangan | Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices[END_REF] appears in the table for Algorithm 1. We only consider here Sum-Product AMP (for MMSE estimation, as opposed to Max-Sum AMP for MAP estimation).

III. AMBAMP

AMB is short for ACM-LSL-BFE: Alternating Constrained Minimization of the Large System Limit of the Bethe Free Energy. As we shall see, AMBAMP uses most of the same updates as AMP, but AMP does not rigorously follow the principle of alternating minimization (block coordinate descent) esp. in the presence of constraints. It has been shown that any fixed point of the AMP algorithm is a critical point of the following constrained minimization of a Large System Limit (LSL) of the Bethe Free Energy (BFE) (see [START_REF] Rangan | Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices[END_REF] and references therein): min qx,qz,τp

J LSL-BF E (q x , q z , τ p ) s.t. E(z|q z ) = A E(x|q x ) τ p = S var(x|q x ) (7)
where the LSL BFE is given by

J LBF E (q x , q z , τ p ) = D(q x ||e -fx )+D(q z ||e -fz )+H G (q z , τ p ), with H G (q z , τ p ) = 1 2 M k=1 var(z k |q z k ) τ p k + ln(2π τ p k ) (8)
and where D(q||p) = E(ln( q p ) |q) is the Kullback-Leibler distance (KLD) and H G (q z , τ p ) is a sum of a KLD and an entropy of Gaussians with identical means but different variances. Here E(z|q z ) denotes the expectation of the vector z using the distribution q z , and

τ p = [τ p1 • • • τ p N ] T denotes
L(q x , q z , τ p , u, s, τ s ) with L = D(q x ||e -fx )+D(q z ||e -fz )+H G (q z , τ p ) +s T (E(z|q z ) -A E(x|q x )) -1 2 τ T s (τ p -S var(x|q x )) + 1 2 E(x|q x ) -u 2 τr + 1 2 E(z|q z ) -A u 2 τp (9)
where s, τ s are Lagrange multipliers, and τ r = 1./(S T τ s ) is just a short-hand notation for quantities that depend on τ s . We also use the notations: u 2 τ = i u 2 i /τ i , element-wise multiplication as in s.τ and element-wise division as in 1./τ , where 1 is a vector of 1's. We interpret the constraints as follows:

E(z|q z ) = A E(x|q x )
is interpreted as a constraint on E(z|q z ), and τ p = S var(x|q x ) (which is a vector of the individual variances) is interpreted as a constraint on τ p . To interpret constraints as constraints on a subset of the variables, such subset should be rich enough to allow to satisfy the constraints. Due to the updating order, the other variables will be fixed actually as can be seen further. So the alternating optimization of ( 9), which corresponds to alternating minimization of the constrained problem [START_REF] Su | Convergence Analysis of the Variance in Gaussian Belief Propagation[END_REF], should be carried out in the following way. In the partitioning of the variables to be updated, the Lagrange multipliers for the constraints in which a given subset of variables is involved, should be optimized at the same time as that subset of variables. Such alternating optimization policy guarantees the cost function to decrease at each update, and hence to converge, to at least a local optimum. We propose to follow the following updating order

{q z , s} → {u} → {τ p , τ s } → {q x } . ( 10
)
In other words, at iteration t we have the following sequence

{q t z , s t } = arg min qz max s L(q t-1 x , q z , τ t-1 p , u t-1 , s, τ t-1 s ) ( 11
)
{u t } = arg min u L(q t-1 x , q t z , τ t-1 p , u, s t , τ t-1 s ) ( 12
)
{τ t p , τ t s } = arg min τp max τs L(q t-1 x , q t z , τ p , u t , s t , τ s ) ( 13
)
{q t x } = arg min qx L(q x , q t z , τ t p , u t , s t , τ t s ) (14)
A. Update of {q z , s}

The most tricky part is the update of {q z , s}. To that end, consider

L(q t-1 x , q z , τ t-1 p , u t-1 , s, τ t-1 s ) = D(q z ||e -fz ) + 1 2 var(z|q z )./τ t-1 p +s T E(z|q z ) + 1 2 E(z|q z ) -A u t-1 2 τ t-1 p + const. = D(q z ||e -fz ) + 1 2 E(z T z|q z )./τ t-1 p -(E(z|q z )) T ((A u t-1 )./τ t-1 p -s) + const. = D(q z ||e -fz ) + 1 2 E( z -p t (s) 2 τ t-1 p |q z ) + const. ( 15
)
where const. denotes constants w.r.t. z and where we introduced

p t (s) = A u t-1 -s.τ t-1 p . ( 16
)
This cost function is separable, hence we can continue per component. Note that the last expression in (15) can be interpreted as a single KLD:

min qz k D(q z k ||g t z k /Z t z k ) ⇒ q t z k = g t z k /Z t z k Z t z k (s k ) = g t z k (z k ; s k ) dz k , -ln g t z k (z k ; s k ) = f z k (z k ) + 1 τ t-1 p k ( z 2 k 2 -z k A k,: u t-1 ) + z k s k (17)
where A k,: denotes row k of A. Note that the partition function Z t z k acts as cumulant generating function:

- ∂ ln Z t z k ∂s k = E(z k |q t z k ) = E(z k |p t k (s k ), τ t-1 p k ) = z t k (s k ) ∂ 2 ln Z t z k ∂s 2 k = var(z k |p t k (s k ), τ t-1 p k ) = τ t z k (s k ) - ∂ 3 ln Z t z k ∂s 3 k = E(z k -E z k ) 3
(18) To satisfy the mean constraint in (7), we require s t k to satisfy

z t k = z t k (s t k ) = A k,: x t-1 , τ t z k = τ t z k (s t k ) . (19)
The second derivative in (18) being positive shows that z t k (s k ) is a monotonically increasing function. Actually, we shall see that in the Gaussian case here, z t k (s k ) is linear and τ t z k is constant as a function of s k . Hence the following first-order Taylor series expansion is exact:

z t k (s t k ) = z t k (s t-1 k ) -τ t z k (s t-1 k ) (s t k -s t-1 k ) = A k,: x t-1 (20)
from which we get

s t k = s t-1 k - 1 τ t z k (A k,: x t-1 -z t k (s t-1 k )) (21)
which is very similar to a Method of Moments (MM) update of the Lagrange multiplier (which allows the MM to converge). Actually, we can recognize from the last expression in (15) that the extrinsic for z is Gaussian:

ln m t z (z) = - 1 2 z -p t (s) 2 τ t-1 p (22)
which together with the Gaussian prior leads to a Gaussian posterior via the Gauss-Markov theorem

q t z (z) = N (z; z t , diag(τ t z )) with z t (s) = p t (s).σ 2 v ./(σ 2 v + τ t-1 p ) + y.τ t-1 p ./(σ 2 v + τ t-1 p ) τ t z = σ 2 v .τ t-1 p ./(σ 2 v + τ t-1 p ) (23
) where p t (s) is defined in [START_REF] Thomas | Hybrid Beamforming Design in Multi-Cell MU-MIMO Systems with per-RF or per-Antenna Power Constraints[END_REF]. This shows that the posterior mean is linear in s and that the posterior variance is constant w.r.t. s. The posterior variance expression leads to line 8 in Algorithm 2. Line 4 follows from ( 16) with p t = p t (s t-1 ). Line 5 follows from (23). Line 6 corresponds to the mean constraint in (19). Line 7 finally follows from (21).

B. Update of u

From ( 9), ( 12), we get

L(q t-1 x , q t z , τ t-1 p , u, s t , τ t-1 s ) = 1 2 x t-1 -u 2 τr + 1 2 A x t-1 -A u 2 τp + const. ( 24
)
where const. denotes constants w.r.t. u. The minimizer is obviously

u t = x t-1 . ( 25
)
Note that due to the update of (only) {q z , s} just before, we have z t = A x t-1 which greatly simplifies this update of u.

In contrast to [START_REF] Rangan | Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization[END_REF] where a complex update of u is required which is not compatible with the fast AMP style algorithms.

C. Update of {τ p , τ s } Due to the preceding update of u, the two quadratic terms shown in ( 24) are now zero. As a result, the dependence of those terms on τ p , τ s via the weights disappears for the update of {τ p , τ s } which comes next. Hence the terms of interest in ( 12) for ( 10) are now

L(q t-1 x , q t z , τ p , u t , s t , τ s ) = H G (q t z , τ p ) -1 2 τ T s (τ p -S τ t-1 x ) + const. = const.+ 1 2 M k=1 τ t z k τ p k + ln(2π τ p k ) - 1 2 M k=1 τ s k (τ p k -S k,: τ t-1 x ) (26
) where const. denotes constants w.r.t. {τ p , τ s }. The optimization yields

∂L ∂τ s k = 0 ⇒ τ t p k = S k,: τ t-1 x ( 27
)
∂L ∂τ p k = 1 2 (- τ t z k τ 2 p k + 1 τ p k -τ s k ) = 0 ⇒ τ t s k = 1 τ t p k (1 - τ t z k τ t p k ) (28)
(29)

D. Update of q x

For the update of q x in ( 14) finally, consider the relevant terms in the augmented Lagrangian (and remember that τ

t r = 1./(S T τ t s ) or 1./τ t r = S T τ t s ) (13) L(q x , q t z , τ t p , u t , s t , τ t s ) = D(q x ||e -fx ) -s t T A E(x|q x ) + 1 2 τ t T s S var(x|q x ) + 1 2 E(x|q x ) -u t 2 τ t r + const. = D(q x ||e -fx ) + 1 2 (1./τ t r ) T E(x.x|q x ) -s t T A E(x|q x ) -(u t ./τ t r )) T E(x|q x ) + const. = D(q x ||e -fx ) + 1 2 (1./τ t r ) T E(x.x|q x ) -(u t + τ t r .A T s t ) T (E(x|q x )./τ t r ) + const. = D(q x ||e -fx ) + 1 2 E( x -r t 2 τ t r |q x ) + const. (30
) where const. denotes constants w.r.t. x and

r t = u t + τ t r .A T s t . ( 31
) Algorithm 2 AMBAMP Require: y, A, S = A.A, f x (x), f z (z) 1: Initialize: t = 0, x t-1 , τ t-1 x , u t-1 , τ t-1 p , s t-1 = 0 2: repeat 3: [Output node update] 4: p t = A u t-1 -s t-1 .τ t-1 p 5: z t (s t-1 ) = (p t .σ 2 v + y.τ t-1 p )./(σ 2 v + τ t-1 p ) 6: z t = z t (s t ) = A x t-1 7: τ t z = σ 2 v .τ t-1 p ./(σ 2 v + τ t-1 p ) 8: s t = s t-1 -( z t -z t (s t-1
))./τ t z 9:

u t = x t-1
10:

[Variance matching] 11:

τ t p = S τ t-1 x 12:
τ t s = (1 -τ t z ./τ t p )./τ t p 13:

τ t r = 1./(S T τ t s )
14:

[Input node update] 15:

r t = u t + τ t r .A T s t 16:
x t = r t .σ 2 x ./(σ 2

x + τ t r )

17:

τ t x = τ t r .σ 2 x ./(σ 2 x + τ t r ) 18: until Convergence
This cost function is separable. We get per component

min qx k D(q x k ||g t x k /Z t x k ) ⇒ q t x k = g t x k /Z t x k Z t x k = g t x k (x k ) dx k , -ln g t x k (x k ) = f x k (x k ) + 1 2τ t r k [(x k -r k ) 2 -r 2 k ] . (32)
Actually, we can recognize from the last expression in (30) that the extrinsic for x is again Gaussian:

ln m t x (x) = - 1 2 x -r t 2 τ t r (33)
which together with the Gaussian prior for x leads to a Gaussian posterior via the Gauss-Markov theorem q t x (x) = N (x; x t , diag(τ t x )) with x t = r t .σ 2

x ./(σ 2 x + τ t r )

τ t x = τ t r .σ 2 x ./(σ 2 x + τ t r ) (34)
where r t is defined in (31).

IV. AMBAMP LARGE SYSTEM ANALYSIS

In the Gaussian case, we have investigated Large System Analysis in [START_REF] Thomas | Posterior Variance Predictions in Sparse Bayesian Learning under Approximate Inference Techniques[END_REF] using large random matrix theory. In this analysis, the entries of A are considered n.i.i.d. with zero mean and variances according to S = A.A. An asymptotic regime is considered in which the two dimensions M and N of A tend to infinity at fixed ratio. According to [13, Appendix A], under some conditions the approximate posterior variances τ x , τ z produced by AMP converge to the solution of the following coupled equations

1./τ x = σ 2 x + S T τ z , 1./τ z = σ 2 v + S τ x . (35)
In this asymptotic regime, these variances converge to their correct LMMSE values, namely

τ x = diag( (D(1./σ 2 x ) + A T D(1./σ 2 v ) A) -1 ) . (36)
V. AMP MEAN CONVERGENCE TO LMMSE By eliminating the variables p, s and z in AMBAMP, one can identify that the mean estimate x in ABMAMP satisfies the following second-order recursion

x t = D(σ 2 x ./(σ 2 x + τ t r )) x t-1 -D(τ t x ) A T D(1./τ t z ) A x t-1 +D(τ t x ) A T D(1./τ t-1 p ) A x t-2 + D(τ t x ) A T D(1./σ 2 v ) y (
37) where D(τ ) = diag(τ ) denotes a diagonal matrix constructed from a vector. One can note that the dynamics in the AMBAMP algorithm are different from those of the AMP algorithm. At convergence we can solve for the steady-state value x from (37). We get

D(1./τ x ) (I -D(σ 2 x ./(σ 2 x + τ r ))) x +A T (D(1./τ z ) -D(1./τ p )) A x = A T D(1./σ 2 v ) y ⇒ x = (D(1./σ 2 x ) + A T D(1./σ 2 v ) A) -1 A T D(1./σ 2 v ) y (
38) which is the LMMSE estimate. This LMMSE steady-state value for the mean is also valid for the original AMP algorithm, if it converges.

VI. CONCLUDING REMARKS

To arrive at the convergent AMBAMP algoritrhm, a particular formulation of the Bethe Free Energy (BFE) criterion has been considered with a judiciously chosen Method of Moments extension to incorporate equality constraints quadratically. The Lagrangian of the resulting augmented BFE is then introduced. The alternating optimization of the resulting cost function only leads to the desired algorithm of low complexity when alternating optimization is done in one particular order. Other updating orders would also lead to convergent algorithms but not to low complexity updates. We have drawn attention to an approach to perform alternating constrained optimization. The approach consists of not only partitioning the variables appearing in the cost function, but also to partition the constraints according to this variable partitioning and to identify for each constraint subset the variable subset that can be used to satisfy these constraints. In the alternating optimization of the cost function w.r.t. each variable subset, the possible corresponding constraint subset should be involved in the constrained optimization sub-problem. This same alternating constraint optimization approach is widely applicable. It has for instance been used in beamforming design where normalized beamformers can be updated separately from the signal powers, which get updated while satisfying the power constraints, leading to waterfilling type solutions [START_REF] Thomas | Hybrid Beamforming Design in Multi-Cell MU-MIMO Systems with per-RF or per-Antenna Power Constraints[END_REF]

  We indicate that asymptotically, for a statistical n.i.i.d. element model for A, the variance computations in AMBAMP are exact and we indicate an asymptotically correct iterative scheme to compute them.

	• We also show (perhaps for the first time) that the esti-
	mates (means) produced by AMP in the Gaussian case
	converge to the actual Linear Mininum Mean Squared
	Error estimates, regardless of whether the variances con-
	verge to the correct LMMSE values or not.
	II. APPROXIMATE MESSAGE PASSING
	The data model considered in AMP is essentially a linear
	mixing model
	z = A x , p x (x) , p y|z (y|z)	(1)
	with (possibly) non identically independently distributed
	(n.i.i.d.) prior p x (x) =	N i=1 p xi (x i ) and n.i.i.d. measure-
	ments p y|z

• The new AMP, dubbed AMBAMP below, requires to solve for the mean constraint Lagrange multipliers s appearing in the posterior mean z(s) to make it satisfies this mean constraint. This can be solved explicitely in the Gaussian case considered here.

•

.

  Dirk T.M. Slock received an EE degree from Ghent University, Belgium in 1982. In 1984 he was awarded a Fulbright scholarship for Stanford University, USA, where he received the MSEE, MS in Statistics, and PhD in EE in 1986, 1989 and 1989 resp. While at Stanford, he developed new fast recursive least-squares algorithms for adaptive filtering. In 1989-91, he was a member of the research staff at the Philips Research Laboratory Belgium. In 1991, he joined EURECOM where he is now professor. At EURECOM, he teaches statistical signal processing (SSP) and signal processing techniques for wireless communications. He invented semi-blind channel estimation, the chip equalizer-correlator receiver used by 3G HSDPA mobile terminals, spatial multiplexing cyclic delay diversity (MIMO-CDD) now part of LTE, and his work led to the Single Antenna Interference Cancellation (SAIC) integrated in the GSM standard in 2006. Recent keywords are multi-cell multiuser (Massive) MIMO, imperfect CSIT, distributed resource allocation, variational and empirical Bayesian learning techniques, large random matrix analysis, audio source separation, location estimation and exploitation. He graduated about 40 PhD students, leading to an edited book and 500+ papers. In 1992 he received one best journal paper award from IEEE-SP and one from EURASIP. He is the coauthor of two IEEE Globecom'98, one IEEE SIU'04, one IEEE SPAWC'05, one IEEE WPNC16 and one IEEE SPAWC18 best student paper award, and a honorary mention (finalist in best student paper contest) at IEEE SSP'05, IWAENC'06, IEEE Asilomar'06 and IEEE ICASSP17. He was an associate editor for the IEEE-SP Transactions in 1994-96 and the IEEE Signal Processing Letters in 2009-10. He was the General Chair of the IEEE-SP SPAWC'06 and IWAENC14 workshops, and EUSIPCO15. He cofounded the start-ups SigTone in 2000 (music signal processing products) and Nestwave in 2014 (Ultra Low-Power Indoor and Outdoor Mobile Positioning). He is a Fellow of IEEE and EURASIP. In 2018 he received the URSI France medal.

ACKNOWLEDGEMENTS

EURECOM's research is partially supported by its industrial members: ORANGE, BMW, SAP, iABG, Norton LifeLock, and by the French ANR project CellFree6G.