# Evaluation of Sparse Acoustic Array Geometries for the Application in Indoor
Localization

Georg K.J. Fischer  0000-0003-1460-1061 Niklas Thiedecke  0009-0005-9432-320X
Thomas Schaechtle  0000-0002-5304-4213 Andrea Gabbrielli  0000-0002-3167-760X
Fabian Höflinger  0000-0001-5877-1439 Alexander Stolz  0000-0003-4730-8830 and
Stefan J. Rupitsch  0000-0002-4806-9838 Member, IEEE This work was partially
supported by the German Ministry of Education and Research (BMBF) under the
grant FKZ: 16ME0028 Verbundprojekt ISA4.0, as well as by the German Ministry
of Economic Affairs and Climate Action (BMWK) under grant FKZ: 03EE3066D
Verbundvorhaben LoCA.Georg K.J. Fischer, Thomas Schaechtle, Fabian Höflinger
and Alexander Stolz are with the Fraunhofer Institute for Highspeed Dynamics,
Ernst-Mach-Institute (EMI), Freiburg, Germany, E-Mail:
<EMAIL_ADDRESS>Thiedecke is with Bosch Sensortec GmbH,
Reutlingen, Germany.Andrea Gabbrielli, Thomas Schaechtle, Fabian Höflinger and
Stefan J. Rupitsch are with the Department of Microsystems Engineering
(IMTEK), University of Freiburg, Germany.

###### Abstract

Angle-of-Arrival (AoA) estimation technology, with its potential advantages,
emerges as an intriguing choice for indoor localization. Notably, it holds the
promise of reducing installation costs. In contrast to Time-of-Flight (ToF)/
Time-Difference-of-Arrival (TDoA) based systems, AoA-based approaches require
a reduced number of nodes for effective localization. This characteristic
establishes a trade-off between installation costs and the complexity of
hardware and software. Moreover, the appeal of acoustic localization is
further heightened by its capacity to provide cost-effective hardware
solutions while maintaining a high degree of accuracy. Consequently, acoustic
AoA estimation technology stands out as a feasible and compelling option in
the field of indoor localization. Sparse arrays additionally have the ability
to estimate the Direction-of-Arrival (DoA) of more sources than available
sensors by placing sensors in a specific geometry. In this contribution, we
introduce a measurement platform designed to evaluate various sparse array
geometries experimentally. The acoustic microphone array comprises 64
microphones arranged in an 8x8 grid, following an Uniform Rectangular Array
(URA) configuration, with a grid spacing of 8.255 mm. This configuration
achieves a spatial Nyquist frequency of approximately 20.8 kHz in the acoustic
domain at room temperature. Notably, the array exhibits a mean spherical error
of 1.26° when excluding higher elevation angles. The platform allows for
masking sensors to simulate sparse array configurations. We assess four array
geometries through simulations and experimental data, identifying the Open-Box
and Nested array geometries as robust candidates. Additionally, we demonstrate
the array’s capability to concurrently estimate the directions of three
emitting sources using experimental data, employing waveforms consisting of
orthogonal codes.

Array signal processing, Direction of Arrival, DoA estimation, Acoustic
Localization, Indoor Localization, Sparse Arrays, Indoor positioning systems.

DoA

    Direction-of-Arrival
ToF

    Time-of-Flight
DoF

    Degrees-of-Freedom
SBL

    Sparse Bayesian learning
RF

    Radio Frequency
MRA

    Minimum Redundancy Array
CRLB

    Cramér-Rao Lower Bound
GDoP

    Geometric Dilution of Precision
UWB

    Ultra-Wideband
AoA

    Angle-of-Arrival
TDoA

    Time-Difference-of-Arrival
ULA

    Uniform Linear Array
URA

    Uniform Rectangular Array
UCA

    Uniform Circular Array
SNR

    Signal-to-Noise Ratio
GCC

    Generalized Cross-Correlation
ESPRIT

    Estimation of Signal Parameters via Rotational Invariance Techniques
MUSIC

    Multiple Signal Classification
LS

    Least Squares
TLS

    Total Least Squares
PCB

    Printed Circuit Board
PSD

    Power Density Spectrum
CDF

    Cumulative Distribution Function
MEMS

    Micro-Electro-Mechanical Systems
TDM

    Time-Division Multiplexing
FPGA

    Field Programmable Gate Array
HPS

    Hard Processor System
RAM

    Random Access Memory
RMSE

    Root Mean Square Error
N-RMSE

    Normalized Root Mean Square Error
GUI

    Graphical User Interface
CPA

    Coprime Planar Array
ZC

    Zadoff-Chu
MLM

    Mainlobe Magnitude
MLW

    Mainlobe Width
MSLR

    Mainlobe / Sidelobe Ratio
MSLS

    Mainlobe / Sidelobe Separation
IQ

    In-Phase Quadrature
SPL

    Sound Pressure Level
MSE

    Mean Squared Error
GT

    Ground Truth
FoV

    Field of View
BPF

    Bandpass Filter
CI

    Confidence Interval

##  1 Introduction

Direction-of-Arrival (DoA) estimation proves to be a common challenge within
the domain of indoor localization. By strategically navigating the trade-off
between hardware and software complexity, it becomes feasible to minimize the
requisite number of anchor nodes for localization tasks. Fundamentally, only
two nodes are necessary to intersect lines in 3-D space, thereby facilitating
position estimation and reducing installation costs. In contrast, ToF systems
demand a minimum of four nodes for 3-D localization. DoA-based systems entail
a more intricate hardware setup, incorporating multiple arranged sensors such
as antennas or microphones. This necessitates sophisticated hardware design,
particularly in areas like Radio Frequency (RF) design, tuning, and data
acquisition and processing, leading to larger devices. Furthermore, the
interdependence of algorithms and hardware development is crucial, as data
models heavily rely on parameters like array geometries, sampling
specifications, and data handling limits. Despite the hardware complexity, the
reduction in required nodes significantly diminishes installation costs.
Additionally, receiver synchronization is unnecessary since only angles are
estimated.

The Geometric Dilution of Precision (GDoP) in DoA-based systems exhibits a
distinct structure compared to ToF/TDoA-based systems. While ToF/TDoA systems
dilute precision outside the polygon of receivers, DoA systems experience
precision dilution in the line of receivers and with distance to the receivers
(forming a cone shape) [1, 2, 3]. This characteristic makes it an intriguing
design choice for engineers to explore and implement.

The selection of technology spans from RF-based devices, such as WiFi,
Bluetooth, 5G, mmWave, or even Ultra-Wideband (UWB), to optical and acoustic
systems and combinations thereof [4, 5, 6]. A key distinguishing factor among
these technologies is primarily the propagation speed of waves in the medium,
which significantly influences the achievable performance bounds [7, 8, 9].
Another critical characteristic is the maturity of the technologies. For
instance, technologies like Bluetooth have specific sections in their
standards dedicated to AoA estimation [10], while others may lack such
provisions. Compatibility is also a noteworthy concern. Given that nearly all
smartphones support technologies like Bluetooth, incorporating acoustic
localization, despite having the required hardware, necessitates the
installation of custom software on the device [11].

Acoustic localization technology, despite not yet being widely deployed,
possesses the advantage of achieving high accuracy with straightforward and
cost-effective hardware. Its positive traits, including resilience to Radio
Frequency (RF) interference, make it a rational choice for deployment in mid-
sized areas where both high accuracy and cost-effectiveness are crucial
considerations. Acoustic AoA estimation has been subject to exploration in
prior research. Conventional algorithms for DoA estimation, particularly when
dealing with multiple tags, often necessitate time-synchronized signal
emissions. However, this requirement increases tag complexity. Alternatively,
accepting a certain degree of message collisions is another approach, albeit
making location updates less predictable [12]. Classical subspace estimators
offer the capability to simultaneously estimate the DoA of multiple signals.
However, the number of locatable sources using these methods is strictly
limited by the number of available sensors [13, 14].

In this study, our primary focus is to explore the potential for increasing
the number of concurrently locatable tags by leveraging sparse arrays. To
facilitate this investigation, we introduce an evaluation platform comprising
64 microphones arranged in an Uniform Rectangular Array (URA) configuration.
This platform enables us to analyze and evaluate the performance of various
sparse array geometries.

It is noteworthy that this paper extends our previously published work in
[15]. In addition to the previously published material, we have expanded the
literature review and related work section to provide a broader overview. New
data has been collected, including more azimuth and elevation angle pairs.
With the complete angle space sampled, a full characterization of the
evaluated geometries is now possible, revealing the characteristics of each.
Furthermore, the multiple sources experiment has been extended to include
another source, now encompassing three sources in total.

##  2 Related Work

The related work section is divided into two main components. First, we
consider the field of acoustic AoA indoor localization, exploring prior
research and advancements. The second part provides a concise review of sparse
arrays, elucidating their applications and contributions in diverse contexts.

###  2.1 Acoustic AoA for Indoor Localization

Various acoustic localization systems grounded in AoA localization have been
proposed, featuring array geometries encompassing microphone pairs, triangular
configurations, Uniform Linear Arrays, and Uniform Circular Arrays. Saadet
al.[16] integrate the AoA methodology with ToF measurements, achieving a 95th
percentile localization error of less than $10\text{\,}\mathrm{cm}$ through
their triangular array configuration. In another endeavor [17], the authors
leverage a uniform linear array with four microphones, yielding a 95-th
percentile localization error under $65\text{\,}\mathrm{cm}$. The work in [18]
explores self-positioning through a microphone pair and strategically deployed
acoustic beacons. Gabbrielliet al.[19, 12, 20] propose a five-microphone UCA
configuration, achieving a 95% error rate of under $17\text{\,}\mathrm{cm}$ in
3-D absolute localization accuracy. Generally, a limited number ($<$10) of
microphones is employed to facilitate AoA estimation on embedded devices.
However, the development of an indoor localization system capable of
concurrently performing AoA estimation for multiple emitting sound sources
(tags) remains a pending objective in the current state of research.

###  2.2 Sparse Arrays and their Applications

Sparse arrays have been a subject of research for several decades [21].
Various geometries have been explored, including Nested arrays [22, 23, 24,
25], Coprime arrays [26, 27, 28], Hourglass arrays [29], and Thermos arrays
[30]. In the RF domain, sparse arrays offer the potential to mitigate mutual
coupling between antennas [30]. Theoretical performance bounds, such as the
Cramér-Rao Lower Bound (CRLB), have been established for various geometries,
including Coprime arrays, Nested arrays, and Minimum Redundancy Arrays [31].
Furthermore, sparse arrays have found application in other domains, such as
medical ultrasound [32], showcasing the potential to reduce costs, albeit with
a trade-off involving diminished image quality.

Within the field of acoustic beamforming applications, sparse arrays have
gained prominence, demonstrating adaptability across diverse scenarios. In the
domain of speech localization, the work in [33] reports the observation that
Semi-Coprime microphone arrays exhibit superior beam patterns and reduced side
lobe levels compared to coprime arrays. Bushet al.[34] conducted an assessment
and validation of simulation results for Coprime linear microphone arrays with
wideband sources. In a related investigation [35], source enumeration
utilizing a Bayesian approach is explored, employing Coprime linear microphone
arrays. A technique utilizing sparse linear arrays for uncorrelated wideband
sources is introduced in [36]. This approach integrates data from different
frequency bins into a unified matrix, employing atomic norm minimization for
precise DoA estimation. The assessment of this technique involved the
utilization of a two-level Nested array. In the experimental domain, the work
in [37, 25] conducted a thorough evaluation of planar sparse arrays employing
the Sparse Bayesian learning (SBL) approach. This array, consisting of 63
microphones, operated in the lower frequency range (under
$3\text{\,}\mathrm{kHz}$). The authors could show, that the SBL algorithm is
able to resolve an equal number of sources as available sensors in the 2-D
case.

Two-Dimensional DoA estimation is a consequential extension to the 1-D arrays.
In light of this, Aboumahmoud et al.[21] offer a comprehensive review
specifically focused on various sparse geometries for 2-D estimation. Within
their work, the authors conduct a comparative evaluation considering critical
factors such as the number of sensors, their maximum Degrees-of-Freedoms, and
aperture sizes. Notably, the predominant nature of these investigations is
analytical and performed in silico. Consequently, the existing body of
research is characterized by a limited number of experimental validations and
demonstrated applications.

The principal contributions of this work encompass:

  * •

The conceptualization of a compact 64-microphone array system tailored for
indoor localization applications in the inaudible frequency range.

  * •

Investigation into the system’s performance, conducted through a comprehensive
analysis involving both simulation and experimentation.

  * •

Evaluation of various sparse array geometries utilizing empirical data.

  * •

A practical demonstration showcasing the system’s proficiency in estimating
the DoA for multiple concurrently emitting sound sources.

##  3 Signal Model

The central idea behind sparse microphone arrays lies in exploiting redundancy
within data recorded using non-sparse arrays, e.g. URAs, by reconstructing the
information of missing microphones using a combination of two or more other
microphones.

##### Difference co-array

Sparse signal processing uses a difference co-array to reconstruct this
information, which is defined as the set of differences in microphone
positions [21]:

$\displaystyle\mathbb{D}=\\{m\ |\ m=\kappa_{i}-\kappa_{j},\quad\forall\
\kappa_{i},\kappa_{j}\in\mathbb{S}\\},$ (1)

where $\mathbb{S}$ is the set of sensor positions in the array. The set of
resulting positions $\mathbb{D}$ describes the position of all virtual sensors
in the difference co-array. Fig. 1 shows an example of a 1-D nested array and
its difference co-array.

Figure 1: 1-D nested array (top) with aperture $N=11d$ and its difference co-
array (bottom). Circles mark sensors and crosses mark gaps. The positions of
all virtual sensors are calculated as the differences of positions of the
physical sensors.

In order to calculate the virtual sensor data of the difference co-array of a
given physical microphone array, the sample auto correlation matrix of the
array’s sensor data has to be vectorized:

$\displaystyle\mathbf{z}=\mathrm{vec}(\mathbf{\hat{R}}_{y})$
$\displaystyle=(\mathbf{A}^{*}\odot\mathbf{A})\mathbf{p}+\sigma_{n}^{2}\mathbf{1}_{n}$
(2) with $\displaystyle\mathbf{\hat{R}}_{y}$
$\displaystyle=\frac{1}{K}\sum_{k=1}^{K}\mathbf{y}[k]\mathbf{y}[k]^{\mathrm{H}},$
(3) $\displaystyle\mathbf{p}$
$\displaystyle=\left[\begin{array}[]{cccc}\sigma_{1}^{2}&\sigma_{2}^{2}&\cdots&\sigma_{M}^{2}\end{array}\right]^{\mathrm{T}}.$
(5)

Here, $\mathbf{y}[k]$ denotes the vector of microphone samples of the $k$-th
microphone and $\mathbf{p}$ holds the powers of the $M$ source signals, which
are the diagonal entries of the source auto correlation matrix
$\mathbf{R}_{s}$. The noise term is represented by
$\sigma_{n}^{2}{\mathbf{1}}_{n}$ and the Hermitian transpose of $\mathbf{y}$
is denoted by $\mathbf{y}^{\mathrm{H}}$. The effective array manifold matrix
$\mathbf{A}_{\mathrm{eff}}=\mathbf{A}^{*}\odot\mathbf{A}$ can be interpreted
as the steering matrix corresponding to the whole difference co-array and is
therefore able to exploit all DoF of the physical array [38]. The
$\odot$-operator denotes the Khatri-Rao product.

##### Spatial Smoothing

The virtual sensor data vector $\mathbf{z}$ cannot be used for DoA-estimation
directly because it behaves like fully coherent sources, which violates the
assumptions required by the subspace methods. This problem can be taken care
of in different ways, one of them being the spatial smoothing technique as
discussed by Pal and Vaidyanathan [38], which can be applied without
modification for any difference co-array that has a coherent ULA segment in
the 1-D case or a coherent URA segment in the 2-D case.

In order to be able to perform spatial smoothing, the data corresponding to
repeating virtual sensors in the difference co-array has to be removed and
afterwards the data is re-ordered. This is equivalent to only keeping unique
entries of the observation vector $\mathbf{z}$ and sorting them, which leads
to a new vector $\mathbf{z}_{1}$. The sorting is done such, that the data in
${\mathbf{z}_{1}}_{j}$ corresponds to the $j$-th element in the center ULA-
segment of the difference co-array.

Figure 2: Difference co-array and entries of auto correlation matrix of 1-D
nested array. Green squares denote virtual positions which appeared for the
first time, red squares denote positions which are repetitions of the green
positions.

Fig. 2 shows entries of the auto correlation matrix in the example of a 1-D
Nested array with physical positions $0d$, $1d$, $2d$, $3d$, $7d$, $11d$. In
this example, red boxes denote repeated (redundant) virtual sensor positions
in the difference co-array. Here, $\mathrm{vec}(\mathbb{D}^{\prime})$ denotes
the vector containing all elements of the set $\mathbb{D}$ in increasing order
regarding virtual sensor positions. The entries of the auto correlation matrix
$\mathbf{\hat{R}}_{y}$, which correspond to redundant virtual sensor
positions, are removed.

In the 2-D case, the ordering is performed such that the center URA-segment
ordering is matched [38].

Figure 3: Construction of spatial smoothing sub-arrays through the example of
1-D Nested array. Each sub-array consists of 12 virtual sensor positions and
therefore 12 auto correlation components. The overlap between neighboring sub-
arrays is chosen to be 10, maximizing the number of smoothed components.

The spatial smoothing step now divides the co-array into overlapping sub-
arrays, and calculates an auto correlation matrix on the corresponding segment
of the virtual sensor observation vector $\mathbf{z}_{1}$. Each individual
auto correlation matrix is computed as

$\displaystyle\mathbf{R}_{i}=\mathbf{z}_{1_{i}}\mathbf{z}_{1_{i}}^{\mathrm{H}}$
(6)

The selection of sub-arrays and the corresponding segments of $\mathbf{z}_{1}$
is visualized in Fig. 3. Finally, the spatial smoothing output auto
correlation matrix $\mathbf{R}_{ss}$ is computed by averaging over all
$\mathbf{R}_{l}$ with

$\displaystyle\mathbf{R}_{ss}=\frac{1}{L}\sum_{l=1}^{L}\mathbf{R}_{l}$ (7)

where $L$ is the number of sub-arrays of the difference co-array, which is a
design parameter depending on the array structure and size.

##### 2-D DoA estimation on sparse arrays

When spatial smoothing was performed, Multiple Signal Classification (MUSIC)
and Estimation of Signal Parameters via Rotational Invariance Techniques
(ESPRIT)[13, 14] can be used on the new auto correlation matrix
$\mathbf{R}_{ss}$ (see Eq. 7), as long as the sparse array is designed such,
that the difference co-array has a coherent URA center piece.

MUSIC has to be used with the steering matrix $\mathbf{A}$ corresponding to a
URA with the size of the segment that was used for the spatial smoothing step
in the previous section. If MUSIC is then performed on the spatially smoothed
auto correlation matrix $\mathbf{R}_{ss}$, the DoA of the signal impinging on
the original physical array can be estimated.

##  4 Hardware

One key property, which most sparse arrays have in common, is that all sensors
are placed on an equidistantly spaced grid, where each node has a distance $d$
to its neighboring nodes. Exploiting this property, each node can be filled
out by actual sensors, such, that multiple sparse geometries can be mapped
onto this grid by not using the data of specific nodes for estimation, given
these nodes are not part of the sparse array currently examined.

Figure 4: Hardware concept of sparse microphone arrays: The left side shows
the actual physical sensors present. On the right side, blue microphones are
actually used for estimation, in order to get the data corresponding to a 2-D
Nested array.

Fig. 4 illustrates this concept. It can be seen, that the only parameters
limiting the number of depictable geometries are the apertures (i.e., the
number of nodes) in x- and y-direction, respectively. Thus, these parameters
were chosen as large as possible, while still being able to sample with more
than double the frequency of the target sound source frequency band of around
$20\text{\,}\mathrm{kHz}$. The resulting array design is built as an 8x8 grid,
which results in a total of 64 microphones.

The main challenges of designing such a system for the acoustical use-case
include:

  * •

Synchronization of exact analog sampling times

  * •

Data integrity with several high frequency signals in the MHz range close to
each other

  * •

Ability to process and store data of all 64 microphones concurrently

In this contribution, the Micro-Electro-Mechanical Systems (MEMS) microphone
ICS52000 was chosen, as it is specifically designed for array applications.
The microphone uses a digital Time-Division Multiplexing (TDM) interface,
which enables having up to 16 microphones use a single data line and
synchronize with each other by sharing one clock line and daisy-chaining a
handshake signal through the whole chain of sensors.

In order to communicate to all microphones at once and store all the data in
parallel at sufficient speed, the communication unit for the system was chosen
to be a Field Programmable Gate Array (FPGA), since the TDM interface, as well
as an on-chip Random Access Memory (RAM) can be implemented in a parallelized
fashion.

Figure 5: Complete hardware system concept: The data flow moves from left to
right. Microphone data is recorded on the PCB, read by the Data Acquisition
Board, and sent to the computer for data handling and analysis.

The complete system concept is depicted in Fig. 5. For acquiring data, the
DE0-Nano-SoC evaluation board was chosen, which contains both a programmable
Cyclone V FPGA and a software programmable Hard Processor System (HPS),
facilitating low-level implementation of the TDM interface, data storage and
transfer to a computer.

###  4.1 System Implementation

Because the maximum number of interconnectable ICS52000 microphones is 16, the
whole eight by eight array is split into four sub-arrays, each taking up a
quarter of the full array. Each sub-array receives a copy of the system clock,
which is provided by a clock-buffer to ensure clean edges. In order to
synchronize the four sub-arrays among each other, the first microphone in each
of them obtains a global word select signal, which is directly connected to
the FPGA. To avoid timing differences induced by length differences of PCB
traces, all clock lines leading to a single microphone are matched to the same
length. The geometric distance $d$ between each neighboring microphone is set
to $8.255\text{\,}\mathrm{mm}$. This distance corresponds to half the smallest
wavelength $\lambda_{min}$ of a signal, which can still be sampled in the half
space. In other words, the largest allowed frequency of sound sources is
determined as
$f_{\mathrm{max}}=c\lambda_{\mathrm{min}}^{-1}=c(2d)^{-1}\approx$20.788\text{\,}\mathrm{kHz}$$
in free air at room temperature. If the frequency band of a sound source is
larger than this limit, robust estimation of its location will not be
possible. footnote 2 displays a picture of the developed array.

$70\text{\,}\mathrm{mm}$$85\text{\,}\mathrm{mm}$

Figure 6: The photo showcases the microphone array mounted on a two-axis
rotation table222Design files of the rotation table are available under:
https://github.com/e1kable/two-axis-rotation-table, essential for conducting
accuracy measurements. Microphone capsules are situated on the backside of the
PCB, linked to the front side via dedicated holes. The PCB is sandwiched onto
the Cyclone V FPGA board, which includes an Ethernet connection for data
transfer and control.

###  4.2 Signal Processing

The signal processing chain is structured as follows (cf. Fig. 7): First, the
$K\times N$ sample matrix, denoted as $\vec{S}$, is obtained by the array,
where $K$ represents the number of channels and $N$ represents the number of
samples. Next, each channel undergoes individual Bandpass Filter (BPF) to a
specific frequency using a 10th order Butterworth filter with a bandwidth $B$.
Subsequently, we apply a Hilbert transform to each channel to derive complex
In-Phase Quadrature (IQ) samples. Following this, a calibration matrix
$\vec{C}$, similar in size to the complex sample matrix, is applied to ensure
accuracy and consistency in the measurements, where $\circ$ denotes the
Hadamard product. Finally, the calibrated, complex sample matrix is passed
through to be further processed by the specific DoA estimators, yielding pairs
of azimuth and elevation angles, as detailed in Sec. 3.

$\mathbf{S}\in\mathbb{R}^{K\times N}$ BPF $\mathbb{H}\\{\cdot\\}$
$\mathbf{C}\circ\mathbf{S}\in\mathbb{C}^{K\times N}$ Estimator DoA
$(\hat{\varphi},\hat{\theta})$

Figure 7: Detailed Overview of the Signal Processing Chain: This figure
Depicts the progression from BPF and Hilbert transform application, through
calibration, to the final DoA estimation.

##  5 Simulation

In this section, we introduce various array geometries and simulatively assess
their performance. Each geometry’s beampattern is evaluated along with
quantitative metrics. The simulations are conducted using the intended design
parameters of the array, including dimensions and sampling frequency. The
probing signal employed is a complex sinusoid at $20\text{\,}\mathrm{kHz}$. In
addition to specific design rules such as Billboard or co-prime, a randomly
selected set of sensors is included as a last geometry, comprising
approximately the same number of sensors as the other sparse geometries.

Fig. 8 illustrates these geometries alongside their directional response to an
impinging wavefront in the broadside direction. The response is calculated
using a traditional delay-and-sum beamformer, providing insights into each
geometry’s performance, such as potential angle confusions due to large
sidelobes.

Table 1 provides quantitative metrics for evaluating the beampatterns of
various array geometries. Asymmetric geometries, such as the Open-box array,
naturally result in asymmetric beampatterns. The URA demonstrates the highest
Mainlobe Magnitude (MLM), outperforming the Nested array which shows a
reduction of approximately $-8\text{\,}\mathrm{dB}$. The Open-Box array is
distinguished by having the narrowest Mainlobe Width (MLW), as defined by the
$-3\text{\,}\mathrm{dB}$ attenuation threshold. Furthermore, the URA secures
the highest Mainlobe / Sidelobe Ratio (MSLR), with the Billboard array
following directly behind. The Coprime array is noted for achieving the
greatest Mainlobe / Sidelobe Separation (MSLS). The correlation between an
array’s symmetry and its beampattern’s symmetry is evident when contrasting
the URA with the Open-Box array in Fig. 8.

Figure 8: The figure depicts the array geometries under investigation alongside their corresponding beampatterns as achieved with a classic delay-and-sum beamformer. The magnitude of the beampattern is represented in dB and mapped to the radius. Array |  MLM in dB | MLW in $\deg$ | MSLR in dB | MSLS in $\deg$
---|---|---|---|---
URA |  0.00* | 13.57 | 12.80 | 21.71
Billboard | -9.28 | 12.66 | 7.38 | 20.35
Coprime | -9.68 | 14.47 | 3.18 | 90.00
Nested | -8.16 | 11.76 | 5.52 | 20.35
Open-Box | -9.28 | 9.95 | 3.26 | 17.64
Random | -8.89 | 12.66 | 5.56 | 23.07
Table 1: Comparison of serveral array metrics (* denotes the reference). In
this comparison, the mainlobe of the URA serves as the reference point for the
Main Lobe Magnitude (MLW). Furthermore, Mainlobe Width (MLW), Mainlobe to
Sidelobe Ratio (MSLR) and Mainlobe to Sidelobe Separation (MSLS) are detailed.

The overall angular error $e$ is assessed using the spherical angular distance
between the unit vectors of the estimated point $\vec{\hat{p}_{i}}$ and the
ground truth value $\vec{p_{i}}$ defined as

$e=\cos^{-1}\left(\vec{\hat{p}_{i}}^{\mathrm{T}}\vec{p_{i}}\right).$ (8)

This metric effectively addresses situations where uncertainties in the
azimuth angle may not lead to significant deviations, particularly noticeable
in low elevation angle regimes. Fig. 9 illustrates the achievable Mean Angular
Error under additive Gaussian noise with a specific modeled Signal-to-Noise
Ratio (SNR). In this simulation, the ordering is solely correlated with the
number of available sensors, with the URA configuration performing the best. A
similar outcome can be attained by assessing the CRLB[39, 40], which defines
the achievable Mean Squared Error (MSE) for both azimuth and elevation angles
separately. The advantage of this simulation lies in its ability to account
for irrelevant errors in fringe regions through a composite metric.

$\mathchar 45\relax 40$$\mathchar 45\relax 30$$\mathchar 45\relax
20$$\mathchar 45\relax 10$$0$$10$SNR in dB$10^{\mathchar 45\relax
1}$$10^{0}$$10^{1}$Mean Angular Error in degURABillboardCoprimeNestedOpen-
BoxRandom$\mathchar 45\relax 22$$\mathchar 45\relax 20$$\mathchar 45\relax
18$$10^{0}$$10^{1}$ Figure 9: Simulation across the angle space
$\varphi\in\left[$0\text{\,}\mathrm{\SIUnitSymbolDegree}$,$360\text{\,}\mathrm{\SIUnitSymbolDegree}$\right]$
and
$\theta\in\left[$0\text{\,}\mathrm{\SIUnitSymbolDegree}$,$90\text{\,}\mathrm{\SIUnitSymbolDegree}$\right]$
with $K=1000$ samples. The error metric is the spherical angles between
estimation and the GT point.

##  6 Experiments

In this section, the results of several experiments are presented. The
measurement setup is first introduced, followed by a discussion of the
calibration results. Next, various algorithms are compared against each other,
along with an evaluation of their performance using different sparse
geometries. The section concludes with an assessment of the system’s
capability to handle multiple concurrently emitting sources, accompanied by a
discussion of the obtained results.

###  6.1 Measurement Setup

The experiments are conducted within an anechoic chamber from the company
Wendt-Noise Control, providing an environment free from sound reflections and
external interference. The array is assembled onto a two-axis rotation table,
as depicted in footnote 2. This rotation table allows rotation in both azimuth
and elevation directions. A speaker is positioned approximately
$3.7\text{\,}\mathrm{m}$ away from the array to emit sound signals for
localization purposes. Additionally, a linear reference microphone is employed
to provide a reference for the measured amplitudes.

###  6.2 Calibration and Analysis

The calibration process comprises both phase calibration and amplitude
adjustment. The amplitude adjustment serves two purposes: firstly, to
standardize the microphones within the array relative to each other, and
secondly, to align the microphone data with Sound Pressure Levels $L_{p}$, in
decibels (dB) relative to $20\text{\,}\mathrm{\SIUnitSymbolMicro Pa}$.

To obtain dB SPL calibration values, a Behringer ECM8000 linear measurement
microphone is referenced with a B&K Type-4231 calibrator at
$94\text{\,}\mathrm{d}\mathrm{B}~{}\mathrm{S}\mathrm{P}\mathrm{L}$.
Subsequently, the frequencies are swept through in the range of
$10\text{\,}\mathrm{kHz}20\text{\,}\mathrm{kHz}$ and measured by both the
array and the measurement microphone, as depicted in Fig. 10 (a). The
variation in sound pressure level arises due to the characteristics of the
employed Beyma T2030 speaker.

In Fig. 10 (b), both uncalibrated and calibrated phase measurements are
displayed, indicating marginal differences at the shown frequency of
$20\text{\,}\mathrm{kHz}$. The sound pressure in dB is modeled with a Log-
normal distribution, with its fit shown in (c). In contrast to the phase
calibration, the total variance of the measured levels may be reduced by
around 40 percent.

It is important to note the significance of amplitude calibration in achieving
accurate Direction-of-Arrival (DoA) measurements, given the assumption of
equal gains across all sensors in the observation matrix $\vec{A}$. The
entries of the calibration matrix are chosen accordingly

$\vec{C}_{i,j}=A_{i,c}\mathrm{e}^{-\mathrm{j}\Psi_{i,c}}$ (9)

where $A_{i,c}$ represents the amplitude calibration factor and $\Psi_{i,c}$
denotes the measured phase factor. The index variable $i\in\\{1,\dots,K\\}$
corresponds to the channel index and $j\in\\{1,\dots,N\\}$ to the sample
index. The calibration process yields slightly more accurate estimations,
particularly noticeable in lower elevation angle regimes. For instance, below
$70\text{\,}\mathrm{\SIUnitSymbolDegree}$ at $20\text{\,}\mathrm{kHz}$, the
measured mean spherical error can be reduced from
$1.24\text{\,}\mathrm{\SIUnitSymbolDegree}$ to
$1.20\text{\,}\mathrm{\SIUnitSymbolDegree}$ .

Figure 10: Calibration analysis: (a) depicts the measured and calibrated sound
pressure levels obtained from the measurement microphone, along with those
recorded by the individual array microphones. (b) and (c) showcase histograms
illustrating the results of the phase and amplitude calibration specifically
at $20\text{\,}\mathrm{kHz}$. These plots include both the raw data
distribution and the fitted normal distributions (for phase) and Log-normal
distributions (for sound pressure).

###  6.3 DoA-Estimation (Single Source)

In order to show that the developed sensor system is capable of collecting
data which are suitable of estimating the AoA of a sound source, a set
spanning the complete range of azimuth and elevation angles is composed. The
incident sound pressure $L_{p}$ at the array is set to
$60\text{\,}\mathrm{d}\mathrm{B}~{}\mathrm{S}\mathrm{P}\mathrm{L}$, which
results in a SNR of around $30\text{\,}\mathrm{dB}$ (inband), in the given
anechoic environment. For each angle pair, the microphone array captures audio
samples which are then sent to a computer for analysis and ultimately
estimating the AoA of each source position. To ensure statistical convergence
of the results, each measurement has a duration of $T=$2\text{\,}\mathrm{s}$$,
resulting in $N=96000$ samples. With only one source involved in this
experiment, inter-source correlations pose no issue. Consequently, a simple
sinusoidal signal is broadcast from the source without the need for additional
processing or coding. The narrowband requirement of subspace algorithms is met
by applying a band-pass filter to the recorded microphone data as detailed in
Subsec. 4.2.

####  6.3.1 Comparison of algorithms

Three algorithms are compared using measured data: SRP-PHAT [41], Unitary
ESPRIT [42], and MUSIC [14]. A grid comprising 1036 different azimuth and
elevation pairs is sampled with the array. The collected samples are
preprocessed with a chunk size of $N=4096$, after which the different
estimators are applied to the processed data. In Fig. 11 (a), the overall
resulting cumulative distribution of the measured spherical error, calculated
using Eq. 8, is depicted. MUSIC performs the best with
$9.3\text{\,}\mathrm{\SIUnitSymbolDegree}$ in the 95th percentile, followed by
SRP-PHAT with $10.4\text{\,}\mathrm{\SIUnitSymbolDegree}$. Fig. 11 (b)
illustrates the distribution of errors, with the elevation angle on the radial
axis. The largest spherical error occurs in the high elevation angle regions,
primarily due to inaccuracies in the elevation angle estimation. Notably,
towards the broadside of the array, the error becomes minimal for all
investigated algorithms. Note the different color scale used for the ESPRIT
algorithm.

Figure 11: Algorithm evaluation on the URA: (a) presents the cumulative error
distribution for the different algorithms. Notably, the MUSIC algorithm
achieves the best performance with a 95% confidence interval error of
$9.3\text{\,}\mathrm{\SIUnitSymbolDegree}$. In (b), the error distribution
across the measured angle space is depicted. Note the different scaling used
for the colors representing the error of the ESPRIT algorithm.

####  6.3.2 Error Distribution

As depicted in Fig. 11, it is evident that the largest errors occur in the
lower elevation regions. When excluding these points, thereby narrowing the
field of view, the attainable error gets minimized. Fig. 12 displays the mean
and 95th percentile error alongside the left field of view in steradians when
excluding data above a certain elevation angle. The steep negative slope of
the 95th percentile curve illustrates this phenomenon. For instance, by
excluding all angles above 75 degrees, the attainable 95th percentile error
reduces to $2.8\text{\,}\mathrm{\SIUnitSymbolDegree}$ (or
$1.26\text{\,}\mathrm{\SIUnitSymbolDegree}$ mean spherical error) while still
retaining around $74\text{\,}\mathrm{\char 37\relax}$ of the Field of View
(FoV). In a real application, this can be implemented by ensuring overlapping
regions of multiple receiver arrays.

$90$$85$$80$$75$$70$$65$$60$$55$$50$$45$Max. included Elevation Angle in
deg$0.0$$2.5$$5.0$$7.5$$10.0$Mean Sph. Err. in
deg$0.0$$0.5$$1.0$$1.5$$2.0$Solid Angle in $\mathrm{sr}\cdot\pi^{-1}$Covered
Solid AngleMean Spherical Err.95% Spherical Err.

Figure 12: Error distribution evaluation: To assess error distribution,
certain points above a threshold are excluded from the evaluation. On the
secondary axis, the available solid angle in normalized steradians
$\mathrm{sr}/\pi$ is depicted, serving as a reference for understanding the
extent of the FoV lost by excluding specific angle sets.

####  6.3.3 Comparison of sparse array geometries

In order to compare sparse array geometries to each other, we used the same
data and parameters as in the previous section. Each sparse array’s data is
then constructed by masking only the microphones which are present in the
current geometry under evaluation and thus, only the data of those microphones
is included. Spatial smoothing is performed, using the apertures in x- and
y-direction of the difference co-array of each respective geometry as window
sizes. Finally, the 2-D Unitary ESPRIT algorithm is applied on the spatially
smoothed sample covariance matrix to estimate the DoA of the sound source. In
addition to this, the URA and Random arrays are included as a reference. For
the URA, once with spatial smoothing as discussed, and once without spatial
smoothing with the estimation algorithm directly working with the standard
sample covariance matrix.

To evaluate geometries capable of estimating more sources than there are
sensors, the unitary ESPRIT estimator with spatial smoothing is essential.
This methodology is specifically applicable to geometries that feature a
coherent URA centerpiece in their difference co-array. This criterion is met
by the geometries discussed herein, with the exception of the random array.
Given the prior introduction of the random array, it is included in the
analysis using the standard MUSIC algorithm, which does not have the
capability to estimate more sources than sensors. Interestingly, a comparison
of the 95th percentile error, as illustrated in Fig. 12, reveals a mere
increase of approximately $1\text{\,}\mathrm{\SIUnitSymbolDegree}$ in error
compared to the fully populated URA.

Fig. 13 illustrates the error distribution for the different array geometries.
Consistent with previous observations, errors tend to accumulate in the high
elevation angle regions across all geometries. Notably, the Coprime array
exhibits a strong azimuth angle dependency in the error distribution,
corroborating findings from Fig. 8. Conversely, the other sparse geometries
demonstrate comparable performance, as indicated by Fig. 14, which displays
the Cumulative Distribution Function (CDF). In this evaluation, the Open-Box
array performs best within the category of sparse geometries, followed by the
Nested and Billboard arrays (cf. Table 2). As expected, the Coprime array,
characterized by the smallest aperture size and fewest number of sensors,
demonstrates the poorest performance.

Figure 13: Error distribution analysis of different array geometries reveals a similar trend as in the algorithms evaluation, with errors accumulating in the high elevation angle regions. It’s noteworthy that the MUSIC estimator is utilized for the Random array. Conversely, the ESPRIT algorithm with Spatial Smoothing is employed for the rest of the geometries. Additionally, spatial smoothing is applied for URA-SS, a necessity for the other sparse geometries to achieve data augmentation. $0$$5$$10$$15$$20$$25$$30$$35$$40$Mean Spherical Error in deg for $\theta\leq$ 75°$0.0$$0.2$$0.4$$0.6$$0.8$$1.0$Cumulative ProbabilityRandomURAURA-SSOpen-BoxNestedBillboardCoprime Figure 14: The cumulative distribution function of the mean spherical error is computed with higher elevations $\theta\leq$75\text{\,}\mathrm{\SIUnitSymbolDegree}$$ excluded. Array |  50% CI in deg |  95% CI in deg |  Estimator
---|---|---|---
URA | 1.26 | 12.22 | U. ESPRIT
URA-SS | 3.49 | 25.57 | U. ESPRIT + SS
Billboard | 7.17 | 38.24 | U. ESPRIT + SS
Coprime | 27.45 | 62.96 | U. ESPRIT + SS
Nested | 5.74 | 39.41 | U. ESPRIT + SS
Open-Box | 4.85 | 31.85 | U. ESPRIT + SS
Random | 1.34 | 3.76 | MUSIC
Table 2: Distribution of the spherical error across different array geometries
with 50- and 95-percentile CIs. This data only takes elevation angles with
$\theta\leq$75\text{\,}\mathrm{\SIUnitSymbolDegree}$$ into account.

###  6.4 DoA-Estimation (Multiple Sources)

In this experiment, three cooperative sources (Tags) are positioned within the
anechoic chamber using a laser which is mounted on a two-axis rotation table,
as depicted in Fig. 15. The tags are equipped with piezoelectric speakers. The
source signals, which are bandlimited ($B=$200\text{\,}\mathrm{Hz}$$) Walsh-
Hadamard sequences mixed to $20\text{\,}\mathrm{kHz}$, ensure good cross-
correlation properties. The tags emit signals simultaneously at an incident
sound pressure ranging from
$50\text{\,}\mathrm{d}\mathrm{B}~{}\mathrm{S}\mathrm{P}\mathrm{L}$ (Tag 2) to
$55\text{\,}\mathrm{d}\mathrm{B}~{}\mathrm{S}\mathrm{P}\mathrm{L}$ (Tag 1).
Instead of employing the data-augmented ESPRIT estimator, the MUSIC estimator
is applied to the nested array selection of the captured data, as depicted in
Figure 4. Fig. 16 presents the MUSIC pseudospectrum of the captured scene
along with the mean spherical error for all three sources. The error ranges
from $0.4\text{\,}\mathrm{\SIUnitSymbolDegree}$ up to
$1.6\text{\,}\mathrm{\SIUnitSymbolDegree}$, primarily depending on the
elevation angle.

123TagsArray

Figure 15: The multisource experiment setup involves positioning three tags
within an anechoic chamber at varying angles. Each tag reproduces a distinct
Walsh-Hadamard sequence. The signals emitted by the tags are sampled by the
array located in the lower right-hand corner. Figure 16: Multiple source
estimation using the Nested array and the standard MUSIC estimator instead of
a data-augmented covariance matrix estimator. In (a), the MUSIC pseudospectrum
of the scene is depicted, with different tag IDs highlighted. (b) illustrates
the mean spherical error for the various tag positions.

###  6.5 Discussion

In the initial experiments, we observed that calibration provided only
marginal benefits, particularly in lower elevation angle regions, highlighting
the robustness of the hardware concept and the quality of the used
microphones. Subsequent analysis of single-source experiments revealed that
errors tend to accumulate in higher elevation angle regions. When designing
localization systems, it may be advisable to ensure overlapping regions where
angle measurements in the higher elevation angle range can be discarded or de-
weighted. The URA, while not isotropic, does not exhibit strong, noticeable
azimuth angle-dependent behavior. Furthermore, we observed that the general-
purpose SRP-PHAT algorithm, widely applied in various applications, performed
worse than the specialized MUSIC algorithm, especially for narrowband signals.
Comparison of multiple array geometries unveiled their performance on real-
world data, with some geometries struggling with azimuth angle dependency,
resulting in inferior estimation performance in general. Notably, increasing
sensor count and aperture size typically leads to better performance. However,
distributing sensors too sparsely in various directions to optimize aperture
size can yield azimuthal dependencies. It’s also worth mentioning that
estimating multiple concurrent sources is possible by employing orthogonal
codes, which may also enable source identification.

##  7 Conclusions and Outlook

In this contribution, a measurement platform has been proposed for the
evaluation of several sparse array geometries. The platform consists of 64
microphones in URA configuration, tuned to a maximum frequency of around
$20.8\text{\,}\mathrm{kHz}$. Through a series of simulations and experiments,
we have demonstrated the feasibility and effectiveness of sparse array
geometries in accurately estimating the direction of arrival of sound sources
in indoor environments. The developed array demonstrates promising
performance, achieving a 95-percentile spherical error of
$2.8\text{\,}\mathrm{\SIUnitSymbolDegree}$ (or a mean error of
$1.26\text{\,}\mathrm{\SIUnitSymbolDegree}$) when high-error producing regions
are excluded using the MUSIC estimator. Our investigation encompassed various
sparse array geometries, revealing notable angle dependencies in some
configurations. Among these, geometries like the Open-Box or Nested array
exhibited superior performance on applied metrics. Furthermore, an experiment
involving three concurrently emitting sources demonstrated the feasibility of
resolving multiple sources simultaneously.

In future research, we aim to explore the capability of estimating more
sources than sensors. Key steps towards this objective will involve finding
optimized orthogonal codes to ensure optimal cross-correlation properties.

## References

  * [1] Dong-Ho Shin and Tae-Kyung Sung, “Comparisons of error characteristics between toa and tdoa positioning,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 38, no. 1, pp. 307–311, 2002.
  * [2] Don Torrieri, “Statistical theory of passive location systems,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. AES-20, no. 2, pp. 183–198, 1984.
  * [3] Rongyan Zhou, Jianfeng Chen, Weijie Tan, Qingli Yan, and Chang Cai, “Optimal 3d angle of arrival sensor placement with gaussian priors,” _Entropy_ , vol. 23, no. 11, p. 1379, 2021.
  * [4] G. Fischer, J. Bordoy, D. J. Schott, W. Xiong, A. Gabbrielli, F. Hoflinger, K. Fischer, C. Schindelhauer, and S. J. Rupitsch, “Multimodal indoor localization: Fusion possibilities of ultrasonic and bluetooth low-energy data,” _IEEE Sensors Journal_ , vol. 22, no. 6, pp. 5857–5868, 2022.
  * [5] M. Girolami, F. Mavilia, F. Furfari, and P. Barsocchi, “An experimental evaluation based on direction finding specification for indoor localization and proximity detection,” _IEEE Journal of Indoor and Seamless Positioning and Navigation_ , vol. 2, pp. 36–50, 2024.
  * [6] A. Sesyuk, S. Ioannou, and M. Raspopoulos, “Radar-based millimeter-wave sensing for accurate 3-d indoor positioning: Potentials and challenges,” _IEEE Journal of Indoor and Seamless Positioning and Navigation_ , vol. 2, pp. 61–75, 2024.
  * [7] A. N. Mirkin and L. H. Sibul, “Cramer-rao bounds on angle estimation with a two-dimensional array,” _IEEE Transactions on Signal Processing_ , vol. 39, no. 2, pp. 515–517, 1991.
  * [8] F. Wen, P. Liu, H. Wei, Y. Zhang, and R. C. Qiu, “Joint azimuth, elevation, and delay estimation for 3-d indoor localization,” _IEEE Transactions on Vehicular Technology_ , vol. 67, no. 5, pp. 4248–4261, 2018.
  * [9] Z. Zhang, Z. Shi, and Y. Gu, “Ziv-zakai bound for doas estimation,” _IEEE Transactions on Signal Processing_ , vol. 71, pp. 136–149, 2023.
  * [10] Bluetooth SIG, “Bluetooth core specification 5.1.” [Online]. Available: https://www.bluetooth.com/specifications/specs/core-specification-5-1/
  * [11] F. Höflinger, R. Zhang, J. Hoppe, A. Bannoura, L. M. Reindl, J. Wendeberg, M. Buhrer, and C. Schindelhauer, “Acoustic self-calibrating system for indoor smartphone tracking (assist),” in _2012 International Conference on Indoor Positioning and Indoor Navigation (IPIN)_. IEEE, 2012, pp. 1–9.
  * [12] A. Gabbrielli, G. K. Fischer, T. Schaechtle, W. Xiong, D. J. Schott, J. Bordoy, J. Wendeberg, F. Höflinger, C. Schindelhauer, and S. J. Rupitsch, “Airborne acoustic chirp spread spectrum communication system for user identification in indoor localization,” _IEEE Transactions on Instrumentation and Measurement_ , p. 1, 2023.
  * [13] R. Roy, A. Paulraj, and T. Kailath, “Esprit–a subspace rotation approach to estimation of parameters of cisoids in noise,” _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 34, no. 5, pp. 1340–1342, 1986\.
  * [14] R. Schmidt, “Multiple emitter location and signal parameter estimation,” _IEEE Transactions on Antennas and Propagation_ , vol. 34, no. 3, pp. 276–280, 1986.
  * [15] G. K. Fischer, N. Thiedecke, A. Gabbrielli, T. Schaechtle, F. Höflinger, A. Stolz, and S. J. Rupitsch, “A measurement platform for the evaluation of sparse acoustic array geometries,” in _2023 13th International Conference on Indoor Positioning and Indoor Navigation (IPIN)_. IEEE, 2023, pp. 1–6.
  * [16] M. M. Saad, C. J. Bleakley, T. Ballal, and S. Dobson, “High-accuracy reference-free ultrasonic location estimation,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 61, no. 6, pp. 1561–1570, 2012.
  * [17] G. Li, L. Zhang, F. Lin, M. Chen, and Z. Wang, “Sailoc: A novel acoustic single array system for indoor localization,” in _2017 9th International Conference on Wireless Communications and Signal Processing (WCSP)_. IEEE, 2017, pp. 1–6.
  * [18] S. Ogiso, K. Mizutani, N. Wakatsuki, and T. Ebihara, “Robust indoor localization in a reverberant environment using microphone pairs and asynchronous acoustic beacons,” _IEEE Access_ , vol. 7, pp. 123 116–123 127, 2019.
  * [19] A. Gabbrielli, J. Bordoy, W. Xiong, G. K. J. Fischer, T. Schaechtle, J. Wendeberg, F. Hoflinger, C. Schindelhauer, and S. J. Rupitsch, “Rails: 3-d real-time angle of arrival ultrasonic indoor localization system,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 72, pp. 1–15, 2023.
  * [20] A. Gabbrielli, W. Xiong, D. J. Schott, G. Fischer, J. Wendeberg, F. Hoflinger, L. M. Reindl, C. Schindelhauer, and S. J. Rupitsch, “An echo suppression delay estimator for angle of arrival ultrasonic indoor localization,” _IEEE Transactions on Instrumentation and Measurement_ , p. 1, 2021.
  * [21] I. Aboumahmoud, A. Muqaibel, M. Alhassoun, and S. Alawsh, “A review of sparse sensor arrays for two-dimensional direction-of-arrival estimation,” _IEEE Access_ , vol. 9, pp. 92 999–93 017, 2021.
  * [22] P. Pal and P. P. Vaidyanathan, “Nested arrays: A novel approach to array processing with enhanced degrees of freedom,” _IEEE Transactions on Signal Processing_ , vol. 58, no. 8, pp. 4167–4181, 2010.
  * [23] ——, “Nested arrays in two dimensions, part i: Geometrical considerations,” _IEEE Transactions on Signal Processing_ , vol. 60, no. 9, pp. 4694–4705, 2012.
  * [24] ——, “Nested arrays in two dimensions, part ii: Application in two dimensional array processing,” _IEEE Transactions on Signal Processing_ , vol. 60, no. 9, pp. 4706–4718, 2012.
  * [25] S. Nannuru, A. Koochakzadeh, K. L. Gemba, P. Pal, and P. Gerstoft, “Sparse bayesian learning for beamforming using sparse linear arrays,” _The Journal of the Acoustical Society of America_ , vol. 144, no. 5, p. 2719, 2018\.
  * [26] P. P. Vaidyanathan and P. Pal, “Sparse sensing with co-prime samplers and arrays,” _IEEE Transactions on Signal Processing_ , vol. 59, no. 2, pp. 573–586, 2011.
  * [27] C.-L. Liu and P. P. Vaidyanathan, “Cramér–rao bounds for coprime and other sparse arrays, which find more sources than sensors,” _Digital Signal Processing_ , vol. 61, pp. 43–61, 2017.
  * [28] Q. Wu, F. Sun, P. Lan, G. Ding, and X. Zhang, “Two-dimensional direction-of-arrival estimation for co-prime planar arrays: A partial spectral search approach,” _IEEE Sensors Journal_ , vol. 16, no. 14, pp. 5660–5670, 2016.
  * [29] C.-L. Liu and P. P. Vaidyanathan, “Hourglass arrays and other novel 2-d sparse arrays with reduced mutual coupling,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 13, pp. 3369–3383, 2017.
  * [30] L. Sun, M. Yang, and B. Chen, “Thermos array: Two-dimensional sparse array with reduced mutual coupling,” _International Journal of Antennas and Propagation_ , vol. 2018, pp. 1–8, 2018.
  * [31] C.-L. Liu and P. P. Vaidyanathan, “Cramér–rao bounds for coprime and other sparse arrays, which find more sources than sensors,” _Digital Signal Processing_ , vol. 61, pp. 43–61, 2017.
  * [32] A. Ramalli, E. Boni, E. Roux, H. Liebgott, and P. Tortoli, “Design, implementation, and medical applications of 2-d ultrasound sparse arrays,” _IEEE transactions on ultrasonics, ferroelectrics, and frequency control_ , vol. 69, no. 10, pp. 2739–2755, 2022.
  * [33] J. Zhao and C. Ritz, “Semi-coprime microphone arrays for estimating direction of arrival of speech sources,” in _2019 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)_. IEEE, 2019, pp. 308–313.
  * [34] D. Bush and N. Xiang, “Broadband implementation of coprime linear microphone arrays for direction of arrival estimation,” _The Journal of the Acoustical Society of America_ , vol. 138, no. 1, pp. 447–456, 2015.
  * [35] ——, “A model-based bayesian framework for sound source enumeration and direction of arrival estimation using a coprime microphone array,” _The Journal of the Acoustical Society of America_ , vol. 143, no. 6, pp. 3934–3945, 2018. [Online]. Available: https://asa.scitation.org/doi/full/10.1121/1.5042162
  * [36] F. Wang, Z. Tian, G. Leus, and J. Fang, “Direction of arrival estimation of wideband sources using sparse linear arrays,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 4444–4457, 2021.
  * [37] S. Nannuru, P. Gerstoft, G. Ping, and E. Fernandez-Grande, “Sparse planar arrays for azimuth and elevation using experimental data,” _The Journal of the Acoustical Society of America_ , vol. 149, no. 1, p. 167, 2021.
  * [38] P. Pal and P. P. Vaidyanathan, “Nested Arrays: A Novel Approach to Array Processing With Enhanced Degrees of Freedom,” _IEEE Transactions on Signal Processing_ , vol. 58, no. 8, pp. 4167–4181, Aug. 2010\.
  * [39] P. Stoica and A. Nehorai, “Performance study of conditional and unconditional direction-of-arrival estimation,” _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 38, no. 10, pp. 1783–1795, 1990.
  * [40] ——, “Music, maximum likelihood, and cramer-rao bound,” _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 37, no. 5, pp. 720–741, 1989.
  * [41] J. H. Dibiase, _A high-accuracy, low-latency technique for talker localization in reverberant environments using microphone arrays_. Brown University Providence, RI, 2000.
  * [42] M. D. Zoltowski, M. Haardt, and C. P. Mathews, “Closed-form 2-d angle estimation with rectangular arrays in element space or beamspace via unitary esprit,” _IEEE Transactions on Signal Processing_ , vol. 44, no. 2, pp. 316–328, 1996.

[]Georg K.J. Fischer received the B.Sc. degree in electrical engineering from
the TU Braunschweig, Germany in 2017 and the M.Sc. degree in electrical
engineering and information technology from the Karlsruhe Institute of
Technology (KIT), Germany in 2019. He joined the Fraunhofer Ernst-Mach-
Institute (EMI) in 2020, as a research assistant in the field of signal
processing.

[]Niklas Thiedecke received the B.Sc. degree in electrical engineering and
information technology from the TU Kaiserslautern, Germany in 2018 and the
M.Sc. degree in embedded systems engineering in 2022 from the University of
Freiburg, Germany. He was employed from 2018 to 2019 at Bosch Sensortec GmbH,
Germany, where he participated in Bosch’s PreMaster-program, working in the
field of smart sensor development. Since August 2022, he’s employed at Bosch
Sensortec GmbH, Germany as a system architect for pre-development and
development of smart sensors and smart connected sensors.

[]Thomas Schaechtle received his B.Eng. degree in electrical engineering from
the Cooperative State University DHBW Lörrach in 2013 with TDK-Micronas,
Freiburg, as education partner and the M.Sc. degree in embedded systems
engineering in 2018 from the University of Freiburg. In 2018, he started as a
Ph.D candidate at the Laboratory of Electrical Instrumentation and Embedded
Systems, University of Freiburg. He was employed from 2010 to 2014 at TDK-
Micronas, where he worked one year as an application engineer in a gas sensor
research group. Since April 2022, he has been also working as research
assistant for the Fraunhofer Ernst-Mach-Institute (EMI) in the field of
ultrasonic communication.

[]Andrea Gabbrielli received the B.Sc. degree in telecommunications
engineering from the Faculty of Engineering of the University of Pisa, Pisa,
Italy, in 2014, the M.Sc. degree in computer science and the Ph.D. degree in
microsystems engineering from the Faculty of Engineering of the University of
Freiburg, Freiburg im Breisgau, Germany, in 2019 and 2024, respectively. He
joined the Laboratory for Electrical Instrumentation and Embedded Systems at
the Department of Microsystems Engineering (IMTEK), University of Freiburg,
Germany, in 2019, as a scientific researcher in the field of signal processing
for indoor localization.

[]Fabian Höflinger received the B.Sc. degree in automation engineering from
the University of Applied Sciences Ravensburg-Weingarten, Weingarten, Germany,
in 2007, the master’s degree in automation and energy systems from the
Mannheim University of Applied Sciences, Mannheim, Germany, in 2007, and the
Ph.D. degree in microsystems engineering, University of Freiburg, Freiburg im
Breisgau, Germany, in 2014, with a focus on localization systems.

He was with Junghans Feinwerktechnik, Dunningen/Seedorf, Germany, where he
developed components for telemetric systems. From 2007 to 2010, he was a
Development Engineer. Since 2010, he has been with the Laboratory for
Electrical Instrumentation and Embedded Systems, Department of Microsystems
Engineering, University of Freiburg, where he has also been a Group Leader
since 2014 and has a research group in the field of indoor localization. Since
2019, he has also been working for the Fraunhofer Ernst-Mach-Institute (EMI).

[]Alexander Stolz holds the Professorship for Resilience Engineering of
Technical Systems at the Department of Sustainable Systems Engineering at the
Faculty of Engineering of the Albert-Ludwigs-University in Freiburg. He
studied civil engineering at University of Wuppertal and wrote his doctoral
thesis about mobilization of bedding stresses in granular soil at the
Professorship for Geotechnique. As head of the department Safety, Security and
Resilience of Technical Systems he is specialized in the experimental
investigation and numerical modeling of complicated and complex structures and
networks under extraordinary disruptive events. Dr. Stolz coordinated the
Thematic Group “Resistance of structures to explosion effects” in the ERNCIP
(European Reference network for Critical Infrastructure protection) framework
from 2012 till 2020 and is since 2017 also appointed international member of
the AMR10 Committee on Critical Infrastructure Protection.

[]Stefan J. Rupitsch (Member, IEEE) was born in Kitzbuehel, Austria, in 1978.
He received the Diploma and Ph.D. degrees in mechatronics from Johannes Kepler
University Linz, Austria, in 2004 and 2008, respectively, and the Habilitation
degree from the University of Erlangen–Nuernberg, Germany, in 2018.

In 2004, he was a Junior Researcher with the Linz Center of Mechatronics,
Linz. From 2005 to 2008, he was with the Institute for Measurement Technology,
Johannes Kepler University Linz. From 2008 to 2020, he was with the Chair of
Sensor Technology, University of Erlangen–Nuernberg, where he held a Deputy
Professorship. Since December 2020, he has been a Full Professor for
electrical instrumentation and embedded systems with the University of
Freiburg.

His research interests include piezoelectric transducers, energy harvesting,
embedded systems, ultrasonic imaging and therapy, simulation-based material
characterization, and noncontact measurements. He has authored more than 150
articles in these fields as well as the book Piezoelectric Sensors and
Actuators: Fundamentals and Applications.

Stefan J. Rupitsch was a recipient of the Austrian Society of Measurement and
Automation Technology Award for his Ph.D. dissertation in 2009 and the
Outstanding Paper Award of the Information Technology Society in 2016. He is
an Associate Editor of the IEEE SENSORS JOURNAL and the TM-Technisches Messen
journal. He serves as a Guest Associate Editor for the Journal of Sensors and
Sensor Systems (JSSS).

  *[AoA]: Angle-of-Arrival
  *[ToF]: Time-of-Flight
  *[TDoA]: Time-Difference-of-Arrival
  *[DoA]: Direction-of-Arrival
  *[GDoP]: Geometric Dilution of Precision
  *[UWB]: Ultra-Wideband
  *[RF]: Radio Frequency
  *[URA]: Uniform Rectangular Array
  *[UCA]: Uniform Circular Array
  *[CRLB]: Cramér-Rao Lower Bound
  *[SBL]: Sparse Bayesian learning
  *[URAs]: Uniform Rectangular Array
  *[DoF]: Degrees-of-Freedom
  *[ULA]: Uniform Linear Array
  *[MUSIC]: Multiple Signal Classification
  *[ESPRIT]: Estimation of Signal Parameters via Rotational Invariance Techniques
  *[MEMS]: Micro-Electro-Mechanical Systems
  *[TDM]: Time-Division Multiplexing
  *[FPGA]: Field Programmable Gate Array
  *[RAM]: Random Access Memory
  *[PCB]: Printed Circuit Board
  *[HPS]: Hard Processor System
  *[BPF]: Bandpass Filter
  *[IQ]: In-Phase Quadrature
  *[MLM]: Mainlobe Magnitude
  *[MLW]: Mainlobe Width
  *[MSLR]: Mainlobe / Sidelobe Ratio
  *[MSLS]: Mainlobe / Sidelobe Separation
  *[SNR]: Signal-to-Noise Ratio
  *[MSE]: Mean Squared Error
  *[GT]: Ground Truth
  *[SPL]: Sound Pressure Level
  *[FoV]: Field of View
  *[CDF]: Cumulative Distribution Function
  *[CIs]: Confidence Interval


# Uncovering Selective State Space Model’s Capabilities in Lifelong Sequential
Recommendation

Jiyuan Yang<EMAIL_ADDRESS>Shandong UniversityQingdaoChina ,
Yuanzi Li<EMAIL_ADDRESS>Shandong UniversityQingdaoChina ,  Jingyu
Zhao<EMAIL_ADDRESS>Shandong UniversityQingdaoChina ,  Hanbing
Wang<EMAIL_ADDRESS>Michigan State UniversityEast LansingUSA ,
Muyang Ma<EMAIL_ADDRESS>Shandong UniversityQingdaoChina ,  Jun Ma
<EMAIL_ADDRESS>Shandong UniversityQingdaoChina ,  Zhaochun Ren
<EMAIL_ADDRESS>Leiden UniversityLeidenThe Netherlands ,  Mengqi
Zhang<EMAIL_ADDRESS>Shandong UniversityQingdaoChina ,  Xin Xin
<EMAIL_ADDRESS>Shandong UniversityQingdaoChina ,  Zhumin Chen
<EMAIL_ADDRESS>Shandong UniversityQingdaoChina and  Pengjie Ren
<EMAIL_ADDRESS>Shandong UniversityQingdaoChina

(2018)

###### Abstract.

Sequential Recommenders have been widely applied in various online services,
aiming to model users’ dynamic interests from their sequential interactions.
With users increasingly engaging with online platforms, vast amounts of
lifelong user behavioral sequences have been generated. However, existing
sequential recommender models often struggle to handle such lifelong
sequences. The primary challenges stem from computational complexity and the
ability to capture long-range dependencies within the sequence.

Recently, a state space model featuring a selective mechanism (i.e., Mamba)
has emerged. In this work, we investigate the performance of Mamba for
lifelong sequential recommendation (i.e., length¿=2k). More specifically, we
leverage the Mamba block to model lifelong user sequences selectively. We
conduct extensive experiments to evaluate the performance of representative
sequential recommendation models in the setting of lifelong sequences.
Experiments on two real-world datasets demonstrate the superiority of Mamba.
We found that RecMamba achieves performance comparable to the representative
model while significantly reducing training duration by approximately 70% and
memory costs by 80%. Codes and data are available at
https://github.com/nancheng58/RecMamba.

Sequential Recommendation, Long-term Recommendation, State Space Models

††copyright: acmlicensed††journalyear: 2018††doi: XXXXXXX.XXXXXXX††conference:
Make sure to enter the correct conference title from your rights confirmation
emai; June 03–05, 2018; Woodstock, NY††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Over the past decade, recommender systems have been widely applied in various
online services, e.g., online shopping (Hu et al., 2018), video or music
platforms (Yuan et al., 2019), news recommendation (Qi et al., 2020), etc.,
with the primary aim of offering users the most compelling items through the
modeling of user interests. Sequential recommendation, a burgeoning field
within recommendation systems, focuses on extracting dynamic user interests
from their sequential interactions. The key to sequential recommendation is to
capture user interests by modeling user interaction sequences. Early studies
in sequential recommendations utilize Markov Chains (Rendle et al., 2010; He
et al., 2016) for modeling user interaction sequences. Over the past few
years, plenty of deep learning-based sequential recommendation models have
been proposed, including recurrent neural networks (RNN) (Hidasi et al.,
2016a, b), convolutional neural networks (CNN) (Yuan et al., 2019; Tang and
Wang, 2018), graph neural networks (GNN) (Wu et al., 2019; Zhang et al.,
2022), attention-based methods (Li et al., 2017; Kang and McAuley, 2018; Sun
et al., 2019) and Transformer-based methods (de Souza Pereira Moreira et al.,
2021).

However, the aforementioned methods are constrained in their ability to model
long user interaction sequences for several reasons. For instance, Markov
Chains-based methods (Rendle et al., 2010; He et al., 2016) assume that the
next interaction is dependent ony on the previous interaction (or a few
preceding ones), making it challenging to characterize long-range item
transitions. GRU4Rec (Hidasi et al., 2015) may not be optimal for lifelong
sequence recommendation due to information forgetting and inherent vanishing
gradients. SASRec (Kang and McAuley, 2018) encounters challenges in modeling
long sequences due to the huge memory requirements and the quadratic
complexity in the input length of self-attention. Currently, the majority of
research only allows their models to accept about 200 user interaction records
(Lin et al., 2023).

The primary challenge in modeling lifelong user interaction sequences revolves
around two key aspects: i) How to efficiently handle extended user behavior
sequences, while addressing concerns like data sparsity and computational
complexity? and ii) How to capture long-range item transition dependencies
within the sequence? Recently, Mamba (Gu and Dao, 2023), a novel state space
model featuring a selective mechanism has emerged, with the aim of achieving
the modeling power of Transformer (Vaswani et al., 2017) while scaling
linearly in sequence length. Some works leverage Mamba for various downstream
tasks, such as visual tasks (Zhu et al., 2024; Liu et al., 2024b), medical
applications (Ma et al., 2024), recommendation (Liu et al., 2024a), and so on.
In this scenario, we are curious about examining the performance of both early
models and Mamba when modeling long (i.e., length¿=2k) sequences.

In this work, we investigate the performance of Mamba in sequential
recommendation, especially for lifelong user behavior sequences. Specifically,
we introduce RecMamba, a sequential recommendation framework that utilizes the
Mamba block to model user preferences over time. By integrating the
capabilities of Mamba into our framework, we aim to improve recommendation
performance and better accommodate evolving user preferences in lifelong
sequential recommendation scenarios. We conduct experiments to assess the
effectiveness of prominent recommendation models for long user sequence (i.e.,
length¿=2k) scenarios on two real-world datasets. We found that  (1) the
performance of RecMamba improves as the length increases on two real-world
datasets; and  (2) RecMamba achieves superior performance than representative
sequential models. More specifically, RecMamba achieves comparable performance
with the representative model SASRec while greatly reducing about 70% training
duration and 80% memory costs.

##  2\. Leveraging Mamba for Sequential Recommendation

State Space Models (SSMs) (Gu et al., 2021; Smith et al., 2022) are a class of
models for sequence modeling. Recently, a novel space state model
incorporating the selective mechanism (i.e., Mamba) (Gu and Dao, 2023) has
become a hot topic. Compared with prior SSMs, Mamba introduces a data-
dependence selection mechanism and utilizes a parallel algorithm optimized for
hardware in recurrent mode, enabling effective sequence modeling, particularly
for long sequences.

Lifelong sequential recommendation is a common task involving long-sequence
modeling. Mamba4Rec (Liu et al., 2024a) is the pioneer in utilizing Mamba for
efficient sequential recommendation. Compared to SASRec (Kang and McAuley,
2018), the principal architectural modification in Mamba4Rec involves
substituting the self-attention block with the Mamba block. In contrast to
Mamba4Rec, our approach, Rec-Mamba, replaces the Transformer layer with the
Mamba block, thereby improving the efficiency of processing lifelong
sequences.

##  3\. Experiments

###  3.1. Methods for Comparison

To demonstrate the effectiveness of RecMamba on lifelong sequential
recommendation, we compare it with a range of representative recommender
models based on Transformers, RNNs, and Linear Transformer:

  * •

SASRec (Kang and McAuley, 2018) is a method that employs the traditional self-
attention block, specifically multi-head attention, to generate sequence
representations.

  * •

GRU4Rec (Cho et al., 2014) is a pioneering method leveraging RNNs to model
user action sequences for session-based recommendation, treating each user’s
feedback sequence as a session.

  * •

Linrec (Liu et al., 2023) adopts a linear Transformer architecture that
utilizes L2 norm to approximate softmax fitting.

###  3.2. Datasets

In recent years, plenty of long-term or lifelong recommendation works have
emerged (Huang et al., 2018; Pi et al., 2019). However, the sequence lengths
discussed in these studies typically range from 10 to 200. We think that such
sequences do not aptly represent a ‘lifelong’ user interests. For instance, in
the micro-video scenario, users watch dozens or hundreds of videos daily.
Hence, conducting experiments assessing model performance on extended
sequences is imperative.

To this end, we choose two real-world datasets with longer user interaction
sequences KuaiRand111https://kuairand.com/ (Gao et al., 2022) and
LFM-1b222http://www.cp.jku.at/datasets/LFM-1b/ (Schedl, 2016) to conduct the
experiments. All items in the sequence are arranged based on chronological
order. We filter out users and items with less than 3 recorded interactions.

Table 1 summarizes the statistics of the two datasets.

Table 1. Dataset statistics. Dataset | KuaiRand | LFM-1b
---|---|---
#users | 27,285 | 120,322
#items | 32,038,725 | 31,634,450
#interactions | 322,278,385 | 1,088,161,692
#avg.len | 11,811 | 9,043

  * •

KuaiRand. KuaiRand is a large-scale dataset derived from the famous micro-
video platform Kuaishou. It uniquely features millions of randomly exposed
items inserted in the standard feeds, ensuring unbiased sequential
recommendations. This dataset contains 27,285 users and 32,038,725 videos and
the average interaction length is 11,811.

  * •

LFM-1b. This is a large-scale dataset conducted by the music platform Last.FM,
which contains more than one billion music-listening interactions covering
31,634,450 music and a total of 120,322 user clicks. The average interaction
length is 9,043.

###  3.3. Implementation Details

We adopted the hyperparameter settings used for sequence recommendation due to
the absence of prior work on sequence recommendation with lengths exceeding
2k. The trainable parameters were initialized using Xavier normal
distribution. We employed the Adam optimizer for each model. For all models,
we used the batch size of 256 for sequence length of 2k, while for the length
of 5k, we used a batch size of 256 for RecMamba, Linrec, GRU4Rec, and a batch
size of 32 for SASRec to avoid Out-of-Memory. The setting of the learning rate
is 0.0004 and 0.0002, respectively. The hidden layer size is set to 50. We pad
the sequence with an additional padding item if the sequence length is less
than 2k. All models were trained 500 epochs on NVIDIA A800 80G.

###  3.4. Evaluation Protocols

Following existing sequential recommendation studies (Kang and McAuley, 2018;
Zhou et al., 2020; Sun et al., 2019; Wang et al., 2024), we split data by the
leave-one-out strategy. For an user $u$, the interaction sequence
$S_{u}=[v_{1}^{u},v_{2}^{u},...,v_{n_{u}}^{u}]$, we use
$([v_{1}^{u},...,v_{n_{u}-3}^{u}],v_{n_{u}-2}^{u})$ for training,
$([v_{1}^{u},...,v_{n_{u}-2}^{u}],v_{n_{u}-1}^{u})$ for validation, and
$([v_{1}^{u},...,v_{n_{u}-1}^{u}],\\\ v_{n_{u}}^{u})$ for testing, where $n$
is the length of $S_{u}$ and $v_{t}^{u}$ is the item user interact with at the
$t$-th timestamp. We adopt Recall and NDCG metrics to evaluate the ranking
performance. We report the average results of three experiments.

##  4\. EXPERIMENTS RESULTS

In this section, we aim to answer the following research questions in terms of
lifelong sequential recommendation:

  * •

RQ1: How does longer sequence length contribute to the effectiveness of
sequence recommendation?

  * •

RQ2: How do different recommenders perform in modeling lifelong sequences?

  * •

RQ3: How is the efficiency of different recommenders?

###  4.1. Lengths Comparison (RQ1)

(a)  (b)

Figure 1. Performance of the user interests modeling about sequence length on
KuaiRand (a) and Tracks (b) datasets.

To demonstrate the performance of modeling different sequence lengths, we
conduct experiments to evaluate the performance of Rec-Mamaba on two real-
world datasets KuaiRand and LFM-1b. We report the main experimental results in
Figure 1.

Overall, with RecMamba, we observe that longer sequences consistently
outperform shorter sequences on both the KuaiRand and LFM-1b datasets,
indicating that introducing longer sequences benefits modeling user interest.
The performance improvement with longer sequences can be attributed to their
ability to capture more comprehensive and meaningful patterns, dependencies,
and user preferences, enabling the recommender systems to make more accurate
predictions and generate more relevant recommendations. In summary, the
experimental results provide strong evidence for the effectiveness of lifelong
sequences in improving recommendation performance. The findings emphasize the
importance of considering longer sequences in sequence recommendation models,
as they can capture richer interaction information and lead to more accurate
recommendations.

###  4.2. Overall Performance (RQ2)

Table 2. Overall performance comparison of different methods on KuaiRand and LFM-1b datasets. Boldface indicates the best result. Underscore indicates the suboptimal results. 2k and 5k denote the max sequence length. Datasets | Method | Recall@5 | NDCG@5 | Recall@10 | NDCG@10 | Recall@20 | NDCG@20
---|---|---|---|---|---|---|---
KuaiRand(2k) | GRU4Rec | 0.4062 | 0.3080 | 0.4439 | 0.3184 | 0.4617 | 0.3230
LinRec | 0.4984 | 0.3774 | 0.6167 | 0.4152 | 0.7242 | 0.4422
SASRec | 0.7143 | 0.5875 | 0.7857 | 0.6126 | 0.8361 | 0.6254
RecMamba | 0.6907 | 0.5584 | 0.7652 | 0.5828 | 0.8172 | 0.5960
LFM-1b(2k) | GRU4Rec | 0.3119 | 0.2300 | 0.3597 | 0.2401 | 0.3864 | 0.2469
LinRec | 0.6163 | 0.5052 | 0.6955 | 0.5327 | 0.7668 | 0.5501
SASRec | 0.8112 | 0.7448 | 0.8388 | 0.7537 | 0.8598 | 0.7591
RecMamba | 0.8019 | 0.7487 | 0.8319 | 0.7393 | 0.8570 | 0.7456
KuaiRand(5k) | GRU4Rec | 0.2593 | 0.2200 | 0.2957 | 0.3080 | 0.2318 | 0.2350
LinRec | 0.5163 | 0.3965 | 0.6278 | 0.4327 | 0.7287 | 0.4582
SASRec | 0.6422 | 0.5224 | 0.7370 | 0.5468 | 0.8042 | 0.5639
RecMamba | 0.7004 | 0.5713 | 0.7733 | 0.5951 | 0.8253 | 0.6082
LFM-1b(5k) | GRU4Rec | 0.3009 | 0.2113 | 0.3800 | 0.2366 | 0.4055 | 0.2432
LinRec | 0.6362 | 0.5296 | 0.7135 | 0.5543 | 0.7776 | 0.5717
SASRec | 0.8542 | 0.7820 | 0.8794 | 0.7905 | 0.8969 | 0.7950
RecMamba | 0.8485 | 0.7823 | 0.8727 | 0.7908 | 0.8904 | 0.7953

In this subsection, we conduct a comprehensive evaluation to verify the
sequence modeling performance of RecMamba. We compare it with different
representative recommendation models including the RNN-based model GRU4Rec,
attention-based model SASRec, and linear attention-based model LinRec. The
results are reported in Table 4.2.

We can see that RecMamba and SASRec significantly outperform both LinRec and
GRU4Rec with max sequence lengths of 2k and 5k on two datasets. The reason may
be that GRU4Rec has not fully addressed the limitations of the RNN-based
architecture, such as information forgetting and intrinsic vanishing gradients
issues. Besides, the LinRec modeling sequence using approximate softmax could
not fit the long-range dependency of item transition. This highlights the
superior ability of RecMamba and SASRec in the lifelong sequential
recommendation.

Compared with SASRec, RecMamba achieves suboptimal performance on sequences of
length 2k, whereas it outperforms SASRec on sequences of length 5k in most
cases. This indicates that RecMamba is capable of effectively modeling longer
user interest sequences, potentially due to its ability to select relevant
items for modeling user interests.

###  4.3. Efficiency Comparison (RQ3)

In this subsection, we conduct experiments to compare the efficiency between
RecMamba and other representative sequential recommenders on the lifelong
sequential recommendation. More specifically, we delve into crucial efficiency
metrics, encompassing GPU memory consumption, training duration, and inference
time. We used the batch size of 256 for sequence length of 2k for all models.
To investigate the model efficiency, we evaluate the computational cost,
including GPU memory consumption, training duration, and inference time as
shown in Table 3.

We can observe that RecMamba notably reduces GPU memory footprint and
significantly slashes both inference and training times. Compared with SASRec
on the LFM-1b(2k) dataset, RecMamba reduces about 73% training duration, 61%
inference time, and 80% memory costs. We can observe similar results on the
KuaiRand(2k) dataset. For the two datasets of the 5k version, SASRec has
encountered an out-of-memory (OOM) issue and RecMamba achieves better
efficiency compared with LinRec. These results demonstrate RecMamba’s prowess
in handling lifelong sequence recommendation tasks with remarkable efficiency.

Besides, we investigate the efficiency comparison for modeling different
lengths. Figure 2 shows the training time and inference time comparison
between RecMamba and SASRec on the LFM-1b dataset. Compared with SASRec,
RecMamba demonstrates a significant efficiency advantage in modeling sequences
of any length reported, including both training and inference time. This
advantage becomes more pronounced as the sequence length increases.

To conclude, the experimental findings provide compelling evidence of
RecMamba’s superior efficiency as a sequence recommendation framework. Its
ability to efficiently reduce GPU memory consumption and optimize both
training and inference times positions RecMamba as an exceedingly promising
solution for building efficient and scalable recommendation systems. This
superiority is evident not only in terms of performance but also in terms of
efficiency, including GPU memory consumption and inference time. This implies
that RecMamba achieves better results on lifelong sequences with fewer
computational resources, making it more efficient and cost-effective for
deployment in recommendation systems.

Table 3. Efficiency comparison. Boldface indicates the best result. 2k and 5k
denote the max sequence length. ✘ denotes the OOM issue.

Datasets | Model | GPU memory(GB) | Time cost(s/epoch)
---|---|---|---
|  |  | Training | Evaluation
| LinRec | 11.85G | 22.49s | 54.72s
KuaiRand(2k) | SASRec | 37.86G | 49.42s | 64.81s
| RecMamba | 8.36G | 18.21s | 25.39s
| LinRec | 20.02G | 39.54s | 61.4s
KuaiRand(5K) | SASRec | ✘ | ✘ | ✘
| RecMamba | 14.68G | 28.09s | 31.35s
| LinRec | 10.69G | 18.19s | 52.95s
LFM-1b(2k) | SASRec | 39.85G | 41.24s | 59.95s
| RecMamba | 7.60G | 11.75s | 23.12s
| LinRec | 19.83G | 32.76s | 56.65s
LFM-1b(5k) | SASRec | ✘ | ✘ | ✘
| RecMamba | 14.46G | 17.62s | 26.54s

(a)  (b)

Figure 2. Training time (a) and Inference time (b) comparision on LFM-1b
dataset.

##  5\. Conclusion and Future Work

In this paper, we have investigated how the selective state space model (i.e.,
Mamba) performs lifelong sequential recommendation. More specifically, we have
leveraged Mamba to adopt the sequential recommendation task. We have conducted
experiments to verify the performance and efficiency of representative
recommendation models for longer user sequences (i.e., length¿=2k) scenarios.
Extensive experiments and analysis on two real-world datasets have
demonstrated that Mamba achieves superior performance than representative
sequential models.

In future work, we plan to refine the Mamba to better perform the subfield of
recommendation. For instance, leveraging Mabma for multi-behavior
recommendations would be a potential research direction. Additionally, how to
effectively deal with longer side information (e.g., title and description of
items) would also be an interesting research direction. We hope the findings
in this work could facilitate future research on using Mamba for sequential
recommendations.

## References

  * (1)
  * Cho et al. (2014) Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014.  On the properties of neural machine translation: Encoder-decoder approaches.  _arXiv preprint arXiv:1409.1259_ (2014).
  * de Souza Pereira Moreira et al. (2021) Gabriel de Souza Pereira Moreira, Sara Rabhi, Jeong Min Lee, Ronay Ak, and Even Oldridge. 2021.  Transformers4rec: Bridging the gap between nlp and sequential/session-based recommendation. In _Proceedings of the 15th ACM conference on recommender systems_. 143–153.
  * Gao et al. (2022) Chongming Gao, Shijun Li, Yuan Zhang, Jiawei Chen, Biao Li, Wenqiang Lei, Peng Jiang, and Xiangnan He. 2022.  KuaiRand: An Unbiased Sequential Recommendation Dataset with Randomly Exposed Videos. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_ (Atlanta, GA, USA) _(CIKM ’22)_. Association for Computing Machinery, New York, NY, USA, 3953–3957.  https://doi.org/10.1145/3511808.3557624
  * Gu and Dao (2023) Albert Gu and Tri Dao. 2023.  Mamba: Linear-time sequence modeling with selective state spaces.  _arXiv preprint arXiv:2312.00752_ (2023).
  * Gu et al. (2021) Albert Gu, Karan Goel, and Christopher Ré. 2021.  Efficiently modeling long sequences with structured state spaces.  _arXiv preprint arXiv:2111.00396_ (2021).
  * He et al. (2016) Ruining He, Chen Fang, Zhaowen Wang, and Julian McAuley. 2016.  Vista: A visually, socially, and temporally-aware model for artistic recommendation. In _Proceedings of the 10th ACM conference on recommender systems_. 309–316.
  * Hidasi et al. (2015) Balázs Hidasi, Alexandros Karatzoglou, Linas Baltrunas, and Domonkos Tikk. 2015.  Session-based recommendations with recurrent neural networks.  _arXiv preprint arXiv:1511.06939_ (2015).
  * Hidasi et al. (2016a) Balázs Hidasi, Alexandros Karatzoglou, Linas Baltrunas, and Domonkos Tikk. 2016a.  Session-based Recommendations with Recurrent Neural Networks. In _ICLR (Poster)_.
  * Hidasi et al. (2016b) Balázs Hidasi, Massimo Quadrana, Alexandros Karatzoglou, and Domonkos Tikk. 2016b.  Parallel recurrent neural network architectures for feature-rich session-based recommendations. In _Proceedings of the 10th ACM conference on recommender systems_. 241–248.
  * Hu et al. (2018) Yujing Hu, Qing Da, Anxiang Zeng, Yang Yu, and Yinghui Xu. 2018.  Reinforcement learning to rank in e-commerce search engine: Formalization, analysis, and application. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. ACM, 368–377.
  * Huang et al. (2018) Jin Huang, Wayne Xin Zhao, Hongjian Dou, Ji-Rong Wen, and Edward Y Chang. 2018.  Improving sequential recommendation with knowledge-enhanced memory networks. In _The 41st international ACM SIGIR conference on research & development in information retrieval_. 505–514.
  * Kang and McAuley (2018) Wang-Cheng Kang and Julian McAuley. 2018.  Self-attentive sequential recommendation. In _2018 IEEE International Conference on Data Mining (ICDM)_. IEEE, 197–206.
  * Li et al. (2017) Jing Li, Pengjie Ren, Zhumin Chen, Zhaochun Ren, Tao Lian, and Jun Ma. 2017.  Neural attentive session-based recommendation. In _CIKM_. 1419–1428.
  * Lin et al. (2023) Jianghao Lin, Rong Shan, Chenxu Zhu, Kounianhua Du, Bo Chen, Shigang Quan, Ruiming Tang, Yong Yu, and Weinan Zhang. 2023.  Rella: Retrieval-enhanced large language models for lifelong sequential behavior comprehension in recommendation.  _arXiv preprint arXiv:2308.11131_ (2023).
  * Liu et al. (2024a) Chengkai Liu, Jianghao Lin, Jianling Wang, Hanzhou Liu, and James Caverlee. 2024a.  Mamba4Rec: Towards Efficient Sequential Recommendation with Selective State Space Models.  _arXiv preprint arXiv:2403.03900_ (2024).
  * Liu et al. (2023) Langming Liu, Liu Cai, Chi Zhang, Xiangyu Zhao, Jingtong Gao, Wanyu Wang, Yifu Lv, Wenqi Fan, Yiqi Wang, Ming He, Zitao Liu, and Qing Li. 2023.  LinRec: Linear Attention Mechanism for Long-term Sequential Recommender Systems. In _Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval_ (¡conf-loc¿, ¡city¿Taipei¡/city¿, ¡country¿Taiwan¡/country¿, ¡/conf-loc¿) _(SIGIR ’23)_. Association for Computing Machinery, New York, NY, USA, 289–299.  https://doi.org/10.1145/3539618.3591717
  * Liu et al. (2024b) Yue Liu, Yunjie Tian, Yuzhong Zhao, Hongtian Yu, Lingxi Xie, Yaowei Wang, Qixiang Ye, and Yunfan Liu. 2024b.  Vmamba: Visual state space model.  _arXiv preprint arXiv:2401.10166_ (2024).
  * Ma et al. (2024) Jun Ma, Feifei Li, and Bo Wang. 2024.  U-mamba: Enhancing long-range dependency for biomedical image segmentation.  _arXiv preprint arXiv:2401.04722_ (2024).
  * Pi et al. (2019) Qi Pi, Weijie Bian, Guorui Zhou, Xiaoqiang Zhu, and Kun Gai. 2019.  Practice on Long Sequential User Behavior Modeling for Click-Through Rate Prediction. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ (Anchorage, AK, USA) _(KDD ’19)_. Association for Computing Machinery, New York, NY, USA, 2671–2679.  https://doi.org/10.1145/3292500.3330666
  * Qi et al. (2020) Tao Qi, Fangzhao Wu, Chuhan Wu, Yongfeng Huang, and Xing Xie. 2020.  Privacy-Preserving News Recommendation Model Learning. In _EMNLP (Findings)_ _(Findings of ACL, Vol. EMNLP 2020)_. Association for Computational Linguistics, 1423–1432.
  * Rendle et al. (2010) Steffen Rendle, Christoph Freudenthaler, and Lars Schmidt-Thieme. 2010.  Factorizing personalized Markov chains for next-basket recommendation. In _WWW_. ACM, 811–820.
  * Schedl (2016) Markus Schedl. 2016.  The lfm-1b dataset for music retrieval and recommendation. In _Proceedings of the 2016 ACM on international conference on multimedia retrieval_. 103–110.
  * Smith et al. (2022) Jimmy TH Smith, Andrew Warrington, and Scott W Linderman. 2022.  Simplified state space layers for sequence modeling.  _arXiv preprint arXiv:2208.04933_ (2022).
  * Sun et al. (2019) Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. 2019.  BERT4Rec: Sequential recommendation with bidirectional encoder representations from transformer. In _CIKM_. 1441–1450.
  * Tang and Wang (2018) Jiaxi Tang and Ke Wang. 2018.  Personalized top-n sequential recommendation via convolutional sequence embedding. In _WSDM_. ACM, 565–573.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is All you Need. In _NIPS_. 5998–6008.
  * Wang et al. (2024) Hanbing Wang, Xiaorui Liu, Wenqi Fan, Xiangyu Zhao, Venkataramana Kini, Devendra Yadav, Fei Wang, Zhen Wen, Jiliang Tang, and Hui Liu. 2024.  Rethinking Large Language Model Architectures for Sequential Recommendations.  _arXiv preprint arXiv:2402.09543_ (2024).
  * Wu et al. (2019) Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. 2019.  Session-based recommendation with graph neural networks. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 33. 346–353.
  * Yuan et al. (2019) Fajie Yuan, Alexandros Karatzoglou, Ioannis Arapakis, Joemon M Jose, and Xiangnan He. 2019.  A Simple Convolutional Generative Network for Next Item Recommendation. In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_. ACM, 582–590.
  * Zhang et al. (2022) Mengqi Zhang, Shu Wu, Xueli Yu, Qiang Liu, and Liang Wang. 2022.  Dynamic graph neural networks for sequential recommendation.  _IEEE Transactions on Knowledge and Data Engineering_ 35, 5 (2022), 4741–4753.
  * Zhou et al. (2020) Kun Zhou, Hui Wang, Wayne Xin Zhao, Yutao Zhu, Sirui Wang, Fuzheng Zhang, Zhongyuan Wang, and Ji-Rong Wen. 2020.  S3-Rec: Self-Supervised Learning for Sequential Recommendation with Mutual Information Maximization. In _CIKM_. ACM, 1893–1902.
  * Zhu et al. (2024) Lianghui Zhu, Bencheng Liao, Qian Zhang, Xinlong Wang, Wenyu Liu, and Xinggang Wang. 2024.  Vision mamba: Efficient visual representation learning with bidirectional state space model.  _arXiv preprint arXiv:2401.09417_ (2024).