11institutetext: Warsaw University of Technology, Warsaw, Poland 11email:
<EMAIL_ADDRESS>
# Large-Scale Topological Radar Localization Using Learned Descriptors
††thanks: The project was funded by POB Research Centre for Artificial
Intelligence and Robotics of Warsaw University of Technology within the
Excellence Initiative Program - Research University (ID-UB)

Jacek Komorowski (✉) 11 0000-0001-6906-4318 Monika Wysoczanska 11
0000-0001-7785-2277 Tomasz Trzcinski 11 0000-0002-1486-8906

###### Abstract

In this work, we propose a method for large-scale topological localization
based on radar scan images using learned descriptors. We present a simple yet
efficient deep network architecture to compute a rotationally invariant
discriminative global descriptor from a radar scan image. The performance and
generalization ability of the proposed method is experimentally evaluated on
two large scale driving datasets: MulRan and Oxford Radar RobotCar.
Additionally, we present a comparative evaluation of radar-based and LiDAR-
based localization using learned global descriptors. Our code and trained
models are publicly available on the project website.
111https://github.com/jac99/RadarLoc

###### Keywords:

topological localization radar-based place recognition LiDAR-based place
recognition global descriptors.

##  1 Introduction

Place recognition is an important problem in robotics and autonomous driving
community. It aims at recognizing previously visited places based on an input
from a sensor, such an RGB camera or a LiDAR scanner, installed on the moving
vehicle. Place recognition plays an important part in mapping and localization
methods. It allows detecting and closing loops during a map creation. It can
improve localization accuracy in areas with restricted or limited GPS coverage
[24].

Sensing capabilities of modern robotic and autonomous driving solutions
constantly improve as technology advances and becomes more affordable [23].
Therefore, methods for visual place recognition span from classical approaches
using RGB camera images to 360∘ range-based measuring systems, such as LiDARs
and radars. Appearance-based methods [2, 5] leverage fine details of observed
scenes, such as a texture of visible buildings. However, they fail under
light-condition variance and seasonal changes. Structure information-based
place recognition methods address these limitations. Modern 3D LiDARs, such as
Velodyne HDL-64E, can capture up to 100 meters range providing a rich
geometrical information about the observed scene. LiDAR-based topological
localization using learned descriptors is currently an active field of
research, with a larger number of published methods [1, 11, 26, 16, 13, 14, 7,
22, 21]. Nevertheless, high-end LiDARs are too expensive to be widely
applicable, with the price as high as 70k USD per unit. Additionally, LiDAR
readings are adversely affected by extreme environmental conditions such as
fog, heavy rain or snow [12]. In such challenging conditions, radars show a
great potential as they are more robust against atmospheric phenomena.
Moreover, modern frequency-modulated continuous wave (FMCW) scanning radars
cover broader area, having an operating range up to 200 meters. However,
radar-based localization is relatively little exploited [12, 19]. This can be
attributed to limited availability of sufficiently large and diverse datasets.
The situation has improved recently with the release of large-scale MulRan
[12] and Radar RobotCar [3] datasets.

In this work, we propose a method for topological localization using learned
descriptors based on Frequency-Modulated Continuous Wave (FMCW) radar scan
images. The idea is illustrated in Fig. 1. A trained neural network computes
low-dimensional descriptors from sensor readings. Localization is performed by
searching the database for geotagged elements with descriptors closests, in
Euclidean distance sense, to the descriptor of the query scan. We present a
simple and efficient deep network architecture to compute rotationally
invariant discriminative global descriptor from a radar scan image. Rotational
invariance is an important property for place recognition tasks, as the same
place can be revisited from different directions.

Figure 1: Radar-based and LiDAR-based topological localization. Trained neural
network (blue arrow) is used to compute a global descriptor from a query
reading. Localization is performed by searching the database for a geo-tagged
sensor readings with closest descriptors.

An interesting research question is the comparison of performance of radar-
based and LiDAR-based localization methods. In this work we perform such
analysis by comparing our radar-based descriptor with LiDAR-based global
descriptor. Contributions of this work can be summarized as follows. First, we
propose a simple yet efficient deep neural network architecture to compute a
discriminative global descriptor from a radar scan image. Second, present a
comparative evaluation of radar-based and LiDAR-based localization using
learned descriptors.

##  2 Related work

Radar-based place recognition. Radar-based place recognition using learned
descriptors is relatively unexplored area. In [12] authors adapt a hand-
crafted ScanContext [11] descriptor, originally used for point cloud-based
place recognition. [19] presents a learned a global descriptor computed using
convolutional neural network with NetVLAD [2] aggregation layer, commonly used
in visual domain. In order to achieve rotational invariance authors introduce
couple of modifications, such as cylindrical convolutions, anti-aliasing
blurring, and azimuth-wise max-pooling. [6] extends this method by developing
a two-stage approach which integrates global descriptor learning with precise
pose estimation using spectral landmark-based techniques.

LiDAR-based place recognition. Place recognition methods based on LiDAR scans
can be split into two categories: handcrafted and learned descriptors. Among
the first group, one of the most effective methods is ScanContext [11], which
represents a 3D point cloud as a 2D image. 3D points above the ground plane
level are converted to egocentric polar coordinates and projected to a 2D
plane. This idea was extended in a couple of later works [8, 4].

The second group of methods leverages deep neural networks in order to compute
a discriminative global descriptor in a learned manner. One of the first is
PointNetVLAD [1], which uses PointNet architecture to extract local features,
followed by NetVLAD pooling producing a global descriptor. It was followed by
a number of later works [26, 16, 21, 13] using the same principle: local
features extracted from the 3D point cloud are pooled to yield a
discriminative global descriptor. However all these works operate on
relatively small point clouds constructed by accumulating and downsampling a
few consecutive scans from a 2D LiDAR. Thus, they do not scale well to larger
point clouds generated by a single 360∘ sweep from a 3D LiDAR with an order of
magnitude more points. To mitigate this limitation another line of methods
uses an intermediary representation of an input point cloud before feeding it
to a neural network. DiSCO [22] first converts a point cloud into a multi-
layered representation, then uses a convolutional neural network to extract
features in a polar domain and produce a global descriptor.

##  3 Topological localization using learned descriptors

The idea behind a topological localization using learned descriptors is
illustrated in Fig. 1. A trained neural network is used to compute a
discriminative global descriptor from a sensor reading (radar scan image or 3D
point cloud from LiDAR). Place recognition is performed by searching the
database of geo-tagged sensor readings for descriptors closests, in Euclidean
distance sense, to the descriptor of the query reading. The geo-position of
the reading with a closest descriptor found in the database approximates query
location. This coarse localization may be followed by a re-ranking step and a
precise 6DoF pose estimation based on local descriptors. But in this work we
focus only on coarse-level localization using learned global descriptors.

###  3.1 Radar scan-based global descriptor

This section describes the architecture of our network to compute a
discriminative global descriptor of an input radar scan image. The high-level
network architecture is shown in Fig. 2. It consists of two parts: local
feature extraction network followed by the generalized-mean (GeM) [18] pooling
layer. Our initial experiments proved that GeM yields better results compared
to commonly used NetVLAD [2] pooling. One of the reasons is much smaller
number of learnable parameters that reduces the risk of overfitting to a
moderately-sized training set. The input to the network is a single-channel
radar scan image in polar coordinates. The scan image is processed using a 2D
convolutional network modelled after FPN [15] design pattern. Upper part of
the network, with left-to-right data flow, contains five convolutional blocks
producing 2D feature maps with decreasing spatial resolution and increasing
receptive field. The bottom part, with right-to-left data flow, contains a
transposed convolution generating an upsampled feature map. Upsampled feature
map is concatenated with the skipped features from the corresponding block in
the upper pass using a lateral connection. Such design is intended to produce
a feature map with higher spatial resolution, having a large receptive field.
Our experiments proved its advantage over a simple convolutional architecture
with one-directional data flow. Table 1 shows details of each network block.
The first convolutional block (2dConv0) has a bigger 5x5 kernel, in order to
aggregate information from a larger neighbourhood. Subsequent blocks
(2dConv${}_{1}\ldots$2dConv4) are made of a stride two convolution, which
decreases spatial resolution by two, followed by residual block consisting of
two convolutional layers with 3x3 kernel and ECA [20] channel attention layer.
All convolutional layers are followed by batch normalization [10] layer and
ReLU non-linearity. Two 1xConv blocks have the same structure, both contain a
single convolutional layer with 1x1 kernel. The aim of these blocks is to
unify the number of channels in feature maps produced by the blocks in the
left-to-right, before they are merged with feature maps from the right-to-left
pass through the network. The bottom part of the network (left-to-right
pass)consists of a single transposed convolution layer (2dTConv4) with 2x2
kernel and stride 2. The feature map $\mathcal{F}_{h}$ computed by the feature
extraction network is pooled with generalized-mean (GeM) [18] pooling to
produce a radar scan descriptor $\mathcal{H}$

Important property for loop closure applications is rotational invariance, as
the same place may be revisited from different directions. Invariance to the
viewpoint rotation translates into shift invariance along the angular
direction of the scan image in polar coordinates. To ensure this invariance we
use a circular padding along the angular direction in all convolutions in the
radar scan descriptor extraction network. The left boundary of the scan image
(corresponding to $0^{\circ}$ angular coordinate) is padded with values on the
right boundary of the image (corresponding to $360^{\circ}$ angle) and vice
verse. This only partially solves the problem, as convolutions and pooling
with stride 2 are not translational invariant due to the aliasing effect. To
mitigate this problem we augment the training data, by randomly rolling the
image over axis corresponding to the angular direction, which gives the same
effect as rotating an image in Cartesian coordinates. Alternative approach is
to apply anti-aliasing blurring [25], where stride 2 max-pooling and
convolutions are replaced with stride 1 operations, followed by a stride 2
Gaussian blur. But we found it giving worse results in practice.

Figure 2: Architecture of a radar scan descriptor extraction network. The input is processed by a 2D convolutional network with FPN [15] architecture to produce a feature map $\mathcal{F}_{h}$. The feature map is pooled with generalized-mean (GeM) [18] pooling to produce a radar scan descriptor $\mathcal{H}$. Block | Layers
---|---
2dConv0 | 2d convolutions with 32 filters 5x5 - BN - ReLU
2dConvk | 2d convolution with $c_{k}$ filters 2x2 stride 2 - BN - ReLU
| 2d convolution with $c_{k}$ filters 3x3 stride 1 - BN - ReLU
| 2d convolution with $c_{k}$ filters 3x3 stride 1 - BN - ReLU
| Efficient Channel Attention (ECA) layer [20]
| where $c_{1}=32,c_{2,3}=64,c_{4,5}=128$
2dTConv6 | 2d transposed conv. with 128 filters 2x2 stride 2
1xConv | 2d convolution with 128 filters 1x1 stride 1
GeM pooling | Generalized-mean Pooling layer [18]
Table 1: Details of the descriptor extractor network for radar scan images.

###  3.2 LiDAR-based global descriptor

This section describes the architecture of the network used to compute a
discriminative global descriptor of a 3D point cloud. We choose a 3D
convolutional architecture using sparse volumetric representation that
produced state of the art results in our previous MinkLoc3D [13] work.
However, MinkLoc3D is architectured to process relatively small point clouds,
constructed by concatenating multiple 2D LiDAR scans. In this work we use
point clouds build from a single 360∘ scans from 3D LiDAR, covering much
larger area, app. 160 meters in diameter, and containing an order of magnitude
more points. To extract informative features from such larger point clouds we
enhanced the network architecture to increase the receptive field. The number
of blocks in upper and lower part of the network is increased compared to
MinkLoc3D design. Fig. 2 shows high-level architecture and details of each
network block are given in Tab. 1. For more information we refer the reader to
our MinkLoc3D [13] paper. To ensure rotational invariance of the resultant
global descriptor, necessary for loop closure applications, we resort to data
augmentation. Point clouds are randomly rotated around the $z$-axis before
they are fed to the network during the training.

Figure 3: Architecture of a LiDAR point cloud descriptor extraction network. The input is quantized into a sparse voxelized representation and processed by a 3D convolutional network with FPN [15] architecture. The resultant sparse 3D feature map is pooled with generalized-mean (GeM) pooling to produce a global point cloud descriptor $\mathcal{G}$.  Block | Layers
---|---
3dConv0 | 32 filters 5x5x5 - BN - ReLU
3dConvk | 3d convolution with $c_{k}$ filters 2x2x2 stride 2 - BN - ReLU
| 3d convolution with $c_{k}$ filters 3x3x3 stride 1 - BN - ReLU
| 3d convolution with $c_{k}$ filters 3x3x3 stride 1 - BN - ReLU
| Efficient Channel Attention (ECA) layer [20]
| where $c_{1}=32,c_{2}=c_{3}=64,c_{4\ldots 7}=128$
3dTConvk, $k=6,7$ | 3d transposed conv. with 128 filters 2x2x2 stride 2
1xConv | 3d convolution with 128 filters 1x1x1 stride 1
GeM pooling | Generalized-mean Pooling layer [18]
Table 2: Details of the descriptor extractor network for LiDAR point clouds.

###  3.3 Network training

To train both networks to generate discriminative global descriptors we use a
deep metric learning approach [17] with a triplet margin loss [9] defined as:

$L(a_{i},p_{i},n_{i})=\max\left\\{d(a_{i},p_{i})-d(a_{i},n_{i})+m,0\right\\},$

where $d(x,y)=||x-y||_{2}$ is an Euclidean distance between embeddings $x$ and
$y$; $a_{i},p_{i},n_{i}$ are embeddings of an anchor, a positive and a
negative elements in $i$-th training triplet and $m$ is a margin
hyperparameter. The loss is formulated to make embeddings of structurally
dissimilar sensor readings (representing different places) further away, in
the descriptor space, than embeddings of structurally similar readings
(representing the same place). The loss is minimized using a stochastic
gradient descent with Adam optimizer.

To improve effectiveness of the training process we use batch hard negative
mining [9] strategy to construct informative triplets. Each triplet is build
using the hardest negative example found within a batch. The hardest negative
example is a structurally dissimilar element that has the closest embedding,
computed using current network weights, to the anchor.

To increase variability of the training data, reduce overfitting and ensure
rotational invariance of global descriptors, we use on-the-fly data
augmentation. For radar scan images, we use random erasing augmentation [27]
and random cyclical shift over $x$-axis (angular dimension). For points
clouds, it includes random jitter and random rotation around $z$-axis. We also
adapted random erasing augmentation to remove 3D points within the randomly
selected frontoparallel cuboid.

##  4 Experimental Results

###  4.1 Datasets and evaluation methodology

To train and evaluate our models we use two recently published large-scale
datasets: MulRan [12] and Oxford Radar RobotCar [3]. MuRan dataset is gathered
using a vehicle equipped with Ouster OS1-64 3D LiDAR with 120 m. range and
Navtech CIR204-H FMCW scanning radar with 200 operating range. Radar RobotCar
data is acquired using Velodyne HDL-32E LiDAR with 100 m. range and Navtech
CTS350-X scanning radar with 160 m. operating range.

In both datasets each trajectory is traversed multiple times, at different
times of day and year, allowing a realistic evaluation of place recognition
methods. Radar scans are provided in similar format, as $360^{\circ}$ polar
images with 400 (angular) by 3360 (radial dimension) pixel resolution. To
decrease computational resources requirements we downsample them to 384
(angular) by 128 (radial) resolution. LiDAR scans are given as unordered set
of points, containing between 40-60 thousand points. To speed up the
processing, we remove uninformative ground plane points with $z$-coordinate
below the ground plane level. Both datasets contain ground truth positions for
each traversal.

The longest and most diverse trajectory from MulRan dataset, Sejong, is split
into disjoint training and evaluation parts. We evaluate our models using
disjoint evaluation split from Sejong trajectory and two other trajectories:
KAIST and Riverside, acquired at different geographic locations. Each
evaluation trajectory contains two traversals gathered at different times of a
day and year. The first traversal (Sejong01, KAIST01, Riverside01) forms a
query set and the second one (Sejong02, KAIST02, Riverside02) is used as a
map. To test generalization ability of our model, we test it using two
traversals from Radar RobotCar dataset acquired at different days: traversal
019-01-15-13-06-37-radar-oxford-10k as a map split and
2019-01-18-14-14-42-radar-oxford-10k as a query split.

To avoid processing multiple scans of the same place when the car doesn’t
move, we ignore consecutive readings with less than 0.1m displacement in the
ground truth position. We also ignore readings for which a ground truth pose
in not given with 1 sec. tolerance. See Fig. 4 for visualization of training
and evaluation trajectories. Details of the training and evaluation sets are
given in Tab. 3.

(a) Sejong

(b) KAIST

(c) Riverside

(d) RobotCar

Figure 4: Visualization of three trajectories in MulRan dataset and one in Radar RobotCar. Red rectangles in Sejong trajectory delimit the training split. Table 3: Length and number of scans in training and evaluation sets. Trajectory | Split | Length | Number of scans (map/query)
---|---|---|---
Radar | LiDAR
Sejong | train | 19 km | $13\,611$ | $33\,698$
Sejong | test | 4 km |  $1\,366$/$1\,337$ |  $3\,358$/$3\,315$
KAIST | test | 6 km |  $3\,209$/$3\,420$ |  $7\,975$/$8\,521$
Riverside | test | 7 km |  $2\,117$/$2\,043$ |  $5\,267$/$5\,084$
Radar RobotCar | test | 10 km |  $5\,904$/$5\,683$ |  $26\,719$/$25\,944$

Training triplets are generated using the ground truth coordinates provided in
each dataset. Positive examples is chosen from structurally similar readings,
that is readings that are at most 5m apart. Negative examples are sampled from
dissimilar readings, that is readings that are at least 20m apart.

Evaluation metrics. To evaluate the global descriptor performance we follow
similar evaluation protocol as in other point cloud-based or radar-based place
recognition works [1]. Each evaluation set is split into two parts: a query
and a database set, covering the same geographic area. A query is formed from
sensor readings acquired during one traversal and the database is build from
data gathered during a different traversal, on a different day. For each query
element we find database element with closests, in Euclidean distance sense,
global descriptors. Localization is successful if at least one of the top $N$
retrieved database elements is within $d$ meters from the query ground truth
position. _Recall@N_ is defined as the percentage of correctly localized
queries.

###  4.2 Results and discussion

We compare the performance of our radar-based global descriptor with a hand-
crafted ScanContext [11] method and our re-implementation of the VGG-16/
NetVLAD architecture used as a baseline in [19]. Evaluation results are shown
in Tab. 4. Our method (RadarLoc) consistently outperforms other approaches on
all evaluation sets at both 5m and 10m threshold. Recall@1 with 5m threshold
is between 2-14 p.p. higher than the runner-up ScanContext. At larger 10m
threshold, learning-based VGG-16/NetVLAD architecture scores higher than
ScanContext, but it’s still about 5-10 p.p. lower than RadarLoc. Our method
generalizes well to a different dataset. The model trained on a subset of
Sejong traversal, from MulRan dataset, has a top performance when evaluated on
Radar RobotCar. It must be noted that these two datasets are acquired using a
different suite of sensors, although having similar operational
characteristics. Figure 5 shows Recall@$N$ plots, for $N$ ranging from 1 to
10, of all evaluated methods on different evaluation sets from MulRan dataset.
For Sejong and KAIST trajectory, the performance of our method increases with
$N$, quickly reaching near-100% accuracy. However characteristics of the
environment in which data was gathered impacts all evaluated methods. The
results for all traversals acquired in the city centre areas (Sejong, KAIST,
Radar RobotCar) are relatively better, for all evaluated methods. Riverside
traversal is acquired outside the city, where significantly fewer structural
elements, such as buildings or lamp posts, are present. Hence it gives
considerably worse results for all evaluated methods.

Table 4: Evaluation results (Recall@1) of a radar-based descriptor. Method | Sejong | KAIST | Riverside | RadarRobotCar
---|---|---|---|---
5m. | 10m. | 5m. | 10m. | 5m. | 10m. | 5m. | 10m.
Ring key [11] | 0.503 | 0.594 | 0.805 | 0.838 | 0.497 | 0.595 | 0.747 | 0.786
ScanContext [11] | 0.868 | 0.879 | 0.935 | 0.946 | 0.671 | 0.772 | 0.906 | 0.933
VGG-16/NetVLAD | 0.789 | 0.938 | 0.8885 | 0.937 | 0.613 | 0.834 | 0.883 | 0.939
RadarLoc (ours) | 0.929 | 0.988 | 0.959 | 0.988 | 0.744 | 0.923 | 0.949 | 0.981

(a)

(b)

(c)

Figure 5: Average Recall@N with 5m. threshold of radar-based descriptor.

Table 5 compares performance of radar-based and LiDAR-based localization on
three different evaluation sets from MulRan dataset. LiDAR has 2-3 times
higher scanning frequency than radar and our datasets contain 2-3 more LiDAR
3D point clouds than radar scan images. To cater for this difference, we
compare the performance of radar versus LiDAR-based topological localization
in two scenarios. First, we use all available data gathered during vehicle
traversals. In this scenario, LiDAR scans cover the mapped area denser than
radar. Second, we evaluate the performance, using a smaller, subsampled LiDAR
dataset with the same number of point clouds as radar scans. In this scenario,
LiDAR and radar scans cover the mapped area equally dense. It can be seen,
that better map coverage caused by higher LiDAR scanning frequency has little
impact. Performance of the LiDAR-based method on full evaluation sets and on
downsampled evaluation sets is very close.

Intuitively, LiDAR provides richer 3D information about the structure of the
observed scene, whereas radar captures only 2D range data. We would expect
LiDAR-based approach to produce more discriminative global descriptors.
Interestingly, this not happen and localization using radar scan images
generally yields better results, especially with larger 10m threshold. We
hypothesize that the reason is bigger complexity and larger susceptibility to
overfitting of a LiDAR-based model. The performance of both methods on MulRan
evaluation split, having scenes with similar characteristic as in the training
split, is very close. When evaluated on different traversals, covering
locations with different characteristic (e.g. suburbs versus city center),
LiDAR-based model generalizes worse.

Table 5: Comparison (Recall@1) of radar-based and LiDAR-based descriptors. Method | Sejong | KAIST | Riverside
---|---|---|---
5m. | 10m. | 5m. | 10m. | 5m. | 10m.
RadarLoc (our) | 0.929 | 0.988 | 0.959 | 0.988 | 0.744 | 0.923
LiDAR-based | 0.950 | 0.986 | 0.901 | 0.930 | 0.748 | 0.881
LiDAR-based (subsampled dataset) | 0.941 | 0.986 | 0.897 | 0.929 | 0.740 | 0.881

##  5 Conclusion

Topological localization using radar scan images is relatively unexplored
area. In this work we demonstrate that it has a high potential and is
competitive to LiDAR-based approaches. Our proposed radar-based localization
method, having a simple and efficient architecture, outperforms baseline
methods and has better generalization abilities than LiDAR-based approach.
LiDAR, however, provides richer 3D information about the structure of the
observed scene, whereas radar captures only 2D range data. An interesting
research question is how to fully exploit structural information available in
3D LiDAR scans to increase discriminative power of resultant global
descriptors and outperform radar-based methods.

## References

  * [1] Angelina Uy, M., Hee Lee, G.: PointNetVlad: Deep point cloud based retrieval for large-scale place recognition. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 4470–4479 (2018)
  * [2] Arandjelovic, R., Gronat, P., Torii, A., Pajdla, T., Sivic, J.: NetVlad: CNN architecture for weakly supervised place recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 5297–5307 (2016)
  * [3] Barnes, D., Gadd, M., Murcutt, P., Newman, P., Posner, I.: The Oxford radar RobotCar dataset: A radar extension to the Oxford RobotCar dataset. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). Paris (2020)
  * [4] Cai, X., Yin, W.: Weighted Scan Context: Global descriptor with sparse height feature for loop closure detection. In: 2021 International Conference on Computer, Control and Robotics (ICCCR). pp. 214–219. IEEE (2021)
  * [5] Cummins, M., Newman, P.: Fab-Map: Probabilistic localization and mapping in the space of appearance. The International Journal of Robotics Research 27(6), 647–665 (2008)
  * [6] De Martini, D., Gadd, M., Newman, P.: kRadar++: Coarse-to-fine fmcw scanning radar localisation. Sensors 20(21) (2020)
  * [7] Du, J., Wang, R., Cremers, D.: DH3D: Deep hierarchical 3d descriptors for robust large-scale 6dof relocalization. In: European Conference on Computer Vision. pp. 744–762. Springer (2020)
  * [8] Fan, Y., He, Y., Tan, U.X.: Seed: A segmentation-based egocentric 3d point cloud descriptor for loop closure detection. In: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 5158–5163. IEEE (2020)
  * [9] Hermans, A., Beyer, L., Leibe, B.: In defense of the triplet loss for person re-identification. arXiv preprint arXiv:1703.07737 (2017)
  * [10] Ioffe, S., Szegedy, C.: Batch normalization: Accelerating deep network training by reducing internal covariate shift. In: Proceedings of Machine Learning Research, vol. 37, pp. 448–456. PMLR, Lille, France (2015)
  * [11] Kim, G., Kim, A.: Scan Context: Egocentric spatial descriptor for place recognition within 3d point cloud map. In: 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 4802–4809. IEEE (2018)
  * [12] Kim, G., Park, Y.S., Cho, Y., Jeong, J., Kim, A.: MulRan: Multimodal range dataset for urban place recognition. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). pp. 6246–6253. Paris (2020)
  * [13] Komorowski, J.: MinkLoc3d: Point cloud based large-scale place recognition. In: Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV). pp. 1790–1799 (2021)
  * [14] Komorowski, J., Wysoczanska, M., Trzcinski, T.: MinkLoc++: Lidar and monocular image fusion for place recognition. In: 2021 International Joint Conference on Neural Networks (IJCNN) (2021)
  * [15] Lin, T.Y., Dollar, P., Girshick, R., He, K., Hariharan, B., Belongie, S.: Feature pyramid networks for object detection. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 2117–2125 (2017)
  * [16] Liu, Z., Zhou, S., Suo, C., Yin, P., Chen, W., Wang, H., Li, H., Liu, Y.H.: LPD-Net: 3d point cloud learning for large-scale place recognition and environment analysis. In: Proceedings of the IEEE International Conference on Computer Vision. pp. 2831–2840 (2019)
  * [17] Lu, J., Hu, J., Zhou, J.: Deep metric learning for visual understanding: An overview of recent advances. IEEE Signal Processing Magazine 34(6), 76–84 (2017)
  * [18] Radenovic, F., Tolias, G., Chum, O.: Fine-tuning CNN image retrieval with no human annotation. IEEE transactions on pattern analysis and machine intelligence 41(7), 1655–1668 (2018)
  * [19] Saftescu, S., Gadd, M., De Martini, D., Barnes, D., Newman, P.: Kidnapped radar: Topological radar localisation using rotationally-invariant metric learning. In: 2020 IEEE International Conference on Robotics and Automation (ICRA). pp. 4358–4364. IEEE (2020)
  * [20] Wang, Q., Wu, B., Zhu, P., Li, P., Zuo, W., Hu, Q.: ECA-Net: Efficient channel attention for deep convolutional neural networks. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (June 2020)
  * [21] Xia, Y., Xu, Y., Li, S., Wang, R., Du, J., Cremers, D., Stilla, U.: SOE-Net: A self-attention and orientation encoding network for point cloud based place recognition. arXiv preprint arXiv:2011.12430 (2020)
  * [22] Xu, X., Yin, H., Chen, Z., Li, Y., Wang, Y., Xiong, R.: Disco: Differentiable Scan Context with orientation. IEEE Robotics and Automation Letters (2021)
  * [23] Yeong, D.J., Velasco-Hernandez, G., Barry, J., Walsh, J.: Sensor and sensor fusion technology in autonomous vehicles: A review. Sensors 21(6) (2021)
  * [24] Yin, H., Xu, X., Wang, Y., Xiong, R.: Radar-to-lidar: Heterogeneous place recognition via joint learning. Frontiers in Robotics and AI 8, 101 (2021)
  * [25] Zhang, R.: Making convolutional networks shift-invariant again. In: International Conference on Machine Learning. pp. 7324–7334. PMLR (2019)
  * [26] Zhang, W., Xiao, C.: PCAN: 3d attention map learning using contextual information for point cloud based retrieval. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 12436–12445 (2019)
  * [27] Zhong, Z., Zheng, L., Kang, G., Li, S., Yang, Y.: Random erasing data augmentation. arXiv preprint arXiv:1708.04896 (2017)


# Weighted Sum Age of Information Minimization in Wireless Networks with
Aerial IRS

Wanting Lyu, Yue Xiu, Songjie Yang, Phee Lep Yeoh, , Yonghui Li, , Zhongpei
Zhang,
Wanting Lyu, Songjie Yang and Zhongpei Zhang are with National Key Laboratory
of Science and Technology on Communications, University of Electronic Science
and Technology of China, Chengdu61173, China (E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>zhangzp@uestc.edu.cn). Yue Xiu is with Chengdu
Research & Development Centre, Huawei Technologies Co., Ltd., People’s
Republic of China (E-mail: xiuyuw12345678@163.com). Phee Lep Yeoh and Yonghui
Li are with the School of Electrical and Information Engineering, University
of Sydney, Sydney, NSW 2006, Australia (e-mail<EMAIL_ADDRESS>yonghui.li@sydney.edu.au).

###### Abstract

In this letter, we analyze a terrestrial wireless communication network
assisted by an aerial intelligent reflecting surface (IRS). We consider a
packet scheduling problem at the ground base station (BS) aimed at improving
the information freshness by selecting packets based on their AoI. To further
improve the communication quality, the trajectory of the unmanned aerial
vehicle (UAV) which carries the IRS is optimized with joint active and passive
beamforming design. To solve the formulated non-convex problem, we propose an
iterative alternating optimization problem based on a successive convex
approximation (SCA) algorithm. The simulation results shows significant
performance improvement in terms of weighted sum AoI, and the SCA solution
converges quickly with low computational complexity.

###### Index Terms:

Age of information, intelligent reflecting surface, unmanned aerial vehicle,
scheduling, trajectory and beamforming design.

##  I Introduction

Intelligent reflecting surface (IRS) has emerged as a promising technology to
meet the ultra high demands on communication quality in beyond fifth-
generation (B5G) mobile communications [1]. Consisting of a large number of
low-cost passive reflecting elements, IRS can reconfigure the wireless signal
propagation environment to mitigate the channel impairments with high energy
efficiency, which thus enhance the wireless links to improve the data rate and
reliability [2].

Existing works have explored the applications of IRS in wireless networks.
Authors in [3] studied the weighted sum-rate maximization through jointly
optimizing the active and passive beamforming with perfect and imperfect
channel state information (CSI). In [4], the secrete key generation capacity
was improved with the assist of IRS. In [5], multiple IRSs cooperation was
investigated to enhance energy efficiency in cell free MIMO networks. To
improve the deployment flexibility of the IRS, an aerial IRS was proposed in
[6], where the IRS is carried by an unmanned aerial vehicle (UAV). It is shown
that aerial IRS can significantly increase the probability of a line-of-sight
(LoS) link between the IRS and the ground nodes [7].

Recently, real-time communications is becoming especially crucial in mission-
critical application scenarios, such as vehicle-to-vehicle (V2V) networks and
industrial Internet of things (IIoT). In these networks, data freshness is a
key requirement to avoid accidents and errors caused by delayed information.
To quantify the freshness of information, the authors of [8] first introduced
the concept of the age of information (AoI), which is defined as the time past
since the generation of the last successfully delivered and decoded
information packet [9]. The authors in [10] analyzed and derived a closed-form
expression for the average AoI using queuing theory and probability channel
fading models. Considering that the relay node is undesirable to keep
transmitting packets in real cases, in [11], an optimal scheduling policy was
studied to minimize the AoI with a tradeoff of forwarding and receiving
operation at the relay. In [12], a UAV sensing and transmission time tradeoff
design during a given period was proposed for a cellular Internet of UAVs to
minimize the AoI.

In this paper, we use aerial IRS to improve the AoI in wireless communication
networks. Our proposed solution is suitable for deployment in urban areas with
densely distributed buildings, vehicles and human bodies, where the direct
link between the terrestrial base station (BS) and user is likely to
experience severe fading with non-line-of-sight (NLoS) channels. With the
assistance of the UAV, the IRS has a higher probability to establish a LoS
channel, and simultaneously, the deployment flexibility is dramatically
increased to cater for real-time user demands. To analyse this network, we
build a 3D environment model, and formulate a joint packet scheduling, active
and passive IRS beamforming, and UAV trajectory optimization problem to
minimize the total weighted sum AoI. An alternating optimization algorithm is
developed to decouple the variables, with introduced slack variables and
successive convex approximation (SCA) algorithm to deal with the non-convex
constraints. Significant performance improvement measured by the sum AoI is
verified by the numerical experiments, which also highlights the rapid
convergence performance with low computational complexity.

##  II System Model and Problem Formulation

###  II-A Wireless Communication Model

Figure 1: System model of the aerial IRS assisted network.

An aerial IRS aided wireless downlink system is considered as shown in Fig.1,
where the IRS is hovering above the ground carried by a UAV. The ground base
station (BS) is equipped with a uniform planar array (UPA) with $M=M_{x}M_{z}$
antennas serving $K$ single-antenna ground users. The IRS is also configured
with a UPA with $N_{s}=N_{sx}N_{sy}$ reflecting elements. The time of the
whole aerial IRS-assisted communications ($T$ for total) is divided into
$N_{T}$ time slots each with duration $\Delta=T/N_{T}$, where $n$ is used to
denote the current time slot.

The BS with height $H$ is located at the origin of the coordinate system, and
the antenna array is located on the x-z plane. The space between adjacent
antennas is $d_{ox}=d_{oz}=\frac{\lambda}{2}$, where $\lambda$ is the
wavelength. The first antenna at the BS is assumed to be located at
$\bm{c}=[0,0,H]^{T}$. Accordingly, the coordinate of the $m_{x}^{th}$ column,
$m_{z}^{th}$ row antenna is
$\bar{\bm{c}}=\bm{c}+[0,(m_{x}-1)d_{ox},(m_{z}-1)d_{oz}],\forall
m_{x}\in\\{1,2,...,M_{x}\\},m_{z}\in\\{1,2,...,M_{z}\\}$. The IRS is placed on
the $x-y$ plane with a fixed altitude of $Z$. We consider the first reflecting
element to be at the corner of the IRS, with coordinate
$\bm{q}(n)=[q_{x}(n),q_{y}(n),Z]^{T}$ at time slot $n$. Fixed distances
$d_{x}<\frac{\lambda}{2}$ and $d_{y}<\frac{\lambda}{2}$ are set for separating
the adjacent elements [6]. Similarly, the location of the $n_{s}^{th}$ IRS
element is denoted as
$\bar{\bm{q}}(n)=[q_{x}(n)+(n_{sx}-1)d_{x},q_{y}(n)+(n_{sy}-1)d_{y},q_{z}(n)]^{T},\forall
n_{sx}\in\\{1,2,...,N_{sx}\\},n_{sy}\in\\{1,2,...,N_{sy}\\}$. The users are
assumed to be on the ground, and the coordinate of user $k$ is
$\bm{l}_{k}=[k_{x},k_{y},0]^{T},\forall k\in\\{1,2,...,K\\}$.

The distance between the reference points at the transmit antenna array and
the IRS is thus $d_{br}(n)=||\bm{q}(n)-\bm{c}||_{2}$, and the distance between
the first reflecting element and the $k^{th}$ user is
$d_{rk}(n)=||\bm{q}(n)-\bm{l}_{k}||_{2}$. The UAV flight platform is
sufficiently high so that the channels between the aerial IRS and the ground
nodes are mainly LoS links with a high probability [7]. Due to the dense urban
environment, assume that the direct links from the BS to the users are
blocked. Without loss of generality, the free space propagation model is
considered for measuring the large-scale attenuation. Therefore, the path loss
of the BS-IRS channel and the IRS-user $k$ channel are
$\rho_{br}(n)=\rho_{o}\frac{d_{o}^{2}}{d_{br}^{2}(n)}$ and
$\rho_{rk}(n)=\rho_{o}\frac{d_{o}^{2}}{d_{rk}^{2}(n)}$ respectively, where
$\rho_{o}$ is the reference path loss at a given reference distance
$d_{o}=1\rm m$.

It is noteworthy that the IRS can be approximated as a UPA since its size is
sufficiently small compared with the distance between the communication links.
As shown in Fig.2, the angle of departure (AoD) at the BS and the angle of
arrival (AoA) are approximately symmetric.

Accordingly, the receiving array response vector at the IRS at time slot $n$
is

$\displaystyle\bm{a}_{R1}$ $\displaystyle(\eta_{r1}(n),\varphi_{r1}(n))$
$\displaystyle=[1,\;e^{-j\phi_{r1x}(n)},\;...,\;e^{-j\phi_{r1x}(n)(N_{sx}-1)}]^{T}$
$\displaystyle\otimes[1,\;e^{-j\phi_{r1y}(n)},\;...,\;e^{-j\phi_{r1y}(n)(N_{sy}-1)}]^{T}\in\mathbb{C}^{N_{s}\times
1},$ (1)

where
$\phi_{r1x}(n)=\frac{2\pi}{\lambda}d_{x}\sin\eta_{r1}(n)\cos\varphi_{r1}(n)$
and
$\phi_{r1y}(n)=\frac{2\pi}{\lambda}d_{y}\sin\eta_{r1}(n)\sin\varphi_{r1}(n)$.
The variables $\eta_{r1}(n)$ and $\varphi_{r1}(n)$ denote the elevation and
azimuth AoA at time slot $n$ at the IRS, and
$\cos(\eta_{r1}(n))=\frac{Z-H}{||\bm{q}-\bm{c}||_{2}}$,
$\sin(\varphi_{r1}(n))=\frac{q_{y}}{||\bm{q}-H||_{2}}$ .

The transmitting array response vector $\bm{a}_{T1}(n)$ at the BS antenna
array is defined similar to (1). Hence the link between the BS and the IRS is
defined as

$\displaystyle\bm{G}$ $\displaystyle(n)=\sqrt{\rho_{br}(n)}e^{-j\frac{2\pi
d_{br}(n)}{\lambda}}\bm{a}_{R1}(\eta_{r1}(n),\varphi_{r1}(n))$
$\displaystyle\bm{a}_{T1}^{H}(\eta_{t1}(n),\varphi_{t1}(n)).$ (2)

The IRS-user link is expressed as

$\bm{h}_{rk}^{H}(n)=\sqrt{\rho_{rk}(n)}e^{-j\frac{2\pi
d_{rk}(n)}{\lambda}}\bm{a}_{T2}^{H}(\eta_{t2}(n),\varphi_{t2}(n)),$ (3)

where the transmitting array response vector at the IRS is

$\displaystyle\bm{a}_{T2}$ $\displaystyle(\eta_{t2}(n),\varphi_{t2}(n))$
$\displaystyle=[1,\;e^{-j\phi_{t2x}(n)},\;...,\;e^{-j\phi_{t2x}(n)(N_{sx}-1)}]^{T}$
$\displaystyle\otimes[1,\;e^{-j\phi_{t2y}(n)},\;...,\;e^{-j\phi_{t2y}(n)(N_{sy}-1)}]^{T}\in\mathbb{C}^{N_{s}\times
1},$ (4)

and
$\phi_{t2x}(n)=\frac{2\pi}{\lambda}d_{x}\sin\eta_{t2}(n)\cos\varphi_{t2}(n)$
and
$\phi_{t2y}(n)=\frac{2\pi}{\lambda}d_{y}\sin\eta_{t2}(n)\sin\varphi_{t2}(n)$.

The phase shift matrix at the IRS is represented as $\bm{\Theta}(n)={\rm
diag}\\{e^{j\theta_{1}(n)},\;e^{j\theta_{2}(n)},...,\;e^{j\theta_{N_{s}}(n)}\\}$,
where $\bm{\theta}(n)=[\theta_{1}(n),\theta_{2}(n),...,\theta_{Ns}(n)]^{T}$.
$\theta_{n_{s}}(n)\in[0,2\pi)$ is the $n_{s}^{th}$ phase shift of the IRS for
$n_{s}\in\\{1,...,N_{s}\\}$. The transmit symbol for user $k$ is $s_{k}(n)$
satisfying $\mathbb{E}\\{|s_{k}(n)|^{2}\\}=1$, and
$\bm{w}_{k}(n)\in\mathbb{C}^{M\times 1}$ is the corresponding transmit
beamforming vector. As such, the transmitted signal at the BS can be expressed
as

$\bm{x}(n)=\sum_{k=1}^{K}\bm{w}_{k}(n)s_{k}(n),$ (5)

where we set the constraint that, the transmit power for each user is less
than or equal to $P_{o}$,

$||\bm{w}_{k}(n)||^{2}\leq P_{o},\;\forall k\in\\{1,...,K\\}.$ (6)

Assuming the direct links are unavailable, the received signal at user $k$ can
be expressed as

$y_{k}(n)=\bm{h}_{rk}^{H}(n)\bm{\Theta}(n)\bm{G}(n)\bm{x}_{n}+u_{k}(n),$ (7)

where $u_{k}(n)\sim\mathcal{CN}(0,\sigma_{o}^{2})$ represents the additive
white Gaussian noise (AWGN) at the receiver of user $k$. For simplicity, the
channel for user $k$ can be denoted as
$\bm{h}_{k}^{H}(n)=\bm{h}_{rk}^{H}(n)\bm{\Theta}(n)\bm{G}(n)$, and
$y_{k}(n)=\bm{h}_{k}^{H}(n)\bm{x}(n)+u_{k}(n)$.

###  II-B The Age of Information Model

In this model, we assume $K$ data streams at the BS corresponding to $K$
users, where a status update data packet of stream $k$ arrives at the base
station with a probability $\epsilon_{k}$ at each time slot, and we define
$p_{k}(n)\in\\{0,1\\}$ to indicate whether there is a packet arriving, with
$Pr[p_{k}(n)=1]=\epsilon_{k}$. $A_{k}(n)$ is used to denote the AoI of the
targeted user $k$ at time slot $n$. We use a binary scheduling indicator
$\alpha_{k}(n)=1$ when the $k^{th}$ data stream is scheduled otherwise it is
equal to $0$. We furthur assume that there is only one available channel at
each time slot, such that

$\alpha_{k}(n)\in\\{0,1\\},\;\forall n.$ (8) $\sum_{k=1}^{K}\alpha_{k}(n)\leq
1,\;\forall n.\vspace*{-0.3\baselineskip}$ (9)

The AoI will increase linearly without newly updated data packets successfully
received by the targeted receiver, and otherwise it is determined by the
packet queuing time $z_{k}(n)$, with $A_{k}(n+1)=z_{k}(n)+1$. Following [12]
and [13], the system time $z_{k}(n)$ is given by

$z_{k}(n+1)=\left\\{\begin{aligned} &0,&if\,\alpha_{k}(n+1)=1,\forall k,n\\\
&z_{k}(n)+1,&otherwise.\end{aligned}\right.\vspace*{-0.2\baselineskip}$ (10)

We define another binary variable $\xi_{k}(n)$ indicating the available packet
status with the value equalling to $1$ when there is a available packet at
stream $k$. Otherwise $\xi_{k}(n)$ only turns to $0$ with a successful
delivery at last time slot and no new packet. A packet is delivered
successfully if the scheduled stream has an available packet and the received
signal-to-noise ratio (SNR) is no less than the threshold value. Therefore the
indicator $\xi_{k}(n)$ can be expressed as

$\xi_{k}(n+1)=p_{k}(n+1)+\xi_{k}(n)(1-\alpha_{k}(n))(1-p_{k}(n+1)),$ (11)

where $\gamma_{th}$ denotes the threshold SNR. As a result, the AoI can be
expressed as

$\displaystyle
A_{k}(n+1)=\,z_{k}(n)\alpha_{k}(n)\xi_{k}(n)+A_{k}(n)[(1-\alpha_{k}(n))\xi_{k}(n)$
$\displaystyle+\alpha_{k}(n)(1-\xi_{k}(n))+(1-\alpha_{k}(n))(1-\xi_{k}(n))]+1,\vspace*{-0.5\baselineskip}$
(12)

with the SNR constraint

$\gamma_{k}(n)\geq\alpha_{k}(n)\xi_{k}(n)\gamma_{th},\vspace*{-0.2\baselineskip}$
(13)

where the received SNR is

$\gamma_{k}(n)=\frac{|\bm{h}_{k}^{H}(n)\bm{w}_{k}(n)|^{2}}{\sigma_{o}^{2}}.\vspace*{-0.5\baselineskip}$
(14)

###  II-C Problem Formulation

To meet the demands of real-time communications and guarantee the freshness of
information, the aim of this paper is to minimize the weighted sum AoI of all
$K$ users. We propose an algorithm to optimize the UAV trajectory, scheduling
scheme at the BS and active and passive beamforming design. The optimization
problem is formulated as (P1),

$\displaystyle\mathrm{(P1)}:\;$
$\displaystyle\min_{\bm{q}(n),\alpha_{k}(n),\atop\bm{w}_{k}(n),\bm{\Theta}(n)}\sum_{k=1}^{K}b_{k}A_{k}^{N_{T}}$
(15) $\displaystyle\bm{s.t.}\quad$
$\displaystyle(\ref{Cons_pow}),(\ref{Cons_alpha}),(\ref{Cons_channel}),(\ref{Cons_SINR})$
$\displaystyle q_{z}(n)=Z,\;\forall n\in\\{1,...,N_{T}\\},$ (15a)
$\displaystyle||\bm{q}(n)-\bm{q}(n-1)||\leq v_{max}\Delta,$ (15b)
$\displaystyle\theta_{n_{s}}(n)\in[0,2\pi),\forall
n_{s}\in\\{1,...,N_{s}\\},\vspace*{-0.5\baselineskip}$ (15c)

where $b_{k}$ is the priority for user $k$, and $A_{k}^{N_{T}}$ denotes the
sum AoI of user $k$ for $N_{T}$ total time slots.

Since the AoI will keep increasing linearly without newly updated data
packets, the problem of minimizing sum AoI becomes maximizing the AoI
reduction at each time slot. Specifically, the stream with the worst weighted
AoI should be scheduled if there is an available packet to be delivered. Hence
the original problem (P1) can be reformulated as

$\displaystyle\mathrm{(P2)}:\;$
$\displaystyle\max_{\bm{q}(n),\alpha_{k}(n),\atop\bm{w}_{k}(n),\bm{\Theta}(n)}\sum_{k=1}^{K}b_{k}A_{k}(n)\alpha_{k}(n)\xi_{k}(n)$
(16) $\displaystyle\bm{s.t.}\quad$
$\displaystyle(\ref{Cons_pow}),(\ref{Cons_alpha}),(\ref{Cons_channel}),(\ref{Cons_SINR}),(\ref{Cons_UAValti}),(\ref{Cons_velocity}),(\ref{Cons_phase}).\vspace*{-0.5\baselineskip}$

However, the problem is intractable because of i) the coupling of variables
$\bm{q}(n),\,\alpha_{k}(n),\,\bm{w}_{k}(n)$ and $\bm{\Theta}(n)$; and ii) the
non-convexity of constraints (8) and (13). The proposed iterative solution
based on SCA algorithm is derived and elaborated as follows.

##  III Proposed Solutions

In this section, the proposed algorithm is given as follows. To decouple the
variables, the problem is solved alternatively, where the active and passive
beamforming are jointly designed for maximizing the array gain with fixed UAV
location, and given the optimized beamforming design, the scheduling policy is
updated with UAV trajectory optimization. The SCA algorithm is an efficient
approach to deal with the non-convexity of the AoI constraints.

###  III-A Joint Active and Passive Beamforming Design

To maximize the AoI reduction at each time slot, the received SNR should be
maximized to satisfy constraint (13). Therefore, it is equivalent to
maximizing the array gains of the UPAs at the BS and IRS respectively through
digital beamforming and IRS phase shift design.

Given the UAV location, the optimal transmit beamforming can be determined by
Maximum Ratio Transmission (MRT) to align with the transmitting array response
vector at the BS, which is given by

$\bm{w}_{k}(n)=\sqrt{P_{k}}\frac{\bm{a}_{T1}(\eta_{t1}(n),\varphi_{t1}(n))}{\sqrt{M}}.\vspace*{-0.5\baselineskip}$
(17)

The array gain at the IRS is expressed as

$\large\displaystyle\Big{|}\sum\limits_{n_{sx}=1}^{N_{sx}}\sum\limits_{n_{sy}=1}^{N_{sy}}e^{j\left(\theta_{n_{sx},n_{sy}}(n)+\mu_{n_{sx}}(n)+\mu_{n_{sy}}(n)\right)}\Big{|},\vspace*{-0.5\baselineskip}$
(18)

where $\mu_{n_{sx}}(n)=(n_{sx}-1)(\phi_{t2x}(n)-\phi_{r1x}(n))$ and
$\mu_{n_{sy}}(n)=(n_{sy}-1)(\phi_{t2y}(n)-\phi_{r1y}(n))$.

Applying the triangle inequality,

$\displaystyle\Big{|}\sum\limits_{n_{sx}=1}^{N_{sx}}\sum\limits_{n_{sy}=1}^{N_{sy}}e^{j\left(\theta_{n_{sx},n_{sy}}(n)+\mu_{n_{sx}}(n)+\mu_{n_{sy}}(n)\right)}\Big{|}$
$\displaystyle\leq$
$\displaystyle\big{|}e^{j\theta_{1,1}(n)}\big{|}+\dots+\big{|}e^{j\left(\theta_{n_{sx},n_{sy}}(n)+\mu_{n_{sx}}(n)+\mu_{n_{sy}}(n)\right)}\big{|}+$
$\displaystyle\dots+\big{|}e^{j\left(\theta_{N_{sx},N_{sy}}(n)+\mu_{N_{sx}}(n)+\mu_{N_{sy}}(n)\right)}\big{|}=N_{s},\vspace*{-0.5\baselineskip}$
(19)

where the equality holds with

$\displaystyle\theta_{n_{sx},n_{sy}}(n)=-(\mu_{n_{sx}}(n)+\mu_{n_{sy}}(n))$
$\displaystyle=$
$\displaystyle-\frac{2\pi}{\lambda}\Big{[}d_{x}(n_{sx}-1)(\sin\eta_{t2}(n)\cos\varphi_{t2}(n)-\sin\eta_{r1}(n)\cos\varphi_{r1}(n))$
$\displaystyle-
d_{y}(n_{sy}-1)(\sin\eta_{t2}(n)\sin\varphi_{t2}(n)-\sin\eta_{r1}(n)\sin\varphi_{r1})(n)\Big{]}.\vspace*{-0.5\baselineskip}$
(20)

###  III-B Scheduling and UAV Trajectory Optimization

With the above optimal active and passive beamforming strategies, the received
SNR at user $k$ can be obtained as

$\displaystyle\bar{\gamma}_{k}(n)=$
$\displaystyle\frac{\rho_{rk}(n)\rho_{br}(n)P_{o}N_{s}^{2}M}{\sigma_{o}^{2}}$
$\displaystyle=\frac{\rho_{o}^{2}d_{o}^{4}P_{o}N_{s}^{2}M}{d_{rk}^{2}(n)d_{br}^{2}(n)\sigma_{o}^{2}}$
$\displaystyle=\frac{\rho_{o}^{2}d_{o}^{4}P_{o}N_{s}^{2}M}{||\bm{q}(n)-\bm{l}_{k}||^{2}||\bm{q}(n)-\bm{c}||^{2}\sigma_{o}^{2}},$
(21)

which is only related to the UAV location $\bm{q}(n)$. Therefore, the problem
(P2) can be reformulated as

$\displaystyle\mathrm{(P3)}:\;$
$\displaystyle\max_{\bm{q}(n),\alpha_{k}(n)}\sum_{k=1}^{K}b_{k}A_{k}(n)\alpha_{k}(n)\xi_{k}(n)$
(22) $\displaystyle\bm{s.t.}\quad$
$\displaystyle\frac{\rho_{o}^{2}d_{o}^{4}P_{o}N_{s}^{2}M}{||\bm{q}(n)-\bm{l}_{k}||^{2}||\bm{q}(n)-\bm{c}||^{2}\sigma_{o}^{2}}\geq\alpha_{k}(n)\xi_{k}(n)\gamma_{th}$
(22a)
$\displaystyle(\ref{Cons_alpha}),(\ref{Cons_channel}),(\ref{Cons_UAValti}),(\ref{Cons_velocity}),$

where the objective function and the available channel constraint (9) are
linear, and the scheduling indicator constraint (8) can be relaxed as

$\alpha_{k}(n)\in[0,1],\vspace*{-0.5\baselineskip}$ (23)

which is convex. The UAV altitude constraint (15a) can be expressed as

$\bm{q}^{\rm T}(n)\bm{\varepsilon}=Z,\vspace*{-0.5\baselineskip}$ (24)

where $\bm{\varepsilon}=[0,0,1]^{T}$. However, problem (P3) is still non-
convex due to the constraint (22a). To tackle the non-convexity, the SCA
algorithm is applied iteratively. First, slack variables $r_{rk}(n)$ and
$r_{br}(n)$ are introduced as the upper bound of $d_{rk}^{2}(n)$ and
$d_{br}^{2}(n)$ respectively, which can be described as

$\displaystyle||\bm{q}(n)-\bm{l}_{k}||^{2}\leq r_{rk}(n),$ (25)
$\displaystyle||\bm{q}(n)-\bm{c}||^{2}\leq
r_{br}(n).\vspace*{-0.5\baselineskip}$ (26)

Thus, the lower bound of the $\bar{\gamma}_{k}(n)$ can be expressed as

$\bar{\gamma}_{k}(n)\geq\frac{\rho_{o}^{2}d_{o}^{4}P_{o}N_{s}^{2}M}{r_{rk}(n)r_{br}(n)\sigma_{o}^{2}}=\frac{\Gamma_{k}(n)}{r_{rk}(n)r_{br}(n)},\vspace*{-0.2\baselineskip}$
(27)

where
$\Gamma_{k}(n)=\frac{\rho_{o}^{2}d_{o}^{4}P_{o}N_{s}^{2}M}{\sigma_{o}^{2}}$,
and the SNR constraint is obtained as

$\frac{\Gamma_{k}(n)}{r_{rk}(n)r_{br}(n)}\geq\alpha_{k}(n)\xi_{k}(n)\gamma_{th},\vspace*{-0.5\baselineskip}$
(28)

which is equivalent to

$\frac{\Gamma_{k}(n)}{\xi_{k}(n)\gamma_{th}}\geq
r_{rk}(n)r_{br}(n)\alpha_{k}(n).$ (29)

To tackle the coupling between the variables, the logarithm is taken at both
sides. Then, we compute the first-order Taylor series of the right-hand side
(RHS) in the $i^{th}$ iteration in (29), which results in

$\displaystyle\ln{\Gamma_{k}(n)}-\ln\xi_{k}(n)\gamma_{th}\geq\ln r_{rk}(n)+\ln
r_{br}(n)+\ln\alpha_{k}(n)$ $\displaystyle=$
$\displaystyle\ln{r_{rk}^{(i-1)}(n)}+\ln{r_{br}^{(i-1)}(n)}+\ln{\alpha_{k}^{(i-1)}(n)}$
$\displaystyle+\frac{r_{rk}^{(i)}(n)-r_{rk}^{(i-1)}(n)}{r_{rk}^{(i-1)}(n)}+\frac{r_{br}^{(i)}(n)-r_{br}^{(i-1)}(n)}{r_{br}^{(i-1)}(n)}$
$\displaystyle+\frac{\alpha_{k}^{(i)}(n)-\alpha_{k}^{(i-1)}(n)}{\alpha_{k}^{(i-1)}(n)}=\hat{r}_{rk}^{(i)}(n)+\hat{r}_{br}^{(i)}(n)+\hat{\alpha_{k}}^{(i)}(n),$
(30)

where $(i-1)$ denotes the value in the $i-1^{th}$ iteration. It is noteworthy
that $\alpha_{k}(n)$ cannot be equal to $0$ for validity, so that constraint
(23) becomes

$\alpha_{k}(n)\in(0,1].\vspace*{-0.5\baselineskip}$ (31)

Hence the problem (P3) in the $i^{th}$ iteration becomes

$\displaystyle\mathrm{(P3.1)}:\;\max_{\bm{q}(n),\alpha_{k}(n),\atop
r_{rk}(n),r_{br}(n)}\sum_{k=1}^{K}b_{k}A_{k}(n)\alpha_{k}(n)\xi_{k}(n)$ (32)
$\displaystyle\bm{s.t.}\;$
$\displaystyle\hat{r}_{rk}^{(i)}(n)+\hat{r}_{br}^{(i)}(n)+\hat{\alpha}_{k}^{(i)}(n)\leq\ln{\Gamma_{k}(n)}-\ln\alpha_{k}(n)\xi_{k}(n)\gamma_{th}$
(32a)
$\displaystyle(\ref{Cons_channel}),(\ref{Cons_velocity}),(\ref{Cons_rela_alpha_0}),(\ref{Cons_UAValti_cvx}),(\ref{Cons_slack1}),(\ref{Cons_slack2}),$

which is a convex problem and can be efficiently solved using standard
optimization solver such as CVX. Finally, the SCA based algorithm is
summarized in Algorithm 1.

Algorithm 1 SCA based joint scheduling and UAV trajectory optimization

1:Initialize $\bm{q}(n),\alpha_{k}(n),r_{rk}(n),r_{br}(n)\;\forall
k\in\\{1,..,K\\}$, $\forall n\in\\{1,...,N_{T}\\}.$ Set iteration index $i=1$.

2:repeat

3: Update $\bm{q}(n),\alpha_{k}(n),r_{rk}(n),r_{br}(n)$ by solving problem
(P3.1).

4:until Convergence.

5:Output $\bm{q}(n),\alpha_{k}(n)$.

##  IV Numerical Results

In this section, the results of the numerical simulations are provided to
demonstrate the performance improvement of the proposed algorithm. A base
station with height $H=25{\rm\,m}$ is considered, with a $M=4\times 4$ UPA.
$K=6$ stationary ground users are located at $\bm{l}_{1}=[200,-100,0]^{\rm
T}{\rm m}$, $\bm{l}_{2}=[150,300,0]^{\rm T}{\rm m}$,
$\bm{l}_{3}=[320,-280,0]^{\rm T}{\rm m}$, $\bm{l}_{4}=[490,20,0]^{\rm T}{\rm
m}$, $\bm{l}_{5}=[50,-200,0]^{\rm T}{\rm m}$, $\bm{l}_{6}=[730,30,0]^{\rm
T}{\rm m}$ respectively. The maximum transmit power for each user is set to be
$P_{o}=1{\rm W}$, and the noise power is $\sigma_{o}^{2}=-110\,{\rm dBm}$.
According to the carrier frequency $f_{c}=2.4\,{\rm GHz}$, the reference
channel power gain is set to be $\rho_{o}=-40\,{\rm dB}$. Besides, the
distance between the adjacent elements at the IRS is $d_{x}=d_{y}=\lambda/10$.
The maximum flying velocity is set as $v_{max}=5\,{\rm m/s}$. We consider
$N_{T}=40$ simulation time slots in total, with each slot lasting
$\Delta=0.1\,{\rm s}$. The initial location of the UAV is set as
$\bm{q}=[0,0,Z]^{\rm T}$, where the flight altitude $Z$ is set as different
values for comparison.

Fig.3 plots AoI for $N_{T}=40$ time slots of the $6$ users. The height of the
aerial IRS is fixed as $Z=100\,{\rm m}$. The number of IRS elements is assumed
to be $N_{s}=550$, and the SNR threshold is set as $\gamma_{th}=25{\rm\,dB}$.
It can be seen that the AoI would increase linearly without the corresponding
stream being scheduled. Therefore, when the AoI is high, it will drop due to
packet scheduling and and transmission by the base station.

Figure 2: AoI performance of 6 users.

Fig.4 illustrates the weighted sum AoI for 40 time slots in total versus the
number of IRS elements. The proposed algorithm shows significantly better
performance than the fixed location scheme for the UAV at $[0,0,100\rm m]^{\rm
T}$ in terms of information freshness. Simultaneously, the weighted sum AoI
decreases with the increase of IRS elements $N_{s}$, from $150$ to $650$,
converging to the optimal value. Thus, with larger-scale IRS, the
communication link can be enhanced with the proposed algorithm. Besides,
different levels of the threshold value of SNR are considered, namely
$\gamma_{th}=25\,{\rm dB},30\,{\rm dB},32\,{\rm dB}$ and $35\,{\rm dB}$
respectively, and it can be seen that with higher $\gamma_{th}$, the freshness
of the received packets becomes worse.

Figure 3: Weighted sum AoI versus number of IRS elements $N_{s}$.

The convergence behavior with iteration number from $2$ to $15$ is highlighted
in Fig.5. We compare the AoI performance by modifying the flying height $Z$,
SNR threshold $\gamma_{th}$, as well as the number of IRS elements $N_{s}$.
Obviously, lower altitude results in better performance, due to the lower path
loss. Furthermore, it can be observed that the proposed algorithm converges
quickly and efficiently within about 5 iterations, verifying the low
computational complexity of our proposed SCA-based solution.

Figure 4: Convergence behavior of the proposed algorithm.

##  V Conclusion

We investigated the AoI performance of an aerial IRS-aided multi-user wireless
network, where a user scheduling model with joint active and passive
beamforming and UAV trajectory is designed to minimize the system weighted sum
AoI. The SCA-based optimization algorithm is proposed to efficiently overcome
the non-convexity of the formulated problem. The significant performance
improvement and the convergence behavior with the proposed low complexity
optimization algorithm is illustrated in the numerical results. We showed that
the flexible aerial IRS deployment can significantly enhance the communication
performance and information freshness for real-time network applications.

## References

  * [1] Q. Wu and R. Zhang, “Towards smart and reconfigurable environment: Intelligent reflecting surface aided wireless network,” _IEEE Communications Magazine_ , vol. 58, no. 1, pp. 106–112, 2020.
  * [2] Q. Wu, S. Zhang, B. Zheng, C. You, and R. Zhang, “Intelligent reflecting surface-aided wireless communications: A tutorial,” _IEEE Transactions on Communications_ , vol. 69, no. 5, pp. 3313–3351, 2021.
  * [3] H. Guo, Y.-C. Liang, J. Chen, and E. G. Larsson, “Weighted sum-rate maximization for reconfigurable intelligent surface aided wireless networks,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 5, pp. 3064–3076, 2020.
  * [4] Z. Ji, P. L. Yeoh, D. Zhang, G. Chen, Y. Zhang, Z. He, H. Yin, and Y. li, “Secret key generation for intelligent reflecting surface assisted wireless communication networks,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 1, pp. 1030–1034, 2021.
  * [5] Y. Zhang, B. Di, H. Zhang, J. Lin, C. Xu, D. Zhang, Y. Li, and L. Song, “Beyond cell-free mimo: Energy efficient reconfigurable intelligent surface aided cell-free mimo communications,” _IEEE Transactions on Cognitive Communications and Networking_ , vol. 7, no. 2, pp. 412–426, 2021.
  * [6] H. Lu, Y. Zeng, S. Jin, and R. Zhang, “Aerial intelligent reflecting surface: Joint placement and passive beamforming design with 3d beam flattening,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 7, pp. 4128–4143, 2021.
  * [7] Y. Zeng, Q. Wu, and R. Zhang, “Accessing from the sky: A tutorial on uav communications for 5g and beyond,” _Proceedings of the IEEE_ , vol. 107, no. 12, pp. 2327–2375, 2019.
  * [8] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _2012 Proceedings IEEE INFOCOM_ , 2012, pp. 2731–2735.
  * [9] T. D. P. Perera, D. N. K. Jayakody, I. Pitas, and S. Garg, “Age of information in swipt-enabled wireless communication system for 5gb,” _IEEE Wireless Communications_ , vol. 27, no. 5, pp. 162–167, 2020.
  * [10] “Age of information in wireless powered networks in low snr region for future 5g,” _Entropy_ , vol. 20, no. 12, 2018.
  * [11] Y. Gu, Q. Wang, H. Chen, Y. Li, and B. Vucetic, “Optimizing information freshness in two-hop status update systems under a resource constraint,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 5, pp. 1380–1392, 2021.
  * [12] S. Zhang, H. Zhang, Z. Han, H. V. Poor, and L. Song, “Age of information in a cellular internet of uavs: Sensing and communication trade-off design,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 10, pp. 6578–6592, 2020.
  * [13] A. Muhammad, M. Elhattab, M. Shokry, and C. Assi, “Age of Information Optimization in a RIS-Assisted Wireless Network,” _arXiv e-prints_ , p. arXiv:2103.06405, Mar. 2021.


# Information causality beyond the random access code model

Baichu Yu  Centre for Quantum Technologies, National University of Singapore,
3 Science Drive 2, Singapore 117543  Valerio Scarani  Centre for Quantum
Technologies, National University of Singapore, 3 Science Drive 2, Singapore
117543  Department of Physics, National University of Singapore, 2 Science
Drive 3, Singapore 117542

###### Abstract

Information causality (IC) was one of the first principles that have been
invoked to bound the set of quantum correlations. For some families of
correlations, this principle recovers exactly the boundary of the quantum set;
for others, there is still a gap. We close some of these gaps using a new
quantifier for IC, based on the notion of “redundant information”. The new
definition is still obeyed by quantum correlations. This progress was made
possible by the recognition that the principle of IC can be captured without
referring to the success criterion of random access codes.

##  I Introduction

Quantum theory differs from classical theory by the fact that the space of
states is a vector space, rather than a set. This change has been necessary to
accommodate the fact that only a fraction of the possible physical properties
can be well-defined in any given state. But why a vector space, instead of
something else? The basic answer is pragmatic: it has worked amazingly well.
But of course, it would be desirable to know which principles underlie this
choice. In the last decades, it was understood that quantum entanglement plays
a crucial role in addressing this question. All the recent representation
theorems use an axiom that has to do with composite systems (see D’Ariano  _et
al._ (2017) for an overview).

The most direct signature of entanglement are the quantum correlations
obtained by measuring the sub-systems separately. It is well known that some
of these correlations cannot be reproduced within classical theory without
communication, because they violate Bell’s inequalities Scarani (2019).
Instead of recovering the whole of quantum theory, a series of works have
tried to find principles that single out the set $\mathcal{Q}$ of quantum
correlations (save the phenomena, rather than the whole formalism). Since
measurements on shared entanglement cannot be used to send a signal, Popescu
and Rohrlich asked whether this no-signaling principle singles out quantum
correlations exactly: they quickly found that it does not Popescu and Rohrlich
(1994). The question then became: can one find other principles, to add on top
of no-signaling, so as to identify the set $\mathcal{Q}$?

Several such principles were proposed Brassard  _et al._ (2006); Pawłowski
_et al._ (2009); Navascués and Wunderlich (2010); Fritz  _et al._ (2013). Most
of them have later been proved to be satisfied in the set of “almost-quantum”
correlations Navascués  _et al._ (2015), which is strictly larger than
$\mathcal{Q}$. Thus, those principles are satisfied by all quantum
correlations, but they don’t identify $\mathcal{Q}$. For the principle of
information causality (IC) Pawłowski  _et al._ (2009), our knowledge is less
definite. For sure, all quantum correlations satisfy it; but its relations
with the set of almost-quantum correlations is not known, and it is then still
possible that IC identifies $\mathcal{Q}$ for bipartite Bell correlations
(some modifications will be needed for multipartite ones Gallego  _et al._
(2011); Yang  _et al._ (2012)). IC was defined in terms of a task: a classical
random access code (RAC), augmented by sharing the no-signaling resource under
study between the two players. In this paper, we propose to redefine IC in a
way that captures the same underlying notion as the original, but without
reference to the specific task of RAC. The new criterion is still obeyed by
all quantum correlations, but is violated by a larger set of non-quantum
correlations. To substantiate this claim, we show the first tightening of the
IC boundary in the simplest Bell scenario (two parties, two inputs and two
outputs, 2-2-2) since the original study Allcock  _et al._ (2009).

##  II Redefining information causality

We use upper case letters $A,B$ to denote random variables, lower case letters
$a,b$ to denote specific values. For bits, thus, one should understand
$A=\\{0,1\\}$, and then $a=0$ or $a=1$. The probability distribution of the
variable $X$ is denoted $p_{X}$, with $p_{X}(x)$ the probability of its event
$x$ (we may sometimes omit the subscript for simplicity).

To define IC, one considers the following two-player game. At every round,
Alice’s input is a string of $N$ bits $A=A_{1}\times...\times A_{N}$, its
value $a=(a_{1},...,a_{N})$ drawn at random with uniform distribution. She can
send information to Bob on a channel with capacity $k$ per round. In addition,
she shares a no-signaling resource with Bob. If $k<N$, Bob obviously can
retrieve at most $k$ bits of Alice’ input, irrespective of what the no-
signaling resource is. But with a clever use of some no-signaling resources,
something unexpected may happen: Bob could choose which $k$ bits to retrieve.
In words, it looks like the information about all $N$ bits was “potentially”
present at Bob’s location, although eventually he can read out only $k$ of
them. The principle of IC states that this should not happen; and more
quantitatively: even the “potential information” available at Bob’s location
should not exceed the capacity $k$ of the channel linking Alice and Bob. In
this paper we discuss how this potential information should be quantified.

In the original paper Pawłowski  _et al._ (2009) and all subsequent works
Allcock  _et al._ (2009); Barnum  _et al._ (2010); Cavalcanti  _et al._
(2010); Al-Safi and Short (2011); Yang  _et al._ (2012); Miklin and Pawłowski
(2021), IC was captured by a random access code (RAC) criterion: Bob receives
an input $t\in\\{1,...,N\\}$ that tells him which of Alice’s bits he is
supposed to retrieve in any given round. Over many rounds, then, the potential
information is estimated by

$IC_{\textrm{RAC}}=\sum_{i=1}^{N}I(A_{i};B|t=i)\,\equiv\,\sum_{i=1}^{N}I(A_{i};B_{i})\,.$
(1)

With this criterion, IC is satisfied if

$IC_{\textrm{RAC}}\leq k.$ (2)

The intuition behind such RAC type of IC characterization is: we would find it
surprising if, in every round, Bob could produce the correct value
$b_{i}=a_{i}$ for the requested $i$, thus achieving $IC_{\textrm{RAC}}=N$.

But the definition of potential information does not necessarily require a
game with a specific winning criterion for each round. The input $A$ of Alice
can be treated as a single symbol (which doesn’t even need to have the
dimension of a string of bits), and the number $M$ of Bob’s inputs can be an
independent number (even if Alice’s input were $N$ bits, we could have $M\neq
N$). After many rounds, Alice and Bob can estimate the $M$ probability
distributions $p_{AB}(a,b|t=i)\equiv p_{AB_{i}}(a,b_{i})$. A bound on
potential information can be obtained directly from those. Specifically, the
quantifier of potential information that we consider would read

$IC_{\textrm{red}}(M)=\sum_{i=1}^{M}I(A;B_{i})-I_{r}(A;B_{1},...,B_{M})\,.$
(3)

The first term in (3) is the sum of the mutual information of $A$ with each of
the $B_{i}$. It can easily reach $Mk$ if $B_{1}$ carries all the information
$k$, and all the other $B_{i}$ are set equal to $B_{1}$ and thus carry the
same piece of information. This observation is the basis for understanding the
role of the second term: one needs to remove redundant information, i.e.
information that is present in several $B_{i}$. The characterization of
redundant information is still debated. The lack of a general expression for
$I_{r}(A;B_{1},...,B_{M})$ is the current limit for our study of IC.
Fortunately, the interest of the approach can already be proved in the
simplest case $M=2$, for which an expression for redundant information has
been given.

##  III IC with Redundant Information

We are going to study

$\displaystyle
IC_{\textrm{red}}=\sum_{i=1}^{2}I(A;B_{i})-I_{r}(A;B_{1},B_{2})$ (4)

with the measure of redundant information proposed by Harder, Salge and Polani
Harder  _et al._ (2013). We first describe this measure, then prove that
quantum correlations obey IC with our new definition, that is

$\displaystyle IC_{\textrm{red}}\leq k\,.$ (5)

###  III.1 The measure of redundant information

Let us now give the recipe of Ref. Harder  _et al._ (2013) to compute
redundant information. The starting point are the two joint probability
distributions $p_{AB_{i}}$ for $i=1,2$. From $p_{AB_{i}}$, for each value of
$B_{i}$ one constructs the probability distribution $p_{A|b_{i}}$ on $A$.
These are $|B_{i}|$ points in the probability simplex of $A$, and we denote by
$C_{i}$ their convex hull. For $|B|=2$, as is the case for us,

$\displaystyle C_{i}=\big{\\{}\lambda
p_{A|b_{i}=0}+(1-\lambda)p_{A|b_{i}=1}\,|\,\lambda\in[0,1]\big{\\}}\,.$ (6)

Now, for every value $b_{1}$ of $B_{1}$, one defines $p_{A[b_{1}\searrow
B_{2}]}$ as the element of $C_{2}$ that is “closest” to $p_{A|b_{1}}$ in the
following sense:

$p_{A[b_{1}\searrow B_{2}]}:=\textrm{argmin}_{r\in
C_{2}}D_{KL}(p_{A|b_{1}}||r),$ (7)

where $D_{KL}$ is the Kullback-Leibler divergence. Having solved this
optimisation for all $b_{1}$, one can compute the “projected information”
111The projected information can be written in a more telling way as
$I_{A}^{\pi}(B_{1}\searrow{B_{2}})=I(A;B_{1})-D_{KL}(p_{AB_{1}}||\tilde{p}_{AB_{1}})$
where $\tilde{p}_{AB_{1}}(a,b_{1})=p_{A[b_{1}\searrow
B_{2}]}(a)p_{B_{1}}(b_{1})$ could be understood as the best guess for the
distribution of $(A,B_{1})$ given $(A,B_{2})$. In order to go from (8) to this
expression, one multiplies both the numerator and the denominator inside the
logarithm by $p_{B_{1}}(b_{1})p_{AB_{1}}(a,b_{1})$ and rearranges the terms.
(Francesco Buscemi, private communication).

$I_{A}^{\pi}(B_{1}\searrow{B_{2}})=\sum_{a,b_{1}}p_{AB_{1}}(a,b_{1})\log\left(\frac{p_{A[b_{1}\searrow
B_{2}]}(a)}{p_{A}(a)}\right)\,.$ (8)

After repeating the recipe with $B_{1}$ and $B_{2}$ exchanged, redundant
information is finally computed as

$I_{r}(A;B_{1},B_{2}):=\min\\{I_{A}^{\pi}(B_{1}\searrow
B_{2}),I_{A}^{\pi}(B_{2}\searrow B_{1})\\}\,.$ (9)

Among the properties of $I_{r}$, it was proved in Harder  _et al._ (2013) that
the quantity (4) is bounded as $IC_{\textrm{red}}\leq I(A;B_{1},B_{2})$.
Notice that $I_{r}$, and thence $IC_{\textrm{red}}$, is a functional of the
two marginal distributions $p_{AB_{i}}$ only. Thus, explicitly, the bound just
mentioned reads

$\displaystyle IC_{\textrm{red}}[p_{AB_{1}},p_{AB_{2}}]$ $\displaystyle\leq$
$\displaystyle I(A;B_{1},B_{2})[p_{AB_{1}B_{2}}]$ (10)

and holds for every joint probability distribution $p_{AB_{1}B_{2}}$ that has
marginals $p_{AB_{1}},p_{AB_{2}}$. We are going to use this observation to
prove that IC holds for quantum correlations.

###  III.2 Proof that IC holds for quantum correlations

When the shared no-signaling resource is quantum, Bob’s outputs $B_{i}$ are
generated by processing the information available to him. This consists of his
part $\rho_{B}=\textrm{Tr}_{A}(\rho_{AB})$ of the initially shared state
$\rho_{AB}$, and of the classical message $m$ received by Alice. We denote
this variable by $Q_{Bm}$ and its set of events by $\\{\rho_{Bm}\\}$. The
observed quantum correlations will be given by

$p_{AB_{i}}(a,b_{i})\equiv\sum_{\rho_{Bm}}p(\rho_{Bm})p(a,b_{i}|\rho_{Bm})\,.$
(11)

But crucially, the information about $A$ in $B_{i}$ is mediated by $Q_{Bm}$,
i.e. we have a Markov chain $A\rightarrow Q_{Bm}\rightarrow B_{i}$. Therefore

$p(a,b_{i}|\rho_{Bm})=p(a|\rho_{Bm})p(b_{i}|\rho_{Bm})$ (12)

holds for every $\rho_{Bm}$. Then we can construct the joint distribution

$\displaystyle p_{AB_{1}B_{2}}(a,b_{1},b_{2})\equiv$ (13)
$\displaystyle\sum_{\rho_{Bm}}p(\rho_{Bm})p(a|\rho_{Bm})$ $\displaystyle
p(b_{1}|\rho_{Bm})p(b_{2}|\rho_{Bm})$ (14)

whose marginals with respect to either of the $B_{i}$ are indeed the quantum
correlations (11). For this distribution, the data-processing inequality gives

$I(A;B_{1},B_{2})[p_{AB_{1}B_{2}}]\leq I(A;Q_{Bm})\,.$ (15)

Finally, $I(A;Q_{Bm})\leq k$ is just another application of the same
inequality, capturing the fact that only the message $m$ has carried
information about $A$ to Bob, and shared quantum information does not change
that (see the formal proof in the first paper on IC Pawłowski  _et al._
(2009)). By comparison with (10), we have proved that IC holds for shared
quantum resources according to our new definition Eq. (5).

##  IV Evidence of improvement

We now prove that our approach to IC constitutes a real improvement over the
original one, as it rules out more non-quantum correlations. Specifically, we
are going to report the first improvement on IC for the 2-2-2 scenario since
the original study by Allcock and coworkers Allcock  _et al._ (2009).

###  IV.1 Definitions and protocol

We denote $x,y\in\\{0,1\\}$ the inputs to the boxes,
$\mathfrak{a},\mathfrak{b}\in\\{0,1\\}$ the outputs. The set of no-signaling
correlation is a polytope with 24 vertices: 8 extremal non-local boxes, which
can be parametrized by $\mu,\nu,\sigma\in\\{0,1\\}$ as

$P_{NL}^{\mu\nu\sigma}(\mathfrak{a}\mathfrak{b}|xy)=\left\\{\begin{array}[]{ll}\frac{1}{2},&\textrm{if}\
\mathfrak{a}\oplus\mathfrak{b}=xy\oplus\mu x\oplus\nu y\oplus\sigma\\\
0,&\textrm{otherwise}\,;\end{array}\right.$ (16)

and 16 local deterministic boxes, which can be parametrized by
$\mu,\nu,\sigma,\tau\in\\{0,1\\}$ as

$P_{L}^{\mu\nu\sigma\tau}(\mathfrak{a}\mathfrak{b}|xy)=\left\\{\begin{array}[]{ll}1,&\textrm{if}\
\mathfrak{a}=\mu x\oplus\nu,\ \mathfrak{b}=\sigma y\oplus\tau\\\
0,&\textrm{otherwise}.\end{array}\right.$ (17)

The box $P_{NL}^{000}$ is the canonical form of the PR-box, maximizing the
value of $CHSH=C_{00}+C_{01}+C_{10}-C_{11}$ where
$C_{xy}=P(\mathfrak{a}=\mathfrak{b}|xy)-P(\mathfrak{a}\neq\mathfrak{b}|xy)$.
All the other $P_{NL}^{\mu\nu\sigma}$ are obtained from it by relabelling some
of the inputs and/or some of the outputs, and maximize the corresponding CHSH-
type expression.

No method is known to decide whether a no-signaling resource violates IC based
on the description of the box alone: one needs to invent an explicit protocol
that uses that resource (the fact that this protocol may not be optimal is the
main reasons why the exact boundaries of the violation of IC are not known).
Here, we follow a recently proposed compact protocol Miklin and Pawłowski
(2021). Although it led to some improvements for other scenarios, for the
2-2-2 scenario this protocol reproduced the results of Allcock  _et al._
(2009). Thus, the improvement we are going to report is really due to our new
definition of IC.

The protocol is the following. Alice inputs $x=a_{1}\oplus a_{2}$ into the
box; upon receiving the output $\mathfrak{a}$, she computes the bit
$m=\mathfrak{a}\oplus a_{1}$. She sends this bit to Bob on a noisy channel:
specifically, a symmetric binary channel that flips the bit with probability
$1-p_{c}$. The capacity of this channel is

$k=1+p_{c}\log_{2}p_{c}+(1-p_{c})\log_{2}(1-p_{c})\,.$ (18)

The bounds for IC get tighter in the limit $p_{c}\rightarrow\frac{1}{2}$
Miklin and Pawłowski (2021).

On his side, when Bob wants to estimate $B_{i}$, he inputs $y=i-1$ in the box.
Upon receiving the output $\mathfrak{b}$, he produces
$b_{i}=\mathfrak{b}\oplus m^{\prime}$ where $m^{\prime}$ is the output of the
noisy channel from Alice.

###  IV.2 Case studies

As concrete case studies, we look at the same three families of boxes studied
in Allcock  _et al._ (2009). These families are defined by the convex
combination

$PR_{\alpha,\beta}=\alpha P_{NL}^{000}+\beta
R_{NS}+(1-\alpha-\beta)\mathbb{I},$ (19)

where $\alpha\in[0,1]$, $\beta\in[0,1-\alpha]$, $R_{NS}$ is an extremal point
of the no-signaling polytope, and $\mathbb{I}$ indicates the white noise
$P(\mathfrak{a}\mathfrak{b}|xy)=\frac{1}{4}$. The case studies will involve
the same three choices of $R_{NS}$ as Allcock  _et al._ (2009), namely
$P_{NL}^{010}$, $P_{NL}^{110}$ and $P_{L}^{0000}$. By the symmetry of the
problem, this choice covers actually all cases: $P_{NL}^{010}$ is equivalently
to $P_{NL}^{011}$, $P_{NL}^{100}$, and $P_{NL}^{101}$; $P_{NL}^{110}$ is
equivalent to $P_{NL}^{111}$; and all the local deterministic points on the
facet $CHSH=2$ are equivalent. Finally, since
$P_{NL}^{001}=2\mathbb{I}-P_{NL}^{000}$ is the PR-box opposite to the
canonical one, that mixing is already taken into account in (19).

The explicit expressions needed to compute the $p_{AB_{i}}$ for each case are
given in Table 1. The numerical calculations require setting $p_{c}$ close to
$\frac{1}{2}$ because the tightest bounds are found in that limit Miklin and
Pawłowski (2021); and identifying the minimum in (7). These are reliably dealt
with by sampling evenly and by varying some precision parameters, details are
given in footnote 222For each curve, we choose 50 values of $\beta$ evenly
distributed from $[0,1]$, and then 3000 values of $\alpha$ evenly distributed
in $[0,1-\beta]$. We identify the largest $\alpha$ such that the IC do not
exceed the channel capacity (18) with $p_{c}=0.5001$; we have run checks on
some points with $p_{c}=0.50001$ and observed no visible difference. The
optimisation (7) is also done by even sampling. Indeed, for each value of
$b_{1}$, we have to find the value of $\lambda$ such that
$r_{A}(\lambda)=\lambda p_{A|b_{2}=0}+(1-\lambda)p_{A|b_{2}=1}$ minimizes
$D_{KL}(p_{A|b_{1}}||r_{A}(\lambda))$; then we have to redo this with the
roles of $B_{1}$ and $B_{2}$ reversed. In each case, we sample $\lambda$ in
the interval $[0,1]$ by steps of $\frac{1}{n}$ and identify the minimum. By
inspection, we found that $n=1000$ was well sufficient (although we run checks
for higher values of $n$, up to $n=20000$).. As a check, we also redid the
curves for the original IC criterion and recovered the plots of Allcock  _et
al._ (2009) as expected.

The results are shown graphically in Fig. 1. In summary:

  * •

For $R_{NS}=P_{NL}^{010}$ (or $P_{NL}^{011}$, $P_{NL}^{100}$, $P_{NL}^{101}$),
both the original definition of IC and our new one recover the boundary of the
quantum set (within numerical precision).

  * •

$R_{NS}=P_{NL}^{110}$ (or $P_{NL}^{111}$), the original definition of IC
stayed very far from the quantum boundary: in fact, it could just detect a
violation of IC for those boxes that violate the Tsirelson bound. By contrast,
our new definition recovers exactly the quantum set, within numerical
precision.

  * •

Finally, for $R_{NS}=P_{L}^{0000}$ (or any other local deterministic point on
the facet $CHSH=2$), our definition and the original one give the same
boundary for IC, but there remains a gap with the quantum boundary.

The fact that the original definition recovered the quantum boundary for some
$R_{NS}=P_{NL}^{\mu\nu\sigma}$ but not others was an artefact of the use of
RAC. This can be intuited by looking at the behavior of the extremal points
for $p_{c}=1$. For the canonical PR-box $P_{NL}^{000}$, the protocol yields
$A_{1}=B_{1}$ and $A_{2}=B_{2}$; for $R_{NS}=P_{NL}^{110}$, the same protocol
yields $A_{1}=B_{2}\oplus 1$ and $A_{2}=B_{1}$. The amount of potential
information is the same for both points (each $B_{i}$ has full information on
one of the $A_{j}$), and our definition captures this. Imposing the RAC
winning condition $A_{i}=B_{i}$ breaks the symmetry.

When $R_{NS}=P_{L}^{0000}$, the quantum boundary is provably a straight line
Goh  _et al._ (2018). The boundary of the set of “almost-quantum” correlations
$\mathcal{Q}_{1+AB}$ is indistinguishable from it at the scale of the figure
333The boundary for $\mathcal{Q}_{1+AB}$ was computed by Koon Tong Goh
(private communication) with the SeDuMi SDP solver. The difference between
those values and the straight line is found at the third significant digit.
Since the precision of the solver was set at with a precision $\sim 10^{-10}$,
the difference is believed to be real.. A significant gap remains between
those sets and the violation of IC, even with the new definition that here
does not improve on the original one. This gap may be real: definitely, this
is a slice where one could focus the efforts to prove that IC does not
coincide with $\mathcal{Q}$. Alternatively, we may not have captured
“potential information” at its tightest yet. For instance, Ref. Ince (2017)
argues that redundant information may have to depend also on the joint
distribution of Bob’s outputs $p_{B_{1}B_{2}}$ and not just on the marginals
with Alice $p_{AB_{i}}$.

Figure 1: Slices (19) of the non-signalling polytope studied in this work: from top to bottom, $R_{NS}=P_{NL}^{010}$, $R_{NS}=P_{NL}^{110}$, and $R_{NS}=P_{L}^{0000}$. In all figures, the top left corner is the PR box $P_{NL}^{000}$, the bottom line is the facet $CHSH=2$. ICO represents IC for the original definition (2); these are the curves found in Allcock  _et al._ (2009). ICR represents IC for our definition based on redundant information (5). The quantum boundary is the Tsirelson-Landau-Masanes bound (see Scarani (2019)) for the first two figures, and a straight line for the third Goh  _et al._ (2018). $R_{NS}$ | $P^{010}_{NL}$ |  | $P^{110}_{NL}$ |  | $P^{0000}_{L}$ |
---|---|---|---|---|---|---
| $B_{1}$ | $B_{2}$ | $B_{1}$ | $B_{2}$ | $B_{1}$ | $B_{2}$
$a=00$ | $k_{+}$ | $k_{-}$ | $k_{+}$ | $k_{-}$ | $k_{+}$ | $k_{+}$
$a=01$ | $k_{+}$ | $1-k_{-}$ | $k_{-}$ | $1-k_{+}$ | $k_{+}$ | $1-k_{-}$
$a=10$ | $1-k_{+}$ | $k_{-}$ | $1-k_{-}$ | $k_{+}$ | $1-k_{+}$ | $k_{-}$
$a=11$ | $1-k_{+}$ | $1-k_{-}$ | $1-k_{+}$ | $1-k_{-}$ | $1-k_{+}$ | $1-k_{+}$
Table 1: Values of $p(b_{i}=0|a)$ for the three slices (19) under study. We
have denoted $k_{\pm}=\frac{1}{2}+(p_{c}-\frac{1}{2})(\alpha\pm\beta)$. Since
the protocol has $p(a)=\frac{1}{4}$, and since in those slices
$p(b_{i})=\frac{1}{2}$, it holds $p(a|b_{i})=p(b_{i}|a)/2$. The latter numbers
define the $p_{A|b_{i}}$ used for the calculation of redundant information.

##  V Conclusion

In this paper we proposed a new quantifier for IC principle based on the
notion of “redundant information”, and provided an explicit proof of its
advantage in the simplest Bell scenario.

In IC, Alice sends information about her random variable $A$ to Bob through a
classical channel, and Bob has multiple indicators that can extract
information from it. Previous works had captured the principle in the context
of a random access code, with $A$ a string of independent symbols, and the
desideratum that each of these symbols should be in one-to-one correspondence
with Bob’s indicators. Our main contribution is to liberate IC from this
constraining structure. We highlight that all that IC needs is a method to
integrate the pieces of information obtained by different indicators of Bob,
while making sure that no information is calculated repeatedly.

The main bottleneck for further progress comes from classical information
theory: there is no suitable candidate expression for redundant information
beyond the case of two indicators for Bob, the one we used for our explicit
examples. We also notice that, even with our improved approach, there remains
a gap between the set of quantum correlations and the set of correlations that
violate IC. We conjecture that such gaps can be closed, or at least reduced,
by future improvements on the definition of redundant information, or more
generally by tightening the quantifier of “potential information”.

## Acknowledgments

We thank Francesco Buscemi and Marcin Pawłowski for feedback and comments, and
Koon Tong Goh for sharing his numerical results on the almost-quantum set.

We acknowledge financial support from the National Research Foundation and the
Ministry of Education, Singapore, under the Research Centres of Excellence
programme.

## References

  * D’Ariano  _et al._ (2017) G. M. D’Ariano, G. Chiribella, and P. Perinotti,  _Quantum Theory from First Principles_ (Cambridge University Press, Cambridge, 2017).
  * Scarani (2019) V. Scarani,  _Bell Nonlocality_ (Oxford University Press, Oxford, 2019).
  * Popescu and Rohrlich (1994) S. Popescu and D. Rohrlich, Foundations of Physics 24, 379 (1994).
  * Brassard  _et al._ (2006) G. Brassard, H. Buhrman, N. Linden, A. A. Méthot, A. Tapp, and F. Unger, Phys. Rev. Lett. 96, 250401 (2006).
  * Pawłowski  _et al._ (2009) M. Pawłowski, T. Paterek, D. Kaszlikowski, V. Scarani, A. Winter, and M. Żukowski, Nature 461, 1101 (2009).
  * Navascués and Wunderlich (2010) M. Navascués and H. Wunderlich, Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 466, 881 (2010).
  * Fritz  _et al._ (2013) T. Fritz, A. B. Sainz, R. Augusiak, J. B. Brask, R. Chaves, A. Leverrier, and A. Acín, Nature Communications 4, 2263 (2013).
  * Navascués  _et al._ (2015) M. Navascués, Y. Guryanova, M. J. Hoban, and A. Acín, Nature Communications 6, 6288 (2015).
  * Gallego  _et al._ (2011) R. Gallego, L. E. Würflinger, A. Acín, and M. Navascués, Phys. Rev. Lett. 107, 210403 (2011).
  * Yang  _et al._ (2012) T. H. Yang, D. Cavalcanti, M. L. Almeida, C. Teo, and V. Scarani, New Journal of Physics 14, 013061 (2012).
  * Allcock  _et al._ (2009) J. Allcock, N. Brunner, M. Pawlowski, and V. Scarani, Physical Review A 80, 040103 (2009).
  * Barnum  _et al._ (2010) H. Barnum, J. Barrett, L. O. Clark, M. Leifer, R. Spekkens, N. Stepanik, A. Wilce, and R. Wilke, New Journal of Physics 12, 033024 (2010).
  * Cavalcanti  _et al._ (2010) D. Cavalcanti, A. Salles, and V. Scarani, Nature Communications 1, 136 (2010).
  * Al-Safi and Short (2011) S. W. Al-Safi and A. J. Short, Phys. Rev. A 84, 042323 (2011).
  * Miklin and Pawłowski (2021) N. Miklin and M. Pawłowski, Physical Review Letters 126, 220403 (2021).
  * Harder  _et al._ (2013) M. Harder, C. Salge, and D. Polani, Physical Review E 87, 012130 (2013).
  * Note (1) The projected information can be written in a more telling way as  $I_{A}^{\pi}(B_{1}\searrow{B_{2}})=I(A;B_{1})-D_{KL}(p_{AB_{1}}||\mathaccentV{tilde}07E{p}_{AB_{1}})$ where $\mathaccentV{tilde}07E{p}_{AB_{1}}(a,b_{1})=p_{A[b_{1}\searrow B_{2}]}(a)p_{B_{1}}(b_{1})$ could be understood as the best guess for the distribution of $(A,B_{1})$ given $(A,B_{2})$. In order to go from (8) to this expression, one multiplies both the numerator and the denominator inside the logarithm by $p_{B_{1}}(b_{1})p_{AB_{1}}(a,b_{1})$ and rearranges the terms. (Francesco Buscemi, private communication).
  * Note (2) For each curve, we choose 50 values of $\beta$ evenly distributed from $[0,1]$, and then 3000 values of $\alpha$ evenly distributed in $[0,1-\beta]$. We identify the largest $\alpha$ such that the IC do not exceed the channel capacity (18) with $p_{c}=0.5001$; we have run checks on some points with $p_{c}=0.50001$ and observed no visible difference. The optimisation (7) is also done by even sampling. Indeed, for each value of $b_{1}$, we have to find the value of $\lambda$ such that $r_{A}(\lambda)=\lambda p_{A|b_{2}=0}+(1-\lambda)p_{A|b_{2}=1}$ minimizes $D_{KL}(p_{A|b_{1}}||r_{A}(\lambda))$; then we have to redo this with the roles of $B_{1}$ and $B_{2}$ reversed. In each case, we sample $\lambda$ in the interval $[0,1]$ by steps of $\frac{1}{n}$ and identify the minimum. By inspection, we found that $n=1000$ was well sufficient (although we run checks for higher values of $n$, up to $n=20000$).
  * Goh  _et al._ (2018) K. T. Goh, J. Kaniewski, E. Wolfe, T. Vértesi, X. Wu, Y. Cai, Y.-C. Liang, and V. Scarani, Physical Review A 97, 022104 (2018).
  * Note (3) The boundary for $\mathcal{Q}_{1+AB}$ was computed by Koon Tong Goh (private communication) with the SeDuMi SDP solver. The difference between those values and the straight line is found at the third significant digit. Since the precision of the solver was set at with a precision $\sim 10^{-10}$, the difference is believed to be real.
  * Ince (2017) R. A. Ince, Entropy 19, 318 (2017).