Feb. 28, 2023 Jul. 09, 2023

# Integrated Sensing and Communication for Network-Assisted Full-Duplex Cell-
Free Distributed Massive MIMO Systems

Fan Zeng 11 Jingxuan Yu 11 Jiamin Li 1122** Feiyang Liu 33 Dongming Wang 1122
Xiaohu You 1122<EMAIL_ADDRESS>National Mobile Communications Research
Laboratory, School of Information Science and Engineering, Southeast
University, Nanjing 210096, China  Purple Mountain Laboratories, Nanjing
211111, China  54th Research Institute of Electronics Technology Group
Corporation, Shijiazhuang 050081, China

###### Abstract

In this paper, we combine the network-assisted full-duplex (NAFD) technology
and distributed radar sensing to implement integrated sensing and
communication (ISAC). The ISAC system features both uplink and downlink remote
radio units (RRUs) equipped with communication and sensing capabilities. We
evaluate the communication and sensing performance of the system using the sum
communication rates and the Cramér-Rao lower bound (CRLB), respectively. We
compare the performance of the proposed scheme with other ISAC schemes, the
result shows that the proposed scheme can provide more stable sensing and
better communication performance. Furthermore, we propose two power allocation
algorithms to optimize the communication and sensing performance jointly. One
algorithm is based on the deep Q-network (DQN) and the other one is based on
the non-dominated sorting genetic algorithm II (NSGA-II). The proposed
algorithms provide more feasible solutions and achieve better system
performance than the equal power allocation algorithm.

###### keywords:

Integrated sensing and communication (ISAC); network-assisted full-duplex
(NAFD); superimposed pilot; Cramér-Rao lower bound (CRLB)

##  1 introduction

Integrated sensing and communication (ISAC)[1, 2, 3] has emerged as a
prominent and challenging research area in the 6G domain due to its
multidimensional technical implications and diverse application scenarios, in
which communication and radar sensing can effectively improve system spectrum
efficiency and hardware resource utilization through time-frequency-space
resource reuse and hardware device sharing. In this regard, extensive research
efforts have been conducted in the literature to improve sensing and
communication performance by proposing innovative designs, such as integrated
waveform design[4], joint transmit beamforming[5], and joint signal
reception[6].

While most of the previous works have focused on individual ISAC transceivers,
recently, there has been an increasing number of research on networked ISAC
receivers. In [7], a comprehensive overview of sensing mobile networks is
provided, proposing the use of multiple ISAC transceivers for distributed
radar sensing and coordinated wireless communication. In [8], a network-
integrated sensing and communication system is implemented using multiple ISAC
transceivers, where a distributed set of ISAC transmitters send individual
messages to their respective communication users while cooperating with
multiple sensing receivers to estimate the location of a target. [9] proposes
a protocol for communication and sensing, where a group of access points (APs)
is allocated by the network to participate in the uplink along with users
(UEs). From the perspective of joint communication and radar, a cell-free (CF)
massive MIMO network architecture is considered. In [10], a two-stage sensing
framework based on orthogonal frequency-division multiplexing (OFDM) cellular
cell architecture is proposed for locating passive targets that cannot send
reference signals received from base stations (BSs) to BSs.

Network ISAC offers several advantages over single-cell ISAC, including larger
monitoring areas, expanded sensing coverage, diverse sensing angles, and
richer sensing information. Furthermore, current research on communication
systems is also focused on multiple base stations, so this is in line with the
mainstream trend. Additionally, network ISAC can solve the full-duplex problem
by transceiver separation than simultaneous transmitting and receiving signal
echoes in single-cell ISAC [11, 12].

However, most of the previous research on network ISAC has primarily focused
on integrating sensing with traditional cellular communication systems, such
as [8] and [10]. However, both of these assume that the communication signals
between each cell are uncorrelated, which is an unreasonable assumption.
Additionally, traditional cellular architecture suffers from severe inter-cell
interference at the cell edge. A promising technology for future wireless
communication standards is the cell-free (CF) communication architecture [13].
By enabling simultaneous coherent multipoint transmission and reception over a
large number of spatially distributed remote antenna units (RRUs), this
architecture can provide better propagation and channel hardening effects and
mitigate cell boundary and inter-cell interference problems associated with
cellular systems. Therefore, investigating how to integrate sensing with CF
networks is a problem worth exploring.

In the CF network, a significant challenge to reusing communication signals
for sensing is the simultaneous transmission of the same data by multiple RRUs
to users. The RRU will receive the same signals emitted by many other RRUs,
which are all interfering signals. Previous research has shown limited success
in extracting useful sensor information from such signals that are
superimposed with multiple simultaneous co-channel interferences. Although
previous work, such as [9], has considered it from the CF network perspective,
it typically requires a specific access point (AP) for sensing, which limits
the overall efficiency of the network. This approach implements sensing and
communication separately, and no integration is achieved.

Furthermore, we observed that the structure of the distributed radar sensing
[13] was similar to the network-assisted full-duplex (NAFD) CF distributed
massive MIMO network in communication [14, 15]. The distributed radar system
is a set of radars transmitting signals, and another set of radars receiving
echo signals reflected on the target, all of them connected to the CPU.
Similarly, NAFD CF distributed massive MIMO network densely distributes
multiple RRUs of multiple antennas in a region and connects them to a common
CPU performing baseband processing. Each RRU can perform uplink(UL) reception
or downlink(DL) transmission in a single time slot, overcoming the problem of
full duplex communication interference caused by simultaneous DL transmission
and UL reception. To eliminate cross-link interference from DL-RRU to UL-RAU,
[16] proposed a beamforming training scheme to help UL-RRU estimate the
effective channel state information (CSI).In [17] and [18], the selection of
RRU uplink and downlink modes and power distribution according to user QOS
requirements in NAFD scenarios are investigated, respectively.

Based on the previous analysis, this paper proposes a design method for
network ISAC. Referring to the design in [16], the system uses TDD mode and
the first symbol is used for uplink channel estimation, where the CPU
estimates the CSI between all users and all RAUs. After completing the uplink
channel estimation, the DL-RRUs superimpose the downlink pilot on the downlink
data to help the UL-RRUs estimate the effective CSI to eliminate DL-to-UL
interference. Simultaneously, UL-RRUs separate the superimposed pilot from the
received signal and reuse the superimposed pilot for sensing. The superimposed
pilot is used to solve the interference problem caused by multiple RRUs
transmitting signals on the same frequency simultaneously in the CF
architecture. The superimposed pilot assigned to each DL-RRU is orthogonal, so
ideally, there is no interference when sensing. The feasibility of using the
superimposed pilot for target sensing has been demonstrated in [19]. The main
contributions of this paper are summarized as follows:

  * $\bullet$

Using the design principles of distributed radar sensing, which separates the
radar transmitter and receiver, with the structure of separate uplink and
downlink remote antenna units (RRUs) in NAFD, we propose a novel design
approach for an integrated communication and sensing system with NAFD (NAFD-
ISAC). This approach enables a more efficient and effective system by
integrating the two structures. To the best of the authors’ knowledge, this
kind of system has never been investigated before.

  * $\bullet$

The utilization of the superimposed pilot solves the challenge of interference
to sensing caused by multiple RRUs transmitting signals on the same frequency
simultaneously in CF architecture. Moreover, it solves the problem of DL-to-UL
interference in NAFD, avoiding the impractical assumption of uncorrelated
communication signals when reusing communication signals for sensing.

  * $\bullet$

Two efficient power allocation schemes, the deep Q-network (DQN) and the non-
dominated sorting genetic algorithm II (NSGA-II) are designed from the
perspective of multi-objective optimization (MOOP) to achieve better
performance of system in communication and sensing.

  * $\bullet$

The conflicting relationship between communication and sensing performance in
power allocation is verified, and the results show that there is a trade-off
region between communication and sensing. The proposed algorithms provide more
feasible solutions and achieve better system performance than the equal power
allocation algorithm.

The rest of the paper is organized as follows. Section II models the system
from the perspective of a communication system, and radar sensing system,
respectively. In Section III, two efficient power allocation schemes are
investigated. In Section IV, the simulation results are given and analyzed.
The fifth section concludes the paper.

Notations: Bold letters denote vectors or matrices. $\mathbf{I}_{M}$ denotes
an M-dimensional identity matrix. The conjugate transpose and transpose are
denoted by $(\cdot)^{\rm H}$ and $(\cdot)^{\rm T}$, respectively.
$\left|\cdot\right|$ and $||\cdot||$ represent the absolute value and spectral
norm, respectively. The Kronecker product is denoted by $\otimes$. For the
matrix $\mathbf{X}$, the $i$-th row and the $j$-th column of $\mathbf{X}$ are
denoted as $\left[\mathbf{X}\right]_{i,j}$. Matrix inequality
$\mathbf{X}\succeq\mathbf{Y}$ denotes that $\mathbf{X}-\mathbf{Y}$ is positive
semidefinite. The estimation of $x$ is denoted by $\hat{x}$, and the
estimation error is denoted by $\tilde{x}$.

Figure 1: An NAFD-ISAC cell-free distributed Massive MIMO system.

##  2 System Model

We consider the NAFD-ISAC CF distributed MIMO system consisting of a CPU, $M$
randomly distributed ISAC-RRU, and $K$ users, a target to be sensed, as shown
in Figure 1. ISAC-RRUs refer to RRUs with communication and sensing signal
processing capability, which we will abbreviate as RRUs later for ease of
presentation. ${\kappa_{\rm ul}}=\\{1,...,{K_{\rm ul}}\\}$ and ${\kappa_{\rm
dl}}=\\{1,...,{K_{\rm dl}}\\}$ denote the set of uplink users and downlink
users, respectively. ${\zeta_{\rm ul}}=\\{1,...,{M_{\rm ul}}\\}$ and
${\zeta_{\rm dl}}=\\{1,...,{M_{\rm dl}}\\}$ denote the set of DL RRUs and UL
RRUs, respectively. The number of antennas of the RRU is $N$, and each user
has only a single antenna. The RRU can perform UL reception or DL
transmission, which is determined by the CPU. The CPU assigns orthogonal
superimposed pilots to the DL-RRUs. We assume that there are ${M_{\rm dl}}$
DL-RRUs, ${M_{\rm ul}}$ UL-RRUs, ${K_{\rm dl}}$ downlink users and ${K_{\rm
ul}}$ uplink users with $M={M_{\rm dl}}+{M_{\rm ul}}$ and $K={K_{\rm
dl}}+{K_{\rm ul}}$.

First, all users transmit uplink pilot ${\tau_{1}}$ for uplink channel
estimation, and then, in the superimposed pilot and data transmission phase,
all DL-RRUs transmit the same data using coherent joint transmission according
to a specific beamforming and resource allocation scheme designed by the CPU.
At the same time, the CPU assigns to each DL-RRU an orthogonal superimposed
pilot and superimposed on the downlink data. The UL-RRUs receive both the
uplink data from the UL users and the DL-to-UL interference from the DL-RRUs.
The CPU performs channel estimation based on the signals received by the UL-
RRUs. After channel estimation, the superimposed pilot is separated from the
data and is reused for sensing analysis.

###  2.1 Communication Model

From the communication perspective, in downlink data transmission, $M_{\rm
dl}$ DL RRUs send data $\boldsymbol{s}$ to $K_{\rm dl}$ downlink users. At
each DL RRU, an orthogonal superimposed pilot $\boldsymbol{\varphi}$ is added.
The signal transmitted by the $m$-th DL RRU can then be represented as
follows:

$\boldsymbol{z}_{\rm
dl,m}=\sqrt{{p_{\max}}{\beta_{m}}}{\mathbf{w}^{s}_{m}}\boldsymbol{\varphi}_{m}+\sum\limits_{i\in{\kappa_{\rm
dl}}}{\sqrt{{p_{\max}}{\alpha_{m,i}}}\mathbf{w}^{c}_{i,m}}s_{i},$ (1)

where $p_{\max}$ is the maximum signal power that can be transmitted by the
DL-RRU, $\alpha_{m,i}$ is the data power ratio factor to the total maximum
transmit power transmitted by the DL-RAUs, $\beta_{m}$ is the pilot power
factor to the total maximum transmit power, $\mathbf{w}^{c}_{i,m}$ is the data
beamforming vector using ZF beamforming, $\mathbf{w}^{s}_{m}$ is the sensing
beamforming vector using conjugate sensing beamforming[20], ${\varphi}_{m}$ is
the superimposed pilot assigned to the $m$-th RRU with
$\mathbb{E}[{\varphi}_{m}^{\rm H}{\varphi}_{m}]=1$, and $s_{i}$ is the
transmitted downlink data signal with $\mathbb{E}[s_{i}^{\rm H}s_{i}]=1$.
Then, the data received by the $l$-th downlink user can be expressed as

$\displaystyle r_{l}^{\rm dl}=$ $\displaystyle\sum\limits_{i\in{\kappa_{\rm
dl}}}{\underbrace{\sqrt{{p_{\max}}{\alpha_{m,i}}}{\mu^{c}_{l,i}}{s_{i}}}_{\rm
downlink{\text{ }}\rm data}+\sum\limits_{m\in{\zeta_{\rm
dl}}}{\underbrace{\sqrt{{p_{\max}}{\beta_{m}}}{\mu^{s}_{l,m}}{\varphi}_{m}}_{\rm
superimposed{\text{ }}\rm pilot}}}$
$\displaystyle+\sum\limits_{k\in{\kappa_{\rm ul}}}{\underbrace{\sqrt{{p_{{\rm
ul},k}}}{g_{{\rm t},l,k}}{x_{k}}}_{\rm uplink{\text{ }}\rm
interference}}+{n_{\rm dl}},$ (2)

where ${\mu^{c}_{l,i}}\buildrel\Delta\over{=}\mathbf{g}_{{\rm dl},l}^{\rm
H}{\mathbf{w}^{c}_{i}}$ is defined as the effective CSI between the $l$-th DL
user and all DL-RRUs, ${\mu^{s}_{l,m}}\buildrel\Delta\over{=}\mathbf{g}_{{\rm
dl},l,m}^{\rm H}{\mathbf{w}^{s}_{m}}$ is defined as the sensing interference.
Here, ${\mathbf{g}_{{\rm dl},l}}={[\mathbf{g}_{{\rm dl},l,1}^{\rm
T},...,\mathbf{g}_{{\rm dl},l,{M_{\rm dl}}}^{\rm T}]^{\rm T}}$ denotes the
downlink channel vector between all DL-RRUs and the $l$-th DL user,
${\mathbf{g}_{{\rm dl},l,m}}=\lambda_{{\rm dl},l,m}^{1/2}{\mathbf{h}_{{\rm
dl},l,m}}$ denotes the channel between the $l$-th user and the $m$-th DL-RRU,
$\lambda_{{\rm dl},l,m}^{1/2}\buildrel\Delta\over{=}d_{\rm
dl,l,m}^{-{\alpha_{\rm dl}}}$ denotes the large scale fading, $d_{{\rm
dl},l,m}$ denotes the transmitted distance, ${\alpha_{\rm dl}}$ denotes the
path loss, and ${\mathbf{h}_{{\rm dl},l,m}}\sim{\cal C}{\cal
N}(0,{I_{N}})\in\mathbb{C}{{}^{N\times 1}}$ is the small scale fading,
$g_{{\rm t},l,k}=\lambda_{{\rm dl},l,k}^{1/2}{h_{{\rm
dl},l,k}}\in\mathbb{C}{{}^{1\times 1}}$ denotes the channel for the $l$-th UL
user to the $k$-th DL user, ${x_{k}}$ is the data sent by the $k$-th uplink
user with $\mathbb{E}\left[{x_{k}^{\rm H}{x_{k}}}\right]=1$, the data sent by
the uplink user is an interference to the downlink user, ${n_{\rm
dl}}\sim{\cal C}{\cal N}(0,\sigma_{\rm dl}^{2})$ is the additive Gaussian
white noise with covariance $\sigma_{\rm dl}^{2}$.

On the user side, local channel estimation is performed when the signal is
received. We can use the iterative method for channel estimation to get the
channel between the users and the DL-RRUs. In this paper, for simplicity, we
model the channel estimation error as additive Gaussian white noise with
covariance $\sigma_{\rm sp,\rm dl}^{2}$[21, 22]. The $l$-th user and the
$m$-th DL-RRU which is expressed as $\mathbf{g}_{{\rm
dl},l,m}=\mathbf{\hat{g}}_{{\rm dl},l,m}+\mathbf{\tilde{g}}_{\rm dl,l,m}$.
Here, $\mathbf{\tilde{g}}_{{\rm dl},l,m}$ denotes the channel estimation
error. Once the user channel estimation process is complete, the downlink
pilot signal can be recovered by the user, since the pilot is typically
known[23, 24]. This enables us to separate the pilot and data signals from
each other. The rest signal can be expressed as

$\displaystyle\bar{r}_{l}^{\rm dl}=$
$\displaystyle\sum\limits_{i\in{\kappa_{\rm
dl}}}{\sqrt{{p_{\max}}{\alpha_{m,i}}}{\mu^{c}_{l,i}{s_{i}}}+}\sum\limits_{k\in{\kappa_{\rm
ul}}}{\sqrt{{p_{\rm ul,k}}}{g_{{\rm t},l,k}}{x_{k}}}$
$\displaystyle+\sum\limits_{m^{\prime}\in{\zeta_{\rm
dl}}}{\sqrt{{p_{\max}}{\beta_{m^{\prime}}}}{\tilde{\mu}^{s}_{l,m}}{\varphi}_{m^{\prime}}}+{n_{\rm
dl}},$ (3)

then the downlink data transmission rate is expressed as

${R_{l}^{\rm dl}}=\mathbb{E}\left[{{{\log}_{2}}(1+{{{\rm\gamma}_{l}^{\rm
dl}}})}\right],$ (4)

where $\gamma_{l}^{\rm dl}$ is the signal-to-interference-plus-noise ratio
(SINR) of the $l$-th downlink user, which is given by Eq. (5) on the top of
the next page. From Eq. (4), it can be seen that the downlink rate is affected
by downlink data power, uplink data power, and channel estimation error
interference. All of these are inextricably linked to power allocation.

$\displaystyle\gamma_{l}^{\rm dl}=\frac{{\sum\limits_{m\in{\zeta_{\rm
dl}}}{{{\left|{\sqrt{{p_{\max}}{\alpha_{m,l}}}{\mu^{c}_{l,l}}}\right|}^{2}}}}}{{\sum\limits_{i\in{\kappa_{\rm
dl}},i\neq
l}{\sum\limits_{m\in{\zeta}}{{{\left|{\sqrt{{p_{\max}}{\alpha_{m,i}}}{\mu^{c}_{l,i}}}\right|}^{2}}}}+\sum\limits_{k\in{\kappa_{\rm
ul}}}{{{\left|{\sqrt{{p_{\rm ul,k}}}{g_{{\rm
t},l,k}}}\right|}^{2}}+\sum\limits_{m^{\prime}\in{\zeta_{\rm
dl}}}{{{\left\|{\sqrt{{p_{\max}}{\beta_{m^{\prime}}}}{\tilde{\mu}^{s}_{l,m}}}\right\|}^{2}}}+\sigma_{\rm
dl}^{2}}}}$ (5)

For uplink transmission, all UL-RRUs receive signals from UL users and signals
from DL-RRUs, then the received signals can be expressed at the CPU as follows

$\displaystyle\boldsymbol{r}^{\rm ul}=$
$\displaystyle\sum\limits_{i\in{\kappa_{\rm ul}}}{\underbrace{\sqrt{{p_{\rm
ul,i}}}{\mathbf{g}_{l,i}}{x_{i}}}_{\rm uplink{\text{ }}\rm
data}}+\sum\limits_{l\in{\kappa_{dl}}}{\underbrace{\sqrt{{p_{\max}}{\alpha_{m,l}}}{\mathbf{f}_{l}}{s_{l}}}_{\rm{DL-
to-UL}{\text{ }}\rm interference}}$
$\displaystyle+\sum\limits_{m\in{\zeta_{\rm
dl}}}{\underbrace{\sqrt{{p_{\max}}{\beta_{m}}}{\mathbf{G}_{{\rm
I},m}}{\mathbf{w}^{s}_{m}}{\varphi}_{m}}_{\rm superimposed{\text{ }}\rm
pilot}}+{\mathbf{n}_{\rm ul}},$ (6)

where $\boldsymbol{r}^{\rm ul}\in\mathbb{C}{{}^{{M_{\rm ul}}N\times 1}}$,
${\mathbf{f}_{l}}\buildrel\Delta\over{=}{\mathbf{G}_{\rm I}}{\mathbf{w}_{l}}$
is defined as the effective interference between DL-RRUs and UL-RRUs,
${\mathbf{G}_{\rm I}}={[\mathbf{G}_{{\rm I},1}^{\rm T},...,\mathbf{G}_{{\rm
I},{M_{\rm ul}}}^{\rm T}]^{\rm T}}$. ${\mathbf{G}_{{\rm
I},l}}={[\mathbf{G}_{{\rm I},l,1}^{\rm T},...,\mathbf{G}_{{\rm I},l,{M_{\rm
ul}}}^{\rm T}]^{\rm T}}$ denotes the $l$-th interfering channel between DL-
RRUs and UL-RRUs, where $\mathbf{G}_{{\rm I},l,{M_{\rm ul}}}^{\rm
T}=\lambda_{I,l,m}^{1/2}{\mathbf{H}_{{\rm I},l,m}}\in\mathbb{C}{{}^{N\times
N}}$, ${\mathbf{n}_{\rm ul}}\sim{\cal C}{\cal N}(0,\sigma_{\rm
ul}^{2}\mathbf{I})\in\mathbb{C}{{}^{{M_{\rm ul}}N\times 1}}$ is the additive
Gaussian white noise with covariance $\sigma_{\rm ul}^{2}$. Similarly, the CPU
performs channel estimation based on the received signal to obtain the channel
between DL-RRUs and UL-RRUs. $\mathbf{\tilde{G}}_{{\rm I},m}=\mathbf{G}_{{\rm
I},m}-\mathbf{\hat{G}}_{{\rm I},m}$ denotes the channel estimation error,
which is assumed to be additive Gaussian white noise with the covariance of
$\sigma_{\rm sp,\rm ul}^{2}$. CPU can replicate the pilot signal at the
receiver using the initial pilot and estimated channel to recover the pilot
signal and then separate the pilot signal from data, the remaining signals are
expressed as

$\displaystyle\boldsymbol{\bar{r}}^{\rm ul}=$
$\displaystyle\sum\limits_{i\in{\kappa_{\rm ul}}}{\sqrt{{p_{{\rm
ul},i}}}{\mathbf{g}_{l,i}}{x_{i}}}+\sum\limits_{l\in{\kappa_{\rm
dl}}}{\sqrt{{p_{\max}}{\alpha_{m,l}}}{\mathbf{f}_{l}}{s_{l}}}$
$\displaystyle+\sum\limits_{m\in{\zeta_{dl}}}{\sqrt{{p_{\max}}{\beta_{m}}}{{\mathbf{\tilde{G}}}_{{\rm
I},m}}{\mathbf{w}^{s}_{m}}{\varphi}_{m}}+{\mathbf{n}_{\rm ul}}.$ (7)

Furthermore, since the channel $\mathbf{\hat{G}}_{{\rm I},m}$ and the
transmitted signal $\sqrt{{p_{\max}}{\alpha_{m,l}}}{s_{l}}$ are known, the CPU
can also regenerate the DL-to-UL interference and remove it from the received
signal. After subtracting regenerative interference, the CPU uses a specific
receiver, then the received signal of the $k$-th user is expressed as

$\displaystyle\boldsymbol{\bar{r}}_{k}^{\rm ul}=\boldsymbol{v}_{k}^{\rm
H}\Big{(}$ $\displaystyle\sum\limits_{i\in{\kappa_{\rm ul}}}{\sqrt{{p_{{\rm
ul},i}}}{\mathbf{g}_{l,i}}{x_{i}}}+\sum\limits_{l\in{\kappa_{\rm
dl}}}{\sqrt{{p_{\max}}{\alpha_{m,l}}}{\mathbf{\tilde{f}}_{l}}{s_{l}}}$
$\displaystyle+\sum\limits_{m\in{\zeta_{\rm
dl}}}{\sqrt{{p_{\max}}{\beta_{m}}}{{\mathbf{\tilde{G}}}_{{\rm
I},m}}{\mathbf{w}^{s}_{m}}{\varphi}_{m}}+{\mathbf{n}_{\rm ul}}\Big{)},$ (8)

then the uplink data transmission rate is expressed as

$\displaystyle R_{{\rm ul},k}=\mathbb{E}\left[{{{\log}_{2}}(1+\gamma_{k}^{\rm
ul})}\right],$ (9)

where $\gamma_{k}^{\rm ul}$ is the signal-to-interference-plus-noise ratio
(SINR) of the $k$-th uplink user, which is given by Eq. (10) on the top of
this page. Similarly, in Eq. (9), the main interference is due to channel
estimation error, and the magnitude of the interferences is also affected by
power allocation.

$\displaystyle\gamma_{k}^{\rm ul}=\frac{{{p_{\rm
ul,k}}{{\left|{\mathbf{v}_{k}^{\rm
H}{\mathbf{g}_{l,k}}}\right|}^{2}}}}{{{{\sum\limits_{i\in{\kappa_{\rm
ul}},i\neq k}{{p_{\rm ul,i}}\left|{\mathbf{v}_{k}^{\rm
H}{\mathbf{g}_{l,i}}}\right|}}^{2}}+{{\sum\limits_{l\in{\kappa_{\rm
dl}}}{\left|{\sqrt{{p_{\max}}{\alpha_{m,l}}}\mathbf{v}_{k}^{\rm
H}{{\mathbf{\tilde{f}}}_{l}}}\right|}}^{2}}+\sum\limits_{m\in{\zeta_{\rm
dl}}}{{{\left|{\sqrt{{p_{\max}}{\beta_{m}}}\mathbf{v}_{k}^{\rm
H}{\mathbf{\tilde{G}}_{{\rm
I},m}}}{\mathbf{w}^{s}_{m}}\right|}^{2}}}+\sigma_{\rm
ul}^{2}{{\left\|{\mathbf{v}_{k}^{\rm H}}\right\|}^{2}}}}$ (10)

###  2.2 Radar Model

Viewed from the radar sensing side, the DL-RRUs superimpose the pilot on the
communication data, and the UL-RRUs separate the superimposed pilot from the
received echo signal and perform radar sensing on the target based on the
pilot. For clutter interference of sense, we make some idealized assumptions.
We assume that the target-free channel between the DL-RRUs and UL-RRUs is
acquired before sensing in the absence of the target. Following the previous
literature[25, 26], we neglect the paths resulting from multi-reflections from
the other objects due to the presence of the target. Since the transmitted
signal is also known at the CPU, the target-free part of the received signal
at each UL-RRU can be canceled. After this cancellation, the separated pilot
signal in the presence of the target at the $n$-th UL-RRU can be expressed as
[27]:

$\displaystyle{\boldsymbol{r}_{n}}=\sum\limits_{m\in{\zeta_{\rm
dl}}}\sqrt{{p_{\max}}{\beta_{m}}}{\eta_{n,m}}{{\boldsymbol{\nu}_{n,m}}}{\mathbf{w}^{s}_{m}}{\varphi}_{m}+{\boldsymbol{w}_{n}},$
(11)

where ${\eta_{n,m}}=\tfrac{{{\lambda^{2}}{G_{\rm t}}{G_{\rm
r}}\sigma}}{{{{(4\pi)}^{3}}d_{n}^{2}d_{m}^{2}}}{e^{-j2\pi(\frac{{\Delta
f}}{\rm c}{d_{n,m}}+\frac{{{\rm T_{p}}}}{\lambda}{{\dot{d}}_{n,m}})}}$ is a
complex amplitude, which is assumed to be deterministic and constant
throughout the processing interval, ${G_{\rm t}}$, ${G_{\rm r}}$ denotes the
transmitting antenna gain, $\sigma$ is the radar cross-sectional area (RCS) of
the target, ${d_{n,m}}={d_{n}}+{d_{m}}$ is the bistatic range between the
transmitters, scatterer and receivers,
${\dot{d}_{n,m}}={\dot{d}_{n}}+{\dot{d}_{m}}$ is the associated bistatic range
rate, ${d_{n}}$ and ${d_{m}}$ denote the distance between transmitter and
scatterer and scatterer and receiver, respectively, $\Delta f$ is the
bandwidth, ${\boldsymbol{\nu}_{n,m}}$ is the spatial steering vector, $N$ is
the number of antennas and indicates the relative displacement of each RRU
antenna array, and ${\boldsymbol{w}_{n}}$ is the noise due to channel
estimation error, which according to Eq. (6) and Eq. (7), is expressed as
${\boldsymbol{w}_{n}}=\sum\nolimits_{m\in{\zeta_{\rm
dl}}}{\sqrt{{p_{\max}}{\beta_{m}}}{\boldsymbol{{\tilde{G}}}_{{\rm
I},m,n}}\boldsymbol{\varphi}_{m}}$. The target of the scenario considered in
this paper is slow-moving. It is assumed to be approximately immobile within a
time window, so ${\dot{d}_{n,m}}=0$.The steering vector
${\boldsymbol{\nu}_{n,m}}={\boldsymbol{b}_{n}}\otimes{\boldsymbol{a}_{m}}\in\mathbb{C}{{}^{N\times
N}}$ represents the relative phase shift of the RRU on the antenna, where
${\boldsymbol{b}_{n}}$ and ${\boldsymbol{a}_{m}}$ are the receive and transmit
steering vectors, denoted as
${\boldsymbol{b}_{n}}=[{b_{n,1}},{b_{n,2}}...,{b_{n,N}}]$ and
${\boldsymbol{a}_{m}}=[{a_{m,1}},{a_{m,2}}...,{a_{m,N}}]$, respectively, and
${b_{n,j}}={e^{-j2\pi\frac{{\boldsymbol{k}_{n}^{\rm
T}{\boldsymbol{q}_{nj}}}}{\lambda}}}$,
${a_{m,i}}={e^{-j2\pi\frac{{\boldsymbol{k}_{m}^{\rm
T}{\boldsymbol{q}_{mi}}}}{\lambda}}}$.
$\boldsymbol{k}_{n}={[\cos({\theta_{n}}),\sin({\theta_{n}})]^{\rm T}}$ and
$\boldsymbol{k}_{m}={[\cos({\phi_{m}}),\sin({\phi_{m}})]^{\rm T}}$ represent
the wave vectors for the respective transmit and receive paths, where
${\theta_{n}}$ and ${\phi_{m}}$ represent the DOA and DOD, respectively.
${\boldsymbol{q}_{nj}}={[{x_{nj}},{y_{nj}}]^{\rm T}}$ and
${\boldsymbol{q}_{mj}}={[{x_{mj}},{y_{mj}}]^{\rm T}}$ represent the position
of the $j$-th antenna of the $n$-th UL-RRU and the $i$-th antenna of the
$m$-th DL-RRU, respectively.

We analyze the sensing performance by the Cramér-Rao lower bound (CRLB) [28].
The squared position error bound (SPEB) and squared orientation error bound
(SOEB) are defined for evaluating performance metrics of radar sense. Assuming
that the target location is approximately known a priori, the corresponding
CRLB can be optimized to improve the accuracy of the real-time estimation
[29]. The CRLB is the mean squared error (MSE) matrix of an unbiased estimate
of a known deterministic parameter or estimate of a random parameter, which is
the inverse of the bayesian fisher information matrix (FIM) as

$\mathbb{E}\left\\{{({\boldsymbol{\hat{\gamma}}_{n,m}}-{\boldsymbol{\gamma}_{n,m}}){{({\boldsymbol{\hat{\gamma}}_{n,m}}-{\boldsymbol{\gamma}_{n,m}})}^{\rm
T}}}\right\\}\succeq\mathbf{J}_{n,m}^{-1},$ (12)

where
${\boldsymbol{\gamma}_{n,m}}={\left[{{d_{n,m}},{\theta_{n}},{\phi_{m}}}\right]^{T}}$
is the true value of the parameters and
$\mathbf{J}_{n,m}\in\mathbb{C}{{}^{3\times 3}}$ is the FIM of the unknown
matrix ${\boldsymbol{\gamma}_{n,m}}$. The FIM can be calculated by the
following equation

${\mathbf{J}_{n,m}}=\frac{1}{{\sigma_{n}^{2}}}{\sum\limits_{m\in{\zeta_{dl}}}{\left(\frac{{d{\boldsymbol{r}_{n,m}}}}{{d\boldsymbol{\gamma}_{n,m}^{\rm
T}}}\right)}^{\rm
H}}\left(\frac{{d{\boldsymbol{r}_{n,m}}}}{{d\boldsymbol{\gamma}_{n,m}^{\rm
T}}}\right).$ (13)

The lower bound of the CRLB for each channel parameter is given by the
corresponding diagonal term of $\mathbf{J}_{n,m}^{-1}$, and the exact
derivation can be found in [28], whose equation is expressed as

$\mathbf{J}_{n}^{-1}=\mathbf{diag}(\sigma_{d,n}^{2},\sigma_{\theta,n}^{2},\sigma_{\phi,n}^{2}),$
(14)

where

$\sigma_{d,n}^{2}=\frac{1}{{\sum\limits_{m\in{\zeta_{dl}}}\frac{{p_{\max}}{\beta_{m}}{\pi^{2}}{{({\Delta
f}/{c})^{2}}}\eta_{n,m}^{2}{N^{2}}}{{\sigma_{n}^{2}}}}{{{\left\|\mathbf{w}^{s}_{m}\right\|}^{2}}}},$
(15)
$\sigma_{\theta,n}^{2}=\frac{1}{{\sum\limits_{m\in{\zeta_{dl}}}{\frac{{{p_{\max}}{\beta_{m}}4{\pi^{2}}\eta_{n,m}^{2}N({B_{n}}-({1}/{N})A_{n}^{2})}}{{{\lambda^{2}}\sigma_{n}^{2}}}}{{{\left\|\mathbf{w}^{s}_{m}\right\|}^{2}}}}},$
(16)
$\sigma_{\phi,n}^{2}=\frac{1}{{\sum\limits_{m\in{\zeta_{dl}}}{\frac{{{p_{\max}}{\beta_{m}}4{\pi^{2}}\eta_{n,m}^{2}N({B_{m}}-({1}/{N})A_{m}^{2})}}{{{\lambda^{2}}\sigma_{n}^{2}}}}{{{\left\|\mathbf{w}^{s}_{m}\right\|}^{2}}}}},$
(17)

${A_{m}}=\sum\nolimits_{i=1}^{N}{\left(({y_{mi}}\cos({\phi_{m}})-{x_{mi}}\sin({\phi_{m}})\right)}$
and
${B_{m}}={\sum\nolimits_{i=1}^{N}{\left(({y_{mi}}\cos({\phi_{m}})-{x_{mi}}\sin({\phi_{m}})\right)}^{2}}$
are related to the antenna array on the transmitter,
${A_{n}}=\sum\nolimits_{i=1}^{N}{\left({y_{ni}}\cos({\theta_{n}})-{x_{ni}}\sin({\theta_{n}})\right)}$
and
${B_{n}}={\sum\nolimits_{i=1}^{N}{\left(({y_{ni}}\cos({\theta_{n}})-{x_{ni}}\sin({\theta_{n}})\right)}^{2}}$
are related to the receiver. The locally estimated
${\boldsymbol{\hat{\gamma}}_{n,m}}$ is sent to the CPU, where a fusion is
carried out to estimate the position of the target. According to Eq. (14), we
can get the local estimation error at each UL-RRU, the 1st term on the
diagonal represents the estimation error of ${d_{n,m}}$, i.e., the position
estimation error SPEB. The 2nd and 3rd terms on the diagonal represent the
estimation error of the angle ${\theta_{n}}$, ${\phi_{m}}$, i.e., the
orientation estimation error SOEB. The SPEB and SOEB are respectively defined
as

$e_{\rm sp}=\frac{{\sum\nolimits_{n\in{\zeta_{\rm
ul}}}{{{\left[{\mathbf{J}_{n}^{-1}}\right]}_{1,1}}}}}{{{M_{\rm ul}}}},$ (18)
${e_{\rm so}}=\frac{{\sum\nolimits_{n\in{\zeta_{\rm
ul}}}{\sum\nolimits_{i=2}^{3}{{{\left[{\mathbf{J}_{n}^{-1}}\right]}_{i,i}}}}}}{{{M_{\rm
ul}}}}.$ (19)

Combining the formula Eq. (15)-(17) and Eq. (18)-(19) it can be found that
both SPEB and SOEB are influenced by the pilot power factor ${\beta_{m}}$.

##  3 Power allocation schemes

Based on the analysis presented, it is evident that the power factor plays an
important role in both communication and sensing performance. And the
requirements for communication performance and sensing performance are
different in different scenarios. Therefore, effective allocation of transmit
power is critical to optimize the overall system performance. In this section,
we propose a multi-objective optimization problem that aims to maximize both
communication and sensing performance while satisfying the system constraints.
Specifically, our objective is to maximize the communication rate and minimize
the localization error.

The problem of maximizing the sum communication rate can be expressed as

$\mathop{\max}\limits_{{\boldsymbol{\alpha}}}~{}{f_{1}}={\omega_{D}}\sum\limits_{l=1}^{{K_{dl}}}{R_{dl,l}+}{\omega_{U}}\sum\limits_{k=1}^{{K_{ul}}}{R_{ul,k}},$
(20)

where
$\boldsymbol{\alpha}=\left[{{\alpha_{1}},...,{\alpha_{{M_{dl}}}}}\right]$
denotes the scale factor of data to total power,
${\alpha_{m}}=\sum\limits_{i\in{\kappa_{dl}}}{{\alpha_{m,i}}}\forall
m\in{\zeta_{dl}}$, ${\omega_{D}}$ and ${\omega_{U}}$ denote the sum rate
weighting factor for downlink and uplink, respectively.

Since minimizing the positioning error is equivalent to maximizing the inverse
of the position error, the second optimization problem can be formulated as

$\mathop{\max}\limits_{{\boldsymbol{\beta}}}~{}{f_{2}}=\frac{1}{{{\omega_{sp}}e_{sp}+{\omega_{so}}e_{so}}},$
(21)

where $\boldsymbol{\beta}=\left[{{\beta_{1}},...,{\beta_{{M_{dl}}}}}\right]$
represents the scaling factor of the pilot to the total power, ${\omega_{sp}}$
and ${\omega_{so}}$ represent the error weighting factors for position and
direction, respectively.

Mathematically, this multi-objective optimization problem can be formulated as

$\mathop{\max}\limits_{\boldsymbol{\alpha},\boldsymbol{\beta}}~{}\mathbf{f}={\left[{{f_{1}},{f_{2}}}\right]^{T}},$
(22) ${\rm
s.t.}~{}\sum\limits_{i\in{\kappa_{dl}}}{{\alpha_{m,i}}{{\left\|{\mathbf{w}_{i,m}^{c}}\right\|}^{2}}+{\beta_{m}}}{\left\|{\mathbf{w}_{m}^{s}}\right\|^{2}}\leq
1~{}\forall m\in{\zeta_{dl}},$ (23)

where $\mathbf{f}$ is a vector of the objective functions $f_{1}$ and $f_{2}$,
and Eq. (23) is the power constraint satisfied by the power allocation factor.
Eq. (22) aims to maximize the system’s communication and sensing performance
simultaneously. Due to the non-convexity of objects and the presence of
multiple optimization variables, traditional optimization techniques face
significant challenges in resolving these complexities. Consequently, we
propose a DQN-based solution and a NSGA-II based solution to solve the joint
optimization problem.

###  3.1 Solution based on DQN

In the optimization problem presented above, the optimal power allocation is
unknown. This makes it a suitable problem for optimization using Deep
Q-Network (DQN). DQN is advantageous in discovering how to choose behaviors
that maximize rewards and achieve goals. The agents in DQN interact with
dynamic environments through repeated observation, action, and reward to find
the optimal strategy. To find this optimal strategy, DQN relies on obtaining
the action value function of ${Q_{\pi}}(s,a)$, which can be estimated using a
deep neural network (DNN). In this context, we will explore how the
application of a DQN-based algorithm can optimize this problem by considering
four key components: agent, state, action, and reward.

  * •

_Agent_ : We use DL-RAUs as the agent for the reinforcement learning
framework. Agents make intelligent decisions based on observation of the
environment, including the adaptive selection of DL-RAUs downlink data power
factor and the pilot power factor.

  * •

_State_ : The state $s_{t}$ of each agent refers to the channel state
information (CSI) and the selection of current downlink data power and pilot
power coefficient.

  * •

_Action_ : The actions of each DQN agent correspond to the optimization
variables, which are the data power coefficient and pilot power coefficient in
the optimization problem. These coefficients are typically continuous values,
while DQN agents usually take discrete actions. Therefore, we discretized the
power coefficients so that they could be represented as discrete actions by
the DQN agents.

  * •

_Reward_ : We define the reward as

${r_{t}}\buildrel\Delta\over{=}{f_{1}}(\boldsymbol{\alpha})+b{f_{2}}(\boldsymbol{\beta}),$
(24)

where ${f_{1}}(\boldsymbol{\alpha})$ in (20) denotes the sum communication
rate, ${f_{2}}(\boldsymbol{\beta})$in (21) denotes the inverse of the position
error, $b$ is a constant that converts two target values to the same order of
magnitude.

DQN employs a neural network to derive the mapping of state-action Q values.
The input to the neural network is the current state, and its output is the Q
value corresponding to all available actions in that state. To determine the
t-step action, we implement a greedy approach based on the state-action Q
value. At each step t, the neural network estimates the value of state-action
Q for every possible action in that state. If the random probability is below
$\varepsilon$, then we select the action with the highest Q value. Otherwise,
we choose an action randomly. To ensure a stable and effective training
process, it is important to dynamically adjust the value of $\varepsilon$. In
the early stages, setting $\varepsilon$ to a small value allows for more
experience accumulation. As training progresses, gradually increasing
$\varepsilon$ helps to stabilize the process. After a certain number of
iterations, the output of DQN becomes increasingly stable and the optimal
power distribution strategy can be determined based on maximizing rewards.

###  3.2 Solution based on NSGA-II

According to the previous system model, when the data power allocation factor
is increased, the data power is increased, and consequently, the sum
communication rate also increases. However, the pilot power allocation factor
is decreased correspondingly to meet the condition satisfied with the data
power allocation factor according to Eq. (15)-(17), the corresponding
positioning error is increased, so the two objectives contradict each other.
Based on the concept of Pareto optimality, a multi-objective optimization
method is proposed to explore the trade-off between conflicting objectives.
Despite the potential of the DQN power allocation approach to optimize both
communication rate and positioning accuracy, there remains a lack of
understanding regarding the Pareto boundary that delineates the trade-off
between these two objectives.

(a) circle deployment

(b) random deployment

Figure 2: RRUs, users, and target layout.

In this paper, we use multi-objective evolutionary algorithms (MOEAs) to
obtain the Pareto bound of Eq. (22). This algorithm has the advantage of
solving all objectives simultaneously in one simulation run. Therefore, the
MOEAs method is applied in this paper to obtain the Pareto optimal points.
Specifically, NSGA-II [30] is used to solve Eq. (22). NSGA-II introduces the
crowding degree and the crowding degree comparison operator based on the fast
non-dominated sorting method and uses the crowding degree as the comparison
criterion among individuals in the population. The individuals of the
population in the quasi-pareto region can even be extended to the whole Pareto
region, and the good individuals in the population are preserved to ensure the
diversity of the population, which has achieved excellent results.

##  4 NUMERICAL RESULTS

(a) SPEB (m)

(b) SOEB(deg)

Figure 3: Contour plots for different metrics in the circle deployment
network.

In this section, we simulate and analyze the distribution of different sensing
performances of the target at different locations and the effect of the power
allocation factor on communication and sensing. In addition, the performance
of the proposed multi-objective optimization-based power allocation scheme is
evaluated.

Theoretically, the RRU locations are randomly distributed. In the simulation,
for the intuition of the results, we assume that there are ${M=16}$ RRUs
uniformly distributed on a circle with a radius of 200 m with $K_{\rm ul}=3$
uplink users, $K_{\rm dl}=3$ downlink users, and a target, randomly
distributed in a region of ${R=300}$ m, as shown in Figure 2a. To make a
partial comparison, we also incorporated the random generation of users, RRU,
and target locations within the ${R=300}$ radius area, as depicted in Figure
2b. It is assumed that in the NAFD-ISAC distributed MIMO system, half of the
RRUs are used for uplink transmission, and the other half for downlink
transmission. We set the carrier frequency to 3.5GHz, the bandwidth to 1MHz,
and the maximum transmits power of each RRU to 1W. According to [16], the path
loss index is set to ${\alpha_{\rm dl}}={\alpha_{\rm ul}}=3.7$, ${\alpha_{\rm
t}}=4$, ${\alpha_{\rm I}}=3$. The antenna gain is ${G_{\rm t}}={G_{\rm t}}=1$
and the RCS is $\sigma=1$ . For the noise of the communication signal
processing, we choose $\sigma_{\rm dl}^{2}=\sigma_{\rm ul}^{2}=-83$ dBm. The
superimposed pilot estimation error is chosen as $\sigma_{\rm
sp,dl}^{2}=\sigma_{\rm sp,ul}^{2}=-105$ dBm[31].

Figure 3 shows contour plots of various performance metrics for individual
targets at different locations in the circle deployment network. To observe
the relationship between the location of the target and the estimated error
performance, the pilot power factor and the data power factor are set to a and
b, and the number of antennas of the RRU is $N=16$. From Figure 3, we can see
that the performance behaviors of these two metrics have a similar trend with
the different locations of the target, and the localization errors are smaller
near each DL-RRU, which is related to the RRU layout. When the target is close
to a DL-RRU, the signal transmitted by this DL-RAU can be received by two UL-
RAUs at approximately the same distance after being reflected by the target,
according to the radar complex amplitude equation. The amplitude intensity of
the reflected signal increases as the distance between the target and the
transmitting and receiving RAUs decreases. Therefore, similar to the previous
analysis, there are two RAUs will receive a strong amplitude of the reflected
signal. And when the target is near a UL-RAU, the reflected signal will have
more losses when received by other UL-RAUs. In addition, we found that the
position error is much larger than the orientation error, which is due to the
larger number of RAU antennas we placed with higher angular resolution.

Figure 4 analyzes the relationship between SPEB and pilot power factor for
different numbers of antennas under different network layouts, according to
Eq. (18)(19), SOEB is similar to the relationship between pilot power factor,
so only SPEB is simulated here. It can be seen that positioning error is
reduced with a higher power factor, and positioning error is reduced with a
higher number of aerials. This is the gain of multiple antennas provided by
the MIMO system. It can also be observed that as the number of antennas
increases, the SPEB of the system becomes less sensitive to varying power for
the same network deployment. When comparing the sensing performance of random
deployment and circle deployment in a network with equal numbers of antennas,
it is found that random deployment exhibits slightly worse results. This
result is due to the closer distance between the RRU location and the target
in the randomly deployed network in Figure 2a. It should be noted that the
effectiveness of SPEB may vary depending on the specific network deployment
utilized.

Figure 4: Relationship between SPEB and $\beta_{m}$ in different deployment.

Figure 5 examines the relationship between SPEB and data power factor
${\alpha_{m}}$ at different numbers of antennas under different network
layouts. Under the assumption that the DL-RRU allocates equal power to each
user, it can be seen that the data power factor increases with the increase of
data power and decreases with the increase of the power factor. This is also a
reflection of the need for reasonable power allocation in NAFD-ISAC systems,
where a certain amount of power can be allocated for sensing when
communication performance is not as high-demand. Similarly, we can see that
the communication performance is better under the random network layout when
the power factor of data is relatively small. But with the increase of
downlink power, the communication performance decreases compared with circle
deployment. This observation can be attributed to the similarity in the
distribution of DL-RRUs and DL-UEs positions, along with the proximity of UL-
RRUs and UL-UEs positions, leading to a reduction in propagation loss and an
improvement in communication performance. As the downlink data power factor
increases, the uplink interference also increases gradually, and the uplink
communication rate decreases. Therefore, the communication and rate decline
compared with circle deployment. Hence, the layout of RRUs plays a crucial
role in determining the communication performance of the NAFD-ISAC system.
Further research can focus on optimizing RRU placement for maximizing system
performance.

Figure 5: Relationship between sum communication rate and ${\alpha_{m}}$ in
different deployment.

In Figure 6, we compare the performance of the proposed ISAC system with two
baseline schemes with the relationship of sensing duration.

  * •

TDD-ISAC scheme: In this scheme, the sensing service, uplink, and downlink are
carried out in turn according to the time slot.

  * •

TDD-NAFD-ISAC scheme: This scheme begins by performing the sensing service,
followed by employing the NAFD to separate the uplink and downlink RRUs,
thereby achieving simultaneous uplink and downlink operations.

(a) Sensing performance

(b) Communication performance

Figure 6: The performance of different schemes.

In the scheme proposed in this paper, sensing and communication are carried
out at the same time, and the communication within the system adopts NAFD
mode. For the proposed scheme, there is no change to the perception duration
and it remains a continuous channel block. When comparing perception
performance, TDD and TDD-NAFD perform similarly as they are both perceived in
a single period. However, the communication performance of TDD-NAFD is
superior to that of the TDD and the proposed scheme. TDD-NAFD enables
simultaneous uplink and downlink communication which results in improved
communication performance compared to TDD. In the proposed scheme, some of the
power in the data signal is reserved for sensing, which leads to a slight loss
in communication performance but results in better sensing performance. As
more sensing symbols are added, the sensing performance will improve,
surpassing that of the proposed NAFD scheme.

However, this also means that the time dedicated to sensing alone will
increase, causing a decrease in communication time within a coherent block and
ultimately resulting in a decline in communication performance. Based on the
previous analysis, we can see that compared with other schemes, the proposed
NAFD-ISAC scheme can achieve longer sensing time with stable sensing
performance. Although there is a certain loss in communication performance,
part of the loss is due to power distribution. The power can be reasonably
allocated according to the specific needs of communication performance and
sensing performance to achieve better system performance.

Figure 7: Comparison between equal power allocation(EPA) scheme and proposed
scheme.

The trade-off between the sum communication rate versus location error for
different numbers of antennas deployed on each RAU is shown in Figure 7. It
can be seen that the Pareto front curve is in a monotonically increasing
state, and the system positioning error increases as the communication
performance increases, while our goal is to minimize the system positioning
error, which verifies the contradiction between these two goals in the NAFD-
ISAC system. In addition, as the number of antennas increases, the effect on
the positioning error becomes smaller and smaller. The solution of the DQN
algorithm is better than the equal power allocation(EPA) scheme, the solution
obtained by DQN is approximately close to the Pareto solution, and the running
complexity of the DQN algorithm is lower than that of the NSGA-II algorithm,
but NSGA-II algorithm reveals the optimal frontier of Pareto.

##  5 Conclusion

In this paper, we proposed a method for the design of a network ISAC system,
combining the distributed radar with a similar structure NAFD system to design
a NAFD-ISAC system. This approach eliminated the full-duplex interference
problem in sensing and communication by separating the transceivers. By
assigning a superimposed pilot to each DL-RAU, the co-channel interference
problem in the CF network is avoided. We simulated the factors influencing the
system performance from the communication and sensing perspectives.
Furthermore, we proposed two efficient power allocation schemes. The DQN power
allocation algorithm solves the problem faster, while the NSGA-II power
allocation algorithm provides all the Pareto-optimal solutions. The simulation
results proved the proposed algorithms are superior to the equal power
allocation. In practical applications, sensing and communication requirements
are different. Therefore, how to reasonably select an appropriate RRU
distribution and power allocation mode based on communication and sensing
requirements in NAFD-ISAC systems is an interesting and challenging problem
that deserves attention in future studies.

## ACKNOWLEDGEMENT

This work was supported in part by the National Key Research and Development
Program under Grant (2021YFB2900300), and by the National Natural Science
Foundation of China (NSFC) under Grants 61971127, 61871122, by the Southeast
University-China Mobile Research Institute Joint Innovation Center, and by the
Major Key Project of PCL (PCL2021A01-2).

## References

  * Cui et al. [2021] CUI Y, LIU F, JING X, et al.  Integrating sensing and communications for ubiquitous IoT: Applications, trends, and challenges[J].  IEEE Network, 2021, 35(5): 158-167.
  * Wei et al. [2022] WEI Z, LIU F, MASOUROS C, et al.  Toward multi-functional 6G wireless networks: Integrating sensing, communication, and security[J].  IEEE Communications Magazine, 2022, 60(4): 65-71.
  * Xiao et al. [2022] XIAO Z, ZENG Y.  An overview on integrated localization and communication towards 6g[J].  Science China Information Sciences, 2022, 65: 1-46.
  * Liu et al. [2018] LIU F, ZHOU L, MASOUROS C, et al.  Toward dual-functional radar-communication systems: Optimal waveform design[J].  IEEE Transactions on Signal Processing, 2018, 66(16): 4264-4279.
  * Sun et al. [2022] SUN P, DAI H, WANG B.  Optimal transmit beamforming for near-field integrated sensing and wireless power transfer systems[J].  Intelligent and Converged Networks, 2022, 3(4): 378-386.
  * Guo et al. [2023] GUO T, LI X, MEI M, et al.  Joint Communication and Sensing Design in Coal Mine Safety Monitoring: 3D Phase Beamforming for RIS-Assisted Wireless Networks[J].  IEEE Internet of Things Journal, 2023.
  * Zhang et al. [2020] ZHANG A, RAHMAN M L, HUANG X, et al.  Perceptive mobile networks: Cellular networks with radio vision via joint communication and radar sensing[J].  IEEE Vehicular Technology Magazine, 2020, 16(2): 20-30.
  * Huang et al. [2022] HUANG Y, FANG Y, LI X, et al.  Coordinated power control for network integrated sensing and communication[J].  IEEE Transactions on Vehicular Technology, 2022, 71(12): 13361-13365.
  * Sakhnini et al. [2022] SAKHNINI A, GUENACH M, BOURDOUX A, et al.  A Target Detection Analysis in Cell-Free Massive MIMO Joint Communication and Radar Systems[C]//ICC 2022-IEEE International Conference on Communications.  IEEE, 2022: 2567-2572.
  * Shi et al. [2022] SHI Q, LIU L, ZHANG S, et al.  Device-free sensing in OFDM cellular network[J].  IEEE Journal on Selected Areas in Communications, 2022, 40(6): 1838-1853.
  * Xiao et al. [2021] XIAO Z, ZENG Y.  Full-duplex integrated sensing and communication: Waveform design and performance analysis[C]//2021 13th International Conference on Wireless Communications and Signal Processing (WCSP).  IEEE, 2021: 1-5.
  * Xiao et al. [2022] XIAO Z, ZENG Y.  Waveform design and performance analysis for full-duplex integrated sensing and communication[J].  IEEE Journal on Selected Areas in Communications, 2022, 40(6): 1823-1837.
  * Demir et al. [2021] DEMIR Ö T, BJÖRNSON E, SANGUINETTI L, et al.  Foundations of user-centric cell-free massive MIMO[J].  Foundations and Trends® in Signal Processing, 2021, 14(3-4): 162-472.
  * Liang et al. [2011] LIANG J, LIANG Q.  Design and analysis of distributed radar sensor networks[J].  IEEE Transactions on Parallel and Distributed Systems, 2011, 22(11): 1926-1933.
  * Wang et al. [2019] WANG D, WANG M, ZHU P, et al.  Performance of network-assisted full-duplex for cell-free massive MIMO[J].  IEEE Transactions on Communications, 2019, 68(3): 1464-1478.
  * Li et al. [2020] LI J, LV Q, ZHU P, et al.  Network-assisted full-duplex distributed massive MIMO systems with beamforming training based CSI estimation[J].  IEEE Transactions on Wireless Communications, 2020, 20(4): 2190-2204.
  * Zhu et al. [2022] ZHU Y, LI J, ZHU P, et al.  Load-aware dynamic mode selection for network-assisted full-duplex cell-free large-scale distributed MIMO systems[J].  IEEE Access, 2022, 10: 22301-22310.
  * Fan et al. [2022] FAN Q, ZHANG Y, WANG Z, et al.  MADDPG-Based Power Allocation Algorithm for Network-Assisted Full-Duplex Cell-Free MmWave Massive MIMO Systems with DAC Quantization[C]//2022 14th International Conference on Wireless Communications and Signal Processing (WCSP).  IEEE, 2022: 556-561.
  * Bao et al. [2020] BAO D, QIN G, DONG Y Y.  A superimposed pilot-based integrated radar and communication system[J].  IEEE Access, 2020, 8: 11520-11533.
  * Demirhan et al. [2023] DEMIRHAN U, ALKHATEEB A.  Cell-Free ISAC MIMO Systems: Joint Sensing and Communication Beamforming[A].  2023\.  arXiv: 2301.11328.
  * Mishra et al. [2021] MISHRA H B, SINGH P, PRASAD A K, et al.  Iterative Channel Estimation And Data Detection in OTFS Using Superimposed Pilots[C]//2021 IEEE International Conference on Communications Workshops (ICC Workshops).  2021: 1-6.
  * Garg et al. [2022] GARG N, RATNARAJAH T.  Generalized Superimposed Training Scheme In Cell-free Massive MIMO Systems[J].  IEEE Transactions on Wireless Communications, 2022, 21(9): 7668-7681.
  * Wu et al. [2023] WU Y, HAN C, CHEN Z.  DFT-Spread Orthogonal Time Frequency Space System with Superimposed Pilots for Terahertz Integrated Sensing and Communication[J].  IEEE Transactions on Wireless Communications, 2023: 1-1.
  * Deng et al. [2023] DENG C, FANG X, WANG X.  Beamforming Design and Trajectory Optimization for UAV-Empowered Adaptable Integrated Sensing and Communication[J].  IEEE Transactions on Wireless Communications, 2023: 1-1.
  * Zhao et al. [2022] ZHAO N, WANG Y, ZHANG Z, et al.  Joint Transmit and Receive Beamforming Design for Integrated Sensing and Communication[J].  IEEE Communications Letters, 2022, 26(3): 662-666.
  * Behdad et al. [2022] BEHDAD Z, DEMIR Ö T, SUNG K W, et al.  Power Allocation for Joint Communication and Sensing in Cell-Free Massive MIMO[C]//GLOBECOM 2022 - 2022 IEEE Global Communications Conference.  2022: 4081-4086.
  * Sakhnini et al. [2021] SAKHNINI A, GUENACH M, BOURDOUX A, et al.  A Cramér-rao lower bound for analyzing the localization performance of a multistatic joint radar-communication system[C]//2021 1st IEEE International Online Symposium on Joint Communications & Sensing (JC&S).  IEEE, 2021: 1-5.
  * Kwon et al. [2021] KWON G, CONTI A, PARK H, et al.  Joint communication and localization in millimeter wave networks[J].  IEEE Journal of Selected Topics in Signal Processing, 2021, 15(6): 1439-1454.
  * Liu et al. [2021] LIU F, LIU Y F, LI A, et al.  Cramér-rao bound optimization for joint radar-communication beamforming[J].  IEEE Transactions on Signal Processing, 2021, 70: 240-253.
  * Qatab et al. [2018] QATAB W S, ALIAS M Y, KU I.  Optimization of multi-objective resource allocation problem in cognitive radio LTE/LTE-A femtocell networks using NSGA II[C]//2018 IEEE 4th International Symposium on Telecommunication Technologies (ISTT).  IEEE, 2018: 1-6.
  * Hoeher et al. [1999] HOEHER P, TUFVESSON F.  Channel estimation with superimposed pilot sequence[C]//Seamless Interconnection for Universal Services. Global Telecommunications Conference. GLOBECOM’99.(Cat. No. 99CH37042): volume 4.  IEEE, 1999: 2162-2166.

authorZeng.epsFan Zeng received the B.S. degree in communication engineering
from Shanghai University, Shanghai, China, in 2021. She is currently pursuing
the M.S. degree with the College of Information Science and Engineering,
Southeast University. Her research interests include integrated sensing and
communication. Her supervisor is Professor Li Jiamin.

authorYu.epsJingxuan Yu received the B.S degree in Information Engineer from
Southeast University in 2021 and is currently pursuing his M.S degree in the
School of Information Science and Engineering at Southeast University. His
main research interests are in communication and sensing integration. His
supervisor is Professor Li Jiamin.

authorLi.epsJiamin Li received the B.S. and M.S. degrees in communication and
information systems from Hohai University, Nanjing, China, in 2006 and 2009,
respectively, and the Ph.D. degree in information and communication
engineering from Southeast University, Nanjing, China, in 2014. He joined the
National Mobile Communications Research Laboratory, Southeast University, in
2014, where he has been an Associate Professor since 2019. His research
interests include massive MIMO, distributed antenna systems, and multi-
objective optimization.

authorLiu.epsFeiyang Liu received the B.S. and M.S. degrees from Xidian
University, Xi’an, China, in 2014 and 2017, respectively. He joined in the
54th Research Institute of China Electronics Technology Group Corporation, in
2017.His research interests include UAV broadband data chain.
authorWang.epsDongming Wang received the B.S. degree from Chongqing University
of Posts and Telecommunications, Chongqing, China, the M.S. degree from
Nanjing University of Posts and Telecommunications, Nanjing, China, and the
Ph.D. degree from the Southeast University, Nanjing, China, in 1999, 2002, and
2006, respectively. He joined the National Mobile Communications Research
Laboratory, Southeast University, in 2006, where he has been an Associate
Professor since 2010. His research interests include turbo detection, channel
estimation, distributed antenna systems, and large-scale MIMO systems.

authorYou.epsXiaohu You received the B.S., M.S. and Ph.D. degrees in
electrical engineering from Nanjing Institute of Technology, Nanjing, China,
in 1982, 1985, and 1989, respectively. From 1987 to 1989, he was with Nanjing
Institute of Technology as a Lecturer. From 1990 to the present time, he has
been with Southeast University, first as an Associate Professor and later as a
Professor. His research interests include mobile communications, adaptive
signal processing, and artificial neural networks with applications to
communications and biomedical engineering. He is the Chief of the Technical
Group of China 3G/B3G Mobile Communication R & D Project. He received the
excellent paper prize from the China Institute of Communications in 1987 and
the Elite Outstanding Young Teacher Awards from Southeast University in 1990,
1991, and 1993. He was also a recipient of the 1989 Young Teacher Award of Fok
Ying Tung Education Foundation, State Education Commission of China.


# Learning from Satisfying Assignments Using Risk Minimization

Manjish Pal<EMAIL_ADDRESS>IIT-Kharagpur, India  Subham Pokhriyal
<EMAIL_ADDRESS>Chang Gung University, Taiwan

###### Abstract

In this paper we consider the problem of Learning from Satisfying Assignments
introduced by [1] of finding a distribution that is a close approximation to
the uniform distribution over the satisfying assignments of a low complexity
Boolean function $f$. In a later work [2] consider the same problem but with
the knowledge of some continuous distribution $D$ and the objective being to
estimate $D_{f}$, which is $D$ restricted to the satisfying assignments of an
unknown Boolean function $f$. We consider these problems from the point of
view of parameter estimation techniques in statistical machine learning and
prove similar results that are based on standard optimization algorithms for
Risk Minimization.

##  1 Introduction

_Computational Learning Theory_ is a field of theoretical computer science
that mostly deals with computational complexity theoretic aspects of machine
learning with its origins from works of Valiant [5] that introduced the notion
of Probably Approximately Correct (PAC) learnability. Learning of Boolean
Functions has become an important part of this topic with a variety of results
obtained over the past three decades or so. We consider the problem mentioned
in the previous sections of estimating the uniform distribution over the
satisfying assignments of an unknown Boolean function $f$ from the point of
view of standard parameter estimation techniques in Statistical Machine
Learning which are highly well established but not much used in the context of
Boolean function analysis. An extensive motivation and background for the
problem is mentioned in [1, 2]. The problem has been considered in another set
up in which we assume that $D$ is a known continuous distribution like
Gaussian, log-concave etc. and we are given i.i.d. samples from $D_{f}$, which
is defined as $D$ restricted to satisfying assignments of $f$ where $f$ is
again an unknown Boolean function, and we intend to estimate $D_{f}$. In these
works the authors prove both algorithmic and impossibility results depending
on the nature of $f$ (for eg. $f$ being a threshold function w.r.t. a low
degree polynomial). In this paper we restrict our attention to the original
version of the problem and hope that our ideas would translate to other case
as well.
Parameter estimation is a widely explored topic in machine learning with a
variety of techniques which have been developed over several years. The main
goal in this exploration is to approximate certain unknown distribution (from
which the data is assumed to be coming) by a distribution that depend on
certain parameters $\theta$; and use certain optimization procedures to find
the values of the parameters $\theta$. In this paper we consider the same
problem of learning the distribution of satisfying assignments but we use
standard parameter estimation techniques for solving this problem. More
formally, for an unknown distribution $P(x)$ chosen from an unknown
distribution $D$ we approximate it with $P_{\theta}(x)$ and compute the
parameters $\theta$ by maximizing the log likelihood function. It turns out
that this optimization is equivalent to minimizing the expected log loss,
which in turn is Risk Minimization under the distribution $D$. We use these
relations along with bounds that relate KL-divergence and $l_{1}$ distance to
get results similar and comparable with De et al.

##  2 Risk Minimization

Risk Minimization [4] is a statistical machine learning framework in which we
formally define the notion of error of a classifier. The risk minimization can
be defined by either w.r.t the given data i.e. Empirical Risk Minimization
(ERM) or it can be defined w.r.t the distribution from which the data is
assumed to be coming from. More formally, ERM for a hypothesis $h$ and a
dataset $S$ with $|S|=m$ is defined as

$L_{S}(h)=|\\{i\in[m]:h(x_{i})\neq y_{i}\\}|/m$

whereas the risk w.r.t. the distribution $D$ the risk is given as

$L_{S}(f,h)=\mathbb{P}_{x\sim D}[f(x)\neq h(x)]$

We will use these notions of risk minimization to revisit some already
established relation between Maximum Likelihood Estimator (MLE) and Empirical
Risk Minimization when we are dealing with a particular loss function. In
general when we have the loss function $l(\textbf{w},x)$ as

$l(\textbf{w},x)=-\log(P_{\textbf{w}}[x])$

where $P_{w}[x]$ is the parametric estimate of the true and unknown $P[x]$
(the probability of choosing $x$ from the unknown distribution $D$) and w is
the unknown parameter to be estimated. It is known that according to this
choice of loss function, the MLE is same as the Risk Minimization i.e.

$\displaystyle E[l(\textbf{w},x)]$ $\displaystyle=$
$\displaystyle-\large\sum_{x}P[x]\log P_{\textbf{w}}[x]$ $\displaystyle=$
$\displaystyle\underbrace{\large\sum_{x}P[x]\log\frac{P[x]}{P_{\textbf{w}}[x]}}+\large\sum_{x}P[x]\log\frac{1}{P[x]}$

We notice that the term in the above equation that is in braces is the
_Kullback Leibler Divergence_ of the two distributions $P[x]$ and
$P_{\textbf{w}}[x]$ which we will denote by $KL(P,P_{\textbf{w}})$.
Intuitively, minimizing the term $E[l(\textbf{w},x)]$ w.r.t. w leads to the KL
divergence being very small because the other term is independent of w. There
are two approaches that can be followed to minimize $E[l(\textbf{w},x)]$:
first is to use the celebrated _Expectation Maximization Algorithm_ which is
not of much use for us directly because the algorithm is well known to get
stuck at local optima. Instead we prefer the second approach that is based on
using the Stochastic Gradient Descent algorithm to serve our purpose that is
guaranteed to return a value of w that is close to the global optimum. In what
follows we describe the SGD algorithm and later describe how these results can
be used to get bounds similar to prior works in the context of learning from
the satisfying assignments of a Boolean function.

##  3 Stochastic Gradient Descent

Over the past few years, many learning algorithms for minimizing risk
functions have been proposed in the field of convex optimization. One of the
important algorithms for convex optimization that is widely used in machine
learning is called Stochastic Gradient Descent (SGD). In SGD we try to
minimize risk function $L_{D}(\textbf{w})$ in which we are not aware of the
unknown distribution $D$ and hence we can’t directly compute gradient for
$L_{D}(w)$ that is needed for standard gradient descent. The approach of SGD
is to initialize the gradient in random direction and use update rule of
gradient descent algorithm for optimization. A major component in the SGD
algorithm is the notion of the set of _subgradients_ that is denoted by
$\partial l(\textbf{w},z)$ that is mentioned in the following vanilla version
of SGD. For a detailed analysis of SGD algorithm in the context of machine
learning can be obtained from [4].

Input: Scalar $\eta>0$, integer $T>0$ ;

Initialization: $\textbf{w}^{(1)}=0$;

for  _$t=1;\ t\leq T;\ t=t+1$_ do

sample $x\sim D$ pick $v_{t}\in\partial l(\textbf{w}^{t},x)$ update
$\textbf{w}^{(t+1)}=\textbf{w}^{(t)}-\eta v_{t}$ ;

end for

Output $\bar{\textbf{w}}=\frac{1}{T}\sum_{t=1}^{T}\textbf{w}^{(t)}$;

Algorithm 1 SGD($X,\eta,T$)

###### Theorem 1

Consider a convex-Lipschitz-bounded learning problem with parameters $\rho$,
B. Then, for every $\epsilon>0$, if we run the SGD method for minimizing
$L_{D}{(\textbf{w})}$ with a number of iterations (i.e., number of examples)

$T\geq\frac{B^{2}\rho^{2}}{\epsilon^{2}}$

and with $\eta=\sqrt{\frac{B^{2}\rho^{2}}{\epsilon^{2}}}$, then the output of
SGD satisfies

$E[L_{D}(\bar{\textbf{w}})]\leq\min\limits_{\textbf{w}\in
H}L_{D}(\textbf{w})+\epsilon$.

##  4 Boolean Functions and Main Result

In this section we describe how our results relate with the results in the
context of the problem of learning from satisfying assignments of a Boolean
Function. In the Boolean Function setting we are given satisfying assignments
of an unknown Boolean function $f:\\{-1,1\\}^{n}\rightarrow\\{-1,1\\}$ and our
objective is to output a highly accurate estimate of $U_{f^{-1}(1)}$. In a
different version of the problem one is given a continuous distribution $D$
and i.i.d. samples of $D_{f}$ where $D_{f}$ is obtained by restricting $D$ to
satisfying assignments of an unknown Boolean function $f$. The objective again
is to get an accurate estimate of $D_{f}$. In those papers the authors measure
the distance of the estimated distribution and the actual distribution by
_variation distance_ that is also the $l_{1}$-norm of the two probability
distributions. In this paper we first estimate there distance by KL divergence
and then use the distortions bounds to translate the error bounds to the
$l_{1}$-norm.

###### Lemma 1

If $\bar{\textbf{w}}$ is the value returned by the algorithm then

$KL(P,P_{\bar{\textbf{w}}})\leq\epsilon\mbox{ and
}l_{1}(P,P_{\bar{\textbf{w}}})\leq\sqrt{2\epsilon}$

### Proof

Let $\min\limits_{\textbf{w}\in H}L_{D}(\textbf{w})=A(\textbf{w}^{\prime})$
and $\Delta=\sum_{x}P[x]\log\frac{1}{P[x]}$, Clearly
$KL(P,P_{\textbf{w}^{\prime}})=0$. Thus
$L_{D}(\bar{\textbf{w}})=KL(P,P_{\bar{\textbf{w}}})+\Delta$. Therefore,

$|A(\textbf{w}^{\prime})-L_{D}(\bar{\textbf{w}})|=|KL(P,P_{\textbf{w}^{\prime}})-KL(P,P_{\bar{\textbf{w}}})|$

From Theorem 1 we know that
$|A(\textbf{w}^{\prime})-L_{D}(\bar{\textbf{w}})|\leq\epsilon$. Hence,
$KL(P,P_{\bar{\textbf{w}}})\leq\epsilon$. From Pinsker Inequality we have
$l_{1}^{2}(P,P_{\bar{\textbf{w}}})\leq 2KL(P,P_{\bar{\textbf{w}}})$.

$l_{(}P,P_{\bar{\textbf{w}}})\leq\sqrt{2\epsilon}$

$\square$

Thus we have the following result,st $1-\delta$ a probability distribution
$P_{\textbf{w}}$ that is close to uniform distribution over $f^{-1}(1)$ by a
variation distance of $\epsilon$.

In our framework, we notice that for SGD to be executed we need to know an
exact functional form for
$L_{D}(\textbf{w})=E[l(\textbf{w},x)]=g(\langle\textbf{w},x\rangle)$ in order
to compute $\nabla(g)$ w.r.t. w. From the well known _No Free Lunch Theorem_
[4] we are aware that in order to achieve learnability of any target function
or distribution, we need to have some prior information about the class of
hypothesis we are restricting ourselves to. In the current set up, we
incorporate this information by assuming that $E[l(\textbf{w},x)]$ can be
expressed as $g(\langle\textbf{w},x\rangle)$ where $g$ is convex
$\rho$-Lipschitz function. For eg. we can choose $g$ to be any of $\sin$,
sigmoid, $\sqrt{x^{2}+5}$ which are 1-Lipschitz. Our assumption about
$L_{D}(\textbf{w})$ as $g(\langle\textbf{w},x\rangle)$ is similar to the
assumptions made by [1, 2] in which authors put a restrictions on $f$ as a low
degree threshold function. Although we have not been able to show a
mathematical equivalence between the assumptions; both the assumptions are
restricting the nature of optimization problem to certain extent.

Also w.l.o.g. we will assume that the value of $B$ used in the SGD is 1 i.e.
we are optimizing inside a unit sphere, $\|\textbf{w}\|=1$.

Retrieving $x$ given $\bar{\textbf{w}}$: Using the “reformulation” of
$L_{D}(\textbf{w})$ as $g(\langle\textbf{w},x\rangle)$, we are able retrieve
$\bar{\textbf{w}}$ and $b=L_{D}(\bar{\textbf{w}})$ but our aim was to sample
assignments $x$ that are from the desired distribution. For that we simply
pick an $\bar{x}\in\\{-1,1\\}^{n}$ and compute
$a=g(\langle\bar{\textbf{w}},\bar{x}\rangle)$ and compare with $b$. If
$|a-b|\leq\epsilon_{1}$ then we declare that $\bar{x}\in f^{-1}(1)$ otherwise
not.

Input: $X={x_{1},x_{2},\dots x_{k}}$ be the satisfying assignment of $f$;

$\bar{w}=SGD(X,B,\rho,\epsilon)$ Output : $P_{\bar{\textbf{w}}}$

Algorithm 2 Algorithm A

###### Theorem 2

The Algorithm $A$ returns a probability distribution $P_{\bar{\textbf{w}}}$
that is $\epsilon$ close to the unknown distribution $U_{f^{-1}(1)}$ w.r.t.
variation distance with probability atleast $1-\delta$ and runs in time in
$\Theta(\frac{n}{\epsilon^{2}}\log(\frac{1}{\delta}))$ where $n$ is the number
of variables of the Boolean function $f$.

### Proof

From Theorem 1 we know that one iteration of the SGD requires
$\Theta(\frac{B^{2}\rho^{2}}{\epsilon^{2}})$ and from the previous discussion
we know that $B=1$ and we can choose an $g(\langle\textbf{w},x\rangle)$ such
that it is $\rho$-lipschitz with $\rho=1$ for example $l$ can be choosen as
sigmoid, sine etc. Using Chernoff-Hoeffding [4] bounds we can infer that by
repeating the SGD algorithm independently $\log(\frac{1}{\delta})$ iterations,
we can success probability to $1-\delta$.

$\square$

##  5 Conclusion

We have shown that the Empirical Risk Minimization approach can lead us to
results that are comparable [2] for the problem of learning from satisfying
assignments [2]. The technique of machine learning models for parameter
estimation helps us to estimate the uniform distribution over $f^{-1}(1)$.
Since we know that stochastic gradient descent algorithm converges in
$\Theta(\frac{n}{\epsilon^{2}})$ iterations, We have been able to conclude
that our algorithm for estimating $U_{f^{-1}(1)}$ runs in
$\Theta(\frac{n}{\epsilon^{2}}\log(\frac{1}{\delta}))$ time and w.h.p. returns
a probability distribution that has low variation distance with
$U_{f^{-1}(1)}$.

## References

  * [1] A. Bhattacharya, P. Kar, M. Pal, “ _On Low Distortion Embeddings of Statistical Distance Measures into Low Dimensional Spaces_ ” $20^{th}$ Database and Expert Systems Applications (DEXA), 164-172 (2009).
  * [2] A. De, I. Diakonikolas, Rocco A. Servedio, “ _Learning from satisfying assignments_ ”, $26^{th}$ Symposium on Discrete Algorithms (SODA), 478-497 (2015).
  * [3] L. Canonne, A. De, Rocco A. Servedio, “ _Learning from satisfying assignments under continuous distributions_ ”, $31^{st}$ Symposium on Discrete Algorithms (SODA), 82-101 (2020).
  * [4] S. Ben-David, S. Shalev-Shwartz, “ _Understanding Machine Learning: From Theory to Algorithms_ ”, Cambridge University Press, (2014).
  * [5] L. Valiant, “ _A Theory of the Learnable_ ”, Communications of the ACM (11), 1134-1142 (1984).