Pierrick Coupé
email: pcoupe@irisa.fr

Pierre Hellier

Xavier Morandi

Christian Barillot

Probe Trajectory Interpolation for 3D Reconstruction of Freehand Ultrasound

Three-dimensional (3D) Freehand ultrasound uses the acquisition of non parallel Bscans localized in 3D by a tracking system (optic, mechanical or magnetic). Using the positions of the irregularly spaced B-scans, a regular 3D lattice volume can be reconstructed, to which conventional 3D computer vision algorithms (registration and segmentation) can be applied. This paper presents a new 3D reconstruction method which explicitly accounts for the probe trajectory. Experiments were conducted on phantom and intra-operative datasets using various probe motion types and varied slice-to-slice B-scan distances. Results suggest that this technique improves on classical methods at the expense of computational time.

Introduction

Ultrasonography has become a very popular medical imaging modality thanks to its low cost, real time image formation capability and non invasive nature. Due to its many attributes, ultrasound has been used in neurosurgery for the last two decades [START_REF] Rubin | Intraoperative ultrasound examination of the brain[END_REF]. Several studies demonstrated that ultrasonography can be used in the location of tumors, definition of their margins, differentiation of internal characteristics and detection of brain shift and residual tumoral tissue [START_REF] Dohrmann | History of intraoperative ultrasound in neurosurgery[END_REF].

Despite its advantages, the lack of 3D information in traditional 2D ultrasound imaging prevents reproductivity of examinations, longitudinal follow-up and precise quantitative measurements. To overcome these limits and produce a 3D representation of the scanned organs, severals techniques exist: mechanicallyswept acquisitions, freehand imaging [START_REF] Rankin | Three-dimensional sonographic reconstruction: techniques and diagnostic applications[END_REF], mechanical built-in probes and 2D phased-array probes [START_REF] Smith | Update on 2-D array transducers for medical ultrasound[END_REF]. The two first approaches are based on the reconstruction of a 3D regular lattice from 2D B-scans and their positions, whereas 3D probes directly acquire 3D images. The main advantages of freehand imaging, compared to other 3D approaches, are flexibility, low cost and large organs examination capabilities. Moreover, compared to 3D probes, the image quality and the field of view are better suited to clinical applications [START_REF] Smith | Feasibility study : real-time 3-D ultrasound imaging of the brain[END_REF][START_REF] San-Jose | A theoretical framework to three-dimensional ultrasound reconstruction from irregularly-sample data[END_REF].

Freehand imaging techniques consist of tracking a standard 2D probe by using a 3D localizer (magnetic, mechanical or optic). The tracking system continuously measures the 3D position and orientation of the probe. This 3D position is used for the localization of B-scans in the coordinate system of the localizer. In order to establish the transformation between the B-scan coordinates and the 3D position and orientation of the probe, a calibration procedure is necessary [START_REF] Rousseau | Confhusius: a robust and fully automatic calibration method for 3D freehand ultrasound[END_REF][START_REF] Rousseau | A novel temporal calibration method for 3-d ultrasound[END_REF]. Calibration is needed to estimate the transformation matrix linking the different coordinate systems (spatial calibration), but also the latency between image and position time stamps (temporal calibration). The localization accuracy of B-scan pixels in the 3D referential system depends on the calibration procedure. A review of calibration techniques is presented in [START_REF] Mercier | A review of calibration techniques for freehand 3-D ultrasound systems[END_REF].

To analyze the sequences of B-scans, two types of approaches can be used: the reslicing (without reconstruction) or the true 3D reconstruction including interpolation step. The first is used by the StradX system [START_REF] Prager | Stradx : real-time acquisition and visualization of freehand three-dimensional ultrasound[END_REF] and enables the analysis of the data without reconstruction. The sequence of B-scans can be arbitrarily resliced and distance/volume measurements are performed without reconstruction. This strategy is very powerful for manual analysis of 3D datasets. However, 3D isotropic reconstruction is still necessary in the clinical context when automatic segmentation or registration procedures are required. The second approach is based on the interpolation of the information within the B-scans to fill a regular 3D lattice thus creating a volumetric reconstruction. Due to the non uniform distribution of the B-scans, this step is acutely expensive with respect to computation time and reconstruction quality: an efficient reconstruction method should not introduce geometrical artifacts, degrade nor distort the images. To resolve this problem several methods were proposed. The most common ones are Pixel Nearest-Neighbor (PNN) [START_REF] Nelson | Interactive acquisition, analysis and visualization of sonographic volume data[END_REF], Voxel Nearest-Neighbor (VNN) [START_REF] Prager | Stradx : real-time acquisition and visualization of freehand three-dimensional ultrasound[END_REF][START_REF] Sherebrin | Freehand three-dimensional ultrasound: implementation and applications[END_REF] and Distance-Weighted interpolation (DW) [START_REF] Barry | Three dimensional freehand ultrasound: image reconstruction and volume analysis[END_REF][START_REF] Trobaugh | Three dimensional imaging with stereotactic ultrasonography[END_REF].

Due to its simplicity of implementation and its reduced computation time, the most straightforward reconstruction algorithm is the PNN method. This algorithm is divided into two stages: the bin-filling and the hole-filling [START_REF] Rohling | Radial basis function interpolation for freehand 3D ultrasound[END_REF]. The bin-filling stage consist in searching, for each pixel in every B-scan. The nearest voxel which is filled with the value of the pixel. Secondly, the remaining gaps in the 3D voxel array are filled via a hole-filling method. Usually, the hole-filling method is a local average of filled voxels. Although the PNN method is fast and simple to implement, this approach generates artifacts. Contrary to the PNN method, the VNN approach does not require the holefilling stage because all voxels are filled in one step using the value of the nearest pixel obtained by orthogonal projection on the nearest B-scan. In the DW interpolation approach, each voxel is filled with the weighted average of pixels from the nearest B-scans (see section 2.1 and Fig. 1 for a detailed explanation). The set of pixels or interpolation kernel is defined either by a spherical neighborhood [START_REF] Barry | Three dimensional freehand ultrasound: image reconstruction and volume analysis[END_REF], or by projection on the two nearest B-scans [START_REF] Trobaugh | Three dimensional imaging with stereotactic ultrasonography[END_REF]. Then, all pixel intensities of this set are weighted by the inverse distance to the voxel to calculate voxel intensity. A complete survey of these three methods is presented in [START_REF] Rohling | A comparison of freehand three-dimensional ultrasound reconstruction techniques[END_REF]. These approaches are designed to reduce computation time, at the cost of a lower reconstruction quality compared to more elaborated methods.

More elaborated methods were recently developed in order to increase the reconstruction quality. Firstly, the registration based approach consists in reconstructing a 3D volume after a non-rigid registration of each successive B-scans. In [START_REF] Penney | Registration-based interpolation[END_REF], a linear interpolation between the two nearest pixels is used to calculate the intensity voxel. This technique is notably used to avoid artifacts due to tissue motion. Some studies focus on the improvement of the interpolation step using radial basis functions (RBF) [START_REF] Rohling | A comparison of freehand three-dimensional ultrasound reconstruction techniques[END_REF], weighted Gaussian convolution [START_REF] San-Jose | A theoretical framework to three-dimensional ultrasound reconstruction from irregularly-sample data[END_REF][START_REF] Meairs | Reconstruction and visualization of irregularity sampled three-and four-dimensional ultrasound data for cerebrovascular applications[END_REF] or Rayleigh model for intensity distribution [START_REF] Sanchez | A rayleigh reconstruction/interpolation algorithm for 3D ultrasound[END_REF]. Finally, the optimization of the axis orientation and voxel size are discussed in [START_REF] San-Jose | A theoretical framework to three-dimensional ultrasound reconstruction from irregularly-sample data[END_REF]. Nevertheless, the quality improvement obtained with these approaches induces computational burden.

The paper is organized as follows. Section 2 describes the proposed reconstruction method using the 3D probe trajectory (PT) information. Section 3 briefly describes the evaluation framework and compares the proposed method with VNN and DW methods. Finally, in section 4 the advantages and limitations of the PT method are discussed and further improvements are outlined. The two orthogonal projections for DW interpolation method and the construction of a "virtual" plane π t containing X for PT method.

Method

This work builds on the distance weighted interpolation and proposes to incorporate probe trajectory information. The distance weighted interpolation is first presented in section (2.1). Then, the probe trajectory information is incorporated in section (2.2).

Distance Weighted Interpolation (DW)

At each point X of the reconstructed volume, the linear interpolation amounts to computing:

f n (X) = 1 G ti∈Kn(X) g ti f (X ti ) (1)
where K n is the interpolation kernel. In other words, K n is the set of the different indexes of the B-scans that are involved in the interpolation, n is the interpolation order. For a given interpolation degree, the n closest Bscans before X and the n closest B-scans after X are considered. For the DW interpolation, X ti is the orthogonal projection of X on the ti th B-scan. f (X ti ) is the intensity at position X ti and is obtained by bilinear interpolation. Finally, G is the normalization constant with G = g ti , where g ti is the distance between X and X ti (see Fig. 1).

Probe Trajectory Interpolation (PT)

The orthogonal projection of points to the nearest B-scans is a straightforward solution. However, it does not take into account the relationship between a given point and its projections. As seen in section 1, registration based in-terpolation uses homologous points to interpolate, thus increasing the computational burden. We propose to incorporate the probe trajectory into the interpolation process. In other words, homologous points are defined as being successive points along the probe trajectory.

We believe there is correlation between the underlying signal structure and the probe trajectory. When imaging cross-sections of a tubular structure for instance, the intuitive displacement of the probe that follows the Structure Of Interest (SOI) will lead to some correlation between the probe trajectory and the anatomical structure (see the cerebral falx Fig. 11). In intra-operative exams, we observed that the surgeon was concentrated in keeping the focus of the US scans on the SOI (i.e. the lesion). This is confirmed by observing the location of the SOI, which is kept at the same position in the x-y place during the sequence (see Fig. 2). Therefore, we think that the introduction of probe trajectory into the interpolation process is relevant.

Instead of using orthogonal projections as in classical DW, we propose to project along the probe trajectory. Firstly, the time stamp t ∈ R, t ∈ [t i , t i+1 ] of the "virtual plane" π t is estimated. The " virtual plane" is the plane which passes through X in the sense of the probe trajectory (see Fig 1). Then, t is used to compute the "virtual plane" parameters (translation and rotation) by interpolation of π t i and π t i+1 positions. Finally, the 2D coordinates of X t (the projection of X on π t ) are used to obtain the projections of X on π t i and π t i+1 in the sense of the probe trajectory.

Determination of the "virtual" plane time stamp

Under the assumption that the probe motion is constant between two consecutive B-scans, the latency ratio is equal to the distance ratio:

t = d ti+1 d ti + d ti+1 (t i ) + d ti d ti + d ti+1 (t i + 1) (2)
where d ti is the distance (in the sense of orthogonal projection) between the current voxel and the B-scan of time stamp ti

(d ti = X -X DW ti
). The assumption of constant probe speed between two slices is justified by the frame rate. The lowest frame rate is usually 10Hz, which means that 100ms separate two frames. It is therefore reasonable to assume a constant motion magnitude between two frames (i.e. no significant acceleration).

Once the time stamp of the "virtual" plane is computed, the probe position can be interpolated.

Determination of the "virtual" plane parameters

The position of each B-scan is defined by 3 translations and 3 rotations. Thus the interpolation of origin position and rotation parameters is needed. We use the Key interpolation for the translations and the Spherical Linear Interpolation (SLERP) for the rotations.

Interpolation of origin position

For the origin of the B-scan, a cubic interpolation is used to estimate the origin of the "virtual" plane at time stamp t. The Key function is used to carry out a direct cubic interpolation and is defined as:

ϕ(t) =              (a + 2)|t| 3 -(a + 3)t 2 + 1 if 0 ≤ |t| < 1, a|t| 3 -5at 2 + 8a|t| -4a if 1 ≤ |t| < 2, 0 if 2 ≤ |t| (3)
With a = -1 2 , ϕ is a C 1 function and a third order interpolation is obtained [START_REF] Thévenaz | Interpolation revisited[END_REF]. In practice, four B-scans are used for cubic interpolation. This seems to be an optimal trade-off between computational time and reconstruction quality. For example, the interpolation of the origin position along x axis T x reads as:

T x (t) = t i +2 k=t i -1 T x (k)ϕ(t -k) (4)
.

Interpolation of rotation parameters

The rotation parameters of each B-scan are converted into a quaternion which is a compact representation of rotations within a hyper-complex number of rank 4:

q = w + ix + jy + kz (5)
This representation of rotations, allows to take into account the coupling of rotations during the interpolation step. The quaternion representing the rotations of the "virtual" plane is obtained through a Spherical Linear Interpolation (SLERP) [START_REF] Shoemake | Animating rotation with quaternion curves[END_REF] at time stamp t:

q t = q ti sin((1 -t)θ) sinθ + q ti+1 sin(tθ) sinθ (6)
where q ti and q ti+1 are the unit quaternions corresponding to B-scans of time stamps ti and ti+1; and θ represents the angle between q ti and q ti+1 computed as:

θ = cos -1 (q ti .q ti+1 ) (7)
The orientation of the "virtual" plane is contained in q t . Then, X P T ti and X P T ti+1 are obtained directly, since they have the same 2D coordinates (defined in each B-scans) as X t .

Labeling

It is possible that a part of the reconstructed volume is visible on several time stamps (or view points) of the B-scans sequence. These different time stamps are computed during the labeling step so as to track this information and fully exploit the speckle decorrelation. In this way, a label vector L X containing time stamps of the nearest B-scans is built for each voxel. In case of a simple translation, L X = (t 1 , t 1 + 1) is the label vector of voxel X while t 1 and t 1 + 1 are the time stamp of the nearest planes. For more complex probe motions with multiple scanning angles, L X is composed of several couples of time-consecutive B-scans: L X = ((t 1 , t 1 + 1), (t 2 , t 2 + 1), ...). Afterward, L X is used to build K n which also depends on interpolation degree n, thus

K n = ((t 1 -n + 1, ..., t 1 + n), (t 2 -n + 1, ..., t 2 + n), ...).
For instance, with an interpolation degree equals to 1 and two view points (see Fig. 3), the "virtual" plane between (π t1 , π t1+1 ) is first computed to estimate the distance of X to (π t1 , π t1+1 ). Then, the "virtual" plane between (π t2 , π t2+1 ) is computed to estimate the distance of X to (π t2 , π t2+1 ). Indeed, all the positions of the nearest B-scans are not used at the same time to estimate the probe trajectory, only the consecutive B-scans in time are used simultaneously. Nonetheless, all the pixels on the nearest B-scans are used simultaneously to estimated the intensity of voxel X.

Fig. 3. Illustration of a multi-scanned voxel X at two different time stamps t 1 and t 2 . For an interpolation degree equals to 1, the two couples of B-scans (π t1 , π t1+1 ) and (π t2 , π t2+1 ) are taken into account to evaluate the intensity of X (i.e K n = ((t 1 , t 1 + 1), (t 2 , t 2 + 1)))

.

3 Material

Ultrasound Phantom sequences

A Sonosite system with a cranial 7 -4M Hz probe was used to acquire the ultrasound images. The positions of the B-scans was given by a magnetic miniBIRD system (Ascension Technology Corporation) mounted on the US probe. The StradX software [START_REF] Prager | Stradx : real-time acquisition and visualization of freehand three-dimensional ultrasound[END_REF] was used to acquire images and 3D position data. The phantom is a CIRS Inc.1 3D ultrasound calibration phantom containing two calibrated volumetric ellipsoids test objects. At the acquisition depth, only one of the ellipsoids is visible in the field of view. The two sequences used for the experiments are composed of 510 × 441 B-scans (204 B-scans for fan motion and 222 B-scans for translation motion, see Fig. 4).

Ultrasound Intra-operative sequences

For intra-operative sequences the sinuosity cranial probe was coupled with the Sononav Medtronic system in an image-guided neurosurgery context. Contrary to the miniBIRD tracker, the Sononav system is based on an optical tracking to estimate the spatial probe positions sent to the neuronavigation system. The sequences were acquired during neurosurgical procedures after the craniotomy

Magnetic Resonance Intra-operative sequences

In freehand ultrasound imaging the validation step is not an easy task because the "ground truth" does not exist. In order to overcome this problem, magnetic resonance sequences were built on geometry of the ultrasonic intra-operative sequences (see Fig. 5 at bottom). Firstly, the intra operative trajectories were used to re-slice the preoperative magnetic resonance volume of the patient. Then, a stack of MR-scans was built on the images obtained by the re-slicing. Finally, the reconstructed MR volume was compared to the "ground truth" (i.e the corresponding preoperative MRI volume). As the US-sequences, the MR-sequence1 is composed of 59 MR-scans (223 × 405) and MR-sequence2 of 46 MR-scans (223 × 405), see Fig. 5.

The following evaluation aims at studying the impact of the probe trajectory incorporation independently of the compounding, the sequences follow simple fan and/or translation motion.

Evaluation framework

The performance of the proposed method was compared with two other interpolation approaches: the VNN technique used in StackX [START_REF] Prager | Stradx : real-time acquisition and visualization of freehand three-dimensional ultrasound[END_REF] and the DW method presented in [START_REF] Trobaugh | Three dimensional imaging with stereotactic ultrasonography[END_REF]. For the VNN method, each voxel is projected on the nearest B-scan and its luminance interpolated bilinearly. In the DW technique, each voxel is projected orthogonally on the 2n nearest B-scans and its luminance is interpolated (see section 2.1 and Fig. 1).

Within this evaluation framework, the influence of two parameters was stud- ied:

• "The distance between two consecutive B-sans". The sequence is sub-sampled thanks to SelectSX2 , which simulates a lower frame acquisition rate, in order to artificially increase the distance between 2 consecutive B-scans. The evaluation framework studies the probe trajectory interpolation impact according to the distance between two consecutive B-scans. • "The size of the interpolation kernel". For ultrasound phantom sequences, the removed B-scans are reconstructed with different methods and different interpolation degrees (from 1 to 2 for DW and PT methods).

Results

The reconstructions were performed on a P4 3.2 Ghz with 2Go RAM. In order to only compare interpolation times, the total computational time is divided as follows: L time corresponds to labeling step and I time corresponds to interpolation time. The labeling step consists in constructing the label vector K n for each voxel X (described in 2.3).

Interpolation Function

In this section, the Key interpolation of rotation parameters is compared with the theoretically optimal approach described in paragraph 2.2.2.2. The direct interpolation of each parameter can be considered as an approximation of the Spherical Linear Interpolation (SLERP) because the coupling of rotations is not taken into account. However, for small rotations, this approximation leads to very similar results. Table 1 compares the reconstruction quality using the SLERP and interpolation approximation. The SLERP interpolation is theoretically correct, but experiments showed that reconstruction results are similar. This is due to the continuity of probe motion and the proximity of two consecutive B-scans. Considering these results, the Key interpolation will be used in the rest of the paper in order to decrease the computational burden. 1 Error measures composed of mean µ and standard deviation σ for the Spherical Linear Interpolation (SLERP) and the Key interpolation. Results on phantom sequence indicate that the improvement in terms of interpolation quality with SLERP was not significant whereas the computational time increased. Results on phantom sequences (described in section 3) are presented in Figure 7 and Table 2. Figure 7 shows the influence of the mean distance between two B-scans on the reconstruction error with two types of motion (i.e. translation and fan). Table 2 presents the error and computation time for different interpolation degrees (1 and 2). In all cases, the PT method outperforms the VNN and the DW methods especially on sequences with few B-scans. The probe trajectory is especially relevant to compensate for the sparsity of data. When the distance of a given point to the B-scans considered in the interpolation increases, the orthogonal projections and probe trajectory differ significantly. This distance introduces artifacts for the DW method. For distances close to 0.2mm, DW and PT methods are equivalent. The difference between PT Table 2 Error measures composed of mean square error µ and standard deviation σ for the different methods (see section 4). L time is the time spent for labeling, while I time is the time spent for interpolation. Results indicate that the PT method obtains better results than the VNN and the DW methods. The improvement in terms of reconstruction quality is obtained at the expense of a slight computational increase.

Phantom sequence

and DW, in terms of mean square error for translation and fan motion was expected to be greater. We think that the phantom images do not contain enough structures to really show the reconstruction quality improvement in case of fan motion. Apart from the ellipsoid in the image center, the image contains only speckle. For the fan sequence, the difference between PT and DW, in terms of projection, is substantial for voxels that are far from the rotation center, that is to say in deep areas. The deep regions do not convey structural information but mostly speckle. 2.

MR Intra-operative sequences

Figure 9 shows the influence of the mean distance between two consecutive B-scans on the reconstruction error. The mean square error is computed between the "Ground Truth" and the reconstructed volume. The PT method outperforms the VNN and DW approaches especially on sparse data. Figure 10 presents slices extracted from initial MR volume and the reconstructed MR volume. Visually, the PT method preserves more the edges and the contrast. Compared to DW method, the PT method improves the reconstruction result especially on edges whose direction is correlated with probe trajectory.

US Intra-operative sequences

The dimension of the reconstructed volume are 263 × 447 × 306 for US-sequence1 and 286×447×234 for US-sequence2 with resolutions of (0.188, 0.172, 0.180). The reconstruction process, with a multithreading implementation on an Intel Pentium Dual Core CPU at 3.40GHz with 2Go RAM, takes 220s for US-sequence1 and 154s for US-sequence2.

The reconstructions of B-scans dataset US-sequence1 are presented in Figure 11 and US-sequence2 are presented in Figure 12. Visually, the VNN method leads to many discontinuities and creates artificial boundaries (see image at the top right of Fig. 12). The DW method generally smooths out the edges and spoils the native texture pattern of US image more than PT (see at the bottom of Fig. 12). "Ground truth" VNN DW PT Fig. 10. Results for MR-sequences of brain. Top: the "ground truth" and the reconstructions obtained via the different methods for a mean distance between MR-scans of 1.8mm. On the bottom: the images of the difference between the "ground truth" and the reconstructed volume. Visually, the PT method preserves more the edge continuity and the contrast. The difference images show that the PT method creates less artifacts and appears closer to the "ground truth", especially on ventricles edges.

The actual implementation of methods can be largely optimized as compared to StackSX, which produces all reconstruction processes of translation phantom sequence in 10 seconds with the VNN method (62s with our implementation of VNN). Although the labeling step needs significant improvement, this study aims to compare computation time between identical implementations of methods. The increased quality of reconstruction for the PT method is obtained at the expense of a slight increase of the computation time. Nonetheless this side effect seems to be reasonable with regards to the reconstruction qual- ity. Contrary to more elaborated techniques like non-rigid registration or RBF, which are considerably computationally expensive, the PT approach offers an attractive compromise between computation time and reconstruction quality.

Discussion and conclusion

This paper presented a 3D freehand ultrasound reconstruction method explicitly taking into account the probe trajectory information. Through an evaluation framework, it shows that the proposed method performs better than traditional reconstruction approaches (i.e. Voxel Nearest Neighbor and Distance Weighted interpolation) with a reasonable increase of the computation time.

The main limitation of PT method is the assumption of constant probe speed between two slices. Nonetheless, this hypothesis is reasonable when using a decent frame rate (more than 10Hz). Moreover, the direct interpolation of rotation parameters instead of Spherical Linear Interpolation (SLERP) does not introduce artifacts but accelerates the reconstruction process. The evaluation results underline the relevance of probe trajectory information, especially on sequences with low frame rate acquisitions or large distances between two consecutive B-scans. The PT method is a trade-off between reconstruction error and computational time. The results show that the hypothesis of a correlation between the signal structure and the probe trajectory is relevant. Indeed, in practice, the probe trajectory and signal structure are correlated because the medical practitioner tends to follow the structure of interest (see on Fig. 11).

The precise localization of anatomy and pathology within the complex 3D geometry of the brain remains one of the major difficulties of neurosurgery. Thus, image-guided neurosurgery (IGNS) is an adequate context to experiment the proposed method because the reconstruction quality is of utmost importance and the time dedicated to image reconstruction is limited. The PT method is thus interesting for applications where an accurate reconstruction is needed in a reasonable time. Further work should be pursued for comparing the PT reconstruction approach with registration based approaches [START_REF] Penney | Registration-based interpolation[END_REF].

Registration based approaches avoid artifacts of slice misregistration due to errors in tracking data (i.e. trajectory) and/or tissue deformation. The compensation of tissue motion can be especially interesting in neurosurgery due to the complex problem of soft tissue deformations also known as brainshift. However, since the registration is a computationally expensive process, the benefit for image reconstruction should be studied. Then, our implementation could be largely optimized using graphic library implementation (ex: OpenGL) or grid computation especially for IGNS purpose. Finally, the impact of PT reconstruction on registration (mono and multimodal) to compensate for errors of localization and brainshift needs to be investigated further. Indeed, the current pitfalls of the neuronavigator system are: the errors caused by geometrical distortion in the preoperative images, registration, tracking errors [START_REF] Golfinos | Clinical use of a frameless stereotactic arm: results of 325 cases[END_REF], and brainshift.

Fig. 1 .

 1 Fig.1. Illustration of DW and PT principles. The two orthogonal projections for DW interpolation method and the construction of a "virtual" plane π t containing X for PT method.

Fig. 2 .

 2 Fig. 2. A longitudinal reslice of the non reconstructed intra-operative data (i.e. the stack of B-scans). The x position in B-scans (horizontal axis of the reslice) of the structure of interest is correlated along the sequence, the vertical axis of the reslice corresponding to the B-scans latencies. The cerebral falx is visible at left and the lesion at center.

Fig. 4 .

 4 Fig. 4. B-scans sequences used during evaluation. Left: fan sequence. Right: translation sequence. step but before opening the dura. US-sequence1 is composed of 59 B-scans (223 × 405) and US-sequence2 of 46 B-scans (223 × 405), see Fig. 5.

Fig. 5 .

 5 Fig. 5. Top: Intra-operative B-scans sequences of brain used during evaluation. The low-grade glioma and ventricles are visible in white. Left: US-sequence1. Right: US-sequence2. Bottom: Intra-operative MR-scans sequences of brain built on B-scans sequences. Left: MR-sequence1. Right: MR-sequence2. In MR images the lowgrade glioma and the ventricles appears in gray.

Fig. 6 .

 6 Fig. 6. Illustration of the validation framework used for the MR-sequences.

Fig. 7 .

 7 Fig. 7. Variation of error reconstruction relatively to distance between two consecutive B-scans on phantom sequence with interpolation degree equals to 1. Left fan motion, right translation motion. Three methods are evaluated: VNN, DW and PT. The PT method outperforms others methods especially on sparse data.

Fig. 8 .

 8 Fig. 8. Differences between original (left) and reconstructed B-scan for fan sequence with n = 1. From left to right: the Voxel Nearest Neighbor, the Distance Weighted interpolation and the Probe Trajectory methods. This shows that the error between the reconstructed B-scan and the initial image is visually lower with the PT method, especially on the contours of the object.

Figure 8

 8 Figure 8 shows the differences between the original and the reconstructed Bscans with the VNN, DW and PT methods. Visually, the PT reconstruction appears closer to the original B-scan, what fits the numerical results of Table

Fig. 9 .

 9 Fig. 9. Variation of mean reconstruction error relatively to the distance between two consecutive MR-scans with interpolation degree of 1. Left MR-sequence1, right MR-sequence2. Three methods are evaluated: VNN, DW and PT. The PT method outperforms others methods especially on sparse data.

Fig. 11 .

 11 Fig. 11. Results for US-sequence1 of brain. Top: the preoperative MRI and the US reconstruction obtained with the VNN method. On the bottom: the reconstruction obtained with DW and PT approaches. The low-grade glioma and the cerebral falx appear in gray in MR image and in white in US images. From left to right the VNN, DW and PT methods. The images highlight the inherent artifacts of VNN (i.e. discontinuities) and DW (i.e. blur) methods. These results underline that the PT method preserves the edges continuity and the native texture of US image more than VNN and DW method.

Fig. 12 .

 12 Fig. 12. Results for US-sequence2 of brain. Top: the preoperative MRI and the US reconstruction obtained with the VNN method. On the bottom: the reconstruction obtained with DW and PT approaches. The low-grade glioma appears in gray in MR image and in white in US images. Visually, the PT method preserves more the edges continuity especially on sulci edges (see at the center bottom of images).

http://www.cirsinc.com

http://mi.eng.cam.ac.uk/˜rwp/stradx/utilities.html

Acknowledgment

We thank Richard Prager, A. Gee and G. Treece from Cambridge Univ. for fruitful assistance in using StradX. This work was possible thanks to a grant of Rennes city council. We thank the reviewers for their valuable comments for improving this paper.

For Ultrasound Phantom Data

To assess the reconstruction quality, evaluation data can be created from any image sequence: given a sequence of 3D freehand US, each B-scan is removed from the sequence, and then reconstructed by using the other B-scans. This "leave one out" procedure is performed for each B-scan. The Mean Square Error (MSE) is used as quality criterion:

where I t is the original image at time t (removed from the sequence), Ĩt the reconstructed image and P is the number of pixel in this B-scan. After M SE estimation for all B-scans of the sequence, we compute the mean µ and the standard deviation σ of the reconstruction error.

N is the total number of B-scan in the sequence and n the interpolation kernel degree.

For Magnetic Resonance Sequences

Contrary to ultrasound phantom data, for MR-sequences the "ground truth" is known. The evaluation framework directly compares the reconstructed volume Ṽ and the corresponding volume V in preoperative MRI. Firstly, the MR sequence, obtained by reslicing the pre-operative MRI accordingly to the US trajectory, was reconstructed with the three evaluated methods. Secondly, the corresponding MR volume V (in terms of field of view and resolution) was computed using cubic interpolation. Finally, the reconstructed volumes obtained with VNN, DW and PT were compared to the "ground truth" V (see Fig. 6). The MSE between V and Ṽ , obtained with the different methods, was evaluated after removing the background (i.e. voxels zero intensity). The transformation matrix given by the neuronavigator is used to register the US and MR images. This registration is not corrected with an external registration procedure since only the intra-operative trajectory is required and used to create the stack of MR-scans. This means that tracking and calibration errors are removed : therefore reconstruction errors can be studied independently of other sources of errors.


Victor Quintero
email: victor.quintero-florez@inria.fr

Samir M Perlaza
email: samir.perlaza@inria.fr

Iñaki Esnaola
email: esnaola@sheffield.ac.uk

Jean-Marie Gorce
email: jean-marie.gorce@inria.fr

When Does Channel-Output Feedback Enlarge the Capacity Region of the Interference Channel?

Keywords: Interference Channel, Noisy Channel-Output Feedback, Capacity Region canal à interférences, rétroalimentation dégradée, Région de Capacité

In this research report, the benefits of channel-output feedback in the Gaussian interference channel (G-IC) are studied under the effect of additive Gaussian noise. Using a linear deterministic (LD) model, the signal to noise ratios (SNRs) in the feedback links beyond which feedback plays a significant role in terms of increasing the individual rates or the sum-rate are approximated. The relevance of this work lies on the fact that it identifies the feedback SNRs for which in any G-IC one of the following statements is true: (a) Feedback does not enlarge the capacity region; (b) Feedback enlarges the capacity region and the sum-rate is higher than the largest sum-rate without feedback; and (c) Feedback enlarges the capacity region but no significant improvement is observed in the sum-rate.

Introduction

The two-user Gaussian interference channel (G-IC) is the simplest channel model that captures the impairments brought by mutual interference into point-to-point communications subject to additive Gaussian noise. The interference channel (IC), in its most general form, was first proposed by Claude E. Shannon in [START_REF] Shannon | Two-way communication channels[END_REF]. The G-IC is a particular case that has been studied by several authors, see for instance [START_REF] Ahlswede | The capacity region of a channel with two senders and two receivers[END_REF][START_REF]A case where interference does not reduce capacity[END_REF][START_REF] Sato | Two-user communication channels[END_REF][START_REF]Interference channels[END_REF][START_REF] Sato | The capacity of the Gaussian interference channel under strong interference[END_REF][START_REF] Han | A new achievable rate region for the interference channel[END_REF][START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF][START_REF] Sason | On achievable rate regions for the Gaussian interference channel[END_REF][START_REF] Kramer | Outer bounds on the capacity of Gaussian interference channels[END_REF][START_REF] Chong | A comparison of two achievable rate regions for the interference channel[END_REF][START_REF] Chong | On the Han-Kobayashi region for the interference channel[END_REF] and references therein. However, despite this active research, the capacity region of the G-IC is characterized only in some special cases [START_REF]A case where interference does not reduce capacity[END_REF]. In general, the capacity region is not known exactly and only approximations to within a constant number of bits per channel-use per user are known [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF].

On the other hand, channel-output feedback, which consists in letting a transmitter observe the channel-output at its intended receiver, was one of the first models for studying two-way point-to-point communications [START_REF] Shannon | The zero-error capacity of a noisy channel[END_REF]. A G-IC with channel-output feedback is a model in which the backward direction (from receivers to transmitters) is exclusively used to let the transmitters observe the channel-output at the receivers with the goal of increasing the information rate or the reliability in the forward direction (from transmitters to receivers). Note that the backward direction may also be an IC since the point-to-point feedback links might be subject to mutual interference. There are several special cases of channel-output feedback in the G-IC. First, the case in which the observation of the channel-output from the intended receiver is noiseless corresponds to perfect channel-output feedback (POF) [START_REF] Suh | Feedback capacity of the Gaussian interference channel to within 2 bits[END_REF]. Second, the case in which such observation is noisy corresponds to noisy channel-output feedback (NOF) [START_REF] Le | Approximate capacity region for the symmetric Gaussian interference channel with noisy feedback[END_REF][START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF]. Third, the case in which such observation is a linear combination of the channel-outputs from both receivers subject to additive noise corresponds to wireless channel-output feedback (WOF) [START_REF] Sahai | Capacity of all nine models of channel output feedback for the two-user interference channel[END_REF]. The most general formulation is referred to as general channel-output feedback (GOF) [START_REF] Tuninetti | On interference channel with generalized feedback (IFC-GF)[END_REF][START_REF] Yang | Interference channel with generalized feedback (a.k.a. with source cooperation): Part I: Achievable region[END_REF][START_REF] Tuninetti | An outer bound region for interference channels with generalized feedback[END_REF][START_REF]An outer bound for the memoryless two-user interference channel with general cooperation[END_REF]. Other types of feedback, including a channel-output processing, e.g., signal decoding, are known as rate-limited feedback (RLF) [START_REF] Vahid | Interference channels with rate-limited feedback[END_REF].

This work focuses in the case of G-IC with NOF (G-IC-NOF). One of the main motivations to focus on the G-IC-NOF stems from the recent findings regarding the impact of additive noise in the feedback links. In particular, in [START_REF] Le | Approximate capacity region for the symmetric Gaussian interference channel with noisy feedback[END_REF] and [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF], it is shown that additive noise in the feedback links can dramatically change the number of generalized degrees of freedom (G-DoF) of the G-IC. In particular, one of the main benefits of feedback is that the number of G-DoF with perfect feedback increases monotonically with the interference to noise ratio (INR) in the very strong interference regime. However, in the presence of additive Gaussian noise in the feedback links, the number of G-DoF is bounded [START_REF] Le | Approximate capacity region for the symmetric Gaussian interference channel with noisy feedback[END_REF][START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF].

From the discussion above a relevant question arises: "When does channel-output feedback enlarge the capacity region of the G-IC?" This paper provides the answer when feedback links are impaired by noise and free of mutual interference, i.e., G-IC-NOF. The desired answer is of the form: "Implementing channel-output feedback in transmitter-receiver i enlarges the capacity region if the feedback SNR is bigger than SNR * i ", with i ∈ {1, 2} and fixed SNRs and INRs in the forward G-IC. Note that the description of the capacity region of the G-IC-NOF in [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF] does not provide an answer of the form mentioned above. An answer in the desired form requires some calculations that, despite the conceptual simplicity of this analysis, are long and tedious. More specifically, the value SNR * i is obtained by comparing the capacity region of the linear deterministic IC (LD-IC) in [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF] and the capacity region of the LD-IC with noisy channel-output feedback (LD-IC-NOF) in [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF] to identify the feedback parameters that ensure strict inclusion of the former into the latter. After, using the fact that the capacity region of the LD-IC-NOF approximates the capacity region of the G-IC-NOF, an approximation of SNR * i is obtained. Solving this problem leads to a handful of equally relevant byproducts to determine whether or not implementing feedback in one of the transmitter-receiver pairs increases any of the individual rates or the sum- The answers to the questions above provide a lot of engineering insights about the benefits of feedback in the G-IC. For instance, all the cases in which feedback, even perfect channel-output feedback, is useless for increasing an individual rate or the sum-rate are identified. Similarly, this work provides guidelines for choosing in which of the point-to-point links feedback should be implemented for increasing either an individual rate or the sum-rate. Interestingly, in some cases, implementing feedback in only one of the transmitter-receiver pairs, despite the additive noise, turns out to be as beneficial as perfect channel-output feedback in both links.

RR n°8862 T x 1 T x 2 Rx 2 Rx 1 + W 1 W 2 c W 2 c W 1 + + + ! h 11 ! h 22 h 22 h 11 h 12 h 21 Delay Delay X 1,n X 2,n ! Y 1,n ! Y 2,n ! Z 1,n ! Z 2,n Y 1,n Y 2,n Z 1,n Z 2,n

Channel Models

Gaussian Interference Channels

Consider the two-user G-IC-NOF depicted in Figure 1. Transmitter i, with i ∈ {1, 2}, communicates with receiver i subject to the interference produced by transmitter j, with j ∈ {1, 2}\{i}. There are two independent and uniformly distributed messages, W i ∈ W i , with W i = {1, 2, . . . , 2 N Ri }, where N denotes the fixed block-length in channel uses and R i is the transmission rate in bits per channel use. At each block, transmitter i sends the codeword

X i = (X i,1 , X i,2 , . . . , X i,N ) T ∈ C i ⊆ X N i
, where X i and C i are respectively the channel-input alphabet and the codebook of transmitter i.

The channel coefficient from transmitter i to receiver i is denoted by -→ h ii , the channel coefficient from transmitter j to receiver i is denoted by h ij ; and the channel coefficient from channel-output i to transmitter i is denoted by ←h ii . All channel coefficients are assumed to be non-negative real numbers. At a given channel use n ∈ {1, 2, . . . , N }, the channel output at receiver i is denoted by -→ Y i,n . During channel use n, the input-output relation of the channel model is given by

- → Y i,n = - → h ii X i,n + h ij X j,n + - → Z i,n , (1)
where -→ Z i,n is a real Gaussian random variable with zero mean and unit variance that represents the noise at the input of receiver i. Let d > 0 be the finite feedback delay measured in channel uses. At the end of channel use n, transmitter i observes ← -Y i,n , which consists of a scaled and noisy version of

- → Y i,n-d . More specifically, ← - Y i,n = ® ← - Z i,n for n ∈ {1,2, . . . , d} ← - h ii - → Y i,n-d + ← - Z i,n , for n ∈ {d+1,d+2, . . . ,N }, (2)
where ← -Z i,n is a real Gaussian random variable with zero mean and unit variance that represents the noise in the feedback link of transmitter-receiver pair i. The random variables -→ Z i,n and ← -Z i,n are independent and identically distributed. In the following, without loss of generality, the feedback delay is assumed to be one channel use, i.e., d = 1. The encoder of transmitter i is defined by a set of deterministic functions f

(1) i , f (2) i , . . . , f (N ) i , with f (1) i : W i → X i and for all n ∈ {2, 3, . . . , N }, f (n) i : W i × R n-1 → X i , such that X i,1 =f (1) i (W i ) , (3a)
and for all n ∈ {2, 3, . . . , N },

X i,n =f (n) i Ä W i , ← - Y i,1 , ← - Y i,2 , . . . , ← - Y i,n-1 ä . (3b)
The components of the input vector X i are real numbers subject to an average power constraint:

1

N N n=1 E X 2 i,n ≤ 1, (4)
where the expectation is taken over the joint distribution of the message indices W 1 , W 2 , and the noise terms, i.e.,

- → Z 1 , - → Z 2 , ← - Z 1 , and ← - Z 2 .
The dependence of X i,n on W 1 , W 2 , and the previously observed noise realizations is due to the effect of feedback as shown in (2) and (3).

Hence, the decoder of receiver i is defined by a deterministic function ψ i : R N i → W i . At the end of the communication, receiver i uses the vector

- → Y i,1 , - → Y i,2 , . . ., - → Y i,N
T to obtain an estimate of the message index:

W i =ψ i Ä - → Y i,1 , - → Y i,2 , . . . , - → Y i,N ä , (5)
where W i is an estimate of the message index. The decoding error probability in the two-user G-IC-NOF, denoted by P e (N ), is given by

P e (N )=max Pr Ä " W 1 = W 1 ä , Pr Ä " W 2 = W 2 ä . (6)
The definition of an achievable rate pair (R 1 , R 2 ) ∈ R 2 + follows:

Definition 1 (Achievable Rate Pairs) A rate pair (R 1 , R 2 ) ∈ R 2 + is achievable if there exists at least one pair of codebooks in X N 1 and in X N 2 with codewords of length N , the corresponding encoding functions f

(1) 1 , f (2) 1 , . . . , f (N ) 1 and f (1) 2 , f (2) 2 , . . . , f (N ) 2
, and the decoding functions ψ 1 and ψ 2 , such that the decoding error probability can be made arbitrarily small by letting the block-length N grow to infinity.

The set of all achievable information rate pairs (R 1 , R 2 ) is known as the information capacity region. The capacity region of a G-IC-NOF is described by six parameters:

--→ SNR i , INR ij and ←--SNR i , with i ∈ {1, 2} and j ∈ {1, 2}\{i}, which are defined as follows:

--→ SNR i = - → h 2 ii , (7)
INR ij =h 2 ij , and (8)
←-- SNR i = ← - h 2 ii Ä - → h 2 ii + 2 - → h ii h ij + h 2 ij + 1 ä . (9)
Given fixed parameters

--→ SNR 1 , --→ SNR 2 , INR 12 , INR 21 , ←-- SNR 1
, and ←--SNR 2 , the capacity region of the G-IC-NOF is approximated to within a constant number of bits by Theorem 4 in [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF].

Linear Deterministic Interference Channels

Consider the two-user LD-IC-NOF with parameters -→ n 11 , -→ n 22 , n 12 , n 21 , ←n 11 and ←n 22 depicted in Fig. 2. Parameter -→ n ii represents the number of bit-pipes between transmitter i and receiver i; parameter n ij represents the number of bit-pipes between transmitter j and receiver i; and parameter ←n ii represents the number of bit-pipes between receiver i and transmitter i (feedback). At transmitter i, the channel-input X i,n during channel use n, with n ∈ {1, 2, . . . , N }, is a q-dimensional binary vector X i,n = Ä X

i,n , X

i,n , . . . , X (q) i,n ä T , where

q = max ( - → n 11 , - → n 22 , n 12 , n 21 ) , ( 10
)
and N is the block-length. At receiver i, the channel-output -→ Y i,n during channel use n is also a

q-dimensional binary vector - → Y i,n = Ä - → Y (1) i,n , - → Y (2) i,n , . . . , - → Y (q) i,n ä T .
Let S be a q × q lower shift matrix of the form:

S =         0 0 0 • • • 0 1 0 0 • • • 0 0 1 0 • • • . . . . . . . . . . . . . . . 0 0 • • • 0 1 0         . ( 11
)
The input-output relation during channel use n is given by

- → Y i,n =S q-- → n ii X i,n + S q-nij X j,n , (12)
and the feedback signal ← -Y i,n available at transmitter i at the end of channel use n satisfies

← - Y i,n =S (max( - → n ii,nij )-← - n ii) + -→ Y i,n-d , ( 13
)
where d is a finite delay, additions and multiplications are defined over the Galois Field of two elements GF(2), and (•) + is the positive part operator.

T X1 T X2 RX2 RX1 n 11 n 22 X 1,5 X 1,1 ! n 11 ! n 22 n 12 n 21

Signal

Interference Feedback Without any loss of generality, the feedback delay is assumed to be equal to one channel use. Let W i be the set of message indices of transmitter i. Transmitter i sends the message index W i ∈ W i by sending the codeword X i = (X i,1 , X i,2 , . . . , X i,N ), which is a binary q × N matrix. The encoder of transmitter i can be modeled as a set of deterministic mappings f

(1) i , f (2) i , . . . , f (N ) i , with f (1) i : W i → {0, 1} q and for all n ∈ {2, 3, . . . , N }, f (n) i : W i × {0, 1} q×(n-1) → {0, 1} q , such that X i,1 =f (1) i W i (14a)
and for all n ∈ {2, 3, . . . , N },

X i,n =f (n) i W i , ← - Y i,1 , ← - Y i,2 , . . . , ← - Y i,n-1 . (14b)
The decoder of receiver i is defined by a deterministic function

ψ i : {0, 1} q×N → W i . At the end of the communication, receiver i uses the sequence Ä - → Y i,1 , - → Y i,2 , . . . , - → Y i,N ä to obtain an estimate W i of the message index W i .
The decoding error probability in the two-user LD-IC-NOF, denoted by P e (N ), is given by [START_REF] Sato | The capacity of the Gaussian interference channel under strong interference[END_REF].

A rate pair (R 1 , R 2 ) ∈ R 2 + is said to be achievable if it satisfies Definition 1.
The set of all achievable information rate pairs (R 1 , R 2 ) is known as the information capacity region and it is characterized by Theorem 1 in [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF].

Connections between Linear Deterministic and Gaussian Interference Channels

The capacity region of the G-IC-NOF with parameters

--→ SNR 1 , --→ SNR 2 , INR 12 , INR 21 , ←-- SNR 1 and ←-- SNR 2 can

be approximated by the capacity region of an LD-IC-NOF with parameters

- → n ii = RR n°8862 1 2 log 2 ( --→ SNR i ) ; n ij = 1 2 log 2 (INR ij ) ; ← - n ii = 1 2 log 2 ( ←-- SNR i )
, with i ∈ {1, 2} and j ∈ {1, 2}\{i}. For instance, in the case without feedback, the capacity region of any G-IC with parameters

--→ SNR 1 > 1, --→ SNR 2 > 1, INR
→ n 11 = 1 2 log 2 ( --→ SNR 1 ) , - → n 22 = 1 2 log 2 ( --→ SNR 2 ) , - → n 12 = 1 2 log 2 ( --→ INR 21 ) , and - → n 21 = 1 2 log 2 ( --→ INR 21 ) (Theorem 2 in [23]
). More specifically, if the capacity region of the G-IC and LD-IC without feedback are denoted by C G and C LD , respectively, the following holds:

C LD ⊆C G + (5, 5), and (15a)
C G ⊆C LD + (13.6, 13.6). (15b)
In a more general setting, for instance in the case with noisy channel-output feedback, the LD-IC is known to be a close approximation of the G-IC [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF]. In Section 5, this approximation is used to simplify the identification of the cases in which channel-output feedback, even subject to additive noise, enlarges the capacity region of the G-IC.

3 Main Results

Preliminaries

Let α i ∈ Q, with i ∈ {1, 2} and j ∈ {1, 2} \ {i} be defined as

α i = n ij - → n ii . (16)
For each transmitter-receiver pair i, there exist five possible interference regimes (IRs), as suggested in [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]: the very weak IR (VWIR), i.e., α i 1 2 , the weak IR (WIR), i.e., 1 2 < α i 2 3 , the moderate IR (MIR), i.e., 2 3 < α i < 1, the strong IR (SIR), i.e., 1 α i 2 and the very strong IR (VSIR), i.e., α i > 2. The scenarios in which the desired signal is stronger than the interference (α i < 1), namely the VWIR, the WIR, and the MIR, are referred to as the low-interference regimes (LIRs). Conversely, the scenarios in which the desired signal is weaker than or equal to the interference (α i 1), namely the SIR and the VSIR, are referred to as the high-interference regimes (HIRs).

The main results of this paper are presented using a set of events (Boolean variables) that are determined by the parameters -→ n 11 , -→ n 22 , n 12 , and n 21 . Given a fixed tuple ( -→ n 11 , -→ n 22 , n 12 , n 21 ), the events are defined below:

E 1 : α 1 < 1 ∧ α 2 < 1, (17)
E 2,i :

α i 1 2 ∧ 1 α j 2, (18)
E 3,i : α i 1 2 ∧ α j > 2, (19)
E 4,i : 1 2 < α i 2 3 ∧ α j 1, (20)
E 5,i : 2 3 < α i < 1 ∧ α j 1, (21)
E 6,i : 1 2 < α i 1 ∧ α j > 1, (22)
E 7,i :

α i 1 ∧ α j 1, (23)
E 8,i : - → n ii > n ji , (24)
E 9 : - → n 11 + - → n 22 > n 12 + n 21 , (25)
RR n°8862

E 10,i : - → n ii + - → n jj > n ij + 2n ji , (26)
E 11,i : - → n ii + - → n jj < n ij . (27)
In the following, given an event, e.g.

E 8,i : - → n ii > n ji , the notation ‹ E 8,i indicates - → n ii < n ji ; the notation E 8,i indicates - → n ii n ji (logical complement); and the notation Ě8,i indicates - → n ii n ji .
Combining the events ( 17)- [START_REF] Perlaza | Perfect output feedback in the two-user decentralized interference channel[END_REF], five main scenarios are identified:

S 1,i : (E 1 ∧ E 8,i )∨(E 2,i ∧ E 8,i )∨(E 3,i ∧ E 8,i ∧ E 9 )∨(E 4,i ∧ E 8,i ∧ E 9 )∨(E 5,i ∧ E 8,i ∧ E 9 ) , (28) S 2,i : Ä E 3,i ∧ ‹ E 8,j ∧ E 9 ä ∨ Ä E 6,i ∧ ‹ E 8,j ∧ E 9 ä ∨ Ä ‹ E 1 ∧ ‹ E 8,j ä , (29)
S 3,i : E 1 ∧ E 8,i ∨ E 2,i ∧ E 8,i ∨ E 3,i ∧ Ě8,j ∧ E 8,i ∨ E 4,i ∧ Ě8,j ∧ E 8,i ∨ E 5,i ∧ Ě8,j ∧ E 8,i ∨ E 1 ∧ Ě8,j ∨ (E 7,i ) , (30)
S 4 : E 1 ∧ E 8,1 ∧ E 8,2 ∧ E 10,1 ∧ E 10,2 , (31)
S 5 : E 1 ∧ E 11,1 ∧ E 11,2 . (32)
For all i ∈ {1, 2}, the events S 1,i , S 2,i , S ), due to the effect of channel-output feedback with respect to the case without feedback is

∆ 1 ( ← - n 11 , ← - n 22 )= max 0<R2<R * 2 sup (R1,R2)∈C( ← - n 11, ← - n 22) R 1 - sup (R † 1 ,R2)∈C(0,0) R † 1 and (33)
∆ 2 ( ← - n 11 , ← - n 22 )= max 0<R1<R * 1 sup (R1,R2)∈C( ← - n 11, ← - n 22) R 2 - sup (R1,R † 2 )∈C(0,0) R † 2 , (34)
with

R * 1 = sup (r1,r2)∈C(0,0) r 1 and (35) R * 2 = sup (r1,r2)∈C(0,0) r 2 . ( 36
) RR n°8862
Note that for a fixed i ∈ {1, 2}, ∆ i ( ←n 11 , ←n 22 ) > 0 if and only if it is possible to achieve a rate pair (R 1 , R 2 ) with channel-output feedback such that R i is higher than the maximum rate achievable by transmitter-receiver i without feedback when the rate of transmitter-receiver pair j is fixed at R j . In the following, given fixed parameters ←n 11 and ←n 22 , the statement "the rate R i is improved by using feedback" is used to indicate that ∆ i ( ←n 11 , ←n 22 ) > 0. Alternatively, the maximum improvement of the sum-rate Σ( ←n 11 , ←n 22 ) with respect to the case without feedback is

Σ( ← - n 11 , ← - n 22 )= sup (R1,R2)∈C( ← - n 11, ← - n 22) R 1 + R 2 - sup (R † 1 ,R † 2 )∈C(0,0) R † 1 + R † 2 . ( 37
)
Note that Σ( ←n 11 , ←n 22 ) > 0 if and only if there exists a rate pair with feedback whose sum is higher than the maximum sum-rate achievable without feedback. In the following, given fixed parameters ←n 11 and ←n 22 , the statement "the sum-rate is improved by using feedback" is used to imply that Σ( ←n 11 , ←n 22 ) > 0. In the following, when feedback is exclusively used by transmitter-receiver pair i, i.e., ←n ii > 0 and ←n jj = 0, then the maximum improvement of the individual rate of transmitter-receiver k, with k ∈ {1, 2}, and the maximum improvement of the sum-rate are denoted by ∆ k ( ←n ii ) and Σ( ←n ii ), respectively. Hence, this notation

∆ k ( ← - n ii ) replaces either ∆ k ( ← - n 11 , 0) or ∆ k (0, ← - n 22
), when i = 1 or i = 2, respectively. The same holds for the notation Σ( ← -

n ii ) that replaces Σ( ← - n 11 , 0) or Σ(0, ← - n 22
), when i = 1 or i = 2, respectively.

Enlargement of the Capacity Region

← - n * ii = ® max Ä n ji , ( - → n ii -n ij ) + ä if S 1,i = True - → n jj + ( - → n ii -n ij ) + if S 2,i = True. (38)
Assume that S 3,i = True. Then, for all ← -

n ii ∈ N, C 0, 0 = C ← - n ii . Assume that either S 1,i = True or S 2,i = True. Then, for all ← - n ii ← - n * ii , C 0, 0 = C ← - n ii and for all ← - n ii > ← - n * ii , C 0, 0 ⊂ C ← - n ii .
Proof: The proof of Theorem 1 is presented in Appendix A. Theorem 1 shows that under event S 3,i in (30), implementing feedback in transmitter-receiver pair i, with any ←n ii > 0 and ←n jj = 0, does not enlarge the capacity region. Note that when both E 8,i and ‹ E 8,j hold false, then both S 1,i and S 2,i hold false, which implies that S 3,i holds true (Corollary 1). The following remark is a consequence of this observation.

Remark 1: A necessary but not sufficient condition for enlarging the capacity region by using feedback in transmitter-receiver pair i is: there exists at least one transmitter able to send more information bits to receiver i than to receiver j, i.e., -

→ n ii > n ji (Event E 8,i ) or n ij > - → n jj (Event ‹ E 8,j ).

RR n°8862

Alternatively, under events S 1,i in (28) and S 2,i in (29), the capacity region can be enlarged when ← -

n ii > ← - n * ii .
It is important to highlight that in the cases in which feedback enlarges the capacity region of the two-user LD-IC-NOF, that is, in events S 1,1 , S 2,1 , S 1,2 or S 2,2 , for all i ∈ {1, 2} and j ∈ {1, 2} \ {i}, the following is always true :

← - n * ii > ( - → n ii -n ij ) + . ( 39
)
Essentially, the inequality in (39) unveils a necessary but not sufficient condition to enlarge the capacity region using channel-output feedback. This condition is that for at least one i ∈ {1, 2}, with j ∈ {1, 2} \ {i}, transmitter i decodes a subset of the information bits sent by transmitter j at each channel use.

Another interesting observation is that the threshold ←n * ii beyond which feedback is useful is different under event S 1,i in (28) and event S 2,i in (29). In general when S 1,i holds true, the enlargement of the capacity region is due to the fact that feedback allows using interference as side information [START_REF] Shannon | Channels with side information at the transmitter[END_REF]. Alternatively, when S 2,i in (29) holds true, the enlargement of the capacity region occurs as a consequence of the fact that some of the bits that cannot be transmitted directly from transmitter j to receiver j, can arrive to receiver j via an alternative path: transmitter j -receiver i -transmitter i -receiver j. Both scenarios, interference as side information and alternative path, are extensively discussed in [START_REF] Suh | Feedback capacity of the Gaussian interference channel to within 2 bits[END_REF], [START_REF] Le | Approximate capacity region for the symmetric Gaussian interference channel with noisy feedback[END_REF], and [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF].

Improvement of the

n † ii = max Ä n ji , ( - → n ii -n ij ) + ä . ( 40
)
Assume that either S 2,i = True or S 3,i = True. Then, for all ← -

n ii ∈ N, ∆ i ( ← - n ii ) = 0. Assume that S 1,i = True. Then, when ← - n ii ← - n † ii , it holds that ∆ i ( ← - n ii ) = 0; and when ← - n ii > ← - n † ii , it holds that ∆ i ( ← - n ii ) > 0.
Proof: The proof of Theorem 2 is presented in Appendix B. Theorem 2 highlights that under events S 2,i in (29) and S 3,i in (30), the individual rate R i cannot be improved by using feedback in transmitter-receiver pair i, i.e., ∆ i ( ←n ii ) = 0.

Alternatively, under event S 1,i in (28), the individual rate R i can be improved, i.e., ∆ i ← -

n ii > 0, whenever ← - n ii > max Ä n ji , ( - → n ii -n ij ) + ä
. Hence, given the definition of S 1,i , the following remark is relevant.

Remark 2: A necessary but not sufficient condition for ∆ i ←n ii > 0 is: the number of bit-pipes from transmitter i to receiver i is higher than the number of bit-pipes from transmitter i to receiver j, i.e., -→ n ii > n ji (Event E 8,i )

Improvement of the

n ii ∈ N, ∆ j ( ← - n ii ) = 0. Assume that either S 1,i = True or S 2,i = True. Then, when ← - n ii ← - n *
ii , it holds that ∆ j ( ←n ii ) = 0; and when ← -

n ii > ← - n * ii , it holds that ∆ j ( ← - n ii ) > 0.
Proof: The proof of Theorem 3 follows along the same lines of the proof of Theorem 2 in Appendix B.

Theorem 3 shows that under event S 3,i in (30), implementing feedback in transmitter-receiver pair i does not bring any improvement on the rate R j . This is in line with the results of Theorem 1. In contrast, under events S 1,i in (28) and S 2,i in (29), the individual rate R j can be improved, i.e., ∆ j ( ← -

n ii ) > 0 for all ← - n ii > ← - n * ii .
From the definition of events S 1,i and S 2,i , the following remark holds:

Remark 3: A necessary but not sufficient condition for ∆ j ←n ii > 0 is: there exists at least one transmitter able to send more information bits to receiver i than to receiver j, i.e., -→ n ii > n ji

(Event E 8,i ) or n ij > - → n jj (Event ‹ E 8,j
). It is important to highlight that under event S 1,i , the threshold on ←n ii for increasing the individual rate R i i.e., ←n † ii , and R j i.e., ←n * ii , are identical, see Theorem 2 and Theorem 3. This implies that in this case, the use of feedback in transmitter-receiver pair i, with ← -

n ii > ← - n † ii = ← - n *
ii , benefits both transmitter-receiver pairs, i.e., ∆ i ( ←n ii ) > 0 and ∆ j ( ←n ii ) > 0. Under event S 2,i , using feedback in transmitter-receiver pair i, with ← -

n ii > ← - n *
ii , exclusively benefits transmitterreceiver pair j, i.e., ∆ i ( ←n ii ) = 0 and ∆ j ( ←n ii ) > 0.

Improvement of the Sum-Rate

← - n + ii = ® max Ä n ji , ( - → n ii -n ij ) + ä if S 4 = True - → n jj + ( - → n ii -n ij ) + if S 5 = True. (41)
Assume that S 4 = False and S 5 = False. Then, Σ( ← -

n ii ) = 0 for all ← - n ii ∈ N. Assume that S 4 = True or S 5 = True. Then, when ← - n ii ← - n + ii , it holds that Σ( ← - n ii ) = 0; and when ← - n ii > ← - n + ii , it holds that Σ( ← - n ii ) > 0.
Proof: The proof of Theorem 4 is presented in Appendix C. Theorem 4 highlights a necessary but not sufficient condition for improving the sum-rate by implementing feedback in transmitter-receiver pair i.

Remark 4: A necessary but not sufficient condition for observing Σ( ←n ii ) > 0 is to satisfy one of the following conditions: (a) both transmitter-receiver pairs are in LIR (Event E 1 ); or (b) both transmitter-receiver pairs are in HIR (Event E 1 ).

Finally, it follows from Corollary 3 that when S 4 or S 5 holds true, with i ∈ {1, 2} and ← - In Example 1, both S 1,1 and S 1,2 hold true. Hence, from Theorem 1, when ←n 11 > 5 or ←n 22 > 3, there always exists an enlargement of the capacity region. More specifically, it follows from Theorem 2 and Theorem 3 that using feedback in transmitter-receiver pair 1, with ←n 11 > 5 or using feedback in transmitter-receiver pair 2, with ←n 22 > 3, both individual rates can be simultaneously improved, i.e., ∆ 1 ( ←n ii ) > 0 and ∆ 2 ( ←n ii ) > 0 with i = 1 or i = 2 respectively. Alternatively, note that S 4 holds true. Hence, it follows from Theorem 4 that using feedback in transmitter-receiver pair 1, with ←n 11 > 5 or using feedback in transmitter-receiver pair 2, with ←n 22 > 3, improves the sum-rate, i.e., Σ( ←n ii ) > 0 with i = 1 or i = 2 respectively. These conclusions are observed in Figure 3, for the case ←n 11 = 6 and ←n 22 = 0, where the capacity regions C(0, 0) (thick red line) and C(6, 0) (thin blue line) are plotted. Note that, when ←n 11 = 6, there always exist a rate pair (R 1 , R 2 ) ∈ C (0, 0) and a rate pair In Example 2, the events S 1,1 and S 1,2 hold true; and the events S 4 and S 5 hold false. Hence, it follows from Theorem 4 that using feedback in either transmitter-receiver pair does not improve the sum-rate, i.e., for all i ∈ {1, 2} and for all ←n ii > 0, Σ( ←n ii ) = 0. These conclusions are observed in Figure 4, for the case ←n 11 = 0 and ←n 22 = 7, where the capacity regions C(0, 0) (thick red line) and C(0, 7) (thin blue line) are plotted. From Example 2, it becomes evident that when S 1,1 and S 1,2 hold true, S 4 and S 5 do not necessarily hold true. That is, the improvements on the individual rates, despite that they can be observed simultaneously, are not enough to improve the sum-rate beyond what is already achievable without feedback. In Example 3, both S 2,1 in (29) and S 3,2 in (30) hold true. Hence, it follows from Theorem 1 that the capacity region can be enlarged by using feedback in transmitter-receiver pair 1 when ←n 11 > 3, whereas using feedback in transmitter-receiver pair 2 is useless. More specifically, it follows from Theorem 2 and Theorem 3 that using feedback in transmitter-receiver pair 1 does not improve the individual rate R 1 but R 2 , i.e., ∆ 1 ( ←n 11 ) = 0 and ∆ 2 ( ←n 11 ) > 0. Note also that S 4 and S 5 hold false. Hence, it follows from Theorem 4 that using feedback in either transmitterreceiver pair does not improve the sum-rate, i.e., Σ( ←n 11 ) = 0 and Σ( ←n 22 ) = 0. These conclusions are observed in Figure 5, for the case ←n 11 = 4 and ←n 22 = 0, where the capacity regions C(0, 0) (thick red line) and C(4, 0) (thin blue line) are plotted.

n ii > ← - n + ii , aside from the fact that Σ( ← - n ii ) > 0, it also holds that ∆ 1 ( ← - n ii ) > 0 and ∆ 2 ( ← - n ii ) > 0.
(R 1 , R 2 ) ∈ C(6, 0) \ C(0, 0) such that R 1 < R 1 and R 2 = R 2 (Theorem 2). Simultaneously, there always exist a rate pair (R 1 , R 2 ) ∈ C (0, 0) and a rate pair (R 1 , R 2 ) ∈ C(6, 0) \ C(0, 0) such that R 2 < R 2 and R 1 = R 1 (Theorem 3). Finally, note that for all rate pairs (R 1 , R 2 ) ∈ C (0, 0) there always exists a rate pair (R 1 , R 2 ) ∈ C(6, 0), for which R 1 + R 2 > R 1 + R 2 (Theorem 4).

Implications on the Gaussian Interference Channel

Given a fixed tuple

Ä --→ SNR 1 , --→ SNR 2 , INR 12 , INR 21 ä , let R( ←-- SNR 1 , ←-- SNR 2
) be the achievable region of the G-IC-NOF described by Theorem 2 in [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF] with parameters

Improvement Metrics

In order to quantify the benefits of channel-output feedback in enlarging the achievable region

R( ←-- SNR 1 , ←-- SNR 2 ) or the converse region R( ←-- SNR 1 , ←-- SNR 2 )
, consider the following improvement metrics, which are similar to those defined in Sec. 3.2 for the LD-IC-NOF. The improvement metrics on the individual rates are defined as

∆ A 1 ( ←-- SNR 1 , ←-- SNR 2 )= max 0<R2<R * 2 sup (R1,R2)∈R( ← -- SNR1, ← -- SNR2) {R 1 } - sup (R † 1 ,R2)∈R(0,0) {R † 1 } , (43)
∆ A 2 ( ←-- SNR 1 , ←-- SNR 2 )= max 0<R1<R * 1 sup (R1,R2)∈R( ← -- SNR1, ← -- SNR2) {R 2 } - sup (R1,R † 2 )∈R(0,0) {R † 2 } , (44)
∆ C 1 ( ←-- SNR 1 , ←-- SNR 2 )= max 0<R2<R † 2 sup (R1,R2)∈R( ← -- SNR1, ← -- SNR2) {R 1 } - sup (R † 1 ,R2)∈R(0,0) {R † 1 } , and (45)
∆ C 2 ( ←-- SNR 1 , ←-- SNR 2 )= max 0<R1<R † 1 sup (R1,R2)∈R( ← -- SNR1, ← -- SNR2) {R 2 } - sup (R1,R † 2 )∈R(0,0) {R † 2 } , (46)
with

R * 1 = sup (r1,r2)∈R(0,0) r 1 , (47)
R * 2 = sup (r1,r2)∈R(0,0) r 2 , (48)
R † 1 = sup (r1,r2)∈R(0,0) r 1 , and (49)
R † 2 = sup (r1,r2)∈R(0,0) r 2 . ( 50
) RR n°8862
Alternatively, the maximum improvements of the sum-rate

Σ A ( ←-- SNR 1 , ←-- SNR 2 ) and Σ C ( ←-- SNR 1 , ←-- SNR 2
) with respect to the case without feedback are

Σ A ( ←-- SNR 1 , ←-- SNR 2 )= sup (R1,R2)∈R( ← -- SNR1, ← -- SNR2) R 1 + R 2 - sup (R † 1 ,R † 2 )∈R(0,0) R † 1 + R † 2 , and (51)
Σ C ( ←-- SNR 1 , ←-- SNR 2 )= sup (R1,R2)∈R( ← -- SNR1, ← -- SNR2) R 1 + R 2 - sup (R † 1 ,R † 2 )∈R(0,0) R † 1 + R † 2 . (52)

Approximate Thresholds on the Feedback SNRs

In Sec. 2.3, the connections between the LD-IC-NOF and the G-IC-NOF were discussed. Using these connections, a G-IC with fixed parameters

Ä --→ SNR 1 , --→ SNR 2 , INR 12 , INR 21 ä is ap- proximated by an LD-IC with parameters - → n 11 = 1 2 log 2 ( --→ SNR 1 ) , - → n 22 = 1 2 log 2 ( --→ SNR 2 ) , - → n 12 = 1 2 log 2 ( --→ INR 21 ) and - → n 21 = 1 2 log 2 ( --→ INR 21
) . From this observation, the results from Theorem 1 -Theorem 4 can used to determine the feedback SNR thresholds beyond which either an individual rate or the sum-rate is improved in the original G-IC-NOF. The procedure consists on using the equalities ← -

n ii = 1 2 log 2 Ä ←-- SNR i ä , with i ∈ {1, 2}.
Hence, the corresponding thresholds in the G-IC can be approximated by:

←-- SNR * i =2 2 ← - n * ii (53a) ←-- SNR † i =2 2 ← - n † ii and (53b) ←-- SNR + i =2 2 ← - n + ii . (53c)
When the corresponding LD-IC-NOF is such that its capacity region can be improved when ←n ii > ←n * ii (Theorem 1), for a given i ∈ {1, 2}, it is expected that either the achievability or converse regions of the original G-IC-NOF become larger when ←--

SNR i > ←-- SNR * i .
Similarly, when the corresponding LD-IC-NOF is such that ∆ i ( ←n ii ) > 0 or ∆ i ( ←n jj ) > 0, it is expected to observe an improvement on the individual rate R i by either using feedback in transmitter-receiver pair i, with ←--SNR i > ←--SNR † i or by using feedback in transmitter-receiver pair j, with ←--SNR j > ←--SNR * j . In the case of the sum-rate, when the corresponding LD-IC-NOF is such that Σ( ←n ii ) > 0 using feedback in transmitter-receiver pair i, with ←n ii > ←n + ii , (Theorem 4), it is expected to observe an improvement on the sum-rate by using feedback in transmitter-receiver pair i, with ←--SNR i > ←--SNR + i . Finally, when no improvement in a given metric is observed in the LD-IC-NOF, i.e., ∆ 1 ( ← -

n 11 ) = 0, ∆ 1 ( ← - n 22 ) = 0, ∆ 2 ( ← - n 11 ) = 0, ∆ 2 ( ← - n 22 ) = 0, Σ( ← - n 11 ) = 0, or Σ( ← - n 22 ) = 0, only a negligible improvement (if any) is observed in the corresponding metric of the G-IC-NOF. For instance, when ∆ 1 ( ← - n 11 ) = 0, it is expected that ∆ C 1 ( ←-- SNR 1 , 0) < and ∆ A 1 ( ←-- SNR 1 , 0) < , with > 0 small. Similarly, when ∆ 2 ( ← - n 11 ) = 0, it is expected that ∆ C 2 ( ←-- SNR 1 , 0) < and ∆ A 2 ( ←-- SNR 1 , 0) < . Finally, when Σ( ← - n 11 ) = 0, it is expected that Σ C ( ←-- SNR 1 , 0) < and Σ A ( ←-- SNR 1 , 0) < .

Examples

The following examples highlight the relevance of the approximations in (53). 7 shows that significant improvements on the metrics 6b, and Figure 6d, where

! SNR1 = 44dB; ! SNR2 = 44dB; INR12 = 20dB; INR21 = 33dB; SNR1 = 100dB ⌃(bits/channel use) ⌃ C ( 100dB, SNR2) ⌃ A ( 100dB, SNR2) (e) (f) SNR ⇤ 1 SNR + 1 SNR + 2 SNR ⇤ 2 SNR ⇤ 1 SNR ⇤ 2 Figure 7: Improvement metrics ∆ A i , ∆ C i , Σ A , and Σ C as functions of ←-- SNR 1 and ←-- SNR 2 , with i ∈ {1, 2}, for Example 4. RR n°8862 ←-- SNR * 1 = ←-- SNR † 1 = ←-- SNR + 1 = 30dB and ←-- SNR * 2 = ←-- SNR † 2 = ←-- SNR + 2 = 18dB. Figure
∆ A i ( ←-- SNR 1 , ←-- SNR 2 ), ∆ C i ( ←-- SNR 1 , ←-- SNR 2 ), Σ A ( ←-- SNR 1 , ←-- SNR 2 ) and Σ C ( ←-- SNR 1 , ←-- SNR
∆ A 1 Ä -100dB, ←-- SNR 2 ä < 0.15 and ∆ C 1 Ä -100dB, ←-- SNR 2 ä < 0.1.
Finally, note that using feedback in either transmitter-receiver pair does not increase the sum-rate in the LD-IC-NOF, i.e., Σ( ←n 11 ) = Σ( ←n 22 ) = 0. This is also verified in the G-IC-NOF by Figure 6e and Figure 6f, where

Σ A Ä ←-- SNR 1 , -100dB ä < 0.15, Σ C Ä ←-- SNR 1 , -100dB ä < 0.05, Σ A Ä -100dB, ←-- SNR 2 ä < 0.15, and Σ C Ä -100dB, ←-- SNR 2 ä < 0.05.

Generalized Degrees of Freedom

This section focuses on the analysis of the number of GDoF of the LD-IC-NOF for studying the case in which feedback is simultaneously implemented in both transmitter-receiver pairs. Moreover, the analysis is only performed for the symmetric case, i.e., -

→ n = - → n 11 = - → n 22 , m = n 12 = n 21 , and ← - n = ← - n 11 = ← - n 22 , with ( - → n , m, ← - n ) ∈ N 3 .
The results in Lemma 1 allow a more general analysis of the GDoF, e.g., non-symmetric case. However, the symmetric case captures some of the most important insights about how the capacity region is enlarged when feedback is used in both transmitter-receiver pairs.

Essentially The plot without feedback is obtained from [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF] and the plot with perfect-output feedback is obtained from [START_REF] Suh | Feedback capacity of the Gaussian interference channel to within 2 bits[END_REF]. and β is given by

D(α, β)=min max(1, α), max Ä 1, β -(1 -α) + ä , 1 2
Ä max(1, α) + (1 -α) + ä , max Ä (1 -α) + , α, 1 -(max(1, α) -β) + ä ,
Properties (56a) and (56b) highlight the fact that the existence of feedback links in the symmetric LD-IC in the VWIR and WIR does not have any impact in the GDoF when β 1 2 , and the GDoF is equal to the case with perfect-output feedback when β > 1. Property (56c) underlines that in the symmetric LD-IC in MIR and SIR, the number of GDoF is identical in

RR n°8862

both extreme cases: without feedback (β = 0) and with perfect-output feedback β = max(1, α) . Finally, from (56d) and (56e), it follows that for observing an improvement in the GDoF of the LD-IC-NOF in VSIR, the following condition must be met: β > 1. That is, the number of bit-pipes in the feedback links must be strictly bigger than the number of bit-pipes in the direct links.

Figure 8 shows the number of GDoF for the two user symmetric LD-IC-NOF for the case in which 0 α 3 and β ∈ { ) holds with strict inclusion. Using these results from the LD approximation, the SNRs in the feedback links beyond which feedback plays a significant role in terms of increasing the individual rates or the sum-rate in the G-IC are identified. The relevance of this work lies on the fact that it allows identifying a number of scenarios in any G-IC for which one of the following statements is true: (a) Feedback does not enlarge the capacity region; (b) Feedback enlarges the capacity region and the sum-rate is higher than the largest sum-rate without feedback; and (c) Feedback enlarges the capacity region but no significant improvement is observed in the sum-rate.

Figure 2 :

 2 Figure 2: Two-user linear deterministic interference channel with noisy channel-output feedback. The bit-pipe line number 1 represents the most significant bit.

Theorem 1

 1 Given fixed parameters ( -→ n 11 , -→ n 22 , n 12 , n 21 ), i ∈ {1, 2}, and j ∈ {1, 2} \ {i}, the capacity region of a two-user LD-IC, when feedback is available only at transmitter-receiver pair i, i.e., ←n ii > 0 and ←n jj = 0, is denoted by C ( ←n ii ) instead of C ( ←n 11 , 0) or C (0, ←n 22 ), when i = 1 or i = 2, respectively. Following this notation, Theorem 1 identifies the exact values of ←n ii for which the strict inclusion C (0, 0) ⊂ C ( ←n ii ) holds for i ∈ {1, 2}. Let ( -→ n 11 , -→ n 22 , n 12 , n 21 ) ∈ N 4 be a fixed tuple. Let also i ∈ {1, 2}, j ∈ {1, 2} \ {i} and ←n * ii ∈ N be fixed integers, with

Figure 3 : 4 ExamplesExample 1

 341 Figure 3: Capacity regions C(0, 0) (thick red line) and C(6, 0) (thin blue line), with -→ n 11 = 7, -→ n 22 = 7, n 12 = 3, n 21 = 5.

Example 2

 2 Consider an LD-IC-NOF with parameters -→ n 11 = 7, -→ n 22 = 8, n 12 = 6, and n 21 = 5.

Figure 4 :

 4 Figure 4: Capacity regions C(0, 0) (thick red line) and C(0, 7) (thin blue line), with -→ n 11 = 7, -→ n 22 = 8, n 12 = 6, n 21 = 5.

Example 3

 3 Consider an LD-IC-NOF with parameters -→ n 11 = 5, -→ n 22 = 1, n 12 = 3, and n 21 = 4.

Figure 5 :

 5 Figure 5: Capacity regions C(0, 0) (thick red line) and C(4, 0) (thin blue line), with -→ n 11 = 5, -→ n 22 = 1, n 12 = 3, n 21 = 4.

Example 4 1 Figure 6 : 22 = 3 .

 416223 Figure 6: Improvement metrics ∆ A i , ∆ C i , Σ A , and Σ C as functions of ←--SNR 1 and ←--SNR 2 , with i ∈ {1, 2}, for Example 5. The linear deterministic approximation to the G-IC in Example 4 is the one presented in Example 1. Hence, ←n * 11 = ←n † 11 = ←n + 11 = 5 and ←n * 22 = ←n † 22 = ←n + 22 = 3. This implies that

Theorem 5

 5 , given the parameters -→ n , m and ←n , with α = m -→ n and β = ←n -→ n , the number of GDoF, denoted by D(α, β), is the ratio between the symmetric capacity, i.e.,C sym ( -→ n , m, ←n ) = sup{R : (R, R) ∈ C( -→ n , -→ n , m, m, ←n , ←n )},and the individual interference-free point-to-point capacity, i.e., -→ n , when ( -→ n , m, ←n ) → (∞, ∞, ∞) at constant ratios α = m -→ n and β = the number of GDoF for the two-user LD-IC-NOF. The number of GDoF for the two user symmetric LD-IC-NOF with parameters α RR n°8862

Figure 8 :

 8 Figure 8: Generalized Degrees of Freedom (GDoF) as a function of parameters α and β, with 0 α 3 and β ∈ { 3 5 , 4 5 , 6 5 }, of the symmetric LD-IC-NOF.The plot without feedback is obtained from[START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF] and the plot with perfect-output feedback is obtained from[START_REF] Suh | Feedback capacity of the Gaussian interference channel to within 2 bits[END_REF].

1 3 ÅCorollary 4 2 ò

 1342 max(1, α) + (1α) + + max ÅÅ 1α ã + , α, 1 -(max (1, α)β)The proof of Theorem 5 is presented in Appendix D. The result in Theorem 5 can also be obtained from Theorem 1 in[START_REF] Le | Approximate capacity region for the symmetric Gaussian interference channel with noisy feedback[END_REF]. The following properties are a direct consequence of Theorem 5. The number of GDoF for the two user symmetric LD-IC-NOF with parameters α and β satisfies the following properties: andβ ∈ [0, ∞), D(α, 0) = D(α, β) = D(α, max(1, α)), (56c) ∀α ∈ (2, ∞) and β 1, 1 D(α, β) min α 2 , β ,(56d)∀α ∈ (2, ∞) and β < 1, D(α, β) = 1.

  In this research report, for any 4-tuple ( -→ n 11 , -→ n 22 , n 12 , n 21 ) ∈ N 4 , the exact values on the feedback parameters ←n 11 and ←n 22 of the two-user LD-IC-NOF beyond which the capacity region can be enlarged are characterized. That is, the exact values of ←n 11 (resp. ←n 22 ) for which C(0, 0) ⊂ C( ←n 11 , 0) resp. C(0, 0) ⊂ C(0, ←n 22

  12 > 1 and INR 21 > 1 is within 18.6 bits per channel use per user of the capacity of an LD-IC with parameters -

  3,i , S 4 and S 5 exhibit the properties stated by the following corollaries.

Corollary 1 For all ( -→ n 11 , -→ n 22 , n 12 , n 21 ) ∈ N 4 , given a fixed i ∈ {1, 2}, only one of the events S 1,i , S 2,i and S 3,i is true. Corollary 2 For all ( -→ n 11 , -→ n 22 , n 12 , n 21 ) ∈ N 4 , when one of the events S 4 or S 5 holds true, then the other necessarily holds false. Note that Corollary 2 does not exclude the case in which both S 4 and S 5 are simultaneously false. Corollary 3 For all ( -→ n 11 , -→ n 22 , n 12 , n 21 ) ∈ N 4 , when S 4 holds true, then both S 1,1 and S 1,2

hold true; and when S 5 holds true, then both S 2,1 and S 2,2 hold true.

3.2 Rate Improvement Metrics

Given a fixed tuple ( -→ n 11 , -→ n 22 , n 12 , n 21 ), let C( ←n 11 , ←n 22 ) be the capacity region of an LD-IC with noisy channel-output feedback with parameters ←n 11 and ←n 22 . The maximum improvement of the individual rates R 1 and R 2 , denoted by ∆ 1 ( ←n 11 , ←n 22 ) and ∆ 2 ( ←n 11 , ←n 22

  Individual Rate R i by Using Feedback in Link i

Given fixed parameters ( -→ n 11 , -→ n 22 , n 12 , n 21 ), and i ∈ {1, 2}, implementing channel-output feedback in transmitter-receiver pair i increases the individual rate R i , i.e., ∆ i ( ←n ii ) > 0 for some values of ←n ii . Theorem 2 identifies the exact values of ←n ii for which ∆ i ( ←n ii ) > 0. Theorem 2 Let ( -→ n 11 , -→ n 22 , n 12 , n 21 ) ∈ N 4 be a fixed tuple. Let also i ∈ {1, 2}, j ∈ {1, 2} \ {i} and ←n † ii ∈ N be fixed integers, with ← -

  Individual Rate R j by Using Feedback in Link i

	∆ j ( ← -n ii ) > 0 for some values of ← -n ii . Theorem 3 identifies the exact values of ← -n ii for which ∆ j ( ← -n ii ) > 0.
	Theorem 3 Let ( -→ n 11 , -→ n 22 , n 12 , n 21 ) ∈ N 4 be a fixed tuple. Let also i ∈ {1, 2}, j ∈ {1, 2} \ {i} and ← -n * ii ∈ N given in (38), be fixed integers. Assume that S 3,i = True. Then, for all ← -
	Given fixed parameters ( -→ n 11 , -→ n 22 , n 12 , n 21 ), i ∈ {1, 2}, and j ∈ {1, 2} \ {i}, implementing
	RR n°8862

channel-output feedback in transmitter-receiver pair i increases the individual rate R j , i.e.,

  2 ) are obtained when the feedback SNRs are beyond the corresponding thresholds. More importantly, negligible effects are observed when It follows from the LD-IC that using feedback in transmitter-receiver pair 1 exclusively increases the individual rate R 2 . This is observed in Figure6c. Note that the improvement in the individual rate R 2 for all Note also that using feedback in either transmitter-receiver pair does not improve the rate R 1 in the LD-IC-NOF, i.e., ∆ 1 ( ← -n 11 ) = ∆ 1 ( ← -n22 ) = 0. This is also verified in the G-IC-NOF by Figure 6a, Figure

	←--SNR * 1 and	←--SNR 2 <	←--SNR * 2 .		←--SNR 1 <
	Example 5 Consider a G-IC with parameters	--→ SNR 1 = 33dB,	--→ SNR 2 = 9dB, INR 12 = 20dB, and
	INR 21 = 27dB.
	The linear deterministic approximation to the G-IC in Example 5 is the one presented in Example 3. Hence, ← -n * 11 = 3, which implies that ←--SNR * 1 = 18dB. ←--SNR 1 < ←--SNR * 1 is negligible. Significant improvement is observed only beyond the threshold ←--SNR * 1 .

RR n°8862

X 1,1 X 1,2 X 1,3 X 1,4 X 1,5 X 2,4 X 2,3 X 2,2 X 2,1 X 1,1 X 1,2 X 1,3 L X 2,1 X 1,4 L X 2,2 X 1,5 L X 2,3 X 2,1 L X 1,2 X 2,2 L X 1,3 X 2,3 L X 1,4X 2,4 L

This research was supported in part by the European Commission under Marie Skłodowska-Curie Individual Fellowship No. 659316 (CYBERNETS); and the Administrative Department of Science, Technology, and Innovation of Colombia (Colciencias), fellowship No. 617-2013.

) ensures C(0, 0) ⊂ C( ←n 11 , 0) (resp. C(0, 0) ⊂ C(0, ←n 22 )) is calculated. This procedure is tedious and repetitive, and thus, in this appendix only one combination of interference regimes is studied, e.g., VWIR -VWIR.

Proof: Consider that both transmitter-receiver pairs are in VWIR, that is,

Under conditions (57), it follows from Theorem 1 in [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF] that C(0, 0) is the set of non-negative rate pairs (R 1 , R 2 ) that satisfy

Under conditions (57) and (59), it follows from Theorem 1 in [START_REF] Quintero | Approximate capacity region of the two-user Gaussian interference channel with noisy channel-output feedback[END_REF] that

When comparing C(0, 0) and C( ←n 11 , 0), note that (58a), (58b), (58c), and (58e) are equivalent to (60a), (60b), (60c), and (60e), respectively. Under these observations, the region C( ←n 11 , 0) is greater than the region C(0, 0) if at least one of the following conditions is true:

min(θ 6 , θ 1 + 2θ

Plugging (63) into (58) yields:

To simplify the inequalities containing the operator max(•, •) in (66), the following 2 cases are identified:

Case 2a : -→ n 11 > n 21 ; and (68)

Case 2a: Plugging (68) into (66) yields:

Comparing inequalities (70a) and (70b) with inequality (67a), it can be verified that min -

Comparing inequalities (70c) and (67b), it can be verified that 2 59), (63), and (68).

Case 2b: Plugging (69) into (66) yields: ). However, under the assumptions (57), ( 59), (63), and (69), the bounds (67b) and (71c) are not active. Hence, condition (61b) does not hold. Therefore, for all ←n 11 ∈ N, the capacity region cannot be enlarged under assumptions (57), ( 59), (63), and (69).

Case 3: Under assumptions (57) and (64), this case is possible. Plugging (64) into (60) yields:

Plugging ( 64) into (58) yields:

To simplify the inequalities containing the operator max(•, •) in ( 72) and (73), the following 2 cases are identified:

Case 3b :

Case 3a: Plugging (74) into (72) yields:

Plugging (74) into (73) yields: Case 3b: Plugging (75) into (72) yields:

Plugging (74) into (73) yields:

Comparing inequalities (78a) and (78b) with inequality (79a), it can be verified that min -→ n

Plugging ( 65) into (58) yields: ), then C(0, 0) ⊂ C( ←n 11 , 0). Otherwise C(0, 0) = C( ←n 11 , 0). Note that when events E 1 and E 8,1 hold simultaneously true, then the event S 1,1 is true, which verifies the statement of Theorem 1. The same procedure can be applied for all the other combinations of interference regimes. This completes the proof.

B Proof of

, is calculated. This procedure is tedious and repetitive, and thus, in this appendix only one combination of interference regimes is studied, e.g., VWIR -VWIR.

Proof:

Consider that both transmitter-receiver pairs are in VWIR, i.e., conditions (57) hold. Under these conditions, the capacity regions C(0, 0) and C( ←n 11 , 0) are given by ( 58) and (60), respectively. When comparing C(0, 0) and C( ←n 11 , 0), note that (58a), (58b), (58c), and (58e) are equivalent to (60a), (60b), (60c), and (60e), respectively. In this case any improvement on R 1 is produced by an improvement on R 1 + R 2 (condition (61a)) or 2R 1 + R 2 (condition (61a)), and thus, the proof of Theorem 2 in these particular interference regimes follows exactly the same steps in Theorem 1. This completes the proof.

C Proof of

, is calculated. This procedure is tedious and repetitive, and thus, in this appendix only one combination of interference regimes is studied, e.g., VWIR -VWIR.

Proof: Consider that both transmitter-receiver pairs are in VWIR, i.e., conditions (57) hold. Under these conditions, the capacity regions C(0, 0) and C( ←n 11 , 0) are given by ( 58) and (60), respectively. When comparing C(0, 0) and C( ←n 11 , 0), note that (58a), (

are equivalent to (60a), (60b), (60c), and (60e), respectively.

In this case, the proof is focused on any improvement on R 1 + R 2 (condition (61a)), and thus, the proof of Theorem 4 in these particular interference regimes follows exactly the same steps in Theorem 1.

From the analysis presented in Appendix A, it follows that: Case 2a: condition (61a) holds true, when ← - , and E 10,2 hold simultaneously true, then the event S 4 is true, which verifies the statement of Theorem 4. The same procedure can be applied for all the other combinations of interference regimes. This completes the proof.

D Proof of Theorem 5: Generalized Degrees of Freedom

This appendix provides a proof to Theorem 5 for the two user LD-IC-NOF. ) of the two-user LD-IC-NOF is the set of non-negative rate pairs (R 1 , R 2 ) that satisfy ∀i ∈ {1, 2} and j ∈ {1, 2} \ {i}: RR n°8862

RR n°8862