# Transmit Optimization for Multi-functional MIMO Systems Integrating Sensing,
Communication, and Powering

Yilong Chen, Haocheng Hua, and Jie Xu J. Xu is the corresponding author.
School of Science and Engineering and Future Network of Intelligence
Institute,
The Chinese University of Hong Kong (Shenzhen), Shenzhen, China
Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper unifies integrated sensing and communication (ISAC) and
simultaneous wireless information and power transfer (SWIPT), by investigating
a new multi-functional multiple-input multiple-output (MIMO) system
integrating wireless sensing, communication, and powering. In this system, one
multi-antenna hybrid access point (H-AP) transmits wireless signals to
communicate with one multi-antenna information decoding (ID) receiver,
wirelessly charge one multi-antenna energy harvesting (EH) receiver, and
perform radar sensing for a point target based on the echo signal at the same
time. Under this setup, we aim to reveal the fundamental performance tradeoff
limits of sensing, communication, and powering, in terms of the estimation
Cramér-Rao bound (CRB), achievable communication rate, and harvested energy
level, respectively. Towards this end, we define the achievable CRB-rate-
energy (C-R-E) region and characterize its Pareto boundary by maximizing the
achievable rate at the ID receiver, subject to the estimation CRB requirement
for target sensing, the harvested energy requirement at the EH receiver, and
the maximum transmit power constraint at the H-AP. We obtain the semi-closed-
form optimal transmit covariance solution to the formulated problem by
applying advanced convex optimization techniques. Numerical results show the
optimal C-R-E region boundary achieved by our proposed design, as compared to
the benchmark scheme based on time switching.

##  I Introduction

Future sixth-generation (6G) wireless networks need to incorporate billions of
low-power Internet-of-things (IoT) devices and support their localization,
sensing, communication, and control in a sustainable manner. Towards this end,
simultaneous wireless information and power transfer (SWIPT) [1] and
integrated sensing and communications (ISAC) [2] have emerged as two enabling
techniques aiming to reuse radio signals to wirelessly charge massive IoT
devices and provide sensing functionality, respectively. With their recent
advancements, we envision that future 6G networks will integrate both SWIPT
and ISAC to evolve towards new multi-functional wireless systems, which can
provide sensing, communication, and powering capabilities at the same time.
Such multi-functional wireless systems are expected to significantly enhance
the utilization efficiency of scarce spectrum resources and densely deployed
base station (BS) infrastructures, and facilitate the localization and
powering of massive low-power devices to support emerging IoT applications.

In the literature, there have been extensive prior works investigating the
transmit optimization for SWIPT (e.g., [3, 4]) and ISAC (e.g., [5, 6, 7, 8])
independently. For instance, the authors in [3] first studied a multiple-input
multiple-output (MIMO) SWIPT system with one information decoding (ID)
receiver and one energy harvesting (EH) receiver, in which the transmit
covariance at the BS was designed to optimally balance the tradeoff between
the communication rate versus the harvested energy level. This design was then
extended to the broadcast channel with multiple ID receivers and multiple EH
receivers (see, e.g., [4]). On the other hand, the works [5] and [6]
considered the basic ISAC setup with one BS, one ID receiver, and one sensing
target, in which the transmit strategies at the BS were optimized to balance
the communication rate versus the estimation Cramér-Rao bound (CRB) as the
sensing performance metric. Furthermore, the authors in [7] and [8] studied
the ISAC system with multiple ID receivers and sensing targets, in which the
transmit beamforming design at the BS was optimized to balance the
communication and sensing performances.

Different from these prior works, this paper studies a multi-functional MIMO
system unifying ISAC and SWIPT as shown in Fig. 1, in which one single multi-
antenna hybrid access point (H-AP) transmits wireless signals to
simultaneously deliver information to one multi-antenna ID receiver, provide
energy supply to one multi-antenna EH receiver, and estimate a sensing target
based on the echo signals. For such a multi-functional wireless system, how to
design the transmit strategies at the multi-antenna H-AP is essential to
optimize the performance tradeoffs among sensing, communication, and powering.
This problem, however, is particularly challenging, since the MIMO sensing
(e.g., [9, 10]), communication (e.g., [11]), and powering (e.g., [3]) are
designed based on distinct objectives and follow different principles. This
thus motivates our study in this work.

Figure 1: A multi-functional MIMO system unifying SWIPT and ISAC.

In this paper, we consider the multi-functional MIMO system by focusing on the
point target model for radar sensing, in which the H-AP aims to estimate the
target angle. We aim to reveal the fundamental performance tradeoffs among
sensing, communication, and powering, in terms of the angle estimation CRB,
the achievable communication rate, and the harvested energy level. Towards
this end, we characterize the complete CRB-rate-energy (C-R-E) region of this
system, which is defined as the set of all C-R-E pairs that are simultaneously
achievable. To find the points on the Pareto boundary surface of the C-R-E
region, we propose to maximize the MIMO communication rate while ensuring the
estimation CRB requirement for target sensing and the harvested energy
requirement at the EH receiver, subject to the maximum transmit power
constraint at the H-AP. We derive the well-structured optimal transmit
covariance solution by using advanced convex optimization techniques. It is
shown that the optimal transmit covariance follows the eigenmode transmission
(EMT) structure based on a composite channel matrix, which can be generally
divided into two parts, one for the triple roles of communication, sensing,
and powering, and the other for sensing and powering only. Finally, numerical
results validate the performance of our proposed design, in comparison to the
benchmark scheme based on time switching.

Notations: Boldface letters are used for vectors (lower-case) and matrices
(upper-case). For a square matrix $\boldsymbol{A}$,
$\mathrm{tr}(\boldsymbol{A})$ and $\det(\boldsymbol{A})$ denote its trace and
determinant, respectively, $\boldsymbol{A}\succeq\boldsymbol{0}$ means that
$\boldsymbol{A}$ is positive semi-definite, and
$\boldsymbol{A}\succ\boldsymbol{0}$ means that $\boldsymbol{A}$ is positive
definite. For an arbitrary-size matrix $\boldsymbol{A}$,
$\mathrm{rank}(\boldsymbol{A})$, $\boldsymbol{A}^{\dagger}$,
$\boldsymbol{A}^{T}$, $\boldsymbol{A}^{H}$, and $\mathcal{R}(\boldsymbol{A})$
denote its rank, conjugate, transpose, conjugate transpose, and range space,
respectively. For a vector $\boldsymbol{a}$, $\|\boldsymbol{a}\|$ denotes its
Euclidean norm. For a complex number $a$, $|a|$ denotes its magnitude. For a
real number $a$, $(a)^{+}\triangleq\max(a,0)$.
$\mathrm{diag}(a_{1},\dots,a_{N})$ denotes a diagonal matrix whose diagonal
entries are $a_{1},\dots,a_{N}$. $\boldsymbol{I}_{N}$ denotes the identity
matrix with dimension $N\times N$. $\mathbb{C}^{M\times N}$ and
$\mathbb{S}^{N}$denote the spaces of $M\times N$ complex matrices and $N\times
N$ Hermitian matrices. $\mathbb{E}[\cdot]$ denotes the statistic expectation.
$j=\sqrt{-1}$.

##  II System Model

This paper considers a multi-functional MIMO system as shown in Fig. 1, which
consists of one H-AP, one EH receiver, one ID receiver, and one sensing target
to be estimated. The H-AP is equipped with a uniform linear array (ULA) of
$M>1$ transmit antennas and $N_{\text{S}}>1$ receive antennas for sensing. The
EH and ID receivers are equipped with $N_{\text{EH}}\geq 1$ and
$N_{\text{ID}}\geq 1$ receive antennas, respectively.

We consider a quasi-static narrowband channel model, in which the wireless
channels remain unchanged over the interested transmission block consisting of
$L$ symbols, where $L$ is assumed to be sufficiently large. Let
$\boldsymbol{H}_{\text{EH}}\in\mathbb{C}^{N_{\text{EH}}\times M}$ and
$\boldsymbol{H}_{\text{ID}}\in\mathbb{C}^{N_{\text{ID}}\times M}$ denote the
channel matrices from the H-AP to the EH receiver and the ID receiver,
respectively. Let $\boldsymbol{H}_{\text{S}}\in\mathbb{C}^{N_{\text{S}}\times
M}$ denote the target response matrix from the H-AP transmitter to the sensing
target to the H-AP receiver, which will be specified later. It is assumed that
the H-AP perfectly knows the information of $\boldsymbol{H}_{\text{EH}}$ and
$\boldsymbol{H}_{\text{ID}}$, and the ID receiver perfectly knows
$\boldsymbol{H_{\text{ID}}}$ to facilitate the transmit optimization, as
commonly assumed in the literature [3, 4].

At each symbol $l\in\\{1,\dots,L\\}$, let
$\boldsymbol{x}(l)\in\mathbb{C}^{M\times 1}$ denote the transmitted signal at
the H-AP. The transmitted signal over the whole block is expressed as

$\boldsymbol{X}=\big{[}\boldsymbol{x}(1),\dots,\boldsymbol{x}(L)\big{]}\in\mathbb{C}^{M\times
L}.$ (1)

Without loss of optimality, we consider the capacity-achieving Gaussian
signaling, such that $\boldsymbol{x}(l)$’s are assumed to be circularly
symmetric complex Gaussian (CSCG) random vectors with zero mean and covariance
matrix
$\boldsymbol{S}=\mathbb{E}\big{[}\boldsymbol{x}(l)\boldsymbol{x}(l)^{H}\big{]}\succeq\boldsymbol{0}$.
As $L$ is sufficiently large, the sample covariance matrix
$\frac{1}{L}\boldsymbol{X}\boldsymbol{X}^{H}$ is approximated as the
statistical covariance matrix $\boldsymbol{S}$, i.e.,
$\frac{1}{L}\boldsymbol{X}\boldsymbol{X}^{H}\approx\boldsymbol{S}$, which is
the optimization variable to be designed111This approximation has been widely
adopted in MIMO radar and MIMO ISAC systems [12, 6].. Suppose that the H-AP is
subject to a maximum transmit power budget $P$. We thus have
$\mathbb{E}\big{[}\|\boldsymbol{x}(l)\|^{2}\big{]}=\mathrm{tr}(\boldsymbol{S})\leq
P$.

First, we consider the radar sensing with a point target. Let $\alpha$ denote
the complex reflection coefficient, and $\theta$ denote the angle of
departure/arrival (AoD/AoA). The echo signal received by the H-AP receiver is

$\boldsymbol{Y}_{\text{S}}=\boldsymbol{H}_{\text{S}}\boldsymbol{X}+\boldsymbol{Z}_{\text{S}}=\alpha\boldsymbol{A}(\theta)\boldsymbol{X}+\boldsymbol{Z}_{\text{S}},$
(2)

where
$\boldsymbol{A}(\theta)\triangleq\boldsymbol{a}_{r}(\theta)\boldsymbol{a}_{t}^{T}(\theta)$,
with $\boldsymbol{a}_{r}(\theta)\in\mathbb{C}^{N_{\text{S}}\times 1}$ and
$\boldsymbol{a}_{t}(\theta)\in\mathbb{C}^{M\times 1}$ denoting the receive and
transmit array steering vectors, and
$\boldsymbol{Z}_{\text{S}}\in\mathbb{C}^{N_{\text{S}}\times L}$ denotes the
additive white Gaussian noise (AWGN) at the H-AP receiver that is a CSCG
random matrix with independent and identically distributed (i.i.d.) entries
each with zero mean and variance $\sigma_{\text{S}}^{2}$. By choosing the
center of the ULA antennas as the reference point and assuming half-wavelength
spacing between adjacent antennas, we have

$\displaystyle\boldsymbol{a}_{t}(\theta)$
$\displaystyle=\big{[}e^{-j\frac{M-1}{2}\pi\sin\theta},e^{-j\frac{M-3}{2}\pi\sin\theta},\dots,e^{j\frac{M-1}{2}\pi\sin\theta}\big{]}^{T},$
(3) $\displaystyle\boldsymbol{a}_{r}(\theta)$
$\displaystyle=\big{[}e^{-j\frac{N_{\text{S}}-1}{2}\pi\sin\theta},e^{-j\frac{N_{\text{S}}-3}{2}\pi\sin\theta},\dots,e^{j\frac{N_{\text{S}}-1}{2}\pi\sin\theta}\big{]}^{T}.$

The objective of sensing is to estimate $\theta$ and $\alpha$ as the unknown
parameters from the received echo signal $\boldsymbol{Y}_{\text{S}}$ in (2),
in which the transmitted signal $\boldsymbol{X}$ is known by the H-AP. In this
case, the CRB for estimating $\theta$ is adopted as the sensing performance
metric222As the target information contained in $\alpha$ is hard to extract,
in this paper we focus on the CRB for estimating $\theta$, similarly as in
prior works [12, 13]., which is given by [10]

$\mathrm{CRB}(\boldsymbol{S})=\frac{\sigma_{\text{S}}^{2}}{2|\alpha|^{2}L}\frac{\mathrm{tr}(\\!\boldsymbol{A}^{H}\\!\boldsymbol{A}\boldsymbol{S})}{\mathrm{tr}(\\!\boldsymbol{\dot{A}}^{H}\\!\boldsymbol{\dot{A}}\boldsymbol{S})\mathrm{tr}(\\!\boldsymbol{A}^{H}\\!\boldsymbol{A}\boldsymbol{S})-|\mathrm{tr}(\\!\boldsymbol{\dot{A}}^{H}\\!\boldsymbol{A}\boldsymbol{S})|^{2}},$
(4)

where we define $\boldsymbol{A}\triangleq\boldsymbol{A}(\theta)$ and
$\boldsymbol{\dot{A}}\triangleq\frac{\partial\boldsymbol{A}(\theta)}{\partial\theta}$.

Next, we consider the point-to-point MIMO communication from the H-AP to the
ID receiver. The received signal by the ID receiver at symbol $l$ is given by

$\boldsymbol{y}_{\text{ID}}(l)=\boldsymbol{H}_{\text{ID}}\boldsymbol{x}(l)+\boldsymbol{z}_{\text{ID}}(l),$
(5)

where $\boldsymbol{z}_{\text{ID}}(l)\in\mathbb{C}^{N_{\text{ID}}\times 1}$
denotes the AWGN at the ID receiver that is a CSCG random vector with zero
mean and covariance matrix
$\sigma_{\text{ID}}^{2}\boldsymbol{I}_{N_{\text{ID}}}$. With the capacity-
achieving Gaussian signaling, the achievable data rate (in bps/Hz) is [11]

${R}(\boldsymbol{S})=\log_{2}\det\Big{(}\boldsymbol{I}_{N_{\text{ID}}}+\frac{1}{\sigma_{\text{ID}}^{2}}\boldsymbol{H}_{\text{ID}}\boldsymbol{S}\boldsymbol{H}_{\text{ID}}^{H}\Big{)}.$
(6)

Then, we consider the WPT from the H-AP to the EH receiver, where the EH
receiver uses the rectifiers to convert the received radio frequency (RF)
signals into direct current (DC) signals for energy harvesting. In general,
the harvested DC power is monotonically increasing with respect to the
received RF power. As a result, we use the received RF power (energy over a
unit time period, in Watt) at the EH receiver as the powering performance
metric [1], i.e.,

${E}(\boldsymbol{S})=\mathrm{tr}(\boldsymbol{H}_{\text{EH}}\boldsymbol{S}\boldsymbol{H}_{\text{EH}}^{H}).$
(7)

Our objective is to reveal the fundamental performance tradeoff among the
estimation CRB $\mathrm{CRB}(\boldsymbol{S})$ in (4), the achievable rate
${R}(\boldsymbol{S})$ in (6), and the received (unit-time) energy
${E}(\boldsymbol{S})$ in (7). Towards this end, we characterize the C-R-E
region that is defined as all the C-R-E pairs simultaneously achievable in the
multi-functional wireless MIMO system, i.e.,

$\displaystyle\mathcal{C}\triangleq\big{\\{}(\widehat{\mathrm{CRB}},\widehat{{R}},\widehat{{E}})|$
$\displaystyle\widehat{\mathrm{CRB}}\geq\mathrm{CRB}(\boldsymbol{S}),\widehat{{R}}\leq{R}(\boldsymbol{S}),$
(8)
$\displaystyle\widehat{{E}}\leq{E}(\boldsymbol{S}),\mathrm{tr}(\boldsymbol{S})\leq
P,\boldsymbol{S}\succeq\boldsymbol{0}\big{\\}}.$

##  III C-R-E Region Characterization

This section characterizes the C-R-E region of the multi-functional MIMO
system $\mathcal{C}$ in (8), by finding its Pareto boundary, which corresponds
to the set of points at which improving one performance metric will inevitably
result in the deterioration of another. The complete Pareto boundary
corresponds to a surface in a three-dimensional (3D) space as shown in Fig. 2,
which is surrounded by three vertices corresponding to rate maximization
(R-max), energy maximization (E-max), and CRB minimization (C-min),
respectively, as well as three edges corresponding to the optimal C-R, R-E,
and C-E tradeoffs, respectively.

Figure 2: The Pareto boundary of an example C-R-E region.

###  III-A Finding Three Vertices of Pareto Boundary

This subsection finds the three vertices of the C-R-E region $\mathcal{C}$.
First, we find the R-max vertex
$(\mathrm{CRB}_{\text{ID}},{R}_{\mathrm{max}},{E}_{\text{ID}})$ by optimizing
the transmit covariance $\boldsymbol{S}$ to maximize the communication rate
${R}(\boldsymbol{S})$, i.e.,
$\max_{\boldsymbol{S}\succeq\boldsymbol{0}}{R}(\boldsymbol{S}),\
\mathrm{s.t.}\ \mathrm{tr}(\boldsymbol{S})\leq P$. This corresponds to a sole
MIMO communication system. It has been established in [11] that the optimal
transmit covariance solution to this problem, denoted by
$\boldsymbol{S}_{\text{ID}}$, can be obtained by the EMT over the ID channel
(i.e., performing the singular value decomposition (SVD) to decompose
$\boldsymbol{H}_{\text{ID}}$) together with the water-filling power
allocation. Accordingly, the maximum communication rate is
${R}_{\mathrm{max}}={R}(\boldsymbol{S}_{\text{ID}})$, and the corresponding
harvested energy level and estimation CRB are
${E}_{\text{ID}}={E}(\boldsymbol{S}_{\text{ID}})$ and
$\mathrm{CRB}_{\text{ID}}=\mathrm{CRB}(\boldsymbol{S}_{\text{ID}})$,
respectively.

Next, we consider the E-max vertex
$(\mathrm{CRB}_{\text{EH}},{R}_{\text{EH}},{E}_{\mathrm{max}})$, which can be
found by optimizing $\boldsymbol{S}$ to maximize the harvested energy level
${E}(\boldsymbol{S})$, i.e.,
$\max_{\boldsymbol{S}\succeq\boldsymbol{0}}{E}(\boldsymbol{S}),\
\mathrm{s.t.}\ \mathrm{tr}(\boldsymbol{S})\leq P$. This corresponds to a sole
MIMO WPT system. It has been shown in [3] that the optimal solution is a rank-
one matrix that can be obtained based on the strongest eigenmode transmission,
denoted by
$\boldsymbol{S}_{\text{EH}}=\sqrt{P}\boldsymbol{v}_{\max}\boldsymbol{v}_{\max}^{H}$,
with $\boldsymbol{v}_{\max}$ being the dominant right singular vector of
$\boldsymbol{H}_{\mathrm{EH}}$. The maximum harvested energy level is hence
${E}_{\mathrm{max}}={E}(\boldsymbol{S}_{\text{EH}})$, and the corresponding
communication rate and estimation CRB are
${R}_{\text{EH}}={R}(\boldsymbol{S}_{\text{EH}})$ and
$\mathrm{CRB}_{\text{EH}}=\mathrm{CRB}(\boldsymbol{S}_{\text{EH}})$,
respectively.

Finally, we consider the C-min vertex
$(\mathrm{CRB}_{\mathrm{min}},{R}_{\text{S}},{E}_{\text{S}})$, which can be
found by optimizing $\boldsymbol{S}$ to minimize the estimation CRB
$\mathrm{CRB}(\boldsymbol{S})$, i.e.,
$\min_{\boldsymbol{S}\succeq\boldsymbol{0}}\mathrm{CRB}(\boldsymbol{S}),\
\mathrm{s.t.}\ \mathrm{tr}(\boldsymbol{S})\leq P$. This corresponds to a sole
MIMO radar sensing system. The optimal solution $\boldsymbol{S}_{\text{S}}$
has been derived in closed form in [9], where
$\boldsymbol{S}_{\text{S}}=\frac{P}{M}\boldsymbol{a}_{t}(\theta)^{\dagger}\boldsymbol{a}_{t}(\theta)^{T}$
holds if $N_{\text{S}}>M$. Thus, the minimum CRB is
$\mathrm{CRB}_{\mathrm{min}}=\mathrm{CRB}(\boldsymbol{S}_{\text{S}})$, and the
corresponding communication rate and harvested energy level are
${R}_{\text{S}}={R}(\boldsymbol{S}_{\text{S}})$ and
${E}_{\text{S}}={E}(\boldsymbol{S}_{\text{S}})$, respectively.

###  III-B Finding Three Edges of Pareto Boundary

This subsection finds the three edges on the Pareto boundary of the C-R-E
region $\mathcal{C}$. First, we find the C-R edge connecting the C-min vertex
$(\mathrm{CRB}_{\mathrm{min}},{R}_{\text{S}},{E}_{\text{S}})$ and the R-max
vertex $(\mathrm{CRB}_{\text{ID}},{R}_{\mathrm{max}},{E}_{\text{ID}})$, by
optimizing $\boldsymbol{S}$ to maximize the communication rate
${R}(\boldsymbol{S})$ subject to a maximum estimation CRB constraint, i.e.,
$\max_{\boldsymbol{S}\succeq\boldsymbol{0}}{R}(\boldsymbol{S}),\mathrm{s.t.}\mathrm{CRB}(\boldsymbol{S})\leq\mathrm{CRB}_{\text{C-R}},\mathrm{tr}(\boldsymbol{S})\leq
P$, where the CRB threshold $\mathrm{CRB}_{\text{C-R}}$ ranges from
$\mathrm{CRB}_{\mathrm{min}}$ to $\mathrm{CRB}_{\text{ID}}$ in order to get
different C-R tradeoff points on the edge. This corresponds to the CRB-
constrained rate maximization problem for the MIMO ISAC system without WPT,
for which the optimal solution has been derived in [6] in semi-closed-form,
denoted by $\boldsymbol{S}_{\text{C-R}}$.

Next, we find the R-E edge connecting the R-max vertex
$(\mathrm{CRB}_{\text{ID}},{R}_{\mathrm{max}},{E}_{\text{ID}})$ and the E-max
vertex $(\mathrm{CRB}_{\text{EH}},{R}_{\text{EH}},{E}_{\mathrm{max}})$.
Towards this end, we optimize $\boldsymbol{S}$ to maximize the communication
rate ${R}(\boldsymbol{S})$ subject to a minimum harvested energy constraint,
i.e.,
$\max_{\boldsymbol{S}\succeq\boldsymbol{0}}{R}(\boldsymbol{S}),\mathrm{s.t.}{E}(\boldsymbol{S})\geq{E}_{\text{R-E}},\mathrm{tr}(\boldsymbol{S})\leq
P$, where the energy threshold ${E}_{\text{R-E}}$ ranges from
${E}_{\text{ID}}$ to ${E}_{\mathrm{max}}$ in order to get different R-E
tradeoff points on the edge. This corresponds to the energy-constrained rate
maximization problem for the MIMO SWIPT system without radar sensing, whose
optimal transmit covariance solution has been obtained in [3] as
$\boldsymbol{S}_{\text{R-E}}$ in semi-closed-form.

Then, we find the C-E edge to connect the C-min vertex
$(\mathrm{CRB}_{\mathrm{min}},{R}_{\text{S}},{E}_{\text{S}})$ and the E-max
vertex $(\mathrm{CRB}_{\text{EH}},{R}_{\text{EH}},{E}_{\mathrm{max}})$. To
achieve this, we optimize $\boldsymbol{S}$ to maximize the harvested energy
level ${E}(\boldsymbol{S})$ subject to a maximum estimation CRB constraint,
i.e.,
$\max_{\boldsymbol{S}\succeq\boldsymbol{0}}{E}(\boldsymbol{S}),\mathrm{s.t.}\mathrm{CRB}(\boldsymbol{S})\leq\mathrm{CRB}_{\text{C-E}},\mathrm{tr}(\boldsymbol{S})\leq
P$, where the CRB threshold $\mathrm{CRB}_{\text{C-E}}$ ranges from
$\mathrm{CRB}_{\mathrm{min}}$ to $\mathrm{CRB}_{\text{EH}}$ in order to get
different C-E tradeoff points on the edge. This corresponds to the case when
there are only sensing and WPT in our integrated system. The optimization
problem can be reformulated into a convex form, as the CRB constraint
$\mathrm{CRB}(\boldsymbol{S})\leq\mathrm{CRB}_{\text{C-E}}$ is equivalent to
the convex semi-definite constraint
$\begin{bmatrix}\mathrm{tr}(\boldsymbol{\dot{A}}^{H}\boldsymbol{\dot{A}}\boldsymbol{S})-\frac{\sigma_{\text{S}}^{2}}{2|\alpha|^{2}L\mathrm{CRB}_{\text{C-E}}}&\mathrm{tr}(\boldsymbol{\dot{A}}^{H}\boldsymbol{A}\boldsymbol{S})^{\dagger}\\\
\mathrm{tr}(\boldsymbol{\dot{A}}^{H}\boldsymbol{A}\boldsymbol{S})&\mathrm{tr}(\boldsymbol{A}^{H}\boldsymbol{A}\boldsymbol{S})\end{bmatrix}\succeq\boldsymbol{0}$
based on the Schur complement [12]. Therefore, the optimal solution
$\boldsymbol{S}_{\text{C-E}}$ in this case can be found by standard convex
optimization techniques333Note that we can obtain a well-structured optimal
solution to this problem by the Lagrangian duality method. However, we omit
the derivation here as it will be similar to that for the more general problem
(P1) in Section IV..

###  III-C Characterizing Complete Pareto Boundary Surface

With the vertices and edges obtained, it remains to find the interior points
on the Pareto boundary surface to characterize the complete C-R-E region
$\mathcal{C}$. Towards this end, we optimize the transmit covariance
$\boldsymbol{S}$ to maximize the communication rate ${R}(\boldsymbol{S})$ in
(6), subject to a maximum estimation CRB constraint $\Gamma_{\text{S}}$ and a
minimum harvested energy constraint $\Gamma_{\text{EH}}$. Mathematically, the
CRB-and-energy-constrained rate maximization problem is formulated as

$\displaystyle(\text{P1}):\max_{\boldsymbol{S}\succeq\boldsymbol{0}}$
$\displaystyle\
\log_{2}\det\Big{(}\boldsymbol{I}_{N_{\text{ID}}}+\frac{1}{\sigma_{\text{ID}}^{2}}\boldsymbol{H}_{\text{ID}}\boldsymbol{S}\boldsymbol{H}_{\text{ID}}^{H}\Big{)}$
(9a) $\displaystyle\mathrm{s.t.}$ $\displaystyle\
\mathrm{tr}(\boldsymbol{H}_{\text{EH}}\boldsymbol{S}\boldsymbol{H}_{\text{EH}}^{H})\geq\Gamma_{\text{EH}}$
(9b) $\displaystyle\ \mathrm{CRB}(\boldsymbol{S})\leq\Gamma_{\text{S}}$ (9c)
$\displaystyle\ \mathrm{tr}(\boldsymbol{S})\leq P.$ (9d)

By exhausting $\Gamma_{\text{EH}}$ and $\Gamma_{\text{S}}$ enclosed by the
projection of the three edges on the C-E plane, we can obtain all the Pareto
boundary surface points. In particular, let
$R^{\star}(\Gamma_{\text{EH}},\Gamma_{\text{S}})$ denote the optimal value of
problem (P1) with given $\Gamma_{\text{EH}}$ and $\Gamma_{\text{S}}$. Then we
have one Pareto boundary point of the C-R-E region $\mathcal{C}$ as
$\big{(}\Gamma_{\text{S}},R^{\star}(\Gamma_{\text{EH}},\Gamma_{\text{S}}),\Gamma_{\text{EH}}\big{)}$.

##  IV Optimal Solution to Problem (P1)

In this section, we present the optimal solution to problem (P1). Notice that
(P1) is not convex due to the estimation CRB constraint in (9c). Fortunately,
based on the Schur complement, constraint (9c) is equivalent to

$\begin{bmatrix}\mathrm{tr}(\boldsymbol{\dot{A}}^{H}\boldsymbol{\dot{A}}\boldsymbol{S})-\frac{1}{\Gamma_{\text{S},1}}&\mathrm{tr}(\boldsymbol{\dot{A}}^{H}\boldsymbol{A}\boldsymbol{S})^{\dagger}\\\
\mathrm{tr}(\boldsymbol{\dot{A}}^{H}\boldsymbol{A}\boldsymbol{S})&\mathrm{tr}(\boldsymbol{A}^{H}\boldsymbol{A}\boldsymbol{S})\end{bmatrix}\succeq\boldsymbol{0},$
(10)

where
$\Gamma_{\text{S},1}\triangleq\frac{2|\alpha|^{2}L}{\sigma_{\text{S}}^{2}}\Gamma_{\text{S}}$.
Thus, by replacing constraint (9c) as that in (10), (P1) is reformulated in a
convex form, and can be optimally solved by using the Lagrangian duality
method.

Let $\lambda\geq 0$, $\nu\geq 0$, and
$\boldsymbol{Z}\triangleq\begin{bmatrix}z_{1}&z_{2}\\\
z_{2}^{\dagger}&z_{3}\end{bmatrix}\succeq\boldsymbol{0}$ denote the dual
variables associated with the constraints in (9b), (9d), and (10),
respectively. The Lagrangian of problem (P1) is

$\displaystyle\mathcal{L}(\boldsymbol{S},\lambda,\nu,\boldsymbol{Z})=$
$\displaystyle\log_{2}\det\Big{(}\boldsymbol{I}_{N_{\text{ID}}}+\frac{1}{\sigma_{\text{ID}}^{2}}\boldsymbol{H}_{\text{ID}}\boldsymbol{S}\boldsymbol{H}_{\text{ID}}^{H}\Big{)}$
(11) $\displaystyle-$
$\displaystyle\mathrm{tr}(\boldsymbol{D}\boldsymbol{S})-\lambda\Gamma_{\text{EH}}+\nu
P-\frac{z_{1}}{\Gamma_{\text{S},1}},$

where
$\boldsymbol{D}\triangleq\nu\boldsymbol{I}_{M}-\lambda\boldsymbol{H}_{\text{EH}}^{H}\boldsymbol{H}_{\text{EH}}-z_{1}\boldsymbol{\dot{A}}^{H}\boldsymbol{\dot{A}}-z_{2}\boldsymbol{\dot{A}}^{H}\boldsymbol{A}-z_{2}^{\dagger}\boldsymbol{A}^{H}\boldsymbol{\dot{A}}-z_{3}\boldsymbol{A}^{H}\boldsymbol{A}$.

Accordingly, the dual function of (P1) is defined as

$g(\lambda,\nu,\boldsymbol{Z})=\max_{\boldsymbol{S}\succeq\boldsymbol{0}}\
\mathcal{L}(\boldsymbol{S},\lambda,\nu,\boldsymbol{Z}).$ (12)

We have the following lemma, which can be verified similarly as in [6, Lemma
1].

###### Lemma 1

In order for the dual function $g(\lambda,\nu,\boldsymbol{Z})$ to be bounded
from above, it must hold that

$\boldsymbol{D}\succeq\boldsymbol{0}~{}{\text{and}}~{}\mathcal{R}(\boldsymbol{H}_{\text{ID}}^{H})\subseteq\mathcal{R}(\boldsymbol{D}).$
(13)

Based on Lemma 1, the dual problem of (P1) is defined as

$(\text{D}1):\min_{\lambda\geq 0,\nu\geq
0,\boldsymbol{Z}\succeq\boldsymbol{0}}\ g(\lambda,\nu,\boldsymbol{Z}),\
\mathrm{s.t.}\ \eqref{D1-constraint}.$ (14)

Since problem (P1) is reformulated in a convex form and satisfies Slater’s
condition, strong duality holds between (P1) and its dual problem (D1) [14].
Therefore, we can solve (P1) by equivalently solving (D1). In the following,
we first obtain the dual function $g(\lambda,\nu,\boldsymbol{Z})$ with given
dual variables, then search over $\lambda\geq 0$, $\nu\geq 0$, and
$\boldsymbol{Z}\succeq\boldsymbol{0}$ to minimize
$g(\lambda,\nu,\boldsymbol{Z})$.

###  IV-A Finding Dual Function $g(\lambda,\nu,\boldsymbol{Z})$

First, we find the dual function $g(\lambda,\nu,\boldsymbol{Z})$ under given
$\lambda\geq 0$, $\nu\geq 0$, and $\boldsymbol{Z}\succeq\boldsymbol{0}$
satisfying (13). By dropping the constant terms
$-\lambda\Gamma_{\text{EH}}+\nu P-\frac{z_{1}}{\Gamma_{\text{S},1}}$, problem
(12) is equivalent to

$\max_{\boldsymbol{S}\succeq\boldsymbol{0}}\
\log_{2}\det\Big{(}\boldsymbol{I}_{N_{\text{ID}}}+\frac{1}{\sigma_{\text{ID}}^{2}}\boldsymbol{H}_{\text{ID}}\boldsymbol{S}\boldsymbol{H}_{\text{ID}}^{H}\Big{)}-\mathrm{tr}(\boldsymbol{D}\boldsymbol{S}).$
(15)

Suppose that $\mathrm{rank}(\boldsymbol{D})=r_{\text{p}}$, the eigenvalue
decomposition (EVD) of $\boldsymbol{D}$ is expressed as

$\boldsymbol{D}=\begin{bmatrix}\boldsymbol{Q}^{\overline{\mathrm{null}}}\
\boldsymbol{Q}^{\mathrm{null}}\end{bmatrix}\begin{bmatrix}\boldsymbol{\Sigma}^{\overline{\mathrm{null}}}&\boldsymbol{0}\\\
\boldsymbol{0}&\boldsymbol{0}\end{bmatrix}\begin{bmatrix}{\boldsymbol{Q}^{\overline{\mathrm{null}}}}\
{\boldsymbol{Q}^{\mathrm{null}}}\end{bmatrix}^{H},$ (16)

where
$\boldsymbol{\Sigma}^{\overline{\mathrm{null}}}=\mathrm{diag}(\sigma_{\text{p},1},\dots,\sigma_{\text{p},r_{\text{p}}})$,
and ${\boldsymbol{Q}^{\overline{\mathrm{null}}}}\in\mathbb{C}^{M\times
r_{\text{p}}}$ and
${\boldsymbol{Q}^{\mathrm{null}}}\in\mathbb{C}^{M\times(M-r_{\text{p}})}$
denote the eigenvectors corresponding to the $r_{\text{p}}$ non-zero
eigenvalues $\sigma_{\text{p},1},\dots,\sigma_{\text{p},r_{\text{p}}}$, and
the remaining $M-r_{\text{p}}$ zero eigenvalues, respectively. Without loss of
generality, we express $\boldsymbol{S}$ as

$\boldsymbol{S}=\begin{bmatrix}\boldsymbol{Q}^{\overline{\mathrm{null}}}\
\boldsymbol{Q}^{\mathrm{null}}\end{bmatrix}\begin{bmatrix}\boldsymbol{S}_{11}&\boldsymbol{S}_{10}\\\
\boldsymbol{S}_{10}^{H}&\boldsymbol{S}_{00}\end{bmatrix}\begin{bmatrix}{\boldsymbol{Q}^{\overline{\mathrm{null}}}}\
{\boldsymbol{Q}^{\mathrm{null}}}\end{bmatrix}^{H},$ (17)

where $\boldsymbol{S}_{11}\in\mathbb{S}^{r_{\text{p}}}$,
$\boldsymbol{S}_{00}\in\mathbb{S}^{M-r_{\text{p}}}$, and
$\boldsymbol{S}_{10}\in\mathbb{C}^{r_{\text{p}}\times(M-r_{\text{p}})}$ are
variables to be optimized.

According to Lemma 1, we only need to deal with problem (15) for the case with
$\boldsymbol{H}_{\text{ID}}(\boldsymbol{Q}^{\overline{\mathrm{null}}}\boldsymbol{S}_{10}{\boldsymbol{Q}^{\mathrm{null}}}^{H}+\boldsymbol{Q}^{\mathrm{null}}\boldsymbol{S}_{10}^{H}{\boldsymbol{Q}^{\overline{\mathrm{null}}}}^{H}+\boldsymbol{Q}^{\mathrm{null}}\boldsymbol{S}_{00}{\boldsymbol{Q}^{\mathrm{null}}}^{H})\boldsymbol{H}_{\text{ID}}^{H}=\boldsymbol{0}$.
Therefore, (15) can be simplified as the optimization of $\boldsymbol{S}_{11}$
in the following.

$\displaystyle\max_{\boldsymbol{S}_{11}\succeq\boldsymbol{0}}$
$\displaystyle\log_{2}\det\Big{(}\boldsymbol{I}_{N_{\text{ID}}}+\frac{1}{\sigma_{\text{ID}}^{2}}\boldsymbol{H}_{\text{ID}}\boldsymbol{Q}^{\overline{\mathrm{null}}}\boldsymbol{S}_{11}{\boldsymbol{Q}^{\overline{\mathrm{null}}}}^{H}\boldsymbol{H}_{\text{ID}}^{H}\Big{)}$
(18)
$\displaystyle-\mathrm{tr}(\boldsymbol{\Sigma}^{\overline{\mathrm{null}}}\boldsymbol{S}_{11}).$

Suppose that
$\mathrm{rank}\big{(}\boldsymbol{H}_{\text{ID}}\boldsymbol{Q}^{\overline{\mathrm{null}}}(\boldsymbol{\Sigma}^{\overline{\mathrm{null}}})^{-\frac{1}{2}}\big{)}=\widetilde{r}_{\text{p}}$.
Then we have the SVD as
$\boldsymbol{H}_{\text{ID}}\boldsymbol{Q}^{\overline{\mathrm{null}}}(\boldsymbol{\Sigma}^{\overline{\mathrm{null}}})^{-\frac{1}{2}}=\boldsymbol{U}_{\text{p}}\boldsymbol{\Lambda}_{\text{p}}\boldsymbol{V}_{\text{p}}^{H}$,
where $\boldsymbol{U}_{\text{p}}\in\mathbb{C}^{N_{\text{ID}}\times
N_{\text{ID}}}$,
$\boldsymbol{\Lambda}_{\text{p}}^{H}\boldsymbol{\Lambda}_{\text{p}}=\mathrm{diag}(\lambda_{\text{p},1}^{2},\dots,\lambda_{\text{p},\widetilde{r}_{\text{p}}}^{2},0,\dots,0)$,
and $\boldsymbol{V}_{\text{p}}\in\mathbb{C}^{r_{\text{p}}\times
r_{\text{p}}}$. Substituting
$\boldsymbol{S}_{11}=(\boldsymbol{\Sigma}^{\overline{\mathrm{null}}})^{-\frac{1}{2}}\boldsymbol{V}_{\text{p}}\boldsymbol{\widetilde{S}}_{11}\boldsymbol{V}_{\text{p}}^{H}(\boldsymbol{\Sigma}^{\overline{\mathrm{null}}})^{-\frac{1}{2}}$,
(18) is re-expressed as

$\max_{\boldsymbol{\widetilde{S}}_{11}\succeq\boldsymbol{0}}\
\log_{2}\det\Big{(}\boldsymbol{I}_{r_{\text{p}}}+\frac{1}{\sigma_{\text{ID}}^{2}}\boldsymbol{\Lambda}_{\text{p}}^{H}\boldsymbol{\Lambda}_{\text{p}}\boldsymbol{\widetilde{S}}_{11}\Big{)}-\mathrm{tr}(\boldsymbol{\widetilde{S}}_{11}).$
(19)

As shown in [3], the optimal solution to problem (19) is given by
$\boldsymbol{\widetilde{S}}_{11}^{*}=\mathrm{diag}(\widetilde{p}_{1},\dots,\widetilde{p}_{\widetilde{r}_{\text{p}}},0,\dots,0)$,
where

$\widetilde{p}_{k}=(\frac{1}{\ln
2}-\frac{\sigma_{\text{ID}}^{2}}{\lambda_{\text{p},k}^{2}})^{+},\forall
k\in\\{1,\dots,\widetilde{r}_{\text{p}}\\}.$ (20)

As a result, the optimal solution to problem (15) is given by
$\boldsymbol{S}^{*}=\begin{bmatrix}\boldsymbol{Q}^{\overline{\mathrm{null}}}\
\boldsymbol{Q}^{\mathrm{null}}\end{bmatrix}\begin{bmatrix}\boldsymbol{S}_{11}^{*}&\boldsymbol{S}_{10}^{*}\\\
{\boldsymbol{S}_{10}^{*}}^{H}&\boldsymbol{S}_{00}^{*}\end{bmatrix}\begin{bmatrix}\boldsymbol{Q}^{\overline{\mathrm{null}}}\
\boldsymbol{Q}^{\mathrm{null}}\end{bmatrix}^{H}$, where

$\boldsymbol{S}_{11}^{*}=(\boldsymbol{\Sigma}^{\overline{\mathrm{null}}})^{-\frac{1}{2}}\boldsymbol{V}_{\text{p}}\boldsymbol{\widetilde{S}}_{11}^{*}\boldsymbol{V}_{\text{p}}^{H}(\boldsymbol{\Sigma}^{\overline{\mathrm{null}}})^{-\frac{1}{2}},$
(21)

and $\boldsymbol{S}_{10}^{*}$ and
$\boldsymbol{S}_{00}^{*}\succeq\boldsymbol{0}$ can be chosen arbitrarily such
that $\boldsymbol{S}^{*}\succeq\boldsymbol{0}$444Note that
$\boldsymbol{S}_{10}^{*}$ and $\boldsymbol{S}_{00}^{*}$ are non-unique here,
and as a result, we need an additional step to determine them for solving the
primal problem (P1) later. Here, we can simply choose
$\boldsymbol{S}_{10}^{*}=\boldsymbol{0}$ and
$\boldsymbol{S}_{00}^{*}=\boldsymbol{0}$ for obtaining the dual function
$g(\lambda,\nu,\boldsymbol{Z})$ only..

###  IV-B Solving Dual Problem (D1)

Next, we solve dual problem (D1), which is convex but not necessarily
differentiable. Therefore, we can solve (D1) by applying subgradient-based
methods such as the ellipsoid method [14]. First, for the objective function
$g(\lambda,\nu,\boldsymbol{Z})$, the subgradient at
$(\lambda,\nu,z_{1},z_{2},z_{3})$ is
$\big{[}\mathrm{tr}(\boldsymbol{H}_{\text{EH}}^{H}\boldsymbol{H}_{\text{EH}}\boldsymbol{S}^{*})-\Gamma_{\text{EH}},P-\mathrm{tr}(\boldsymbol{S}^{*}),\mathrm{tr}(\boldsymbol{\dot{A}}^{H}\boldsymbol{\dot{A}}\boldsymbol{S}^{*})-\frac{1}{\Gamma_{\text{S},1}},\mathrm{tr}(\boldsymbol{\dot{A}}^{H}\boldsymbol{A}\boldsymbol{S}^{*}+\boldsymbol{A}^{H}\boldsymbol{\dot{A}}\boldsymbol{S}^{*})+j\mathrm{tr}(\boldsymbol{\dot{A}}^{H}\boldsymbol{A}\boldsymbol{S}^{*}-\boldsymbol{A}^{H}\boldsymbol{\dot{A}}\boldsymbol{S}^{*}),\mathrm{tr}(\boldsymbol{A}^{H}\boldsymbol{A}\boldsymbol{S}^{*})\big{]}^{T}$.
Then, let $\boldsymbol{q}_{1}$ denote the eigenvector corresponding to the
minimum eigenvalue of $\boldsymbol{D}$. Since constraint
$\boldsymbol{D}\succeq\boldsymbol{0}$ is equivalent to
$\boldsymbol{q}_{1}^{H}\boldsymbol{D}\boldsymbol{q}_{1}\geq 0$, the
subgradient of constraint $\boldsymbol{D}\succeq\boldsymbol{0}$ at
$(\lambda,\nu,z_{1},z_{2},z_{3})$ is
$\big{[}\boldsymbol{q}_{1}^{H}\boldsymbol{H}_{\text{EH}}^{H}\boldsymbol{H}_{\text{EH}}\boldsymbol{q}_{1},-1,\boldsymbol{q}_{1}^{H}\boldsymbol{\dot{A}}^{H}\boldsymbol{\dot{A}}\boldsymbol{q}_{1},\boldsymbol{q}_{1}^{H}(\boldsymbol{\dot{A}}^{H}\boldsymbol{A}+\boldsymbol{A}^{H}\boldsymbol{\dot{A}})\boldsymbol{q}_{1}+j\boldsymbol{q}_{1}^{H}(\boldsymbol{\dot{A}}^{H}\boldsymbol{A}-\boldsymbol{A}^{H}\boldsymbol{\dot{A}})\boldsymbol{q}_{1},\boldsymbol{q}_{1}^{H}\boldsymbol{A}^{H}\boldsymbol{A}\boldsymbol{q}_{1}\big{]}^{T}$.
Furthermore, let $\boldsymbol{q}_{2}=[q_{2,1},q_{2,2}]^{T}$ denote the
eigenvector corresponding to the minimum eigenvalue of $\boldsymbol{Z}$. The
subgradient of constraint $\boldsymbol{Z}\succeq\boldsymbol{0}$ at
$(\lambda,\nu,z_{1},z_{2},z_{3})$ is
$\big{[}0,0,-|q_{2,1}|^{2},-(q_{2,1}^{\dagger}q_{2,2}+q_{2,2}^{\dagger}q_{2,1})-j(q_{2,1}^{\dagger}q_{2,2}-q_{2,2}^{\dagger}q_{2,1}),-|q_{2,2}|^{2}\big{]}^{T}$.
With these derived subgradients, the ellipsoid method can be implemented
efficiently, based on which we can obtain the optimal dual solution to (D1) as
$\lambda^{*}$, $\nu^{*}$, and $\boldsymbol{Z}^{*}$.

###  IV-C Optimal Solution to Primal Problem (P1)

Now, we present the optimal solution to primal problem (P1). With optimal dual
variables $\lambda^{*}$, $\nu^{*}$, and $\boldsymbol{Z}^{*}$ at hand, the
corresponding unique optimal solution $\boldsymbol{S}_{11}^{*}$ to problem
(15) can be directly used for constructing the optimal primal solution to
(P1), denoted by $\boldsymbol{S}_{11}^{\mathrm{opt}}$. However, as indicated
in Section IV-A, the optimal solutions of $\boldsymbol{S}_{10}^{*}$ and
$\boldsymbol{S}_{00}^{*}$ to (15) are not unique. As a result, with given
$\boldsymbol{S}_{11}^{\mathrm{opt}}$, we need to find the optimal solutions of
$\boldsymbol{S}_{10}$ and $\boldsymbol{S}_{00}$, denoted by
$\boldsymbol{S}_{10}^{\mathrm{opt}}$ and $\boldsymbol{S}_{00}^{\mathrm{opt}}$,
by solving one additional feasibility problem. We have the following
proposition.

###### Proposition 1

The optimal solution to problem (P1) is

$\boldsymbol{S}^{\mathrm{opt}}=\begin{bmatrix}\boldsymbol{Q}^{\overline{\mathrm{null}}}\
\boldsymbol{Q}^{\mathrm{null}}\end{bmatrix}\begin{bmatrix}\boldsymbol{S}_{11}^{\mathrm{opt}}&\boldsymbol{S}_{10}^{\mathrm{opt}}\\\
{\boldsymbol{S}_{10}^{\mathrm{opt}}}^{H}&\boldsymbol{S}_{00}^{\mathrm{opt}}\end{bmatrix}\begin{bmatrix}\boldsymbol{Q}^{\overline{\mathrm{null}}}\
\boldsymbol{Q}^{\mathrm{null}}\end{bmatrix}^{H},$ (22)

where $\boldsymbol{S}_{11}^{\mathrm{opt}}$ is given by (21) based on
$\lambda^{*}$, $\nu^{*}$, and $\boldsymbol{Z}^{*}$, and
$\boldsymbol{S}_{10}^{\mathrm{opt}}$ and $\boldsymbol{S}_{00}^{\mathrm{opt}}$
are obtained by solving the following feasibility problem.

$\displaystyle\mathrm{find}$ $\displaystyle\ \boldsymbol{S}_{10}\ \text{and}\
\boldsymbol{S}_{00}$ (23) $\displaystyle\mathrm{s.t.}$ $\displaystyle\
\eqref{Ra},\ \eqref{Rc},\ \eqref{Rb-reformulation},\ \text{and}\ \eqref{S_p}.$

###### Remark 1

We have the following interesting observations from Proposition 1. First, the
optimal transmit covariance solution $\boldsymbol{S}^{\mathrm{opt}}$ follows
the EMT structure based on the composite channel $\boldsymbol{D}$ consisting
of ID, EH, and sensing channels (see (16)), together with the water-filling-
like power allocation (see (20)). Next, it is observed that
$\boldsymbol{S}^{\mathrm{opt}}$ is divided into two parts, i.e.,
$\boldsymbol{S}_{11}^{\mathrm{opt}}$ for the triple roles of communication,
sensing, and powering; and $\boldsymbol{S}_{10}^{\mathrm{opt}}$ and
$\boldsymbol{S}_{00}^{\mathrm{opt}}$ for sensing and powering only. Notice
that based on extensive simulations, for the cases with randomly generated
channels, we have $\boldsymbol{D}\succ\boldsymbol{0}$ and
$\boldsymbol{S}^{\mathrm{opt}}=\boldsymbol{Q}^{\overline{\mathrm{null}}}\boldsymbol{S}_{11}^{\mathrm{opt}}{\boldsymbol{Q}^{\overline{\mathrm{null}}}}^{H}$,
i.e., only $\boldsymbol{S}_{11}^{\mathrm{opt}}$ is needed; by contrast, in
some special cases (e.g., $\boldsymbol{H}_{\text{ID}}$ and
$\boldsymbol{H}_{\text{EH}}$ being orthogonal to $\boldsymbol{A}$), it could
happen that $\boldsymbol{D}$ is rank-deficient, and
$\boldsymbol{S}_{10}^{\mathrm{opt}}$ and $\boldsymbol{S}_{00}^{\mathrm{opt}}$
are also needed.

##  V Numerical Results

This section evaluates the performance of our proposed optimal design. In the
simulation, the H-AP is equipped with a ULA of $M=10$ and $N_{\text{S}}=16$
antennas with half-wavelength spacing between consecutive antennas. The target
angle is $\theta=\frac{\pi}{3}$, and the reflection coefficient is set as
$\alpha=10^{-8}$, accounting for a round-trip path loss of $160$ dB. The ID
channel and the EH channel are set as
$\boldsymbol{H}_{\text{ID}}=\alpha_{\text{ID}}\widehat{\boldsymbol{H}}_{\text{ID}}$
and
$\boldsymbol{H}_{\text{EH}}=\alpha_{\text{EH}}\widehat{\boldsymbol{H}}_{\text{EH}}$,
where $\alpha_{\text{ID}}^{2}$ and $\alpha_{\text{EH}}^{2}$ correspond to the
path loss of $120$ dB and $60$ dB, respectively, and
$\widehat{\boldsymbol{H}}_{\text{ID}}$ and
$\widehat{\boldsymbol{H}}_{\text{EH}}$ correspond to the normalized channel
accounting for the small-scale fading. The transmission frame length is set as
$L=256$. The noise powers at the sensing receiver and the ID receiver, i.e.,
$\sigma_{\text{S}}^{2}$ and $\sigma_{\text{ID}}^{2}$, are set to be $-80$ dBm.

Figure 3: Pareto boundary for the C-R-E region with
$N_{\text{ID}}=N_{\text{EH}}=1$ and $P=50$ dBm.

Fig. 3 shows the Pareto boundary of the C-R-E region with
$N_{\text{ID}}=N_{\text{EH}}=1$ and $P=50$ dBm. In this figure, we consider
the line-of-sight (LoS) channels for the ID and EH channels, i.e.,
$\widehat{\boldsymbol{H}}_{\text{ID}}=\boldsymbol{a}_{t}^{T}(\theta_{\text{ID}})$
and
$\widehat{\boldsymbol{H}}_{\text{EH}}=\boldsymbol{a}_{t}^{T}(\theta_{\text{EH}})$.
Furthermore, we set $\theta=0$, $\sin\theta_{\text{ID}}=\frac{2\gamma}{M}$,
and $\sin\theta_{\text{EH}}=\frac{4\gamma}{M}$. We consider three cases with
$\gamma=0$, $0.4$, and $1$, which correspond to the cases when the sensing,
ID, and EH channels are identical, correlated, and orthogonal, respectively.
It is observed that when $\gamma=0$, the Pareto boundary is a point, which
means that the R-max, E-max, and C-min strategies are identical, and thus the
three performance metrics are optimized at the same time. In is also observed
that when $\gamma=1$, optimizing one metric (e.g., E-max) leads to poor
performances for the other two metrics (e.g., zero rate and highest CRB), thus
showing that the three objectives are competing. Furthermore, when
$\gamma=0.4$, the C-R-E region boundary is observed to lie between those with
$\gamma=1$ and $\gamma=0$, thus showing the C-R-E tradeoff when the channels
are correlated.

Next, we evaluate the performance of our proposed design as compared to the
benchmark scheme based on time switching. In this scheme, the transmission
duration is divided into three portions, $t_{\text{ID}}\geq 0$,
$t_{\text{EH}}\geq 0$, and $t_{\text{S}}\geq 0$, with
$t_{\text{ID}}+t_{\text{EH}}+t_{\text{S}}=1$, during which the H-AP employs
the transmit covariance matrices $\boldsymbol{S}_{\text{ID}}$,
$\boldsymbol{S}_{\text{EH}}$, and $\boldsymbol{S}_{\text{S}}$, respectively.
The corresponding communication rate, harvested energy, and estimation CRB in
this scheme are expressed as
${R}_{\text{TS}}(t_{\text{ID}},t_{\text{EH}},t_{\text{S}})=t_{\text{ID}}{R}(\boldsymbol{S}_{\text{ID}})$,
${E}_{\text{TS}}(t_{\text{ID}},t_{\text{EH}},t_{\text{S}})=t_{\text{ID}}{E}(\boldsymbol{S}_{\text{ID}})+t_{\text{EH}}{E}(\boldsymbol{S}_{\text{EH}})+t_{\text{S}}{E}(\boldsymbol{S}_{\text{S}})$,
and
$\mathrm{CRB}_{\text{TS}}(t_{\text{ID}},t_{\text{EH}},t_{\text{S}})=\mathrm{CRB}(t_{\text{ID}}\boldsymbol{S}_{\text{ID}}+t_{\text{EH}}\boldsymbol{S}_{\text{EH}}+t_{\text{S}}\boldsymbol{S}_{\text{S}})$,
respectively. Then, we optimize $t_{\text{ID}}$, $t_{\text{EH}}$, and
$t_{\text{S}}$ to achieve different C-R-E tradeoffs.

Figure 4: The communication rate ${R}$ versus the CRB constraint
$\Gamma_{\text{S}}$ with $N_{\text{ID}}=N_{\text{EH}}=4$ and $P=40$ dBm.

Fig. 4 shows the obtained communication rate ${R}$ by (P1) versus the
estimation CRB constraint $\Gamma_{\text{S}}$, in which two EH constraints
$\Gamma_{\text{EH}}=0.5{E}_{\mathrm{max}}$ (high $\Gamma_{\text{EH}}$ case)
and $\Gamma_{\text{EH}}=0.05{E}_{\mathrm{max}}$ (low $\Gamma_{\text{EH}}$
case) are considered. Here, we set $N_{\text{ID}}=N_{\text{EH}}=4$ and $P=40$
dBm, and generate $\widehat{\boldsymbol{H}}_{\text{ID}}$ and
$\widehat{\boldsymbol{H}}_{\text{EH}}$ as CSCG random matrices with each
element being zero mean and unit variance. It is observed that under each EH
constraint, our proposed optimal design outperforms the time switching scheme.
For the case when $\Gamma_{\text{EH}}$ is high, the performance gap is
observed to be significant over the whole regime of $\Gamma_{\text{S}}$. By
contrast, for the case when $\Gamma_{\text{EH}}$ is low, the time switching
scheme is observed to perform close to the optimal design when
$\Gamma_{\text{S}}$ becomes large. This is due to the fact that both schemes
can achieve the R-max vertex with the maximum communication rate in this case.

##  VI Conclusion

This paper studied the fundamental C-R-E tradeoff performance limits for a new
multi-functional MIMO system integrating triple functions of sensing,
communication, and powering. We characterized the Pareto boundary of the so-
called C-R-E region, by optimally solving a new MIMO communication rate
maximization problem subject to both energy harvesting and estimation CRB
constraints. It was shown that the resultant C-R-E tradeoff highly depends on
the correlations of the ID, EH, and sensing channels, and the proposed optimal
design significantly outperforms the benchmark scheme based on time switching.

## References

  * [1] B. Clerckx, R. Zhang, R. Schober, D. W. K. Ng, D. I. Kim, and H. V. Poor, “Fundamentals of wireless information and power transfer: From RF energy harvester models to signal and system designs,” _IEEE J. Sel. Areas Commun._ , vol. 37, no. 1, pp. 4–33, Jan. 2019.
  * [2] F. Liu, Y. Cui, C. Masouros, J. Xu, T. X. Han, Y. C. Eldar, and S. Buzzi, “Integrated sensing and communications: Toward dual-functional wireless networks for 6G and beyond,” _IEEE J. Sel. Areas Commun._ , vol. 40, no. 6, pp. 1728–1767, Jun. 2022.
  * [3] R. Zhang and C. K. Ho, “MIMO broadcasting for simultaneous wireless information and power transfer,” _IEEE Trans. Wireless Commun._ , vol. 12, no. 5, pp. 1989–2001, May 2013.
  * [4] J. Xu, L. Liu, and R. Zhang, “Multiuser MISO beamforming for simultaneous wireless information and power transfer,” _IEEE Trans. Signal Process._ , vol. 62, no. 18, pp. 4798–4810, Sep. 2014.
  * [5] Y. Xiong, F. Liu, Y. Cui, W. Yuan, and T. X. Han, “Flowing the information from Shannon to Fisher: Towards the fundamental tradeoff in ISAC,” _arXiv preprint arXiv:2204.06938_ , 2022.
  * [6] H. Hua, T. X. Han, and J. Xu, “MIMO integrated sensing and communication: CRB-rate tradeoff,” _arXiv preprint arXiv:2209.12721_ , 2022.
  * [7] X. Liu, T. Huang, N. Shlezinger, Y. Liu, J. Zhou, and Y. C. Eldar, “Joint transmit beamforming for multiuser MIMO communications and MIMO radar,” _IEEE Trans. Signal Process._ , vol. 68, pp. 3929–3944, Jun. 2020.
  * [8] H. Hua, J. Xu, and T. X. Han, “Optimal transmit beamforming for integrated sensing and communication,” _arXiv preprint arXiv:2104.11871_ , 2021.
  * [9] J. Li, L. Xu, P. Stoica, K. W. Forsythe, and D. W. Bliss, “Range compression and waveform optimization for MIMO radar: A Cramér-Rao bound based study,” _IEEE Trans. Signal Process._ , vol. 56, no. 1, pp. 218–232, Jan. 2008.
  * [10] I. Bekkerman and J. Tabrikian, “Target detection and localization using MIMO radars and sonars,” _IEEE Trans. Signal Process._ , vol. 54, no. 10, pp. 3873–3883, Oct. 2006.
  * [11] E. Telatar, “Capacity of multi-antenna Gaussian channels,” _Eur. Trans. Telecommun._ , vol. 10, no. 6, pp. 585–595, Nov. 1999.
  * [12] F. Liu, Y.-F. Liu, A. Li, C. Masouros, and Y. C. Eldar, “Cramér-Rao bound optimization for joint radar-communication beamforming,” _IEEE Trans. Signal Process._ , vol. 70, pp. 240–253, Dec. 2021.
  * [13] X. Song, J. Xu, F. Liu, T. X. Han, and Y. C. Eldar, “Intelligent reflecting surface enabled sensing: Cramér-Rao bound optimization,” _arXiv preprint arXiv:2207.05611_ , 2022.
  * [14] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, 2004.


# Affinity-based Attention in Self-supervised Transformers Predicts Dynamics
of Object Grouping in Humans

Hossein Adeli1,2∗, Seoyoung Ahn2, Nikolaus Kriegeskorte1, Gregory J.
Zelinsky2,3

1Zuckerman Mind Brain Behavior Institute, Columbia University, New York, USA

2Department of Psychology, 3Department of Computer Science, Stony Brook
University, New York, USA

∗ corresponding author<EMAIL_ADDRESS>

###### Abstract

The spreading of attention has been proposed as a mechanism for how humans
group features to segment objects. However, such a mechanism has not yet been
implemented and tested in naturalistic images. Here, we leverage the feature
maps from self-supervised vision Transformers and propose a model of human
object-based attention spreading and segmentation. Attention spreads within an
object through the feature affinity signal between different patches of the
image. We also collected behavioral data on people grouping objects in natural
images by judging whether two dots are on the same object or on two different
objects. We found that our models of affinity spread that were built on
feature maps from the self-supervised Transformers showed significant
improvement over baseline and CNN based models on predicting reaction time
patterns of humans, despite not being trained on the task or with any other
object labels. Our work provides new benchmarks for evaluating models of
visual representation learning including Transformers.

##  1 Introduction

A fundamental problem that our visual system must solve is how to group parts
of the visual input together into coherent whole objects [Peters and
Kriegeskorte, 2021]. The role of attention in solving this problem has been
experimentally studied for decades [Treisman, 1996, Adeli et al., 2022]. A
proposed solution is that attention can bind object features through
activation spreading within an object using horizontal connectivity in
retinotopic visual areas [Roelfsema, 2023]. However, the modeling work in this
domain has focused on bottom-up, Gestalt cues, and clear object boundaries for
how attention can spread within an object to bind its features (e.g. the
"growth cone" model [Jeurissen et al., 2016]). A compelling model of primate
vision, however, should be able to handle natural images where object
boundaries are frequently ambiguous and bottom-up cues must be combined with
prior object-specific knowledge.

Building a model of object-based attention applicable to natural images
requires the modeling of connectivity between image regions that can guide the
spread of attention. In this work, we test the hypotheses that features from
recent vision Transformers can capture this connectivity and are therefore
well-suited to address the spreading of object-based attention. To that end,
we introduce a model of object-based attention built on self-supervised vision
Transformers. In this model, feature similarly, which we call affinity (Fig.
1) [Chen et al., 2022], guides the spread of attention in the visual input to
perform perceptual grouping, playing the role of long-range lateral
connections in linking distance points of the visual input in the retinotopic
maps of the ventral pathway [Gilbert and Li, 2013, Ramalingam et al., 2013].
We also designed and collected human data on a well-controlled behavioral
experiment to probe how people group complex objects in natural scenes. We
then test the models on two benchmarks based on this dataset. The first
benchmark evaluates the alignment between the affinity signals in the feature
maps and the ground truth object boundaries, measuring the extent to which the
learned representations are object-centric. The second benchmark evaluates the
models’ ability to predict human object-based perception and behavior,
measured by an object grouping task.

Figure 1: Example affinity maps for a few image patches from the grid,
generated using features from DINO.

##  2 Related works

#### Models of object-based attention and grouping in the brain:

The human visual system continuously captures objects in a scene by spatially
segregating their features from the background and dynamically grouping those
features. Formation of these objects rely on different grouping signals
ranging from part-whole matching and Gestalt processes to prior semantic
knowledge of object categories [Greff et al., 2020, Vecera, 2000, Wagemans et
al., 2012, Gilbert and Li, 2013]. Most modeling work, however, has been
focused on understanding how the former, more bottom-up cues can be
implemented in the retinatopic maps of the visual cortex. For example, the
models of "association fields" [Field et al., 1993] suggests the effective
connectivity between units depends on the similarity between the simple
represented features (e.g. orientation). Attention is believed to modulate the
effective connectivity between the units and therefore guide the grouping
process. Most modeling work in this domain has also focused on Gestalt cues
and clear object boundaries [Jeurissen et al., 2016]. These models therefore
cannot be applied to objects in natural context where objects become less
spatially separated or when contours lack definition.

#### Self-supervised Vision Transformers:

Application of Transformers to vision has been very successful, with these
models outperforming convolutional neural networks (CNNs) on object
recognition and other tasks [Dosovitskiy et al., 2020]. In Transformers, the
visual input is first divided into different patches that are then encoded as
feature vectors called tokens. At each layer of processing, a given token,
that represents a particular image patch, updates its value by interacting
with and mixing ("attending" to) the values of all other tokens that it finds
relevant. The selective nature of this mixing has motivated naming this
process "attention" in Transformers [Vaswani et al., 2017]. These attention
weights in supervised vision Transformers have been shown to perform some
perceptual grouping [Mehrani and Tsotsos, 2023]. More recently, studies have
explored training these models on self-supervised objectives yielding some
intriguing object-centric properties that are not as prominent in the models
trained for classification. When trained with self-distillation loss (DINO,
Caron et al. [2021] and DINOv2 Oquab et al. [2023]), the attention values
contain explicit information about the semantic segmentation of the foreground
objects and their parts, reflecting that these models can capture object-
centric representations without labels. In Masked auto-encoding (MAE, He et
al. [2022]), the input image is significantly occluded and the model is
trained to reconstruct the whole image from a small number of visible patches.
Minimizing the reconstruction loss enables the model to learn object-centric
feature that yield great performance on other downstream tasks.

#### Self-supervised Transformers for objects and part discovery:

There have been recent attempts to investigate the extent to which self-
supervised Transformers can learn high-level characteristics of a scene. These
studies involve computing feature similarity among all tokens and examining
their correspondence with high-level concepts such as objects and parts. LOST
[Siméoni et al., 2021] and Tokencut [Wang et al., 2022] use the similarity
graph to perform unsupervised object discovery showing success when there is
one salient object in the scene. Other work [Amir et al., 2021] have used the
feature similarity to perform co-segmentation of object parts. These results
collectively corroborate that vision Transformers trained with a self-
supervised objective begin to represent object-centric information, meaning
the patches that have the highest affinity to a given patch are likely to be
on the same object (Fig. 1).

##  3 Behavioral experiment

Figure 2: A) Behavioral procedure. Participants maintain fixation on the
center dot during the trial. B) Sample trial from all four conditions, each
coded by color. C) Placement of dots in all conditions and trials. D) Mean
reaction time for correct trials by condition, with SEM.

We use a "two-dot" paradigm (Fig. 2) to directly probe how humans group and
segment the regions of natural images into objects. In this paradigm, two dots
are placed on an image and participants are asked to indicate by button press
whether they are on the same object or two different objects (Fig. 2A). One of
these dots is always at the center location, and the other is at a peripheral
location. The reaction time (RT) of this button press is the primary measure
in this task, and reveals the difficulty of object grouping and the spread of
attention within an object. Previous works using this paradigm have been
limited in scale or have focused on simpler stimuli [Vecera, 2000, Kim et al.,
2019, Korjoukov et al., 2012]. For example, in Korjoukov et al. [2012] 24
images were hand selected to depict two instances of either a vehicle or an
animal. Our work significantly scales up this effort, and our dataset is
available at github.com/Hosseinadeli/affinity_attention.

###  3.1 Behavioral methods

#### Participants:

72 undergraduate students participated in our experiment for course credit.
Their mean age was 20.4 years (range = 17–32) and all had normal or corrected-
to-normal vision. This study was approved by the school Institutional Review
Board.

#### Stimuli and Apparatus:

We selected 288 images from the Microsoft COCO (Common Objects in Context)
dataset (2017 validation set), which has images of complex everyday scenes
depicting common objects in their natural context [Lin et al., 2014]. The
images also come with object-level segmentations, which we used to generate
four versions of each display (Fig. 2B): "same-close" (two dots on the same
object with a close distance), "same-far" (two dots on the same object with a
far distance), "different-close" (two dots on two different objects with a
close distance), and "different-far" (two dots on two different objects with a
far distance). We ensured that the distances are controlled between the two
same/different conditions, thus preventing the participants from making the
same/different decision based on distance. Fig. 2C shows the placement of the
dots across all four conditions. Each participant saw each image only in one
condition. The assignment of images to the four conditions was counterbalanced
across participants so that every 4 participants saw the full set of trials.
The experiment was conducted on a 19-inch flat-screen CRT ViewSonic SVGA
monitor with a screen resolution of 1024×768 pixels and a refresh rate of 100
Hz. Participants were seated approximately 70 cm away from the monitor, which
resulted in the screen subtending a visual angle of 30∘ ×22∘. This meant that
around 34 image pixels spanned approximately 1 degree of visual angle, making
the ’close’ peripheral dot in the experiment located around 3 degrees from the
fixation point (central dot) and ’far’ peripheral dot located 6 degrees from
the fixation point. Gaze position before the button response was recorded
using an EyeLink 1000 eye-tracking system (SR Research) with a sampling rate
of 1000 Hz. Gaze coordinates were parsed into fixations using the default
Eyelink algorithm, which employed a velocity threshold of 30 degrees per
second and an acceleration threshold of 8000 degrees per second squared.
Calibration drift was checked before every trial, and recalibration was
performed if necessary to ensure accurate eye-tracking data.

#### Procedure:

Participants were instructed to determine whether the two dots were on the
same object or two different objects. Each trial started with the presentation
of a fixation cross for 500 ms, indicating the location of the central dot.
Both the central and peripheral dots were then displayed for 1,000 ms without
the image. Next, the cues were superimposed on the image and flickered at a
frequency of 5 Hz to ensure their visibility. During the trial, participants
were required to maintain their gaze on the center dot for the entire
duration. If their gaze deviated more than 1 degree of visual angle away from
that location, the trial was terminated. 7 percent of the trials were removed
due to breaking fixation. To record their responses, participants utilized a
Microsoft gamepad controller, with buttons assigned to the "same" or
"different" condition. The assignment of the same button were randomized to
the right or left hand across participants to ensure the RT differences were
not due to the dominant hand bias. Each participant performed 32 practice
trials and 256 experimental trials. The experimental trials were divided into
four blocks, with breaks provided between the blocks. The order of image
presentation in each block was randomized across the trials. To provide
accuracy feedback, a sound was used to indicate an incorrect response to
participants. We removed one experimental image from our analyses based on the
ground truth response being ambiguous, leavening 255 experimental images and
1020 (255$\times$4) trials for behavioral analyses and model evaluations.

###  3.2 Behavioral results

Figure 3: A) Sample trials for the four conditions in our experiment. The
corresponding average reaction times from subjects is displayed on top.

The average subject accuracy on this task was 90 percent. We only show the
analyses for trials where the subject response was correct (however the
patterns were largely the same when considering both correct and incorrect
trials). Fig. 2D shows the RT data for each condition. Subjects were faster to
respond when the two dots were on the same object compared to when the
peripheral dot was on a different object. This effect is know as the same
object advantage [Egly et al., 1994], indicating that the first dot
facilitates the selection of the whole object. This effect interacted with dot
distance, where we observed the fastest RTs in the close-separation same-
object condition. This behavioral pattern is consistent with the hypothesis
that attention spreads from the center dot within the cued object, thereby
reaching the closer dot faster than the farther dot. If the peripheral dot is
on a different object, dot separation would not be expected to play a large
role on RTs [Roelfsema, 2023].

Fig. 3 shows four sample trials for each condition with comparable
difficulties. For this visualization, We first ordered the trials for each
condition by their RTs and then selected the 50th, 100th, 150th and 200th
trials, displayed from left to right, respectively, for each condition. Of
note, RTs increase with the distance between the dots when the dots are on the
same object. Comparing the cat figures (top row) illustrates this pattern for
dots on the same object. When the dots are on different objects, there is no
effect of dot separation on RTs, as can be seen by comparing the elephants.
While average and cross condition behavioral patterns are interesting, there
is also interesting variability within each condition. Task difficulty, and
RTs, increase when there are within object boundaries between the dots, when
the dots are on different object parts (with different textures), when the
dots are on the narrower parts of the object, when they are close to the
boundaries, or when there are multiple objects from the same category. Our
behavioral dataset is therefore rich in capturing the variable conditions
under which humans group objects in natural scenes. We will test models on how
well they can predict the mean RT of the subjects for each trial.

##  4 Modeling experiments

Table 1: All model run specifications run name |  training objective |  architecture |  model size |  patch size |  feature type
---|---|---|---|---|---
DINOv2_ViTb14 |  DINO v2 |  ViT |  base |  14 |  key, query, or value
DINOv2_ViTl14 |  DINO v2 |  ViT |  large |  14 |  key, query, or value
DINOv2_ViTg14 |  DINO v2 |  ViT |  giant |  14 |  key, query, or value
DINO_ViTb16 |  DINO |  ViT |  base |  16 |  key, query, or value
DINO_ViTb8 |  DINO |  ViT |  base |  8 |  key, query, or value
MAE_ViTb16 |  MAE |  ViT |  base |  16 |  key, query, or value
DINO_ResNet50 |  DINO |  ResNet50 |  |  |  conv
ImageNet_ResNet50 |  ImageNet |  ResNet50 |  |  |  conv

In our modeling experiments, we set out to evaluate a wide range of
representation learning models, as shown in Table 1. We considered both
Transformer and CNN based models. For the Transformer models we focused on the
ViT architecture [Dosovitskiy et al., 2020] with different number of
parameters (base, large, or giant) using different patch sizes (8, 14, or 16).
The models are trained with either the self-distillation method, DINO [Caron
et al., 2021] or the updated method, DINO version 2 [Oquab et al., 2023]. Also
included are models trained using masked autoencoding (MAE,[He et al., 2022]).
In Transformers, each token is represented with three vectors: key, query, and
value. The affinity between tokens can be calculated using any of these
feature representations (self-attention is the dot product of one token’s key
with another token’s query). For these models, we extract the patch features
from the last Transformer layer and calculate affinity by performing the dot
product of each token’s feature with all the other tokens. Sample affinity
maps for a few patches are shown in Fig. 1, generated using the key features
from the a model trained with DINO objective. Our code is available at
github.com/Hosseinadeli/affinity_attention.

We also included two CNN models in our comparison, both using the ResNet50
architecture [He et al., 2016]. One is pre-trained on ImageNet for object
classification and the other is trained using the DINO method. Convolutional
features are extracted from the third convolutional block of the model to have
feature dimensions comparable to a Transformer model with the path size of 16.
The feature tensors (with size h x w x d) are then divided into h x w feature
vectors of length d to represent different patches of the image. We then take
the dot product of each feature vector with all the others to calculate the
affinity map for each patch.

###  4.1 Quantifying the object-centric component of affinity

Figure 4: A) A sample experimental trial with the central and peripheral dots
shown on the top left. The affinity map for the peripheral dot is shown below
the trial image. The activity remaining on the affinity map after decreasing a
threshold in steps of 0.5 from 1 to 0. The True Positive Rate (TPR) and False
Positive Rate (FPR) are displayed above the activity map for each step. The
TPR increases significantly before the FPR increases, showing a strong object-
centric signal in this map. B) Affinity map from another trial, with the same
step-wise analysis of TPR and FPR as the threshold decreases. Compared to A),
the object-centric signal in this example is not as strong. C) The ROC curves
for all the model runs. The figure legend is ordered by the area under the
curve with model performance decreasing from top to bottom.

Affinity between two patches of an image is driven by feature similarity.
However, in order for the object-based attention to spread within an object,
the affinity has to have a strong object-centric component. We quantify this
by performing an ROC analyses of our experimental dataset. For each of the
1020 trials, we first extract the affinity map from the peripheral dot
location. A sample map is shown in Fig. 4A on the left, which used the key
features from the ViT based model (trained on DINO v2 with patch size 14;
DINOv2_ViTb14 in Table 1). This affinity map represents the strength of the
feature similarity between the patch at the peripheral dot location and all
the other patches in the image. We utilized different thresholds to evaluate
the spatial distribution of affinity signals at a specific strength and assess
their alignment with the ground truth object boundary. This analysis allowed
us to determine the extent to which the signals were concentrated within the
object or dispersed outside of it, providing insights into the object-centric
nature of the learned features. In the example shown in Fig. 4A, the threshold
is decreasing in steps of 0.05 from 1 to 0. True Positive Rate (TPR) is
calculated for each threshold as the size of the area that is active in the
object divided over the entire area of that object. False Positive Rate (FPR)
is calculated as the size of the area active outside of the object divided
over the entire area outside of that object. The figure shows that the TPR
increases as the threshold decreases, but that the FPR does not increase,
meaning the patches having the strongest affinity to the given peripheral
location are in the same object. This indicates a strong object-centric signal
in this affinity map. Only after the TPR reaches a high level of >0.96, does
the FPR start to increase with a decreasing threshold. Figure 4B illustrates
an example trial from the same model where the object-centric signal is not
strong in the affinity map. In this case, FPR increases significantly before
the TPR reaches a high level.

Averaging the TPR and FPR across all the trials, we can then get a gist of how
object-centric the affinity is for a given model. Fig. 4C shows ROC curves for
all the model runs in Table 1. We calculate the area under the ROC curves
(AUC) as the performance measure. The figure legend is ordered from top to
bottom based on decreasing AUC. For the Transformer models we report the best
results among the key, query, and value features. We generally observed
similar performance from the affinity maps built using the key and query
features, and that they outperform the value features. This observation
generally agrees with prior work on using these features for unsupervised
object discovery [Siméoni et al., 2021, Wang et al., 2022]. Results reveal
that DINO v2 clearly improves upon the earlier DINO model. The MAE based
affinity maps perform strongly, outperforming original DINO model but not the
v2. Interestingly, the CNN-based models perform poorly on this task regardless
of the training objective. The results corroborate earlier findings suggesting
that self-supervised learning methods, paired with a Transformer architecture,
learn more object-based features.

###  4.2 Affinity spread

Figure 5: A) 20 steps of attention spread for two trials (top vs bottom two
rows), each starting from the center dot. B) Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the close
(top) and far (bottom) conditions for both trials. C) Examples of attention
spreading in objects.

We designed a simple algorithm to spread attention through an object using the
affinity signal (that is normalized to have all values between 0 and 1). The
model, like the subjects, starts every trial from the patch at the center dot
location. From this starting location, the model then selects all the tokens
with strong affinity above the starting threshold (tau), causing attention to
spread to a bigger segment around the center dot (Fig. 5A top-left). At each
new step, the model identifies the patches in the image that have a strong
affinity with the already attended segment by taking an average of the
affinity maps for all the tokens over this growing segment. We put a
constraint on this process to have the segment grow as one contiguous region
but only allowing the newly added patches to be connected to the current
segment. Fig. 5A shows the iterative spread of attention in two sample objects
over 20 steps (generated from DINOv2_ViTb14_k features). As the segment grows,
the attention spread becomes more conservative due to the constraint placed on
the segment growth and that all the patches in the segment vote where to
spread next. To counter this conservative spread, the model gradually reduces
the threshold (tau_step) at each time step, thereby allowing attention to
spread within the entire object before spreading outside of it. Tau and
tau_step are two hyperparameters in the algorithm that we explored for each
run.

The number of steps that it takes for attention to reach the peripheral dot is
the model’s prediction of the RT for that trial. Fig. 5B shows the attention
spread overlaid on the original images for the two trials. In both cases, the
model reaches the close peripheral dot (top) in fewer steps than the far
peripheral dot (bottom). Fig. 5C shows more examples of trials where attention
reaches the dot in the object. We find that, while the individual affinity
maps could be noisy and scattered, the act of spreading object-based attention
from a point inside the object that relies on averages of many affinity maps
can yield object-centric incremental segments.

Figure 6: A) Histogram of the number of trials where the attention spread
reaches the peripheral dot for each condition, with number of steps on the
x-axis. B) Mean number of model steps for attention to reach the peripheral
dot in the close (light bars) and far (dark bars) conditions for both same and
different trials, with SEMs. C) Correlation between different model
predictions and average subject RT. The gray line shows the subject-subject
agreement, serving as a rough upper bound on model performance.

Model predictions were similarly made for the "different" condition trials
where two dots are located on two different objects. Given that the threshold
is decreasing at each step, in some trials the attention spreads outside the
object and reaches the peripheral dot even when the dot is on a different
object. That step number will be the model prediction for the RT of the
participants on that trial. In other cases, attention never reaches the
peripheral dot when it is on a different object, in which case the model
prediction would be 21 (maximum number of steps + 1). We plot in Fig. 6A the
histogram of the number of trials where attention reaches the peripheral dot
as a function of number of steps (1 to 21) for the DINOv2_ViTb14 run with tau
and tau_step set at 0.8 and 0.2, respectively. The rightmost bar at bin 21 in
each condition indicates the number of trials where attention did not reach
the peripheral dot. Fig. 6B shows the average number of steps that the model
took for attention to reach the close and far peripheral dot for each
condition. The model predicts the same object advantage in the same condition,
evidenced by a smaller number of steps, compared to the different condition.
Also for the same condition, the model behavior shows the effect of distance
on the number of steps, similar to the effect of distance on RT that we
observed in humans. However, the model also showed an effect of distance in
the different condition trials, contrary to the pattern in human RT. This
Highlights a limitation in our approach to predicting RT in the different
condition that needs to be addressed in future work. Lastly, we observed that
the behavioral trends of the model shown in Fig. 6B largely stayed the same
for a range of tau and tau_step values, but that the average number of steps
that it took to reach the peripheral dot was higher with higher starting
thresholds and smaller steps.

Fig. 6C shows how affinity-spread based on features from different models can
predict the human behavior on the grouping task. The bars show the correlation
of each model prediction with the average reaction time of the subjects across
the 1020 trials. We also include a Euclidean model as a simple baseline that
predicts longer RT when there is a greater distance between the two dots. The
gray horizontal line labeled "Subject model" indicates the upper bound for
model prediction. In order to create this model, we split the 72 subjects’
data into two groups with 36 subject and correlated the average response of
the two groups. We then repeated the process 50 times with different splits
and then took the average of the correlation coefficients across the splits.

The results suggest that affinity spread models built using feature maps from
self-supervised Transformers better align with human grouping behavior when
compared to baseline models and models based on convolutional neural networks
(CNN), despite not being trained on the same/different task or with any other
object labels. We can observe that models exhibiting stronger object-centric
affinity signals tend to achieve superior performance in predicting human
behavior, a trend we expect to continue. Another notable observation is that
larger models do not necessarily perform better, with ViTg14 underperforming
the base and large ViT models. Given the still large gap between model and
human behavior on individual trials, this model comparison and dataset will be
a useful benchmark for future developments.

##  5 Discussion

In this work, we proposed a novel affinity-based model of object grouping and
demonstrate that self-supervised Transformers provide a plausible mechanism
for human grouping and object-based attention, thus extending the value of
these models beyond core object recognition [VanRullen and Thorpe, 2001]. Our
affinity spread method, building on self-supervised representation learning,
does not require a large number of labeled samples for training, making this a
more biologically plausible mechanism for how the primate visual system learns
to group features and perceive objects. Our work also provides a new
behavioral dataset and framework for evaluating models of representation
learning, including Transformers. This work further contributes to computer
vision by showing how object-based attention, a core element of human
cognition, can be integrated into an AI model.

## References

  * Adeli et al. [2022] H. Adeli, S. Ahn, and G. J. Zelinsky.  A brain-inspired object-based attention network for multi-object recognition and visual reasoning.  _bioRxiv_ , pages 2022–04, 2022.
  * Amir et al. [2021] S. Amir, Y. Gandelsman, S. Bagon, and T. Dekel.  Deep vit features as dense visual descriptors.  _arXiv preprint arXiv:2112.05814_ , 2021.
  * Caron et al. [2021] M. Caron, H. Touvron, I. Misra, H. Jégou, J. Mairal, P. Bojanowski, and A. Joulin.  Emerging properties in self-supervised vision transformers.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 9650–9660, 2021.
  * Chen et al. [2022] H. Chen, R. Venkatesh, Y. Friedman, J. Wu, J. B. Tenenbaum, D. L. Yamins, and D. M. Bear.  Unsupervised segmentation in real-world images via spelke object inference.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXIX_ , pages 719–735. Springer, 2022.
  * Dosovitskiy et al. [2020] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Egly et al. [1994] R. Egly, J. Driver, and R. D. Rafal.  Shifting visual attention between objects and locations: evidence from normal and parietal lesion subjects.  _Journal of Experimental Psychology: General_ , 123(2):161, 1994.
  * Field et al. [1993] D. J. Field, A. Hayes, and R. F. Hess.  Contour integration by the human visual system: evidence for a local “association field”.  _Vision research_ , 33(2):173–193, 1993.
  * Gilbert and Li [2013] C. D. Gilbert and W. Li.  Top-down influences on visual processing.  _Nature reviews neuroscience_ , 14(5):350–363, 2013.  ISSN 1471-003X.
  * Greff et al. [2020] K. Greff, S. van Steenkiste, and J. Schmidhuber.  On the binding problem in artificial neural networks.  _arXiv preprint arXiv:2012.05208_ , 2020.
  * He et al. [2016] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * He et al. [2022] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick.  Masked autoencoders are scalable vision learners.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 16000–16009, 2022.
  * Jeurissen et al. [2016] D. Jeurissen, M. W. Self, and P. R. Roelfsema.  Serial grouping of 2d-image regions with object-based attention in humans.  _Elife_ , 5:e14320, 2016.
  * Kim et al. [2019] J. Kim, D. Linsley, K. Thakkar, and T. Serre.  Disentangling neural mechanisms for perceptual grouping.  _arXiv preprint arXiv:1906.01558_ , 2019.
  * Korjoukov et al. [2012] I. Korjoukov, D. Jeurissen, N. A. Kloosterman, J. E. Verhoeven, H. S. Scholte, and P. R. Roelfsema.  The time course of perceptual grouping in natural scenes.  _Psychological Science_ , 23(12):1482–1489, 2012\.
  * Lin et al. [2014] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick.  Microsoft coco: Common objects in context.  In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_ , pages 740–755. Springer, 2014.
  * Mehrani and Tsotsos [2023] P. Mehrani and J. K. Tsotsos.  Self-attention in vision transformers performs perceptual grouping, not attention.  _arXiv preprint arXiv:2303.01542_ , 2023.
  * Oquab et al. [2023] M. Oquab, T. Darcet, T. Moutakanni, H. V. Vo, M. Szafraniec, V. Khalidov, P. Fernandez, D. Haziza, F. Massa, A. El-Nouby, R. Howes, P.-Y. Huang, H. Xu, V. Sharma, S.-W. Li, W. Galuba, M. Rabbat, M. Assran, N. Ballas, G. Synnaeve, I. Misra, H. Jegou, J. Mairal, P. Labatut, A. Joulin, and P. Bojanowski.  Dinov2: Learning robust visual features without supervision, 2023.
  * Peters and Kriegeskorte [2021] B. Peters and N. Kriegeskorte.  Capturing the objects of vision with neural networks.  _Nature Human Behaviour_ , pages 1–18, 2021.
  * Ramalingam et al. [2013] N. Ramalingam, J. N. McManus, W. Li, and C. D. Gilbert.  Top-down modulation of lateral interactions in visual cortex.  _Journal of Neuroscience_ , 33(5):1773–1789, 2013\.
  * Roelfsema [2023] P. R. Roelfsema.  Solving the binding problem: Assemblies form when neurons enhance their firing rate—they don’t need to oscillate or synchronize.  _Neuron_ , 111(7):1003–1019, 2023.
  * Siméoni et al. [2021] O. Siméoni, G. Puy, H. V. Vo, S. Roburin, S. Gidaris, A. Bursuc, P. Pérez, R. Marlet, and J. Ponce.  Localizing objects with self-supervised transformers and no labels.  _arXiv preprint arXiv:2109.14279_ , 2021.
  * Treisman [1996] A. Treisman.  The binding problem.  _Current opinion in neurobiology_ , 6(2):171–178, 1996.
  * VanRullen and Thorpe [2001] R. VanRullen and S. J. Thorpe.  The time course of visual processing: from early perception to decision-making.  _Journal of cognitive neuroscience_ , 13(4):454–461, 2001.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin.  Attention is all you need.  _arXiv preprint arXiv:1706.03762_ , 2017.
  * Vecera [2000] S. P. Vecera.  Toward a biased competition account of object-based segregation and attention.  _Brain and Mind_ , 1(3):353–384, 2000.
  * Wagemans et al. [2012] J. Wagemans, J. H. Elder, M. Kubovy, S. E. Palmer, M. A. Peterson, M. Singh, and R. von der Heydt.  A century of gestalt psychology in visual perception: I. perceptual grouping and figure–ground organization.  _Psychological bulletin_ , 138(6):1172, 2012.
  * Wang et al. [2022] Y. Wang, X. Shen, S. X. Hu, Y. Yuan, J. L. Crowley, and D. Vaufreydaz.  Self-supervised transformers for unsupervised object discovery using normalized cut.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14543–14553, 2022.

##  6 Supplementary results

In this section we provide the complete model comparison and more sample
trials from our affinity-spread model.

Table 2 provides the Area Under the Curve (AUC) for the ROC curves of all
model runs. In this table the performance is also broken down for each feature
type. Fig. 7 shows the ROC curves.

Table 3 provides the correlation coefficients between all model runs and the
human behavior. In this table, the performance is also broken down for each
feature type. Fig. 8 shows this information in a bar graph.

Fig. 9 shows the histograms of the predictions for the best performing model.

Fig. 10 through Fig. 29 show more example model outputs.

Table 2: AUCs for all model runs run name |  training objective |  architecture |  model size |  patch size |  feature type |  AUC
---|---|---|---|---|---|---
DINOv2_ViTb14 |  DINO v2 |  ViT |  base |  14 |  key |  0.870
|  |  |  |  |  query |  0.877
|  |  |  |  |  value |  0.770
DINOv2_ViTl14 |  DINO v2 |  ViT |  large |  14 |  key |  0.856
|  |  |  |  |  query |  0.854
|  |  |  |  |  value |  0.785
DINOv2_ViTg14 |  DINO v2 |  ViT |  giant |  14 |  key |  0.810
|  |  |  |  |  query |  0.840
|  |  |  |  |  value |  0.770
DINO_ViTb16 |  DINO |  ViT |  base |  16 |  key |  0.800
|  |  |  |  |  query |  0.800
|  |  |  |  |  value |  0.786
DINO_ViTb8 |  DINO |  ViT |  base |  8 |  key |  0.768
|  |  |  |  |  query |  0.785
|  |  |  |  |  value |  0.791
MAE_ViTb16 |  MAE |  ViT |  base |  16 |  key |  0.840
|  |  |  |  |  query |  0.850
|  |  |  |  |  value |  0.820
DINO_ResNet50 |  DINO |  ResNet50 |  |  |  conv |  0.618
ImageNet_ResNet50 |  ImageNet |  ResNet50 |  |  |  conv |  0.611
Figure 7:  The ROC curves for all the model runs. The figure legend is ordered by the area under the curve with model performance decreasing from top to bottom. Table 3: Human-model correlation for all model runs run name |  training objective |  architecture |  model size |  patch size |  feature type |  Spearman rank correlation
---|---|---|---|---|---|---
DINOv2_ViTb14 |  DINO v2 |  ViT |  base |  14 |  key |  0.238
|  |  |  |  |  query |  0.252
|  |  |  |  |  value |  0.213
DINOv2_ViTl14 |  DINO v2 |  ViT |  large |  14 |  key |  0.241
|  |  |  |  |  query |  0.231
|  |  |  |  |  value |  0.219
DINOv2_ViTg14 |  DINO v2 |  ViT |  giant |  14 |  key |  0.195
|  |  |  |  |  query |  0.206
|  |  |  |  |  value |  0.189
DINO_ViTb16 |  DINO |  ViT |  base |  16 |  key |  0.201
|  |  |  |  |  query |  0.215
|  |  |  |  |  value |  0.212
DINO_ViTb8 |  DINO |  ViT |  base |  8 |  key |  0.187
|  |  |  |  |  query |  0.229
|  |  |  |  |  value |  0.227
MAE_ViTb16 |  MAE |  ViT |  base |  16 |  key |  0.218
|  |  |  |  |  query |  0.234
|  |  |  |  |  value |  0.217
DINO_ResNet50 |  DINO |  ResNet50 |  |  |  conv |  0.116
ImageNet_ResNet50 |  ImageNet |  ResNet50 |  |  |  conv |  0.103
Figure 8: Correlation between different model predictions and average subject
RT. The gray line shows the subject-subject agreement, serving as a rough
upper bound on model performance. Figure 9:  Restuls for DINOv2_ViTb14_query
run. A) Histogram of the number of trials where the attention spread reaches
the peripheral dot for each condition, with number of steps on the x-axis. B)
Mean number of model steps for attention to reach the peripheral dot in the
close (light bars) and far (dark bars) conditions for both same and different
trials, with SEMs. Figure 10: 20 steps of attention spreading from the center
dot. Attention spread overlaid on the image for the steps that attention
reached the peripheral dot in the same - close, same - far, different - close
and different - far conditions shown at the bottom. Figure 11: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom. Figure 12: 20 steps of attention spreading from the center dot.
Attention spread overlaid on the image for the steps that attention reached
the peripheral dot in the same - close, same - far, different - close and
different - far conditions shown at the bottom. Figure 13: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom. Figure 14: 20 steps of attention spreading from the center dot.
Attention spread overlaid on the image for the steps that attention reached
the peripheral dot in the same - close, same - far, different - close and
different - far conditions shown at the bottom. Figure 15: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom. Figure 16: 20 steps of attention spreading from the center dot.
Attention spread overlaid on the image for the steps that attention reached
the peripheral dot in the same - close, same - far, different - close and
different - far conditions shown at the bottom. Figure 17: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom. Figure 18: 20 steps of attention spreading from the center dot.
Attention spread overlaid on the image for the steps that attention reached
the peripheral dot in the same - close, same - far, different - close and
different - far conditions shown at the bottom. Figure 19: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom. Figure 20: 20 steps of attention spreading from the center dot.
Attention spread overlaid on the image for the steps that attention reached
the peripheral dot in the same - close, same - far, different - close and
different - far conditions shown at the bottom. Figure 21: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom. Figure 22: 20 steps of attention spreading from the center dot.
Attention spread overlaid on the image for the steps that attention reached
the peripheral dot in the same - close, same - far, different - close and
different - far conditions shown at the bottom. Figure 23: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom. Figure 24: 20 steps of attention spreading from the center dot.
Attention spread overlaid on the image for the steps that attention reached
the peripheral dot in the same - close, same - far, different - close and
different - far conditions shown at the bottom. Figure 25: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom. Figure 26: 20 steps of attention spreading from the center dot.
Attention spread overlaid on the image for the steps that attention reached
the peripheral dot in the same - close, same - far, different - close and
different - far conditions shown at the bottom. Figure 27: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom. Figure 28: 20 steps of attention spreading from the center dot.
Attention spread overlaid on the image for the steps that attention reached
the peripheral dot in the same - close, same - far, different - close and
different - far conditions shown at the bottom. Figure 29: 20 steps of
attention spreading from the center dot. Attention spread overlaid on the
image for the steps that attention reached the peripheral dot in the same -
close, same - far, different - close and different - far conditions shown at
the bottom.


For $\operatorname{\mathbf{swap}}$ and $\operatorname{\mathbf{traverse}}$,
consider the loop nest for the stage of $f$. Analogously to the proof of lemma
7.3, syntactic separation ensures that distinct iterations of pure loops
access $f$ at disjoint sets of points. Since $\operatorname{\mathbf{split}}$
and $\operatorname{\mathbf{fuse}}$ preserve the sets and order of accesses as
they introduce new loops, two writes agree on their pure dimensions iff the
pure loop variable values agree.

But this means that two assignments touch the same memory of $f$ only if the
values of the pure loops are the same. Since
$\operatorname{\mathbf{traverse}}$ parallelizes over a single pure loop, no
two tasks touch the same memory. And $\operatorname{\mathbf{swap}}$
interchanges two pure loops, so the writes which do touch memory in common are
not interchanged with respect to one another. ∎

###### Lemma A.7 (Compute phase is sound).

Let $P\in\operatorname{\mathbf{Alg}}$ be a valid algorithm and let
$T_{i}\in\operatorname{\mathbf{Tgt}}^{?}$ be the result of lowering $P$ and
applying scheduling directives up through this phase. Let $s$ be a compute-at
directive moving the func $f$ to some location $\ell_{g}$. Then
$T_{i+1}=\mathcal{S}(s,T_{i})$ is confluent with $P$.

###### Proof of Lemma A.7.

Let $P_{i}^{\prime}\in\operatorname{\mathbf{BI}}(S_{i})$ and let
${\left\\{P_{i}^{\prime\prime}\right\\}}$ be the set of programs resulting
from applying $s$ to $P_{i}^{\prime}$. Let
$P_{i+1}^{\prime}\in\operatorname{\mathbf{BI}}(T_{i+1})$. First observe that
any $P_{i}^{\prime\prime}$ computes the same values as $P_{i}^{\prime}$
because the $\operatorname{\mathbf{compute}}$ statement for $f$ computes _all_
of the points ever needed in $P_{i}^{\prime\prime}$ and dominates all of its
consumer funcs. This also implies that
$P_{i}^{\prime\prime}\in\operatorname{\mathbf{BI}}(T_{i+1})$.

Now suppose $P_{i+1}^{\prime}$ is not one of the $P_{i}^{\prime\prime}$. Then
for each $z$, if $P(z)$ does not contain an error, then there is some
$P_{i}^{\prime\prime}\geq P_{i+1}^{\prime}$ (see definition A.2). By lemma
A.3, $P_{i+1}^{\prime}$ computes the exact same values of $f$ on the narrower
range, which bounds inference guarantees is sufficient for confluence. ∎

###### Lemma A.8 (Storage phase is sound).

Let $P\in\operatorname{\mathbf{Alg}}$ be a valid algorithm and let
$T_{i}\in\operatorname{\mathbf{Tgt}}^{?}$ be the result of lowering $P$ and
applying scheduling directives up through this phase. Let $s$ be a store-at
directive, then $T_{i+1}=\mathcal{S}(s,T_{i})$ is confluent with $P$.

###### Proof of Lemma A.8.

Lemma 7.2 required only dominance of the $\operatorname{\mathbf{allocate}}$
statement over all accesses to the associated func for correctness. This is
preserved by definition. ∎

###### Lemma A.9 (Bounds phase is sound).

Let $P\in\operatorname{\mathbf{Alg}}$ be a valid algorithm and let
$T_{i}\in\operatorname{\mathbf{Tgt}}^{?}$ be the result of lowering $P$ and
applying scheduling directives up through this phase. Let $s$ be a scheduling
directive in this phase, then $T_{i+1}=\mathcal{S}(s,T_{i})$ is confluent with
$P$.

###### Proof of Lemma A.9.

The directives in this phase only mutate programs by adding assertions to
them, the only side effect of which is to transition to an error state. Thus
in any non-erroring execution of any
$P_{i}\in\operatorname{\mathbf{BI}}(S_{i})$, there is some
$P_{i}\in\operatorname{\mathbf{BI}}(T_{i})$ whose behavior exactly matches
$P_{i+1}$. ∎