Timely and Painless Breakups: Off-the-grid Blind Message Recovery and Users' Demixing

Abstract

In the near future, the Internet of Things will interconnect billions of devices, forming a vast network where users sporadically transmit short messages through multi-path wireless channels. These channels are characterized by the superposition of a small number of scaled and delayed copies of Dirac spikes. At the receiver, the observed signal is a sum of these convolved signals, and the task is to find the amplitudes, continuous-indexed delays, and transmitted messages from a single signal. This task is inherently ill-posed without additional assumptions on the channel or messages. In this work, we assume the channel exhibits sparsity in the delay domain and that i.i.d. random linear encoding is applied to the messages at the devices. Leveraging these assumptions, we propose a semidefinite programming optimization capable of simultaneously recovering both messages and the delay parameters of the channels from only a single received signal. Our theoretical analysis establishes that the required number of samples at the receiver scales proportionally to the sum-product of sparsity and message length of all users, aligning with the degrees of freedom in the proposed convex optimization framework. Numerical experiments confirm the efficacy of the proposed method in accurately estimating closely-spaced delay parameters and recovering messages.

References in corpus (18)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• The Convex Geometry of Linear Inverse Problems
• Self-Calibration and Biconvex Compressive Sensing
• Harnessing Sparsity over the Continuum: Atomic Norm Minimization for Super Resolution
• Sparse Signal Processing Concepts for Efficient 5G System Design
• Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization
• Nomographic Functions: Efficient Computation in Clustered Gaussian Sensor Networks
• Two-Dimensional Super-Resolution via Convex Relaxation
• Exploiting Prior Information in Block Sparse Signals
• Sparse Blind Deconvolution and Demixing Through ${\ell }_{1,2}$-Minimization
• Living near the edge: A lower-bound on the phase transition of total variation minimization
• Sample Complexity of Total Variation Minimization
• On the Error in Phase Transition Computations for Compressed Sensing
• Multi-weight Nuclear Norm Minimization for Low-rank Matrix Recovery in Presence of Subspace Prior Information
• Blind Two-Dimensional Super Resolution in Multiple Input Single Output Linear Systems
• Distribution-aware Block-sparse Recovery via Convex Optimization
• Demixing Sines and Spikes Using Multiple Measurement Vectors
• Off-the-grid Recovery of Time and Frequency Shifts with Multiple Measurement Vectors