Approximate Message Passing for Multi-Preamble Detection in OTFS Random Access The University of Bologna team is supported by the European Union – Next Generation EU under the Italian National Recovery and Resilience Plan (NRRP), partnership on “Telecommunications of the Future” (PE00000001 – progra

Alessandro Mirri 1 , Vishnu Teja Kunde 2 , Enrico Paolini 1 , Jean-Francois Chamberland 2 · 2025

Read Approximate Message Passing for Multi-Preamble Detection in OTFS Random Access The University of Bologna team is supported by the European Union – Next Generation EU under the Italian National Recovery and Resilience Plan (NRRP), partnership on “Telecommunications of the Future” (PE00000001 – progra by Alessandro Mirri 1 , Vishnu Teja Kunde 2 , Enrico Paolini 1 , Jean-Francois Chamberland 2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-03980.txt.

Introduction

Alessandro Mirri and three co-authors work on detecting multiple preambles in random access systems using OTFS signalling in a 2025 research paper. In random access, many devices announce themselves with short preamble signals, and the receiver must spot which preambles arrived. OTFS, orthogonal time frequency space modulation, suits fast-moving channels by working in the delay-Doppler domain.

The detection problem is cast as structured sparse recovery in the complex domain: few preambles are active, and OTFS signals are themselves sparse in delay-Doppler coordinates. Their approximate message passing algorithm enforces that double sparsity at once. Because the complex sparsity constraint does not separate, deriving it takes care, and the result is a novel denoiser inside the message passing loop. Simulations show robust detection with significant gains over leading existing techniques. The work targets future wireless systems where many devices contend for access over difficult, high-mobility channels.

Catalog record

CREATORAlessandro Mirri 1 , Vishnu Teja Kunde 2 , Enrico Paolini 1 , Jean-Francois Chamberland 2
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-03980

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximate Message Passing for Multi-Preamble Detection in OTFS Random Access The University of Bologna team is supported by the European Union – Next Generation EU under the Italian National Recovery and Resilience Plan (NRRP), partnership on “Telecommunications of the Future” (PE00000001 – program “RESTART”). This material is based, in part, upon work conducted at Texas A&M University and supported by the National Science Foundation (NSF) under Grant CNS-2148354. This is the author’s preprint version of a work submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible on arXiv. Alessandro Mirri 1 , Vishnu Teja Kunde 2 , Enrico Paolini 1 , Jean-Francois Chamberland 2 Abstract This article addresses the problem of multiple preamble detection in random access systems based on orthogonal time frequency space (OTFS) signaling. This challenge is formulated as a structured sparse recovery problem in the complex domain. To tackle it, the authors propose a new approximate message passing (AMP) algorithm that enforces double sparsity: the sparse selection of preambles and the inherent sparsity of OTFS signals in the delay–Doppler domain. From an algorithmic standpoint, the non-separable complex sparsity constraint necessitates a careful derivation and leads to the design of a novel AMP denoiser. Simulation results demonstrate that the proposed method achieves robust detection performance and delivers significant gains over state-of-the-art techniques. AMP approximate message passing AWGN additive white Gaussian noise BS base station CAMP complex AMP DD delay-Doppler GL group LASSO SG sparse Group SGL sparse group LASSO CSG complex sparse group CSGL complex sparse group LASSO CGL complex group LASSO CL complex LASSO i.i.d. independent and identically distributed ISTA iterative soft-thresholding LASSO least absolute shrinkage and selection operator OFDM orthogonal frequency-division multiplexing OMP orthogonal matching pursuit OST one step thresholding OTFS orthogonal time frequency space PHY physical SNR signal-to-noise ratio Veh-A Vehicular A ZC Zadoff-Chu I Introduction Many high-dimensional communication problems exhibit sparsity, either due to the physical characteristics of wireless channels or as a result of coding schemes [ 1 , 2 , 3 ] . For example, sparse regression coding achieves optimal asymptotic performance [ 4 , 5 ] , while coded compressed sensing formulates unsourced random access as a sequence of sparse recovery tasks [ 6 ] . Multipath fading also induces sparsity, motivating the use of OFDM ( OFDM ) and, more recently, OTFS ( OTFS ) signaling [ 7 ] , which exploits sparsity in the DD ( DD ) domain. Sparsity-inducing methods such as the LASSO ( LASSO ) [ 8 ] and its algorithmic variants [ 9 , 10 ] , promote element-wise sparsity but do not account for hierarchical structures. To address this limitation, structured approaches like GL ( GL ) [ 11 ] and SGL ( SGL ) [ 12 ] enforce both group and intra-group sparsity, providing a better fit for problems with double sparsity, such as multiple preamble detection in OTFS -based random access [ 13 ] . In this setting, only a few preambles are active, and each active signal propagates through a sparse multipath channel. In parallel, AMP ( AMP ) algorithms [ 14 ] have emerged as efficient, theoretically grounded solutions for large-scale sparse recovery. Extensions to the complex domain, such as CAMP ( CAMP ) [ 15 ] , are particularly relevant in wireless applications. Recently, AMP has been extended to incorporate structured sparsity, paving the way for powerful new frameworks. The main contributions of our article are: ( i ) an AMP algorithm tailored to complex-valued SGL , specifically designed for multiple preamble detection in OTFS -based random access; ( ii ) a structured denoiser that jointly exploits group and intra-group sparsity, with a rigorously derived Onsager correction term to enhance convergence; and ( iii ) extensive simulations demonstrating significant performance gains over state-of-the-art methods. II Background and Problem Formulation This section offers an overview of sparse regression, focusing on structured sparsity in complex-valued settings. We start with the canonical linear inverse problem \displaystyle\mathbf{y}=\mathbf{X}\boldsymbol{\beta}+\mathbf{w}, (1) where \mathbf{y}\in\mathbb{C}^{n} is the received vector, \mathbf{X}\in\mathbb{C}^{n\times N} represents the sensing matrix, and \boldsymbol{\beta}\in\mathbb{C}^{N} is the unknown sparse vector. Additive noise vector \mathbf{w}\in\mathbb{C}^{n} has i.i.d. ( i.i.d. ) entries, each with complex Gaussian distribution w_{i}\sim\mathcal{CN}(0,\sigma_{\mathrm{n}}^{2}) , where \sigma_{\mathrm{n}}^{2} denotes the noise variance. For the problem we wish to study, ( 1 ) arises from an OTFS -based random access scenario. We analyze this setting in detail, as it shapes both the sensing matrix and the sparsity exploited in recovery. II-A OTFS-Based Random Access Model OTFS is a two-dimensional modulation scheme designed for robust transmission over high-mobility, doubly-dispersive channels, mapping signals onto a DD grid to exploit channel sparsity [ 16 ] . We consider an uplink random access scenario with K active users, each selecting a preamble \mathbf{s}\in\mathbb{C}^{M_{\mathrm{dd}}N_{\mathrm{dd}}} from a common pool of G sequences, where M_{\mathrm{dd}} and N_{\mathrm{dd}} denote the number of delay and Doppler bins, respectively. Every active user k\in\{1,\dots,K\} randomly selects an index i_{k}\in\{1,\dots,G\} and transmits the corresponding OTFS -modulated preamble \mathbf{s}_{i_{k}} . As is typical in random access, only a small fraction of preambles are active at any given time, with K\ll G . The wireless channel between each user and the receiver is modeled as a sparse multipath channel with L dominant DD components. Each multipath component is described by its delay \tau_{k,l} , Doppler shift \nu_{k,l} , and complex gain h_{k,l} , for l=1,\dots,L . The received OTFS signal at the access point is \textstyle\mathbf{y}=\sum_{k=1}^{K}\sum_{l=1}^{L}h_{k,l}\,\mathbf{s}_{i_{k}}^{(\tau_{k,l},\nu_{k,l})}+\mathbf{w}, (2) where \mathbf{s}_{i_{k}}^{(\tau_{k,l},\nu_{k,l})} denotes the preamble \mathbf{s}_{i_{k}} shifted in the DD domain by (\tau_{k,l},\nu_{k,l}) , and \mathbf{w} denotes additive complex Gaussian noise. This gives rise to a structured sparse recovery problem: a small number of active preambles, each experiencing sparse multipath propagation. Interpreting ( 1 ) in this context, we see that \mathbf{X} is a structured sensing matrix whose columns correspond to OTFS -modulated preambles shifted over discrete sets of delays \mathcal{T} and Dopplers \mathcal{D} , defined as \displaystyle\mathcal{T} \displaystyle=\left\{0,\frac{\tau_{p}}{M_{\mathrm{dd}}},\dots,\left\lfloor\frac{\tau_{\max}M_{\mathrm{dd}}}{\tau_{p}}\right\rfloor\frac{\tau_{p}}{M_{\mathrm{dd}}}\right\}, (3) \displaystyle\mathcal{D} \displaystyle=\left\{\!-\!\left\lfloor\frac{\nu_{\max}N_{\mathrm{dd}}}{\nu_{p}}\right\rfloor\frac{\nu_{p}}{N_{\mathrm{dd}}},\dots,0,\dots,\left\lfloor\frac{\nu_{\max}N_{\mathrm{dd}}}{\nu_{p}}\right\rfloor\frac{\nu_{p}}{N_{\mathrm{dd}}}\right\}. (4) Above, \tau_{p} is the delay period, \nu_{p}=1/\tau_{p} is the Doppler period, and (\tau_{\max},\nu_{\max}) denote the maximum delay and Doppler supported by the system. The Cartesian product \mathcal{S}=\mathcal{T}\times\mathcal{D} defines the full grid of DD shifts used to construct the columns of \mathbf{X} . For each preamble \mathbf{s}_{j} , and for each DD shift (\tau_{i},\nu_{i})\in\mathcal{S} , the corresponding column of \mathbf{X} is given by \displaystyle\mathbf{X}_{j|\mathcal{S}|+i}=h_{\text{eff},i}\ast_{\sigma}\mathbf{s}_{j}, (5) where h_{\text{eff},i} denotes the effective channel impulse response associated with the DD shift (\tau_{i},\nu_{i}) , as defined in [ 17 , Eq. (13)] , and \ast_{\sigma} represents the twisted convolution operator. The unknown vector \boldsymbol{\beta}\in\mathbb{C}^{G|\mathcal{S}|} captures both user activity and channel properties, with two levels of sparsity: group sparsity across preambles and within-group sparsity across DD components. II-B Sparse Regression and Proximal Methods Sparse regression aims to recover \boldsymbol{\beta} under sparsity constraints. The original problem \displaystyle\operatorname{min}_{\boldsymbol{\beta}}\|\mathbf{y}-\mathbf{X}\boldsymbol{\beta}\|_{2}^{2}\quad\text{s.t.}\quad\|\boldsymbol{\beta}\|_{0}\leq K, (6) is combinatorial and NP-hard. A common relaxation replaces \ell_{0} with the convex \ell_{1} norm, yielding the LASSO formulation \operatorname{min}_{\boldsymbol{\beta}}\|\mathbf{y}-\mathbf{X}\boldsymbol{\beta}\|_{2}^{2}+\lambda\|\boldsymbol{\beta}\|_{1}. (7) This multi-objective optimization balances fidelity and sparsity while remaining amenable to proximal methods. The proximal operator of the \ell_{1} norm is \prox_{\lambda\|\cdot\|_{1}}(\boldsymbol{\beta})=\argmin_{\mathbf{v}}\frac{1}{2}\|\mathbf{v}-\boldsymbol{\beta}\|_{2}^{2}+\lambda\|\mathbf{v}\|_{1}, (8) which reduces to elementwise soft-thresholding for real entries \operatorname{prox}_{\lambda|\cdot|}(\beta)=\begin{cases}\beta-\lambda&\beta>\lambda\\ 0&|\beta|\leq\lambda\\ \beta+\lambda&\beta<-\lambda.\end{cases} (9) For complex vectors, the \ell_{1} norm becomes \textstyle\|\mathbf{v}\|_{1}=\sum_{i}|v_{i}|=\sum_{i}\sqrt{\Re(v_{i})^{2}+\Im(v_{i})^{2}}, (10) which

Read the complete text