# Sensing Aided OTFS Channel Estimation for
Massive MIMO Systems

Shuaifeng Jiang and Ahmed Alkhateeb
School of Electrical, Computer, and Energy Engineering - Arizona State
University
Emails: {s.jiang<EMAIL_ADDRESS>
###### Abstract

Orthogonal time frequency space (OTFS) modulation has the potential to enable
robust communications in highly-mobile scenarios. Estimating the channels for
OTFS systems, however, is associated with high pilot signaling overhead that
scales with the maximum delay and Doppler spreads. This becomes particularly
challenging for massive MIMO systems where the overhead also scales with the
number of antennas. An important observation however is that the delay,
Doppler, and angle of departure/arrival information are directly related to
the distance, velocity, and direction information of the mobile user and the
various scatterers in the environment. With this motivation, we propose to
leverage radar sensing to obtain this information about the mobile users and
scatterers in the environment and leverage it to aid the OTFS channel
estimation in massive MIMO systems.

As one approach to realize this vision, this paper formulates the OTFS channel
estimation problem in massive MIMO systems as a sparse recovery problem and
utilizes the radar sensing information to determine the support (locations of
the non-zero delay-Doppler taps). The proposed radar sensing aided sparse
recovery algorithm is evaluated based on an accurate 3D ray-tracing framework
with co-existing radar and communication data. The results show that the
developed sensing-aided solution consistently outperforms the standard sparse
recovery algorithms (that do not leverage radar sensing data) and leads to a
significant reduction in the pilot overhead, which highlights a promising
direction for OTFS based massive MIMO systems.

###### Index Terms:

OTFS, MIMO, channel estimation, radar, sensing-aided, ISAC, delay-Doppler
communications.

##  I Introduction

Orthogonal time frequency space (OTFS) modulation is a promising approach for
achieving robust communication in highly-mobile scenarios. This is thanks to
multiplexing the information bearing data into the nearly-constant channels in
the delay-Doppler domain [1, 2, 3]. Realizing these gains in massive MIMO
systems, however, is challenging. This is mainly due to the high downlink
pilot overhead which scales with the maximum delay spread and the maximum
Doppler spread of the channel and with the number of antennas at the
transmitter [3, 4]. This motivates the development of novel approaches that
enable the OTFS gains in massive MIMO systems, which is the objective of this
paper.

For massive MIMO-OTFS systems, the channels typically experience 3D sparsity
in the delay, Doppler, and angle dimensions [3, 5]. The channel sparsity in
the delay dimension is due to the limited number of dominant propagation paths
compared to the considered delay range, while the sparsity in the Doppler
dimension goes back to the small Doppler frequency of the dominant paths
compared to the system bandwidth. For the angle dimension, the channel
sparsity is a result of the usually small angle of departure (AoD) spread for
the propagation paths. Exploiting this channel sparsity in the three
dimensions, prior work used different compressive sensing (CS) approaches to
reduce the pilot overhead in estimating the OTFS massive MIMO channels [3, 5,
6, 7]. Despite its reduction, however, this channel acquisition overhead could
still be significant for large-scale MIMO systems, especially in scenarios
with large delay and Doppler spreads.

Contribution: The delay-Doppler domain channel has a close and direct relation
to the position, direction, and velocity of the mobile users and the various
scatterers in the surrounding environment. Based on that, in this paper, we
propose to leverage the radar sensing information about the users and the
surrounding environment to aid the OTFS channel estimation in massive MIMO
systems. This is further motivated by the potential integration of sensing and
communication in future systems at which the sensing information could
potentially be collected with negligible overhead on the wireless
communication resources [8, 9, 10, 11, 12]. The contributions of the paper can
be summarized as follows.

  * •

Proposing a novel approach that utilizes the radar sensing information at the
basestation to facilitate the massive MIMO OTFS channel estimation with a
significant reduction in the pilot overhead.

  * •

Developing a sensing framework that infers the delay, Doppler, and the AoD of
the communication channel paths using information collected from the radar
signals.

  * •

Designing an orthogonal matching pursuit (OMP) based algorithm that utilizes
the extracted propagation delay, Doppler frequency, and AoD to improve the
sparse OTFS channel recovery performance.

  * •

Developing a new simulation framework with co-existing wireless communication
and radar sensing data and adopting it to evaluate the performance of the
proposed sensing-aided OTFS channel estimation approach.

Simulation results show that the proposed sensing-aided OTFS channel
estimation approach consistently outperforms the conventional sparse recovery
algorithms. Specifically, the proposed approach can achieve similar channel
estimation normalized mean square error (NMSE) performance with $5$dB lower
SNR. Further, the proposed approach can lead to more than $50\%$ reduction in
the pilot/channel acquisition overhead without any degradation in the channel
estimation NMSE.

##  II System, Signal, and Channel Models

In this section, we first present the adopted system model. After that, we
introduce the discrete-time signal model and the channel model for the
considered MIMO-OTFS systems. Lastly, we introduce the adopted radar signal
model.

###  II-A System Model

TABLE I: Notation Adopted in the Paper Variable | Description
---|---
$M$, $N$ | number of transmit symbols in the delay and Doppler dimensions
$m$, $m^{\prime}$ | indices of delay taps
$n$, $n^{\prime}$ | indices of Doppler taps
$M_{p}$, $M_{g}$ | Lengths of the pilot and guard symbols in the delay dimension
$A$ | number of communication transmit antennas at the BS
$a$ | index of communication transmit antennas at the BS
$B$ | number of radar receive antennas at the BS
$b$ | index of radar receive antennas at the BS
$f_{c}$, $\Delta_{f}$, $\lambda$, $d$ | carrier frequency, subcarrier spacing, wavelength, and antenna spacing of the communication system
$f_{0}$, $S$, $\lambda_{\mathrm{r}}$, $d_{\mathrm{r}}$ | start frequency, slope, wavelength, and antenna spacing of the FMCW radar system
$L$ | number of communication propagation paths
$\alpha_{i}$, $\tau_{i}$, $\nu_{i}$, $\psi_{i}$ | complex gain, delay, Doppler frequency shift, and AoD of the $i$-th communication path
$J$ | number of detected radar propagation paths
$\tau^{p}_{j}$, $v_{j}$, $\theta^{p}_{j}$ | delay, Doppler velocity, and AoA of the $j$-th detected radar path
$q$ | index of discrete time
Figure 1: An illustration of the adopted system model. The BS exploits the
radar sensing data to aid the MIMO-OTFS channel estimation.

As shown in Fig. 1, we consider a communication system where a BS serves a
single highly mobile UE using a carrier frequency $f_{c}$. The BS employs a
uniform linear array (ULA) of $A$ antennas to communicate with the UE. The BS
is also equipped with an FMCW radar operating on the start frequency $f_{0}$.
The FMCW radar collects sensing information about the surrounding
communication environment, which is then utilized to aid the downlink channel
estimation. For simplicity, we assume that the UE is equipped with a single
antenna. The proposed sensing-aided OTFS channel estimation in this paper,
however, can be extended to systems wtih the multi-antenna UEs.

###  II-B OTFS Communication Signal Model

For the downlink, the BS applies OTFS modulation to prepare the transmitted
data. This OTFS modulation is performed as follows. First, $M\times N$ data
symbols are arranged into a two-dimensional OTFS frame
${{\mathbf{X}}}^{\mathrm{DD}}\in{\mathbb{C}}^{M\times N}$ in the delay-Doppler
domain. After that, the ${{\mathbf{X}}}^{\mathrm{DD}}$ is transformed into the
time-frequency domain signal
${{\mathbf{X}}}^{\mathrm{FT}}\in{\mathbb{C}}^{M\times N}$ as

$\displaystyle{{\mathbf{X}}}^{\mathrm{FT}}={\mathbf{W}}^{\mathrm{t}x}\odot\left({{\mathbf{F}}}_{M}{{\mathbf{X}}}^{\mathrm{DD}}{{\mathbf{F}}}_{N}^{\mathrm{H}}\right),$
(1)

where ${\bf F}_{M}$ and ${\bf F}_{N}$ denote the $M$-point and $N$-point
discrete Fourier transformation (DFT) matrices, and
${\mathbf{W}}^{\mathrm{t}x}$ is a windowing function111In the general case
where the delay/Doppler values do not belong exactly to the integer
delay/Doppler bins, it becomes interesting to optimize the windowing matrix to
suppress inter-Doppler interference [13].. The operation $\odot$ denotes the
point-wise multiplication. In this paper, we assume that the
${\mathbf{W}}^{\mathrm{t}x}$ adopts rectangular windowing [14]. That is,
${\mathbf{W}}^{\mathrm{t}x}$ is an all-one matrix and therefore can be
omitted. The two-dimensional time-frequency domain signal
${{\mathbf{X}}}^{\mathrm{FT}}$ is then converted into a two-dimensional delay-
time domain signal ${{\mathbf{X}}}^{\mathrm{DT}}$ as

$\displaystyle{{\mathbf{X}}}^{\mathrm{DT}}={{\mathbf{F}}}_{M}^{\mathrm{H}}{{\mathbf{X}}}^{\mathrm{FT}}.$
(2)

With ${{\mathbf{X}}}^{\mathrm{DT}}=[{\mathbf{x}}_{1},\ldots{\mathbf{x}}_{N}]$,
each column ${\mathbf{x}}_{i}$ can be regarded as a time-domain OFDM symbol of
$M$ subcarriers and ${{\mathbf{X}}}^{\mathrm{DT}}$ consists of $N$ consecutive
OFDM symbols. To avoid inter-symbol interference, the cyclic prefix (CP) is
added to each OFDM symbol.

$\displaystyle{\mathbf{S}}={\mathbf{A}}_{\mathrm{CP}}{{\mathbf{X}}}^{\mathrm{DT}},$
(3)

where ${\mathbf{A}}_{\mathrm{CP}}\in{\mathbb{R}}^{(M+N_{\mathrm{CP}})\times
M}$ is the CP addition matrix. Finally, the discrete-time time-domain baseband
transmit signal can be obtained as

$\displaystyle{\mathbf{s}}=\mathrm{vec}({\mathbf{S}}),$ (4)

where ${\mathbf{s}}\in{\mathbb{R}}^{(M+N_{\mathrm{CP}})N\times 1}$ is the
concatenation of all the columns in ${\mathbf{S}}$ with $\mathrm{vec}(\cdot)$
representing the vectorization operation.

Figure 2: An illustration of the adopted signal models for both the
communication and radar systems.

####  II-B1 OTFS Demodulation

At the user, the discrete-time time-domain basedband receive signal can be
denoted by ${\mathbf{r}}\in{\mathbb{R}}^{(M+N_{\mathrm{CP}})N\times 1}$. In
OTFS demodulation, the ${\mathbf{r}}$ is first rearranged into a two-
dimensional signal ${\mathbf{R}}$, which is given by

$\displaystyle{\mathbf{R}}=\mathrm{invec}({\mathbf{r}}),$ (5)

where $\mathrm{invec}(\cdot)$ denotes the inverse operation of
$\mathrm{vec}(\cdot)$, i.e.,
${\mathbf{A}}=\mathrm{invec}(\mathrm{vec}({\mathbf{A}}))$. After that, the
delay-time domain receive signal ${\mathbf{Y}}^{\mathrm{DT}}$ can be obtained
by

$\displaystyle{\mathbf{Y}}^{\mathrm{DT}}={\mathbf{R}}_{\mathrm{CP}}{{\mathbf{R}}},$
(6)

where ${\mathbf{R}}_{\mathrm{CP}}\in{\mathbb{R}}^{M\times(M+N_{\mathrm{CP}})}$
is the CP removal matrix. The time-frequency domain receive signal can then be
written as

$\displaystyle{\mathbf{Y}}^{\mathrm{FT}}={\mathbf{W}}^{\mathrm{rx}}\odot\left({\mathbf{F}}_{M}{\mathbf{Y}}^{\mathrm{DT}}\right),$
(7)

where ${\mathbf{W}}^{\mathrm{rx}}$ is a windowing matrix, and we also adopt
the all-one matrix for ${\mathbf{W}}^{\mathrm{rx}}$. Finally, given
${\mathbf{Y}}^{\mathrm{FT}}$, the delay-Doppler receive signal
${{\mathbf{Y}}}^{\mathrm{DD}}$ is obtained by

$\displaystyle{{\mathbf{Y}}}^{\mathrm{DD}}=\left({{\mathbf{F}}}_{M}^{\mathrm{H}}{{\mathbf{Y}}}^{\mathrm{FT}}{{\mathbf{F}}}_{N}\right).$
(8)

###  II-C OTFS Channel Model

We consider a wide-band time-varying channel model incorporating $L$
propagation paths. Let $\alpha_{i}$, $\tau_{i}$, $\nu_{i}$, and $\psi_{i}$
denote the complex gain, the delay, the Doppler frequency shift, and the angle
of departure (AoD) associated with the $i$-th ($i\in[1,\ldots,L$]) path,
respectively. Let $M\Delta f$ denote the bandwidth of the OTFS system, and
$NT$ denote the time duration of one OTFS frame. The delay tap index $m_{i}$
and the Doppler tap index $n_{i}$ corresponding to the $i$-th path can then be
written as

$m_{i}=round(M\Delta f\tau_{i})$ (9a) $n_{i}=round(NT\nu_{i}),$ (9b)

where $round(\cdot)$ denotes the rounding operation. Note that, for
simplicity, this paper only considers the integer delay and Doppler cases,
i.e., $m_{i}\in{\mathbb{Z}}$ and $n_{i}\in{\mathbb{Z}}$. The discrete delay-
time baseband channel of the $a$-th ($a\in[1,\ldots,A]$) transmit antenna can
then be written as

$\displaystyle
h[m,q,a]=\sum_{i=1}^{L}\alpha_{i}z^{n_{i}(q-m)}e^{-j2\pi\frac{d}{\lambda}(a-1)\psi_{i}}\mathrm{sinc}(m-m_{i}),$
(10)

where $m\in[0,\ldots,M+N_{\mathrm{CP}}-1]$ denotes the index of the delay tap,
$q\in[0,\ldots,N(M+N_{\mathrm{CP}})-1]$ denotes the index of the time tap, and
$z=\frac{j2\pi}{N(M+N_{\mathrm{CP}})}$. With this channel model, the receive
signal at the user can be written as

$\displaystyle r[q]=\sum_{a=1}^{A}\sum_{m=0}^{M-1}h[m,q,n]s_{a}[q-m]+v[q]$
(11)

where $r[q]$ denotes the $q$-th element in
${\mathbf{r}}\in{\mathbb{R}}^{(M+N_{\mathrm{CP}})N\times 1}$, and $s_{a}[q-m]$
denotes the $(q-m)$-th symbol transmitted by the $a$-th transmit antenna. The
noise at the $q$-th time tap is denoted by $v[q]$.

OTFS Delay-Doppler Domain Channel Effect: Let $Y_{m,n}^{\mathrm{DD}}$ denote
the element at the $m$-th row and the $n$-th column in
${\mathbf{Y}}^{\mathrm{DD}}$, and $X_{m^{\prime},n^{\prime},a}^{\mathrm{DD}}$
denote the element at the $m^{\prime}$-th row and the $n^{\prime}$-th column
in ${\mathbf{X}}^{\mathrm{DD}}$ transmitted by the $a$-th antenna. Then, the
input-output relation between the delay-Doppler domain signal
${\mathbf{X}}^{\mathrm{DD}}$ in (1) and the ${\mathbf{Y}}^{\mathrm{DD}}$ in
(8) can be written as

$\displaystyle Y_{m,n}^{\mathrm{DD}}$
$\displaystyle=\sum_{a=1}^{A}\sum_{m^{\prime}=0}^{M-1}\sum_{n^{\prime}=-N/2}^{N/2-1}X_{m^{\prime},n^{\prime},a}^{\mathrm{DD}}H_{m-m^{\prime},n-n^{\prime},a}^{\mathrm{DD}}\,z^{l\left(n-n^{\prime}\right)_{N}}$
$\displaystyle+V_{m,n}^{\mathrm{DD}},$ (12)

where $V_{m,n}^{\mathrm{DD}}$ is the noise in the delay-Doppler domain. Note
that $(n)_{N}$ denotes the modulo operation. The $H_{m,n,a}^{\mathrm{DD}}$ in
(II-C) is the delay-Doppler domain channel coefficient corresponding to the
$m$-th delay tap, $n$-th Doppler tap, and the $a$-th transmit antenna, which
satisfies

$\displaystyle
H_{m,n,a}^{\mathrm{DD}}=\sum_{i=1}^{L}\alpha_{i}\delta\left(m_{i}-(m)_{M},n_{i}-(n)_{N}\right)e^{-j2\pi\frac{d}{\lambda}(a-1)\psi_{i}}.$
(13)

###  II-D Radar Signal Model

In our system model, the BS is equipped with an FMCW radar. For simplicity, we
assume that the radar has a single transmit antenna and $B$ receive antennas.
However, our radar signal model and processing can be generalized to MIMO
radars. Since the sensing targets of our interest are usually located away
from the radar, we can assume that they are in the far-field region of the
radar.

The function of this radar is to obtain sensing information about the
surrounding environment. In particular, the FMCW radar first emits chirp
signals into the surrounding environment. These chirp signals interact with
the surrounding objects and are reflected/scattered back to the radar. The
received chirp signals are then processed to extract the sensing information.
Mathematically, a transmitted radar chirp signal can be expressed as [15]

$s_{\text{chirp }}(t)=\begin{cases}\cos\left(2\pi f_{0}t+\pi
St^{2}\right)&\text{ if }0\leq t\leq T_{c}\\\ 0&\text{ otherwise
}\end{cases},$ (14)

where $f_{0}$, $S$, and $T_{c}$ represent the start frequency, the slope, and
the duration of the chirp signal, respectively. Note that the frequency of the
chirp signal linearly increases from $f_{0}$ to $f_{0}+ST_{c}$ during the
transmission. The effective bandwidth of the chirp signal is given by
$B_{\mathrm{w}}=ST_{c}$.

To be able to obtain the Doppler/velocity information of the surrounding
objects, the radar typically transmits $N_{\text{loop}}$ identical chirp
signals. These identical chirp signals form a radar frame. The transmitted
signal in one radar frame can then be written as

$s_{\text{frame}}(t)=\sum_{n=0}^{N_{\text{loop}}-1}s_{\text{chirp}}\left(t-nT_{p}\right),\quad
0\leq t\leq T_{f},$ (15)

where $T_{p}$ denotes the chirp repetition time, and $T_{f}$ denotes the radar
frame duration. Note that $T_{c}\leq T_{p}$ is satisfied so that the chirp
signals are non-overlapping. After the transmitted signal is
reflected/scattered back and captured by the receive antennas, the received
signal at each antenna is mixed with the transmitted signal using a quadrature
mixer. The outputs of the quadrature mixer are the in-phase and quadrature
components. The in-phase and quadrature components are then passed through a
low-pass filter to obtain the so-called intermediate frequency (IF) signal.
Assuming $W$ ideal point reflectors to be the sensing targets, the IF signal
corresponding to a single chirp at the $b$-th ($b\in[1,\ldots,B]$) antenna can
be written as

$\displaystyle r_{\text{chirp}}^{b}(t)$ $\displaystyle\approx$
$\displaystyle\sum_{w=1}^{W}\beta_{w}\exp(j2\pi f_{0}\tau_{w}-j\pi
S\tau_{w}^{2})\exp(j2\pi
S\tau_{w}t)e^{-j2\pi\frac{d_{\mathrm{r}}}{\lambda_{\mathrm{r}}}(b-1)}$ (16)
$\displaystyle\approx$ $\displaystyle\sum_{w=1}^{W}\beta_{w}\exp(j2\pi
f_{0}\tau_{w})\exp(j2\pi
S\tau_{w}t)e^{-j2\pi\frac{d_{\mathrm{r}}}{\lambda_{\mathrm{r}}}(b-1)},$ (17)

where $d_{\mathrm{r}}$ and $\lambda_{\mathrm{r}}$ are the wavelength and the
antenna spacing of the radar. The $\beta$ is the complex gain that depends on
the radar cross section (RCS), the transmit power, and the path-loss.
$\tau_{w}=\frac{2D_{w}}{c}$ is the round-trip propagation delay with $D_{w}$
denoting the propagation distance between the radar and $w$-th ideal point
reflector. $c$ represents the speed of light. In (16), we neglect the receive
signals that have interacted with multiple sensing targets since they have
smaller power. The approximation in (17) holds when $S\tau\ll f_{0}$.

The receive signal at each antenna $r^{b}_{\text{chirp}}(t)$ is then sampled
by ADCs with the sampling rate of $f_{s}$. Let $N_{s}$ denote the number of
complex ADC samples for each chirp. Note that each receive antenna has an
independent receive chain including a quadrature mixer, low-pass filter, and
ADCs. Finally, the ADC samples corresponding to $N_{\text{loop}}$ chirps and
$B$ receive antennas are collected to form a radar data frame denoted by
${\mathbf{X}}\in{\mathbb{C}}^{N_{s}\times N_{\text{loop}}\times B}$.

##  III MIMO-OTFS Downlink Channel Estimation

Section II-B presented the OTFS signal model. Particularly, the delay-Doppler
channel is given by (13), and the delay-Doppler domain input-output relation
is given by (II-C). In this section, we first present the adopted delay-
Doppler domain OTFS frame structure. After that, we introduce the formulation
of the delay-Doppler domain channel estimation problem.

###  III-A OTFS Frame Structure

Fig. 3 shows the adopted pilot OTFS frame structure. The pilot and data
symbols co-exist in the same OTFS frame. For simplicity, the data and pilot
symbols are assumed to span across the entire Doppler dimension. The zero-
power guard symbols are used to separate the pilot and data symbols along the
delay dimension. The lengths of the pilot and guard symbols along the delay
dimensions are $M_{p}$ and $M_{g}$ respectively. With $M_{\mathrm{max}}$
denoting the maximum delay spread, the length of the guard symbols along the
delay dimension is assumed to satisfy $M_{\mathrm{g}}\geq M_{\mathrm{max}}$.
This way, the guard symbols can guarantee that the data symbols do not
interfere with the pilot symbols. Note that all the transmit antennas transmit
pilot signals on the pilot resources simultaneously. The pilot overhead of the
adopted OTFS frame structure can be described by the pilot overhead ratio
$\eta=\frac{M_{p}}{M}$. A good pilot design/channel estimation strategy will
attempt to minimize the pilot overhead ratio.

Figure 3: This figure shows the adopted structure of the delay-Doppler frame
with the data, pilot, and guard symbols.

(a) LoS and NLoS communication paths

(b) Backscattering radar paths

(c) Radar transmit and receive paths could be different

Figure 4: This figure illustrates an example of the propagation paths for the
radar and the downlink communication systems. The transmitted radar signals
could be backscattered to the receiver through the same transmit paths or
reflected and received from different directions.

###  III-B MIMO-OTFS Downlink Channel Estimation: A Sparse Recovery
Formulation

Let $x_{m,n,a}$ denote the training pilots in the delay-Doppler domain
transmitted by the $a$-th antenna, where $m\in[0,\ldots,M_{p}-1]$ is the pilot
index along the delay dimension and $n\in[-\frac{N}{2},\ldots,\frac{N}{2}-1]$
is the pilot index along the Doppler dimension. Derived from (II-C), the
received signal $y_{m,n}$ can be written as

$\displaystyle y_{m,n}$ $\displaystyle=$
$\displaystyle\sum_{a=1}^{A}\sum_{m^{\prime}=0}^{M_{\mathrm{g}}-1}\sum_{n^{\prime}=-N/2}^{N/2-1}z^{n\left(m-m^{\prime}\right)_{M}}H_{m^{\prime},n^{\prime},a}^{\mathrm{DD}}\,x_{(m-m^{\prime})_{M},(n-n^{\prime})_{N},a}$
$\displaystyle+v_{m,n}.$ (18)

Next, the pilot symbols $x_{m,n,a}$, delay-Doppler channel coefficients
$H_{m,n,a}^{\mathrm{DD}}$, and received pilot $y_{m,n}$ symbols are
rearranged, and (III-B) is rewritten as a matrix-vector multiplication to form
a sparse problem.

Let ${\mathbf{Z}}\in{\mathbb{C}}^{M_{p}N\times AM_{\mathrm{g}}N}$ with the
$(mN+n+N/2+1,A(m^{\prime}N+n^{\prime}+N/2)+a)$-th element being
$z^{n\left(m-m^{\prime}\right)_{M}}$. Let
${\mathbf{P}}\in{\mathbb{C}}^{M_{p}N\times AM_{\mathrm{g}}N}$ with the
$(mN+n+N/2+1,A(m^{\prime}N+n^{\prime}+N/2)+a)$-th element being
$x_{(m-m^{\prime})_{M},(n-n^{\prime})_{N},a}$. Then (III-B) can be re-written
as

$\displaystyle{\mathbf{y}}=\left({\mathbf{Z}}\odot{\mathbf{P}}\right){\mathbf{h}}+{\mathbf{v}},$
(19)

where ${\mathbf{y}}\in{\mathbb{C}}^{M_{p}N\times 1}$ with the
$(mN+n+N/2+1)$-th element being $y_{m,n}$, and
${\mathbf{h}}\in{\mathbb{C}}^{AM_{\mathrm{g}}N\times 1}$ with the
$(A(m^{\prime}N+n^{\prime}+N/2)+a)$-th element being
$H_{m^{\prime},n^{\prime},a}^{\mathrm{DD}}$.

Let ${\bf\Psi}={\mathbf{Z}}\odot{\mathbf{P}}$, then following [3], the sparse
formulation is given by

$\displaystyle{\mathbf{y}}={\bf\Psi}{\mathbf{h}}+{\mathbf{v}}.$ (20)

Note that each element in ${\mathbf{h}}$ corresponds to a delay and Doppler
tap in the delay-Doppler domain, and ${\mathbf{h}}$ is a sparse vector due to
the sparsity of the delay-Doppler channel. According to [16], the number of
dominant propagation path is limited (e.g. 6 paths). Therefore, the delay-
Doppler channel is sparse in the delay dimension. The delay-Doppler channel is
also sparse in the Doppler dimension since the Doppler frequency of a path is
usually much smaller than the system bandwidth, and only the near-zero Doppler
taps have relatively high power. Moreover, the transmit antenna domain can be
further converted to the virtual angle domain to increase the sparsity of the
${\mathbf{h}}$. Let
${\mathbf{A}}={\mathbf{I}}_{M_{\mathrm{g}}N}\otimes{\mathbf{F}}_{A}$, with
$\otimes$ denoting the Kronecker product, and ${\mathbf{I}}$ denoting the
identity matrix. The angle domain sparse formulation is then given by

$\displaystyle{\mathbf{y}}=\tilde{\bf\Psi}\tilde{{\mathbf{h}}}+{\mathbf{v}},$
(21)

where $\tilde{\bf\Psi}=\bf\Psi{\mathbf{A}}^{\mathrm{H}}$ and
$\tilde{{\mathbf{h}}}={\mathbf{A}}{\mathbf{h}}$. Utilizing the sparsity of the
delay-Doppler domain channel [3], the MIMO-OTFS channel estimation can be
achieved by solving (20) or (21) using conventional CS recovery algorithms
such as basis pursuit [17] and matching pursuit [18]. Next, we discuss the key
idea of utilizing sensing to guide the OTFS-based MIMO channel estimation.

##  IV Sensing Aided Delay-Doppler Channel Estimation

The convergence of communication, sensing, and localization is considered one
of the key features in 6G and beyond [19]. The sensing and localization
capabilities may not just support new interesting applications such as AR/VR
and autonomous driving, but also provide rich information and awareness about
the surrounding environment to aid the communication systems. Furthermore, as
will be explained in Section IV-A, this sensing information can be
particularly meaningful and beneficial for delay-Doppler communication
systems. To that end, we propose to utilize the sensing capability at the BS
to aid the MIMO-OTFS channel estimation problem.

Figure 5: This figure presents the adopted radar processing. The radar data
frame is processed through clutter removal, 3D-DFT, and peak detection to
extract the radar propagation paths.

In this section, we first briefly introduce the key idea of sensing-aided
delay-Doppler communications. After that, we discuss the relationship between
communication and radar channels. Then, we explain the adopted radar
processing to extract sensing information. Last, we elaborate on the proposed
sensing-aided channel estimation.

###  IV-A Key Idea: Sensing Aided Delay-Doppler Communications

The delay-Doppler domain channel has a close and direct relation to the
direction/position of the UEs and the geometry of the surrounding environment.
In particular, as shown in (13), each tap of the delay-Doppler domain channel
corresponds to an existing propagation path of a certain delay and a certain
Doppler frequency shift. This motivates utilizing the sensing capability to
obtain prior information about the communication channel and improve delay-
Doppler communications. For instance, using the sensing capability, the BS can
obtain/estimate the relative position and velocity of the UE, and also the
positions and shapes of the reflecting/scattering objects in the surrounding
environment. With this sensing information, the BS can infer the potential
propagation path parameters: the delay, the Doppler velocity, and the AoD/AoA.
This prior knowledge of the propagation paths can help the delay-Doppler
communications in several ways: (i) guiding or even bypassing channel
estimation, (ii) improving channel feedback, and (iii) enabling proactive
resource allocation.

In this paper, we are particularly interested in exploiting radar at the BS to
obtain sensing information. Compared with other sensory options, radars have
the following advantage. (i) Recently, joint communication and radar systems
have gained increasing interest [9, 20]. Being able to share the hardware and
software resources with the communication systems can make the radar a more
available and low-cost sensing solution. (ii) Since the radar sensing signals
are also transmitted through the wireless channel, the sensing information
extracted from radars can have a closer and more straightforward relation to
the wireless communication channels. (iii) Radar sensing can potentially
obtain NLoS sensing information, which may not be available using other
sensors.

Next, we discuss the relationship between the communication channel and the
radar channel.

###  IV-B Relation Between Communication and Radar Channels

In Fig. 4, we present a scenario incorporating a BS, a UE, and a static
reflector. Fig. 4(a) shows the line-of-sight (LoS) path and the non-line-of-
sight (NLoS) paths of communication and radar channels. In Fig. 4(b), two sets
of radar propagation paths resulting from backscattering are presented. In
this backscattering case, the radar propagation paths are closely related to
the communication propagation paths shown by Fig. 4(a) in terms of the
propagation delay, the Doppler velocity, and the AoD/AoA. Note that, the radar
signal is likely to be reflected by other components of the UE instead of the
UE antenna. Therefore, the communication paths in Fig. 4(b) does not align
perfectly with the radar paths in Fig. 4(a). However, when the distance
between the BS and the UE is much greater than the size of the UE, the
relation between the communication and radar paths can be approximated as
follows.

  * •

The propagation delays and Doppler velocities of the radar paths are
approximately twice of those of the corresponding communication paths.

  * •

The AoDs/AoAs of radar paths are approximately the same as the AoDs of the
corresponding communication paths.

Apart from the backscattering cases shown in Fig. 4(b), the radar transmit and
receive propagation paths may be completely different. For instance, as shown
in both Fig. 4(c), the radar transmit and receive signals propagate through
the LoS and NLoS paths, respectively. As a result, the delay, the Doppler
velocity, and the AoA/AoD of the radar propagation paths are not directly
related to one communication path. Although the radar propagation paths shown
in Fig. 4(c) can lead to interference in the radar receive signals, they can
be identified and filtered by exploiting the fact that the AoD and AoA are
different. This can be potentially achieved when the radar has the transmit
beamforming capability. However, this case shown in Fig. 4(c) is not handled
by this paper.

###  IV-C Radar Processing

From the captured radar data frame ${\mathbf{X}}$, we aim to extract the
propagation delay, Doppler velocity, and angle of arrival (AoA) of the radar
propagation paths corresponding to the UE. The proposed radar processing is
illustrated in Fig. 5.

Cutter removal: Since we are interested in high-mobility scenarios, the
clutter removal is first applied to the radar data frame ${\mathbf{X}}$ to
remove the radar signals corresponding to static objects. The clutter removal
is mathematically given by

$X^{r}_{m,n,b}=X_{m,n,b}-\frac{1}{N_{\text{loop}}}\sum_{n=1}^{N_{\text{loop}}}X_{m,n,b},$
(22)

where ${\mathbf{X}}^{r}$ denotes the radar data frame after clutter removal.
$X_{m,n,b}$ and $X^{r}_{m,n,b}$ index the elements from ${\mathbf{X}}$ and
${\mathbf{X}}^{r}$ according to the indices $m$, $n$, and $b$.

3D-DFT: After the clutter removal, we sequentially apply three DFTs on
${\mathbf{X}}^{r}$ to extract the range, Doppler, and angle information
corresponding to the moving objects in the radar data frame.

  * •

Range DFT: we first apply the DFT on the ADC samples dimension of
${\mathbf{X}}^{r}$. This converts the chirp signal into the frequency domain.
As can be observed from (17), the frequency of the received chirp signal is
proportional to the propagation delay.

  * •

Doppler DFT: After the range DFT, we apply the Doppler DFT along the second
dimension of the ${\mathbf{X}}^{r}$. The Doppler DFT obtains the phase shift
across the consecutive chirp signals. From these phase shifts, the Doppler
velocity of the moving objects can be extracted.

  * •

Angle DFT: The angle DFT operation is performed on the radar virtual antenna
dimension, which extracts the angular information of the moving objects. Note
that zero-paddings can be applied before the angle DFT for more accurate
angular estimation.

With $\text{DFT}_{\text{3D}}$ denoting the three DFT operations on the range,
Doppler, and angle dimensions, the radar 3D-heatmap can be obtained by

$\displaystyle{\mathbf{X}}^{\text{3D}}=|\text{DFT}_{\text{3D}}\left({\mathbf{X}}^{r}\right)|,$
(23)

where the absolute operation is applied element-wise.

Peak detection: To detect the peaks in the 3D-heatmap
${\mathbf{X}}^{\text{3D}}$, we employ the constant rate false alarm rate
(CFAR) algorithm [21]. Since the 3D-CFAR is computationally expensive, we
first apply a 2D-CFAR on the range-angle heatmap ${\mathbf{X}}^{\text{RA}}$.
The range-angle heatmap can be obtained by averaging the Doppler dimension of
${\mathbf{X}}^{\text{3D}}$ as shown by

$\displaystyle
X^{\text{RA}}_{m,b}=\frac{1}{N_{\text{loop}}}\sum_{n=1}^{N_{\text{loop}}}X^{\text{3D}}_{m,n,b}.$
(24)

After that, a non-maximum suppression is applied to the peaks detected by the
2D-CFAR to deal with the power leakage along the range and angle dimensions.
Then we apply a 1D-CFAR on the Doppler dimensions of
${\mathbf{X}}^{\text{3D}}$ according to the peaks detected on the range-angle
heatmap. The non-maximum suppression is also employed after the 1D-CFAR.

After the peak detection, the propagation delay, Doppler velocity, and AoA of
each peak is extracted. Let $J$ denote the number of detected peaks from the
radar peak detection, we can obtain
$\mathcal{P}=\\{(\tau^{p}_{1},v^{p}_{1},\theta^{p}_{1}),\ldots,(\tau^{p}_{J},v^{p}_{J},\theta^{p}_{J})\\}$,
where $\tau^{p}_{j}$, $v^{p}_{j}$, $\theta^{p}_{j}$ denote the propagation
delay, Doppler velocity, and AoA of the $j$-th $(j=[1,\ldots,J])$ peak,
respectively.

###  IV-D Sparse Recovery with Radar Sensing Information

To utilize the sensing information obtained from the radar to MIMO-OTFS
channel estimation, we first convert each peak in $\mathcal{P}$ to the index
of angle domain OTFS channel $\tilde{{\mathbf{h}}}$ according to the
propagation delay, Doppler velocity, and AoA of the peak. The propagation
delay of the radar-detected propagation paths is normalized as follows:

$\tilde{\tau}^{p}_{j}=\frac{\tau^{p}_{j}-\min_{j}\tau^{p}_{j}}{2}.$ (25)

The above normalization is based on that the shortest radar propagation path
can be detected as a peak in $\mathcal{P}$. This is a reasonable assumption
since the shortest propagation path is likely to be one of the strongest
paths. To convert the Doppler velocity of each detected peak to Doppler
frequency, the Doppler velocity is multiplied by the carrier frequency of the
communication system as shown by

Algorithm 1 OMP Algorithm using Radar Sensing

1: Received pilot signal ${\mathbf{y}}$ sensing matrix $\tilde{\bf\Psi}$
receive radar data frame ${\mathbf{X}}$ threshold $\rho$

2:recovered MIMO-OTFS channel $\tilde{{\mathbf{h}}}$

3:Obtain $\mathcal{S}^{r}$ from ${\mathbf{X}}$ using radar processing

4:Initialization $S^{(0)}=\mathcal{S}^{r}$, $\tilde{{\mathbf{h}}}^{(0)}={\bf
0}$, $iter=1$,
${\mathbf{b}}={\mathbf{y}}-\tilde{\bf\Psi}\tilde{{\mathbf{h}}}^{(0)}$

5:while $|\mathcal{S}|<\rho\cdot|\mathcal{S}_{r}|$ do

6: ${\mathbf{z}}=\tilde{\bf\Psi}^{H}{\mathbf{b}}$

7: $\mathcal{S}\leftarrow\mathcal{S}\cup\arg\max_{j}z[j]^{(iter)}$

8:
$\tilde{{\mathbf{h}}}^{(iter)}_{S}=\tilde{\bf\Psi}_{S}^{\dagger}{\mathbf{y}}$,
$\tilde{{\mathbf{h}}}^{(iter)}_{S^{c}}=0$

9: ${\mathbf{b}}={\mathbf{y}}-\tilde{\bf\Psi}\tilde{{\mathbf{h}}}^{(iter)}$

10: $iter=iter+1$

11:end while

Figure 6: This figure shows the developed 3D ray-tracing scenario. The BS is
deployed along the horizontal street, and the UE is randomly dropped (in
different locations for the different realizations) within the area defined by
the red rectangle.

$\tilde{\nu}^{p}_{j}=\frac{v^{p}_{j}}{2}\cdot f_{c}.$ (26)

The normalized propagation delay $\tilde{\tau}^{p}_{j}$ and Doppler frequency
$\tilde{\nu}^{p}_{j}$ are converted to delay tap and Doppler tap indices
$m^{p}_{j}$ and $n^{p}_{j}$ of the communication channel using (9),
respectively. The AoA $\theta^{p}_{j}$ of the radar detected peaks are
converted to the row indices $f_{j}$ of ${\mathbf{F}}_{A}$ according to the
beam steering angle of the row vectors in ${\mathbf{F}}_{A}$. Mathematically,
$f_{j}$ is given by

$\displaystyle f_{j}=$ $\displaystyle\underset{f_{j}}{\arg\max}\
\bigg{|}{\mathbf{f}}_{f_{j}}[1,e^{-j2\pi\frac{d}{\lambda}\cos\theta^{p}_{j}},\ldots,e^{-j2\pi\frac{d}{\lambda}(A-1)\cos\theta^{p}_{j}}]^{T}\bigg{|}^{2},$
(27)

where ${\mathbf{f}}_{f}$ denotes the $f$-th row of ${\mathbf{F}}_{A}$.
Finally, the $\mathcal{P}$ is converted to set
$\mathcal{S}_{r}=\\{t_{1},\ldots,t_{J}\\}$, where $t_{j}$ is the index of
$\tilde{{\mathbf{h}}}$ corresponding to the $j$-th detected peak in
$\mathcal{P}$. $t_{j}$ can be obtained by

$t_{j}=f_{j}+(A-1)m^{p}_{j}+(A-1)(M_{g}-1)(n^{p}_{j}+\frac{N}{2}).$ (28)

After that, the $\mathcal{S}_{r}$ is sent to the UE over the control channel.

At the UE side, we propose to utilize the radar extracted sensing information
$\mathcal{S}_{r}$ to improve sparse channel recovery. The proposed sparse
channel recovery approach is presented in Algorithm 1, which is a modification
of the OMP algorithm [22]. The OMP iteratively updates the estimated support
of the sparse signal by calculating the strongest correlations between the
residual signal and the sensing matrix. After the last iteration, the OMP
applies the least square (LS) estimation on the elements in the sparse signal
as indicated by the estimated support. Based on the OMP algorithm, we make two
modifications. First, we use the $\mathcal{S}_{r}$ to initialize the estimated
support of the sparse signal. The delay, Doppler, and AoAs taps extracted from
the radar sensing information are expected to be similar to those of the
communication channels. Second, we set the maximum number of iterations and
the size of the estimated support adaptively according to the number of peaks
detected in $\mathcal{S}_{r}$ as shown by

$|\mathcal{S}|\leq\rho\cdot|\mathcal{S}_{r}|,$ (29)

where $\rho\geq 1$ is a hyper-parameter. The intuition is that, when the UE is
in a more complicated environment with many potential reflectors, the
communication channel is more likely to incorporate more (resolvable)
propagation paths. Meanwhile, the radar should also tend to detect more
peaks/paths.

##  V Simulation Data Generation

In this paper, we propose to utilize radar sensing capability at the BS to
improve downlink channel estimation for MIMO-OTFS systems. Hence, realistic
co-existing wireless communication and radar channel modeling is essential for
our simulation. To that end, we generate wireless communication and radar
channels based on accurate ray-tracing. Fig. 6 shows the bird view of the
adopted ray-tracing scenario. The ray-tracing scenario models a downtown area.
It consists of the intersections of one horizontal street and two vertical
streets, and various buildings. The BS is located on one side of the
horizontal street and points to the other side of the street. The UE is
randomly distributed in the area noted by the red box with a random velocity
uniformly sampled from $[50,90]\ m/s$. For communication and radar channels,
we adopt the $6$GHz and $28$GHz frequency bands, respectively. The detailed
simulation parameters are summarized in Table II. We sample 100 scenes with
different UE locations and velocities. For each scene, we generate the
communication and radar channel parameters. Specifically, based on ray-
tracing, we simulate the parameters of each propagation path including the
complex gain, the propagation delay, the Doppler frequency, the AoA, and the
AoD. From these channel parameters, we can obtain the communication channel
$H_{m,n,a}^{\text{DD}}$, and the radar data frame ${\mathbf{X}}$.

TABLE II: System Parameters for simulation \- Wireless Communication Parameters- |
---|---
Carrier frequency ($f_{c})$ | $6\ GHz$
Number of BS antennas ($A$) | $32$
Number of UE antennas | $1$
Number of subcarriers $(M)$ | 256
Number of symbols $(N)$ | 14
Cyclic prefix | $25\%$
Subcarrier spacing | $15\ kHz$
UE velocity | $50\sim 90\ m/s$
\- Radar Configuration - |
Start frequency ($f_{0}$) | $28\ GHz$
Slope ($S$) | $30\ MHz/\mu s$
Sampling rate ($f_{s}$) | $30\ MHz$
Effective bandwidth ($B_{\mathrm{w}}$) | $512\ MHz$
Number of samples per chirp ($N_{s}$) | $512$
Number of loops ($N_{\text{loop}}$) | $256$
Number of transmit antenna | $1$
Number of receive antenna ($B$) | $16$
\- Radar Derived Parameters - |
Max. unambiguous range | $149.6\ m$
Range resolution | $0.29\ m$
Max. unambiguous velocity | $\pm 121.47\ m/s$
Velocity resolution | $0.96\ m/s$
Figure 7: This figure shows the NMSE performance under different SNRs. The
number of BS antennas is $32$ and the $\eta$ (pilot overhead ratio) is $20\%$.

##  VI Simulation Results

In this section, we investigate the performance of the proposed sensing-aided
channel estimation compared with the conventional OMP in terms of the
normalized mean square error (NMSE) and pilot overhead ratio.

###  VI-A Does Sensing Improve Channel Estimation Accuracy?

In Fig. 7, we show the NMSE performance comparison under various SNR levels.
The number of antennas is set to $32$, the pilot overhead ratio $\eta$ is
$20\%$, i.e., $256\times 14\times 0.2\approx 716$ symbols are allocated to the
pilot signal. The genie-aided approach “LS with perfectly known support”
relies on perfect knowledge of the communication channel support to solve
(20). That is, the support of ${\mathbf{h}}$ is assumed to be known, and LS is
applied to recover the channel taps indicated by the support. Therefore, it
acts as an approximated upper bound for the other solutions without perfect
support knowledge. The “OMP with no radar data” do not exploit any prior
channel support information. Instead, it directly applies the OMP algorithm to
solve (21). The “radar sensing-aided OMP” is the proposed approach shown in
Algorithm 1.

It can be observed that the NMSE performance of all three methods improve as
the SNR increases. The proposed approach outperforms the conventional OMP
(angle domain) in the SNR region shown in Fig. 7. In particular, the proposed
approach achieves similar NMSE performance with $\bf 4$dB lower SNR compared
with the OMP (angle domain). The performance gap between the proposed method
and the OMP (angle domain) is slightly larger at the low SNR region. When the
noise level is high, as it becomes difficult for the conventional OMP (angle
domain) solution to estimate the correct dominant channel taps. However, the
proposed method can leverage the channel support extracted from the radar
signals, making it more robust even at low SNRs.

Figure 8: This figure shows the NMSE performance with different $\eta$ (pilot
overhead ratio). The BS has $32$ antennas. The SNR is set to $10$dB.

###  VI-B Does Sensing Reduce the Pilot Overhead?

In Fig. 8, we present the NMSE performance comparison under various pilot
overhead ratios $\eta$. The SNR here is set to $10$dB. It can be observed that
the NMSE decreases when more pilot signals are used for channel estimation,
which is expected. The proposed approach consistently outperforms the
conventionaly OMP (angle domain) for all pilot overhead values. Particularly,
the proposed approach achieves similar NMSE performance using $\eta=0.15$
compared to the “OMP (angle domain)” using $\eta=0.3$. This indicates a
$\mathbf{50\%}$ reduction in the pilot overhead. This result captures the
prospect of utilizing radar sensing to reduce channel estimation overhead.
Note that the LS with perfectly known support (which can act as an upper
bound) has much better performance than the other approaches. This indicates
that there is still a clear room for enhancements on the proposed approach
that attempts to estimate the support using radar sensing, which motivates
future research.

##  VII Conclusions

In this paper, we investigated the downlink channel estimation problem for
massive MIMO-OTFS systems and developed a novel approach that leverages the
radar sensing information at the basestation to aid the OTFS channel
estimation task. This is particularly motivated by the integratration of
sensing and communication in future wireless systems and by the direct
relationship between the delay-Doppler channel and the sensing infomration
(such as location/velocity/direction) about the mobile user/scatterers in the
environment. We formulated the delay-Doppler channel estimation problem as a
sparse recovery problem and utilized radar sensing to aid the compressive
sensing solution. Using accurate 3D ray tracing, we constructed an evaluation
platform with co-existing communication and radar sensing data and used it to
assess the performance of the proposed solution. The results showed that the
proposed sensing-aided OTFS channel estimation approach consistently
outperforms the conventional OMP in terms of both the channel estimation NMSE
and the required pilot overhead, highlighting a promising approach for future
OTFS massive MIMO systems.

## References

  * [1] R. Hadani, S. Rakib, M. Tsatsanis, A. Monk, A. J. Goldsmith, A. F. Molisch, and R. Calderbank, “Orthogonal time frequency space modulation,” in _2017 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2017, pp. 1–6.
  * [2] A. M. Sayeed, “How is time frequency space modulation related to short time fourier signaling?” in _2021 IEEE Global Communications Conference (GLOBECOM)_ , 2021, pp. 1–6.
  * [3] W. Shen, L. Dai, J. An, P. Fan, and R. W. Heath, “Channel estimation for orthogonal time frequency space (OTFS) massive mimo,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 16, pp. 4204–4217, 2019.
  * [4] J. Guo, C.-K. Wen, S. Jin, and G. Y. Li, “Convolutional neural network-based multiple-rate compressive sensing for massive mimo CSI feedback: Design, simulation, and analysis,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 4, pp. 2827–2840, 2020.
  * [5] O. K. Rasheed, G. Surabhi, and A. Chockalingam, “Sparse delay-Doppler channel estimation in rapidly time-varying channels for multiuser OTFS on the uplink,” in _2020 IEEE 91st Vehicular Technology Conference (VTC2020-Spring)_. IEEE, 2020, pp. 1–5.
  * [6] M. Zhang, F. Wang, X. Yuan, and L. Chen, “2D structured turbo compressed sensing for channel estimation in OTFS systems,” in _2018 IEEE International Conference on Communication Systems (ICCS)_. IEEE, 2018, pp. 45–49.
  * [7] D. Shi, W. Wang, L. You, X. Song, Y. Hong, X. Gao, and G. Fettweis, “Deterministic pilot design and channel estimation for downlink massive MIMO-OTFS systems in presence of the fractional Doppler,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 11, pp. 7151–7165, 2021\.
  * [8] U. Demirhan and A. Alkhateeb, “Integrated sensing and communication for 6G: Ten key machine learning roles,” 2022. [Online]. Available: https://arxiv.org/abs/2208.02157
  * [9] F. Liu, C. Masouros, A. P. Petropulu, H. Griffiths, and L. Hanzo, “Joint radar and communication design: Applications, state-of-the-art, and the road ahead,” _IEEE Transactions on Communications_ , vol. 68, no. 6, pp. 3834–3862, 2020.
  * [10] U. Demirhan and A. Alkhateeb, “Radar aided 6g beam prediction: Deep learning algorithms and real-world demonstration,” in _2022 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2022, pp. 2655–2660.
  * [11] J. A. Zhang, F. Liu, C. Masouros, R. W. Heath, Z. Feng, L. Zheng, and A. Petropulu, “An overview of signal processing techniques for joint communication and radar sensing,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 15, no. 6, pp. 1295–1315, 2021.
  * [12] P. Kumari, J. Choi, N. González-Prelcic, and R. W. Heath, “Ieee 802.11ad-based radar: An approach to joint vehicular communication-radar system,” _IEEE Transactions on Vehicular Technology_ , vol. 67, no. 4, pp. 3012–3027, 2018.
  * [13] Z. Wei, W. Yuan, S. Li, J. Yuan, and D. W. K. Ng, “Transmitter and receiver window designs for orthogonal time-frequency space modulation,” _IEEE transactions on communications_ , vol. 69, no. 4, pp. 2207–2223, 2021.
  * [14] P. Raviteja, K. T. Phan, Y. Hong, and E. Viterbo, “Interference cancellation and iterative detection for orthogonal time frequency space modulation,” _IEEE transactions on wireless communications_ , vol. 17, no. 10, pp. 6501–6515, 2018.
  * [15] P. Asuzu and C. Thompson, “A more exact linear fmcw radar signal model for simultaneous range-velocity estimation,” in _2018 IEEE Radar Conference (RadarConf18)_. IEEE, 2018, pp. 0007–0011.
  * [16] 3GPP TR 25.996 version 11.0.0 Release 11, “Universal Mobile Telecommunications System (UMTS); Spatial channel model for Multiple Input Multiple Output (MIMO) simulations,” , Tech. Rep., 2012.
  * [17] S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” _SIAM review_ , vol. 43, no. 1, pp. 129–159, 2001.
  * [18] S. G. Mallat and Z. Zhang, “Matching pursuits with time-frequency dictionaries,” _IEEE Transactions on signal processing_ , vol. 41, no. 12, pp. 3397–3415, 1993.
  * [19] T. S. Rappaport, Y. Xing, O. Kanhere, S. Ju, A. Madanayake, S. Mandal, A. Alkhateeb, and G. C. Trichopoulos, “Wireless communications and applications above 100 GHz: Opportunities and challenges for 6G and beyond,” _IEEE access_ , vol. 7, pp. 78 729–78 757, 2019.
  * [20] Z. Feng, Z. Fang, Z. Wei, X. Chen, Z. Quan, and D. Ji, “Joint radar and communication: A survey,” _China Communications_ , vol. 17, no. 1, pp. 1–27, 2020.
  * [21] H. Rohling, “Radar CFAR thresholding in clutter and multiple target situations,” _IEEE transactions on aerospace and electronic systems_ , no. 4, pp. 608–621, 1983.
  * [22] J. A. Tropp and A. C. Gilbert, “Signal recovery from random measurements via orthogonal matching pursuit,” _IEEE Transactions on information theory_ , vol. 53, no. 12, pp. 4655–4666, 2007.


# Bandit-Driven Batch Selection
for Robust Learning under Label Noise

Michal Lisicki
University of Guelph, Vector Institute
<EMAIL_ADDRESS>
&Mihai Nica
University of Guelph, Vector Institute
<EMAIL_ADDRESS>
&Graham W. Taylor
University of Guelph, Vector Institute
<EMAIL_ADDRESS>
###### Abstract

We introduce a novel approach for batch selection in Stochastic Gradient
Descent (SGD) training, leveraging combinatorial bandit algorithms. Our
methodology focuses on optimizing the learning process in the presence of
label noise, a prevalent issue in real-world datasets. Experimental
evaluations on the CIFAR-10 dataset reveal that our approach consistently
outperforms existing methods across various levels of label corruption.
Importantly, we achieve this superior performance without incurring the
computational overhead commonly associated with auxiliary neural network
models. This work presents a balanced trade-off between computational
efficiency and model efficacy, offering a scalable solution for complex
machine learning applications.

##  1 Introduction

As applications increasingly demand larger and more complex deep learning
models, the need for efficient training strategies has become paramount. One
way to accelerate training and potentially improve model performance is
through the use of Curriculum Learning (CL) and adaptive batch selection.
These techniques optimize learning by selectively focusing on data samples
that are intrinsically rich and informative at the most appropriate stages of
the learning process. Such strategies not only accelerate convergence but also
enhance the model’s ability to generalize [19, 20, 27].

While many methods use difficulty metrics to select easy, hard, or uncertain
instances for training [31], a key area lies in handling noisy or mislabeled
datasets [28]. This domain is particularly important for two reasons: a) the
impact of batch selection strategies is easily measured, leading to more
insightful conclusions; and b) it addresses the prevalent real-world scenarios
where data is often sourced from the web [18] or crowdsourced [7], and a large
portion is considered “unclean”.

Sample selection strategies using auxiliary Deep Neural Networks (DNN)
effectively mitigate the impact of noisy or mislabeled data. However, these
approaches incur substantial computational overhead, limiting their
scalability [9, 13, 17, 33]. While alternative methods like SELFIE [26] offer
computational efficiency, they are under-explored and rely on steps like re-
labeling for optimal performance. Meanwhile, the literature on CL and batch
selection offers numerous methods for efficient sample selection across
diverse domains [8, 19].

This paper introduces a novel approach that synergizes insights from the CL
and batch selection literature to enhance efficient sampling schemes,
specifically targeting scenarios with prevalent label noise. Our methodology
aims to achieve superior performance without the computational burden often
associated with deploying additional DNNs, thereby striking a balance between
efficacy and computational efficiency. Unlike traditional CL approaches that
focus on individual instances or tasks, our method refines the feedback loop
from each training iteration to optimize the _selected batch_. This approach
is particularly relevant for tackling the challenges posed by the increasing
computational complexity and diversity of machine learning applications across
various domains.

##  2 Background

### Batch selection and curriculum learning

CL [3] and its variants like Self-Paced Learning (SPL) [15] and Hard-Example
Mining (HEM) [6, 19] provide frameworks for adaptive instance, batch, or task
selection based on difficulty or importance. Despite the efficacy of these
strategies in enhancing stability and convergence, a universal solution
remains elusive, prompting exploration into varied strategies, new importance
metrics, and advanced re-weighting and sampling techniques.

Re-weighting the model’s loss by instance, akin to importance-sampling
techniques, has been investigated by [6, 19, 24]. These studies have indicated
that re-weighting can stabilize gradient estimates and reduce bias in the
original objective function. However, both Loshchilov and Hutter [19] and
Chang et al. [6] have argued that the impact of this strategy on performance
is limited, and that comparable or superior results can be achieved by
sampling from a weight-induced distribution. Matiisen et al. [20] compared the
_sample selection_ strategies, $\varepsilon$-greedy, Boltzmann, and Thompson
sampling, and concluded that the optimal strategy hinges heavily on the sample
weight metric. A novel metric not tied to difficulty was introduced by Chang
et al. [6], emphasizing samples with high prediction uncertainty, and inspired
by active learning. The authors demonstrated that, by avoiding overly easy or
hard instances, their strategy surpassed SPL or HEM on datasets like MNIST and
CIFAR with and without label noise. Song et al. [27] introduced Recency Bias
to boost SGD’s convergence by combining principles of [19] and [6]. The
technique centers on prediction uncertainty, measured by predicted label
entropy, as its adaptive sample selection metric. It uses a Boltzmann
distribution with energy based on prediction uncertainty and a pressure
parameter. Leveraging a sliding window, it emphasizes recent scores,
mitigating overfitting and slow convergence. Importantly, Active Bias, Recency
Bias, and our approach add minimal computational load to model training.

Automated curriculum learning (ACL) distinguishes itself among CL approaches
by the degree of control over the learning process. In ACL, the selection of
tasks is determined dynamically using an algorithm, typically an RL or a
bandit method. Graves et al. [8] and Matiisen et al. [20] have proposed
utilizing a non-stationary bandit (Exp3). They demonstrated that when an agent
lacks prior knowledge of its tasks, ACL can significantly boost training
efficiency relative to uniform sampling. Moreover, a bandit algorithm can
discover complex orderings and opportunities for efficient knowledge transfer
in an unsorted curriculum. Although prior literature has focused primarily on
task-based ACL, the same principles can be utilized in instance and batch
selection.

This paper aims to build upon the mentioned foundational CL techniques by
introducing efficient batch selection methods, particularly in the context of
learning with noisy labels.

### Efficient learning with noisy labels

Learning with Noisy Labels (LNL) shares a connection with batch selection but
has a different objective. While batch selection picks instances that
inherently aid training, LNL focuses on distinguishing between those with
clean and noisy labels. Both fields converge when the right batch selection
strategy is used to isolate the “clean” instances.

LNL is challenging due to DNNs’ tendency to memorize complex and possibly
incorrect instances, after initially learning simpler patterns [1, 34]. This
can lead to memorization of inaccurate labels, compromising model
generalization. Mislabeled data can also cause confirmation bias, which arises
when models overfit to early-selected instances. Multi-network and co-training
[9, 33] address these issues but add computational overhead and complexity.
Both challenges highlight the need for robust training methods.

The “small-loss trick” is a commonly utilized tool for filtering out noisy
labels by deeming instances with smaller losses as likely clean. While
prevalent in DNN approaches (e.g., [9, 13, 17, 25, 33]), this method is not
optimal when noisy and clean example distributions overlap significantly.
Alternative methods, like measuring prediction uncertainty over time, have
been explored as indicators of label corruption [6, 22, 26].

Similarly to batch selection, LNL methods can be broadly categorized into:
loss correction and sample selection [28]. Loss correction includes re-
weighting or re-labeling. Active Bias [6] re-weights instances based on
prediction variance, bridging LNL and batch selection. A method by Ren et al.
[24] uses a clean validation set to dynamically assign weights. Re-labeling
refines labels from a mix of noisy labels and DNN predictions, as seen in [23,
29, 32], effectively providing data augmentation. While innovative, these
methods pose risks like overfitting to noisy labels and add complexity.
Filtering out noisy labels, by contrast, provides a simpler approach but
sacrifices information from label refinement. Sample selection filters out
mislabeled data during training, often using an auxiliary DNN. MentorNet [13]
stands out as a pivotal multi-network approach. It supervises a StudentNet by
emphasizing “clean” instances and refining the learning trajectory based on
feedback. Han et al. [9] proposed a “Co-teaching” paradigm, an alternative,
where two DNNs are trained simultaneously and share insights on small-loss
instances to diminish errors from noisy labels. “Co-teaching+” [33] tackles
the risk of two networks reaching a consensus with an ’update by disagreement’
strategy. The "deep abstaining classifier" [30] is a feature-based multi-
network approach, which is particularly effective against structured noise.
DivideMix [17] has demonstrated the state-of-the-art LNL performance by
employing a semi-supervised (SSL) approach. It dynamically segregates training
data into clean and noisy sets using a Gaussian Mixture Model (GMM) and the
small-loss trick. To avoid confirmation bias, it utilizes co-teaching. The
mislabeled instances are stripped of their labels and refined using SSL [4].
Despite their ability to counteract confirmation bias, the multi-network
training approaches often come with significant computational overhead.

SELFIE [26] is a hybrid approach, combining both loss correction and sample
selection. SELFIE seeks to refurbish labels of unclean samples selectively,
based on uncertainty, and leverage them along with clean samples, to further
reduce false corrections while fully exploiting the current training data.
While methods like SELFIE are computationally efficient and provide increase
in performance, we argue that their selection strategies can be made better.
In this paper we focus on improving the batch selection methodology, and
compare performance to the pure selection method, Active Bias [6], and two
bandit approaches — the _Exponential-weight algorithm for Exploration and
Exploitation_ (Exp3) [2] and _Follow the Perturbed Leader_ (FPL) [16, 21].
Details on these algorithms can be found in Sec. 3 and in Appendix, Sec. A.

### Improving sampling efficiency by exploration

The challenge of balancing exploration and exploitation is inherent in the
process of batch selection. This balance is crucial for identifying new
instances that can enhance training efficiency and subsequently leverage them
for optimal training outcomes. In addition, it is essential to account for the
high degree of non-stationarity in neural network training. Specifically, a
network can typically be trained on a particular data instance for only a few
iterations before it risks overfitting. To address this issue, our approach
aims to manage non-stationarity by dynamically adapting weight estimates. This
adaptation can be achieved either through periodic reevaluation, which may be
computationally expensive, or by employing a discounted moving average.

So far we are aware of only one study that has directly compared various
exploration-exploitation strategies in the context of instance selection: its
mixed results suggest such strategies depend highly on the researcher’s choice
of a sample weight metric [20]. Although $\varepsilon$-greedy and UCB bandit
methods have demonstrated effective performance in instance selection [6, 20],
the Boltzmann exploration strategy has recently gained prominence in this
subfield [5, 19]. In particular, the adversarial bandit — Exp3 [2], which uses
Boltzmann exploration, is commonly utilized as a baseline in non-stationary
environments, and has been shown to be particularly effective in automated
curriculum learning [8, 20].

Our work diverges from prior studies focused on choosing instances [6, 27] or
tasks [8, 20], and targets batch selection instead. We utilized the FPL
strategy, which can be thought of as a natural extension of Exp3 into
combinatorial (batch), rather than individual (instance) action selection.

##  3 Methods

### Adversarial multi-armed bandit problem

A classic baseline approach for non-stationary environments is the adversarial
bandit, in particular, the Exp3 algorithm and its variants. In an adversarial
$K$-armed bandit problem, at each time step $t\in\\{1,2,...,T\\}$, the player
selects an action $a_{t}\in\\{1,2,...,K\\}$ and then an adversary, with full
knowledge of the player’s previous actions, assigns a reward vector
$\mathbf{r_{t}}=(r_{t,1},r_{t,2},...,r_{t,K})\in[0,1]^{K}$ across all actions.
The player receives a reward $r_{t,a_{t}}$ corresponding to the selected
action $a_{t}$. There is typically almost no restrictions on how the adversary
can choose the reward vectors, as long as the sequence of reward vectors
$\mathbf{r_{1}},\mathbf{r_{2}},...,\mathbf{r_{T}}$ is fixed in advance or
chosen based on the player’s past actions. The player’s goal remains to
maximize the total collected reward or equivalently, to minimize regret.

### Combinatorial bandits for batch selection

In order to select a full batch of instances at once we need to utilize the
combinatorial bandit paradigm, which considers the joint utility of
combinations of “basic arms”. Formally, combinatorial bandits can be
considered a type of bandit where a subset of arms is selected in a form of a
binary vector $\mathbf{a}\in\\{0,1\\}^{d}$, and the final reward is derived
from either a Hadamard or a dot product of that vector with the reward vector
$\mathbf{r}$. In this work we consider only the subset of a pre-specified
batch size $m$, s.t. $||\mathbf{a}||_{1}=m$, and a semi-bandit reward model
(see Appendix, Sec. A). A direct application of Exp3 to the semi-bandit
problem would entail monitoring the sequence of estimates for ${K\choose m}$
arms, a task that is computationally infeasible. The state-of-the-art approach
to semi-bandits is _Follow the Perturbed Leader_ (FPL) [10], which mimics
Exp3, but estimates probabilities using reward perturbations, rather than
storing them directly. FPL was originally introduced by Hannan [10] and Kalai
and Vempala [14], with an efficient version operating on a principle of
geometric re-asmpling (GR) proposed by Neu and Bartók [21]. In this work, we
adapt the FPL algorithm to batch selection.

FPL operates over $n$ rounds, maintaining a vector of weights $w_{t,i}$ for
each action $\mathbf{a}_{i}$ in the action set $\mathcal{A}$. In our case
$\mathbf{a}$ is a binary vector, such that setting an $i$-th action $a_{i}=1$
corresponds to selecting an $i$-th instance $\mathbf{x}_{i}$. Each round the
algorithm perturbs the weights with noise $\boldsymbol{\rho}_{t}$ from
distribution $Q$, selecting the action $\mathbf{a}_{t}$ that maximizes the
inner product with the perturbed weight vector. While Neu and Bartók [21] used
the $\text{Exp}(1)$ distribution for $Q$, recent work by Honda et al. [11]
suggests the $\text{Fr\'{e}chet}(2)$ (also known as inverse Weibull)
distribution yields optimal regret in adversarial settings. As opposed to the
algorithms presented in literature [11, 21] we estimate reward, rather than
loss associated with each arm. We have found this adaptation to significantly
improve performance in our application, however we acknowledge that while this
algorithm remains in line with reward estimation done in Exp3, the original
theoretical performance guarantees for combinatorial arm selection may no
longer apply.

Data: $\mathcal{A},n,\eta,M,Q$

1

2for  _$i=1$ to $d$_ do

$w_{0,i}\leftarrow 0$ // Initialize weight vector

3

4

5for  _$t=1$ to $n$_ do

Sample $\boldsymbol{\rho}_{t}\sim Q$ // Sample weight perturbations

Compute
$\mathbf{a_{t}}=\arg\max_{\mathbf{a}\in\mathcal{A}}\langle\mathbf{a},\eta\mathbf{w}_{t-1}+\boldsymbol{\rho}_{t}\rangle$
// Choose combinatorial action

6

$\mathbf{r}_{t}\sim\nu_{a_{t}}$ // Draw reward vector from arm
$\mathbf{a}_{t}$ of MAB $\nu$

7

8 foreach  _$i$ with $a_{t,i}=1$_ do

// Geometric Re-sampling

9 Sample $\sigma_{t,i}\sim\text{Geometric}(p_{t,i})$

$\hat{r}_{t,i}=\min\\{M,\sigma_{t,i}\\}a_{t,i}r_{t,i}$ // Compute bounded
reward estimate

$w_{t,i}=w_{t-1,i}+\hat{r}_{t,i}$ // Update weight of chosen action

10

11

Algorithm 1 Follow The Perturbed Leader (Reward-guided)

Following action selection, for each $i$ where $a_{t,i}=1$, the algorithm
proceeds with a geometric re-sampling (GR) step. Sampling from the geometric
distribution estimates $1/p_{i}$ and in practice is not done directly, but
rather by sampling arms from $Q+\eta\mathbf{w}_{t-1}$ and counting the number
of iterations to re-occurrance. $M$ is the cap on sampling size, to trade off
computational efficiency with estimation accuracy. The algorithm draws a
sample $\sigma_{t,i}$ from the approximated geometric distribution, and
computes a bounded reward estimate $\hat{r}_{t,i}$ in the same way as Exp3, as
an importance-weighted estimate, by
$a_{t,i}\sigma_{t,i}r_{t,i}$.111$\sigma_{t,i}$ estimates $1/p_{i}$

Finally, the algorithm updates the weight $w_{t,i}$ of the chosen action
$a_{i}$ by adding the reward estimate $\hat{r}_{t,i}$ to the previous weight
$w_{t-1,i}$. This process continues for $n$ rounds, enabling the algorithm to
effectively explore and exploit the action space by balancing the current
estimated rewards and the exploration noise introduced by perturbations. While
FPL may require more computational resources compared to Exp3, it offers the
advantage of reducing dependency on the combinatorial action space. This makes
FPL a practical choice for real-world sequential decision-making tasks.

### Label noise

According to Song et al. [28], label noise can be either instance-independent,
characterized by constant rates and probabilities, or instance-dependent,
where corruption probabilities vary with data features and true labels. This
study concentrates on symmetric, instance-independent noise to provide a
baseline in a controlled setting.

### LNL weight metric

Choosing the right metric to select informative instances is still an open
problem. In the field of LNL, metrics based on prediction loss [9, 13, 17, 33]
and prediction uncertainty [6, 22, 26] have shown particular promise. The
following metric was proposed by Chang et al. [6] as part of the Active Bias
method:

$w_{i}\propto\operatorname*{\widehat{var}}(p_{\mathcal{H}^{t-1}_{i}}(y_{i}|\mathbf{x}_{i})),$

where, for each instance $\mathbf{x}_{i}$, it saves prediction probabilities
for their target class over time in a history buffer $\mathcal{H}_{i}$, and
then computes their variance.

We employed this metric in our study, as it was shown suitable both for LNL
and for batch selection in general. Unlike the metrics that are derived from
the change in the state of the model, the probability-based metrics reflect
the model’s current confidence in its predictions, rendering them independent
of the target solutions, and therefore, consistent across instances. This
property makes them inherently balanced for problems such as LNL. However, it
should be noted that while these metrics offer advantages, they do not
directly track the progression of training. Therefore, following Song et al.
[27], we limit the size of the history to 10 predictions.

The estimated weights serve two main purposes: either to re-weight the loss as
in [24] or to parameterize the probability distribution over data instances.
The latter often employs a Boltzmann distribution (e.g. [8, 20]):
$P_{s}(i|H,S_{e},D)=e^{w_{i}/\tau}/Z$ where $Z$ is the normalization constant,
$H$ denotes the history of scores (e.g. instance losses or prediciton
probabilities), $S_{e}$ is the set of samples used in the current epoch, and
$D=\\{(\mathbf{x}_{i},y_{i})\mid i=1,2,\ldots,N\\}$ represents the dataset.
Given our interest in the role of exploration in sample efficiency, we
primarily focus on sampling methods underpinned by bandit algorithms such as
Exp3, which also employs a Boltzmann-like distribution.

##  4 Results

### Experimental Setup

We evaluated the performance of various sampling methods including Uniform
Sampling, Active Bias, Exp3, and FPL on the CIFAR-10 dataset using a DenseNet
model [12] with 40 layers. We used the Adam optimizer with momentum 0.9 and an
initial learning rate of 0.1 that is decayed by multiplicative factor of 0.1
after 40 k and 60 k iterations. The batch size was set to 128 and we ran 200
epochs, consisting of 391 batches each. All methods were repeated 5 times with
different seeds, under varying label corruption percentages ranging from 0% to
50%. We report the mean and 95% confidence intervals (CI) of test accuracy
achieved by each method. We will release a PyTorch implementation to reproduce
our experiments upon paper acceptance.

Figure 1: Test error over the course of training with confidence intervals
(CI) over 5 runs for Uniform, Active Bias (weighted), Exp3 and FPL, for label
noise ratio $\in\\{0.1,0.3,0.5\\}$.

### Results

Under all label corruption scenarios, FPL exhibited significantly reduced
noise and superior performance compared to the other methods, with Exp3
outperforming Active Bias, and Active Bias performing better than Uniform
Sampling. In conditions with no label noise, no significant improvement was
observed across methods, revealing a potential limitation in sensitivity to
“hard to classify” instances and an overfocus on mislabeling.

Method Noise |  | 10% | 20% | 30% | 40% | 50%
---|---|---|---|---|---|---
Uniform | best | 10.24$\pm$0.25 | 12.05$\pm$0.54 | 14.08$\pm$0.39 | 16.75$\pm$0.30 | 19.40$\pm$0.26
last | 13.61$\pm$0.24 | 16.73$\pm$1.30 | 20.28$\pm$0.72 | 23.88$\pm$0.78 | 30.34$\pm$1.70
Active Bias | best | 9.17$\pm$0.15 | 10.69$\pm$0.13 | 12.85$\pm$0.09 | 15.09$\pm$0.19 | 18.09$\pm$0.19
last | 12.03$\pm$0.57 | 13.74$\pm$0.62 | 17.26$\pm$0.45 | 20.70$\pm$0.31 | 25.86$\pm$0.88
Exp3 | best | 8.74$\pm$0.13 | 10.28$\pm$0.13 | 12.19$\pm$0.15 | 14.51$\pm$0.23 | 18.02$\pm$0.51
last | 10.64$\pm$0.22 | 12.30$\pm$0.49 | 14.67$\pm$0.80 | 17.42$\pm$0.51 | 22.27$\pm$0.50
FPL | best | 8.37$\pm$0.19 | 10.04$\pm$0.15 | 12.11$\pm$0.34 | 14.25$\pm$0.36 | 17.65$\pm$0.29
last | 8.97$\pm$0.15 | 10.46$\pm$0.24 | 12.77$\pm$0.37 | 15.37$\pm$0.46 | 19.79$\pm$0.51

Figure 2: Left: Lowest and final epoch test errors (%) for each method on
CIFAR-10 by noise ratio. Right: Visualizing last epoch performance.

### Discussion

The methods maintained a consistent ranking across noise levels, with the
performance gap widening as noise increased (see Fig. 1 and 2). FPL
consistently yielded smooth and stable convergence, due to its ability to
choose informative instances. When adopting the same weight metric and neural
network architecture as Active Bias, our results show that implementing a
bandit strategy can lead to significant performance gains. This underscores
the importance of not just selecting an optimal weight metric, but also
employing a beneficial exploration policy.

(a)

(b)

(c)

Figure 3: Analysis of instance selection for Uniform, Exp3, and FPL222Active
bias method is excluded here as we use its loss re-weighting variant, and so
its sampling distribution is the same as uniform. with 20% label noise,
showing selection occurrence during the initial (a) and final (b) 1000
iterations and total proportion of mislabeled instances (c; front) over total
occurrences (c; background). The order of curves at index 0 aligns well with
the overall performance of the methods, revealing a concentration of selection
in Exp3 and FPL, particularly pronounced in FPL, with Exp3 demonstrating
overfitting to a limited set of instances.

Analysis of instance occurrences (Fig. 2) reveals insights into the
differences in sampling strategies, addressing our initial inquiry into
performance gain from utilizing batch- as opposed to instance-based feedback.
Initially (Fig. 2a), all methods show similar selection frequencies, but
distinctions emerge as training concludes (Fig. 2b), especially for Exp3 and
FPL. Notably, the algorithm’s pattern of concentration on specific instances
correlates well with its performance. While Exp3 resembles an exponential
distribution, FPL produces a threshold at about 20 k instances, filtering 30 k
of the remaining images. The preference for ‘clean’ instances between the 10 k
and 20 k sorted index intensifies towards the end of training, indicating the
algorithm’s inclination to retain instances initially deemed ‘clean’. These
insights emphasize FPL’s efficiency as an $m$-set combinatorial bandit method,
and highlight its suitability for batch selection.

In Fig. 2c, we display curves representing total counts throughout the run,
providing a holistic view of each method’s sample selection strategy. Over
these, with solid lines, we superimpose the percentage of mislabeled instances
within a sliding window of 1000 sorted instances. Each point on the overlay
represents the mislabeling percentage within that window, revealing a trend:
instances sampled less frequently (toward the right) have higher mislabeling
percentages. This visualization supports our hypothesis that bandit methods
with uncertainty-based metrics, like Exp3 and FPL, enhance performance by
focusing on and filtering out mislabeled instances.

While Exp3 effectively identifies mislabeled instances like FPL (Fig. 2c), it
tends to overfit to a narrow set and over-explore the rest (Fig. 2b). This is
expected as Exp3 is an instance-based algorithm. However, this overfitting
poses risks to its efficacy, as consistently selecting the same subset of
impactful instances, combined with a broad array of less pertinent ones, leads
to lower performance. Conversely, FPL, by adjusting weights in accordance with
other instances, revisits a larger, more balanced subset regularly, forming
more informative and consequential batches, ensuring optimal selection in
batch training scenarios.

As weights play a crucial role in understanding the learning process in depth,
we further analyze the weight dynamics of FPL in Fig. 4. Initially set to 0,
the weights adjust smoothly throughout training, maintaining a balance in
instance selection without anomalies or overfitting. There is a 40%-60% split
in instance selection (Fig. 2b) that is clearly reflected in the weights, with
those corresponding to highly informative instances increasing rapidly,
whereas those consistently labeled (either correctly or as mislabeled)
remaining closer to zero. It is worth noting here that all instances were
selected at least once, with all weights turning strictly positive by the end
of the run. Entropy visualization (Fig. 4a) further emphasizes effective
convergence on a well-sized subset of instances, reinforcing selection for
better exploitation without excessive exploration.

(a) Weight entropy

(b) Weights over time

(c) Lowest Weights sorted

Figure 4: Instance weight visualization. Entropy-aggregated weights are
visualized over time in (a). Once all instances are selected by epoch 40, the
entropy gradually declines as certain instances gain importance. This pattern
indicates effective diversification without overfitting. In (b), a random
subset of weights is displayed over time to further validate their individual
trajectories. In (c) the lowest weights are shown to dynamics of weights that
remain close to 0.

### Scalability and hyperparameter sensitivity

We ran our experiments using $\eta=0.3$ and $\gamma=0.1$ for Exp3 and
$\eta\approx 18$, $\beta\approx 20$, and the $\text{Fr\'{e}chet}(0.45)$
distribution for FPL. To show that FPL has small sensitivity to these
hyperparameters, we ran a grid search in their vicinity (see Fig. 5). We found
the number of GR samples to be optimal between 500 and 1000. In that range GR
introduces an additional computational overhead of 20%-40%. This may seem
alarming at first, however, we point out that GR is embarrassingly
parallelizable and instance-based, which makes it scalable in practical
applications.

(a) Error w.r.t. Eta (Beta=25.0, Shape=0.4)

(b) Error w.r.t. Beta (Eta=27.0, Shape=0.4)

(c) Error w.r.t. Shape (Eta=27.0, Beta=25.0)

Figure 5: FPL hyperparameter sensitivity analysis for 50% label noise.

### Limitations and future directions

Exp3’s slower adaptation and potential benefits of its variants like Exp3.P or
Exp3.IX warrant further consideration. FPL excels in balancing exploration and
exploitation but shows limited improvement in noise-free scenarios, suggesting
a potential overfocus on mislabeled instances. While all methods generalize
well, tests were limited in scope. Future work will include naturally noisy
sets like WebVision [18], as well as metrics like area under the margin (AUM)
[22], to deepen insights and enhance results.

##  5 Conclusions

This investigation into the performance of sampling methods under different
noise conditions has revealed key insights into their adaptability, stability,
and algorithmic nuances. FPL’s effective balance between exploration and
exploitation, particularly its focus on uncertain instances, underscores its
superior performance. Nonetheless, the absence of marked improvement in noise-
free settings and the limited scope of our experiments highlight avenues for
future research and refinement.

## References

  * Arpit et al. [2017] Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien.  A Closer Look at Memorization in Deep Networks, July 2017.  URL http://arxiv.org/abs/1706.05394.  arXiv:1706.05394 [cs, stat].
  * Auer [2002] Peter Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Bengio et al. [2009] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston.  Curriculum learning.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , ICML ’09, pages 41–48, New York, NY, USA, June 2009. Association for Computing Machinery.  ISBN 978-1-60558-516-1.  doi: 10.1145/1553374.1553380.  URL https://doi.org/10.1145/1553374.1553380.
  * Berthelot et al. [2019] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel.  Mixmatch: A holistic approach to semi-supervised learning.  _Advances in neural information processing systems_ , 32, 2019.
  * Cesa-Bianchi et al. [2017] Nicolò Cesa-Bianchi, Claudio Gentile, Gábor Lugosi, and Gergely Neu.  Boltzmann Exploration Done Right, November 2017.  URL http://arxiv.org/abs/1705.10257.
  * Chang et al. [2017] Haw-Shiuan Chang, Erik Learned-Miller, and Andrew McCallum.  Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samples.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper/2017/hash/2f37d10131f2a483a8dd005b3d14b0d9-Abstract.html.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * Graves et al. [2017] Alex Graves, Marc G. Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu.  Automated curriculum learning for neural networks.  In _international conference on machine learning_ , pages 1311–1320. PMLR, 2017.
  * Han et al. [2018] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama.  Co-teaching: Robust training of deep neural networks with extremely noisy labels.  In _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper_files/paper/2018/hash/a19744e268754fb0148b017647355b7b-Abstract.html.
  * Hannan [1957] James Hannan.  Approximation to Bayes risk in repeated play.  _Contributions to the Theory of Games_ , 3:97–139, 1957\.
  * Honda et al. [2023] Junya Honda, Shinji Ito, and Taira Tsuchiya.  Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for Bandit Problems.  In _Proceedings of The 34th International Conference on Algorithmic Learning Theory_ , pages 726–754. PMLR, February 2023.  URL https://proceedings.mlr.press/v201/honda23a.html.
  * Huang et al. [2018] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger.  Densely Connected Convolutional Networks, January 2018.  URL http://arxiv.org/abs/1608.06993.  arXiv:1608.06993 [cs].
  * Jiang et al. [2018] Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei.  MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels, August 2018.  URL http://arxiv.org/abs/1712.05055.  arXiv:1712.05055 [cs].
  * Kalai and Vempala [2003] Adam Kalai and Santosh Vempala.  E cient algorithms for online decision problems.  In _Proceedings of the 16th Annual Conference on Computational Learning Theory_. Citeseer, 2003.
  * Kumar et al. [2010] M. Pawan Kumar, Benjamin Packer, and Daphne Koller.  Self-paced learning for latent variable models.  In _Proceedings of the 23rd International Conference on Neural Information Processing Systems - Volume 1_ , NIPS’10, pages 1189–1197, Red Hook, NY, USA, December 2010. Curran Associates Inc.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.  URL https://tor-lattimore.com/downloads/book/.
  * Li et al. [2020] Junnan Li, Richard Socher, and Steven C. H. Hoi.  DivideMix: Learning with Noisy Labels as Semi-supervised Learning, February 2020.  URL http://arxiv.org/abs/2002.07394.  arXiv:2002.07394 [cs].
  * Li et al. [2017] Wen Li, Limin Wang, Wei Li, Eirikur Agustsson, and Luc Van Gool.  Webvision database: Visual learning and understanding from web data.  _arXiv preprint arXiv:1708.02862_ , 2017.
  * Loshchilov and Hutter [2016] Ilya Loshchilov and Frank Hutter.  Online Batch Selection for Faster Training of Neural Networks, April 2016.  URL http://arxiv.org/abs/1511.06343.
  * Matiisen et al. [2019] Tambet Matiisen, Avital Oliver, Taco Cohen, and John Schulman.  Teacher-student curriculum learning.  _IEEE transactions on neural networks and learning systems_ , 2019\.
  * Neu and Bartók [2016] Gergely Neu and Gábor Bartók.  Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits.  _Journal of Machine Learning Research_ , 17(154):1–21, 2016.  URL http://jmlr.org/papers/v17/15-091.html.
  * Pleiss et al. [2020] Geoff Pleiss, Tianyi Zhang, Ethan R. Elenberg, and Kilian Q. Weinberger.  Identifying Mislabeled Data using the Area Under the Margin Ranking, December 2020.  URL http://arxiv.org/abs/2001.10528.  arXiv:2001.10528 [cs, stat].
  * Reed et al. [2015] Scott Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich.  Training Deep Neural Networks on Noisy Labels with Bootstrapping, April 2015.  URL http://arxiv.org/abs/1412.6596.  arXiv:1412.6596 [cs].
  * Ren et al. [2018] Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun.  Learning to Reweight Examples for Robust Deep Learning.  In _Proceedings of the 35th International Conference on Machine Learning_ , pages 4334–4343. PMLR, July 2018.  URL https://proceedings.mlr.press/v80/ren18a.html.
  * Shen and Sanghavi [2019] Yanyao Shen and Sujay Sanghavi.  Learning with Bad Training Data via Iterative Trimmed Loss Minimization, February 2019.  URL http://arxiv.org/abs/1810.11874.  arXiv:1810.11874 [cs, stat].
  * Song et al. [2019] Hwanjun Song, Minseok Kim, and Jae-Gil Lee.  SELFIE: Refurbishing Unclean Samples for Robust Deep Learning.  In _Proceedings of the 36th International Conference on Machine Learning_ , pages 5907–5915. PMLR, May 2019.  URL https://proceedings.mlr.press/v97/song19b.html.  ISSN: 2640-3498.
  * Song et al. [2020] Hwanjun Song, Minseok Kim, Sundong Kim, and Jae-Gil Lee.  Carpe Diem, Seize the Samples Uncertain “at the Moment” for Adaptive Batch Selection.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, CIKM ’20, pages 1385–1394, New York, NY, USA, October 2020. Association for Computing Machinery.  ISBN 978-1-4503-6859-9.  doi: 10.1145/3340531.3411898.  URL https://dl.acm.org/doi/10.1145/3340531.3411898.
  * Song et al. [2022] Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee.  Learning from noisy labels with deep neural networks: A survey.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2022\.
  * Tanaka et al. [2018] Daiki Tanaka, Daiki Ikami, Toshihiko Yamasaki, and Kiyoharu Aizawa.  Joint Optimization Framework for Learning with Noisy Labels, March 2018.  URL http://arxiv.org/abs/1803.11364.  arXiv:1803.11364 [cs, stat].
  * Thulasidasan et al. [2019] Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal Mohd-Yusof.  Combating Label Noise in Deep Learning Using Abstention, August 2019.  URL http://arxiv.org/abs/1905.10964.  arXiv:1905.10964 [cs, stat].
  * Wang et al. [2022] Xin Wang, Yudong Chen, and Wenwu Zhu.  A Survey on Curriculum Learning.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 44(9):4555–4576, September 2022.  ISSN 1939-3539.  doi: 10.1109/TPAMI.2021.3069908.
  * Yi and Wu [2019] Kun Yi and Jianxin Wu.  Probabilistic End-To-End Noise Correction for Learning With Noisy Labels.  pages 7017–7025, 2019.  URL https://openaccess.thecvf.com/content_CVPR_2019/html/Yi_Probabilistic_End-To-End_Noise_Correction_for_Learning_With_Noisy_Labels_CVPR_2019_paper.html.
  * Yu et al. [2019] Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor W. Tsang, and Masashi Sugiyama.  How does Disagreement Help Generalization against Label Corruption?, May 2019.  URL http://arxiv.org/abs/1901.04215.  arXiv:1901.04215 [cs, stat].
  * Zhang et al. [2017] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization, February 2017.  URL http://arxiv.org/abs/1611.03530.  arXiv:1611.03530 [cs].

##  Appendix A Bandit algorithms

### Classic adversarial bandits

The classic adversarial algorithm, Exp3 (Alg. 2), employs a multi-step process
for importance adjustments of reward estimates. First, it adjusts the reward
$r_{j}$ for arm $j$ at time $t$ using the formula
$\hat{r}_{j}=\frac{r_{t,j}}{p_{t,j}}\mathbb{I}_{j=i_{t}}$, where $p_{t,j}$ is
the probability of choosing arm $j$. These adjusted rewards are then used to
estimate sample weights $w_{j}$. Finally, these weights $w_{j}$ are utilized
in the Boltzmann distribution for sampling instances.

Data: $\gamma\in(0,1]$, $K$

1

2for  _$i=1$ to $K$_ do

$w_{1,i}\leftarrow 1$ // Initialize weights

3

4

5for  _each round $t=1,2,...$_ do

$p_{t,j}\leftarrow(1-\gamma)\frac{w_{t,j}}{\sum_{k=1}^{K}w_{t,k}}+\frac{\gamma}{K}$
// Compute pmf

$i_{t}\sim p_{t}$ // Sample action

$r_{t,i_{t}}\sim\nu_{i_{t}}$ // Draw reward from arm $i_{t}$ of MAB $\nu$

$\hat{r}_{j}\leftarrow\frac{r_{t,j}}{p_{t,j}}\mathbb{I}_{\\{j=i_{t}\\}}$ //
Compute reward estimate

$w_{t+1,j}\leftarrow w_{t,j}\exp(\gamma\hat{r}_{t,j})$ // Update weights

6

Algorithm 2 Exp3 Algorithm

The Exp3 algorithm is very efficient computationally and is suitable for task
or individual instance selection, but it doesn’t take into account an impact
of a full batch of instances on the performance of the neural network, which
may result in suboptimal performance when competing instances are present in
the same batch.

### Analysis and adoption of semi-bandit feedback in combinatorial bandits

Combinatorial bandits can be categorized as full-information, semi-bandits, or
full-bandit feedback. In the full-bandit feedback scenario we observe just one
reward per batch. While maximizing this reward is our ultimate objective,
ignoring the available information about rewards received for individual arms
makes the decision process suboptimal. The full information setup, where
rewards from all the arms are observed is computationally infeasible, as it
requires re-evaluating the network on all the instances. In our research we
adopt the semi-bandit, in which the rewards are observed only for the basic
arms selected in the current round. This setup aligns well with our problem,
where we observe the rewards for instances that the neural network was trained
on in current iteration. As this information is readily available, no
additional passes through the network are required.

Efficient variant of FPL was proposed by Neu and Bartók [21], who deployed
Geometric Re-sampling to estimate probabilities for importance-weighted reward
estimates (re-weighting step), making FPL the first computationally feasible
solution to semi-bandits with strong guarantees. While other methods may offer
comparable or superior theoretical performance in terms of upper regret
bounds, they frequently suffer from computational inefficiency or require
additional optimization steps, rendering them impractical for real-world
applications. The primary appeal of FPL lies in its computational efficiency.