⚡ electrical engineering

Complex Approximate Message Passing with Non-separable Denoising

This paper establishes a unified state evolution theory for complex Approximate Message Passing (AMP) with non-separable denoisers by constructing an augmented real-valued system that enables accurate performance prediction and significant gains in high-dimensional inference problems, such as complex sparse group LASSO for OTFS-based unsourced random access.

Original authors: Vishnu Teja Kunde, Alessandro Mirri, Jean-Francois Chamberland, Enrico Paolini

Published 2026-04-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vishnu Teja Kunde, Alessandro Mirri, Jean-Francois Chamberland, Enrico Paolini

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Solving a Puzzle with a Twist

Imagine you are trying to solve a massive jigsaw puzzle, but someone has taken a photo of the finished picture, scrambled it, added some static noise, and then handed you the blurry, distorted photo. Your job is to figure out what the original picture looked like.

In the world of engineering and data science, this is called compressed sensing or signal recovery. You have a lot of data (the puzzle pieces), but you only have a few measurements (the blurry photo). To solve it, you need to guess the missing pieces based on patterns you know exist (like "sky is usually blue" or "trees are usually green").

This paper introduces a new, super-smart way to solve these puzzles when the data is complex (involving both magnitude and phase, like radio waves) and when the patterns are grouped (like a whole family of puzzle pieces that must be either all present or all missing).

The Problem: The "Complex" and "Grouped" Challenge

Most old methods for solving these puzzles worked well for simple, real-world numbers (like counting apples). But in modern wireless communication (like 5G or OTFS), data is complex. Think of complex numbers not just as "numbers," but as arrows on a map. They have a length (how strong the signal is) and a direction (the phase).

Furthermore, the signals often come in groups. Imagine a choir. You don't just have random singers; you have sections (Sopranos, Tenors, etc.). If the Sopranos are singing, they usually all sing together. If they are silent, they are all silent. This is called Sparse Group Sparsity.

The Old Problem:
Previous algorithms tried to solve these complex, grouped puzzles by breaking them apart. They treated the "length" of the arrow and the "direction" as two separate, unrelated problems. It's like trying to fix a car engine by looking at the wheels and the steering wheel separately, ignoring how they work together. This led to inefficient and inaccurate results.

The Solution: The "Augmented Reality" Trick

The authors of this paper came up with a clever trick. Instead of trying to solve the complex puzzle directly (which is mathematically messy), they built a bigger, simpler version of the puzzle first.

The Analogy: The Shadow Puppet Show

Imagine you want to understand a complex 3D shadow puppet show (the complex signal).

The Old Way: Try to analyze the shadow directly. It's confusing because the light bends and twists.
The New Way (This Paper):
- Step 1 (Lifting): Imagine you take the puppet and build a giant, 3D model of it in a bright, well-lit room (the Augmented Real System). This model is huge and has twice as many parts as the shadow, but it's made of simple, straight lines (Real numbers).
- Step 2 (Solving): You solve the puzzle using this giant 3D model. Because it's made of simple parts, standard math tools work perfectly.
- Step 3 (Collapsing): Once you understand the 3D model, you shine a light on it again to cast the shadow. You use a special "lens" (a Canonical Transformation) to map the giant 3D solution back down to the 2D shadow.

Why this works: The "lens" is designed so that when you collapse the big 3D model back down, the complex relationships (the twisting arrows) are perfectly preserved. You get the answer to the complex problem without ever having to do the hard math on the complex numbers directly.

The Secret Sauce: The "Onsager Correction"

In these iterative guessing games, the algorithm makes a guess, checks the error, and tries again. But there's a catch: the algorithm tends to get "confused" by its own previous guesses, thinking they are new information. This is like trying to walk in a straight line while constantly looking at your own footprints and getting dizzy.

To fix this, the algorithm uses an Onsager Correction. Think of this as a gyroscope or a balance beam. It tells the algorithm, "Hey, you already used that information; don't count it again."

The paper's breakthrough is showing that when you use their "Shadow Puppet" trick, this gyroscope automatically adjusts itself to handle the complex, grouped nature of the data. It naturally uses a special type of math derivative (called Wirtinger derivatives) that understands how complex arrows rotate and stretch, ensuring the algorithm stays balanced and doesn't get dizzy.

The Real-World Application: Finding a Needle in a Haystack (OTFS)

The authors tested this on a specific problem: Preamble Detection in OTFS (Orthogonal Time-Frequency Space).

The Scenario: Imagine a massive stadium where thousands of people (devices) are trying to send a text message to a central tower.
The Problem: Only a few people are actually talking at any given moment (Sparse). Furthermore, they talk in bursts (Groups). The tower receives a jumbled mess of signals.
The Result: Using their new method, the tower can figure out exactly who is talking and what they are saying much faster and more accurately than before.

The Takeaway

Don't fight the complexity: Instead of trying to force complex, grouped data into simple, separate boxes, build a bigger, simpler model that naturally contains all the complexity.
The Magic Lens: Use a mathematical transformation to solve the big model and then collapse it back down. The math works out so that the complex relationships are preserved automatically.
Better Performance: This method allows wireless systems to recover signals faster and with less error, especially when signals come in groups and have complex phases.

In short, the authors found a way to turn a difficult, twisting, complex puzzle into a straightforward, blocky one, solved it, and then turned the solution back into the complex answer we needed—all while keeping the algorithm from getting confused along the way.

1. Problem Statement

The paper addresses a critical gap in the theory of Approximate Message Passing (AMP), a powerful iterative framework for high-dimensional inference. While AMP has been successfully extended to complex-valued signals and non-separable denoising functions independently, a unified State Evolution (SE) theory for complex AMP with non-separable denoisers was missing.

The Challenge: Many practical problems in communications (e.g., OTFS preamble detection, OFDM channel estimation) involve complex-valued signals with structured sparsity (e.g., group sparsity combined with element sparsity).
The Limitation of Naive Approaches: Simply mapping complex variables to real vectors (e.g., $x \in \mathbb{C}^N \to [\Re(x); \Im(x)] \in \mathbb{R}^{2N}$ $x \in C^{N} \to [ℜ (x); ℑ (x)] \in R^{2 N}$ ) fails because:
1. It destroys the independent and identically distributed (i.i.d.) structure of the sensing matrix required for standard AMP analysis.
2. It decouples the real and imaginary components, preventing the algorithm from exploiting the rotational invariance and phase relationships inherent in complex data.
Specific Application: The paper focuses on the Complex Sparse Group LASSO (SGL) problem, where the proximal operator is non-separable because group-level thresholding depends on the joint norm of elements within a group.

2. Methodology

The authors propose a novel framework that bridges the gap between real-valued matrix AMP theory and complex non-separable denoising through a three-step strategy:

A. Augmented Real-Valued System Construction

Instead of directly analyzing the complex system, the authors construct an augmented real-valued system that lifts the problem to a higher-dimensional space ( $4n$ real dimensions instead of $2n$ ).

Mapping: They define a real sensing matrix $W \in \mathbb{R}^{2n \times N}$ and a state matrix $S_0 \in \mathbb{R}^{N \times 2}$ such that the complex observation $y = Ax_0 + w$ is recovered via a linear transformation of the real augmented system $O = WS_0 + N$ .
Information Richness: This augmented system contains more information than the original complex system, allowing existing real-valued AMP theorems (specifically those for matrix-valued variables) to be applied directly.

B. Canonical Transformation (State Collapse)

To recover the complex dynamics from the augmented real system, the authors introduce a many-to-one canonical transformation using the vector $\rho = [1, i]^T$ .

Transformation: Complex iterates are recovered by collapsing real matrix blocks (e.g., $2 \times 2$ blocks) using $\rho$ .
Admissible Functions: The framework restricts the class of real-valued denoising functions to those that respect the complex structure (specifically, functions whose real matrix representation has a specific $2 \times 2$ block form $\begin{bmatrix} a & b \\ b & -a \end{bmatrix}$ ). This ensures the dynamics remain consistent with complex multiplication.

C. Derivation of State Evolution

By applying the canonical transformation to the established state evolution of the real matrix AMP, the authors derive the state evolution for the complex system.

Wirtinger Derivatives: A key insight is that the Onsager correction term naturally involves Wirtinger derivatives ( $\frac{\partial}{\partial z}$ ) as a byproduct of the transformation, rather than requiring them to be imposed ad hoc.
Scalar Recursion: Despite the non-separable nature of the denoisers and the matrix-valued nature of the augmented system, the resulting state evolution reduces to scalar complex recursions due to the rotational symmetry of the complex Gaussian distribution.

3. Key Contributions

Unified State Evolution Theory: The paper establishes the first rigorous state evolution theory for complex AMP with fully non-separable denoisers.
Augmented System Framework: It introduces a method to lift complex problems to augmented real systems, leveraging existing real-valued AMP results to prove convergence and performance metrics for complex non-separable problems.
Complex Sparse Group LASSO (SGL): The framework is instantiated for the Complex SGL problem, providing a closed-form proximal operator and its Wirtinger derivative. This is crucial for applications like OTFS preamble detection where users form sparse groups with sparse channel taps.
Matrix Extension: The theory is generalized to the matrix-valued setting, allowing for the simultaneous estimation of multiple feature vectors (e.g., $p$ vectors) with Onsager corrections generalized to $p \times p$ Jacobian matrices.

4. Results

The authors validate their theoretical findings through numerical experiments:

State Evolution Accuracy: The predicted State Evolution (SE) curves closely match the empirical Normalized Mean Squared Error (NMSE) of the algorithm, confirming the theoretical accuracy of the derived recursions.
Convergence Speed: Complex AMP converges significantly faster (within ~15 iterations) compared to Complex ISTA (Iterative Soft Thresholding Algorithm), which lacks the Onsager correction.
Performance Gains: The proposed Complex SGL denoiser outperforms all baselines:
- Complex LASSO: Ignores group structure.
- Complex Group LASSO (GL): Ignores element-wise sparsity.
- Real SGL: Treats real and imaginary parts independently, failing to capture complex coupling.
- Complex SGL: Jointly exploits group sparsity, element sparsity, and complex phase coherence, achieving the lowest NMSE across all Signal-to-Noise Ratio (SNR) levels.

5. Significance

This work is significant for several reasons:

Theoretical Unification: It resolves a long-standing theoretical gap, enabling the rigorous analysis of complex AMP algorithms with complex, non-separable priors.
Practical Impact: It provides a robust tool for modern communication systems (like 5G/6G OTFS and unsourced random access) where signals are inherently complex and exhibit multi-level sparsity.
Design Automation: The derived State Evolution serves as an "oracle," allowing engineers to optimize regularization parameters and denoiser schedules without extensive trial-and-error simulations.
Future Directions: The framework opens the door for "deep unfolding" complex AMP networks, Bayesian-optimal estimation with group priors, and extensions to structured sensing operators (e.g., partial DFT matrices).

In summary, the paper provides a mathematically rigorous and practically effective framework for solving complex, structured inverse problems using AMP, demonstrating that treating real and imaginary components as a unified complex entity yields superior performance compared to decoupled real-valued approaches.