Blind Demixing and Deconvolution at Near-Optimal Rate

Peter Jung, Felix Krahmer, Dominik Stöger

Abstract

We consider simultaneous blind deconvolution of $r$ source signals from their noisy superposition, a problem also referred to as blind demixing and deconvolution. This signal processing problem occurs in the context of the Internet of Things where a massive number of sensors sporadically communicate only short messages over unknown channels. We show that robust recovery of message and channel vectors can be achieved via convex optimization when random linear encoding using i.i.d. complex Gaussian matrices is used at the devices and the number of required measurements at the receiver scales with the degrees of freedom of the overall estimation problem. Since the scaling is linear in $r$, our result significantly improves over recent works.

Introduction

In the burgeoning landscape of the Internet of Things (IoT), massive networks of sensors sporadically transmit short bursts of data to central base stations. This creates a dual challenge for signal processing: blind deconvolution and demixing. Because the environment between a sensor and the receiver is often unknown and changing, the receiver must simultaneously estimate the signal and the channel distortion (blind deconvolution). Furthermore, because many sensors transmit simultaneously, the receiver must untangle a "noisy soup" of overlapping signals (demixing).

Mathematically, this is framed as a bilinear inverse problem. Until recently, theoretical guarantees for solving this via convex optimization suggested that the number of required measurements ($L$) had to scale quadratically with the number of active users ($r^2$). This "quadratic bottleneck" suggested a significant gap between theoretical requirements and practical feasibility. This paper provides a mathematical breakthrough, proving that linear scaling ($L \propto r$) is sufficient for robust recovery, reaching a near-optimal rate.

Methodology: The Lifting Approach

To address the bilinear nature of the problem—where unknown message vectors are multiplied by unknown channel vectors—the authors employ a technique known as Lifting. By representing the interaction of these vectors as an outer product, the bilinear task is transformed into a linear problem in a higher-dimensional space. This allows the researchers to treat the recovery as a Low-Rank Matrix Recovery problem.

The primary tool for solving this lifted problem is Nuclear Norm Minimization. This convex optimization strategy serves as a computationally tractable proxy for finding the lowest-rank solution, effectively identifying the simplest signal structure that fits the observed data.

Theoretical Innovations

The core of the paper’s contribution lies in overcoming the previous $r^2$ scaling limitation. The authors achieve this through three key mathematical strategies:

  1. Global Viewpoint: Rather than analyzing the incoherence of each signal individually (which introduces the $r^2$ factor), the authors analyze the measurement operator's effect on the entire subspace of signals simultaneously.
  2. Local Isometry Property: They demonstrate that the measurement operator preserves the essential structure of the signals across the subspace.
  3. The Golfing Scheme: This iterative construction is used to prove the existence of a "dual certificate," providing a rigorous mathematical guarantee that the optimization will converge on the correct solution.

Experimental Validation

While the paper is primarily theoretical, the authors validate their proofs using synthetic benchmarks designed to simulate wireless communication environments.

  • Encoding and Subspaces: Messages are encoded using i.i.d. complex Gaussian matrices, while channel vectors are modeled using partial Discrete Fourier Transform (DFT) matrices to represent typical low-frequency wireless channels.
  • Phase Transitions: The researchers tested the "Phase Transition" points—the threshold where the algorithm moves from failure to consistent success. These simulations confirmed that the success rate depends linearly on the number of active devices ($r$).
  • Algorithm Comparison: The study also compared the convex approach to Wirtinger Flow, a faster non-convex algorithm. Interestingly, while the proof focuses on convex optimization, the non-convex Wirtinger Flow showed even better empirical performance, suggesting that the linear scaling principle is a robust feature of the underlying problem structure.

Key Insights and Results

The primary result (Theorem 2.5) establishes that signals can be recovered with high probability as long as the measurement length $L$ scales linearly with the number of sources $r$. Specifically, the required measurements scale as $L \gtrsim r(K+N)$, where $K$ and $N$ represent the dimensions of the channel and signal subspaces. This is considered near-optimal because $r(K+N)$ represents the total degrees of freedom in the system.

Furthermore, the authors demonstrate robustness to noise. The recovery is stable; if the input is corrupted by a small amount of noise, the resulting recovery error remains proportionally small, making the approach viable for real-world sensor environments.

Limitations and Future Directions

Despite the theoretical success, practical implementation faces hurdles. The "lifting" technique, while mathematically elegant, significantly increases computational complexity and memory requirements due to the creation of massive matrices. This makes Nuclear Norm Minimization difficult to scale for very long messages or extremely high user counts.

Additionally, the current model assumes signals lie in known low-dimensional subspaces. Future work is needed to integrate explicit sparsity constraints (where signals are mostly zeros), which would more accurately reflect certain IoT data patterns. Finally, while this paper proves linear scaling for convex methods, developing a similarly rigorous proof for the faster non-convex algorithms remains an open area of research.

Summary updated

Abstract

We consider simultaneous blind deconvolution of r source signals from their noisy superposition, a problem also referred to blind demixing and deconvolution. This signal processing problem occurs in the context of the Internet of Things where a massive number of sensors sporadically communicate only short messages over unknown channels. We show that robust recovery of message and channel vectors can be achieved via convex optimization when random linear encoding using i.i.d. complex Gaussian matrices is used at the devices and the number of required measurements at the receiver scales with the degrees of freedom of the overall estimation problem. Since the scaling is linear in r our result significantly improves over recent works.
BibTeX
@article{jung2018blind,
  author = {Peter Jung and Felix Krahmer and Dominik Stöger},
  title = {{Blind Demixing and Deconvolution at Near-Optimal Rate}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  url = {https://openreview.net/forum?id=mdh9neqHcBD},
}
Figure