⚡ electrical engineering

Gaussian-Process Dynamics of Diagonal Expectation Propagation under Variance-Profile Gaussian Measurements

This paper establishes that for diagonal expectation propagation under variance-profile Gaussian measurements, the effective channel is not a fresh scalar Gaussian but rather a coordinate-dependent Gaussian process with profile-dependent memory, which can be characterized via a conditioned matrix-Dyson equation and corrected through a Gaussian-regression decomposition to yield an oracle state-evolution description.

Original authors: Fangqing Xiao, Dirk T. M. Slock

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fangqing Xiao, Dirk T. M. Slock

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: Trying to Guess a Hidden Message

Imagine you are trying to guess a secret message (a signal) that has been scrambled and sent to you through a noisy, messy channel. You don't know the original message, but you have a "decoder" (an algorithm called Expectation Propagation) that tries to figure it out step-by-step.

In the past, scientists found that for certain types of messiness (specifically, when the noise is perfectly random and uniform), this decoder works like a magic trick. Every time it takes a step, it receives a brand-new, clean piece of information that is completely unrelated to what it saw before. This is called a "fresh" signal. Because the information is always fresh and independent, the math to predict how well the decoder works is simple: you just track a single number (like an average error rate) for the whole system. This is known as State Evolution.

The Problem: The Messy, Uneven Channel

This paper asks: What happens if the channel isn't perfectly uniform?

Imagine the channel is a wall made of bricks. In the old "perfect" model, every brick is identical. In this paper's model, the bricks are still made of the same material (Gaussian noise), but some are thick, some are thin, and some are cracked. This is called a "variance profile."

The authors wanted to know: If the wall is uneven, does the decoder still get "fresh" information at every step, or does it get confused by the unevenness?

The Discovery: The "Echo" Effect

The paper's main finding is surprising but logical: The information is no longer "fresh."

Here is the analogy:

The Old Way (Uniform Wall): You shout into a room with perfect acoustics. Every time you shout, you hear a clear, new echo that tells you exactly where you are. You don't need to remember your previous shouts to understand the new one.
The New Way (Uneven Wall): You shout into a room with uneven walls. When you shout, the sound bounces off the thick bricks and the thin bricks differently. The sound you hear now isn't just a new echo; it's a mix of the new sound plus a lingering "ghost" of your previous shouts that bounced around the uneven walls.

The authors proved that in this uneven environment, the decoder receives a Gaussian Process with Memory.

Gaussian: It's still a random signal (like static noise).
With Memory: The current signal contains a predictable part based on what happened in the past. It's like hearing a song where the current note is influenced by the notes you played five seconds ago.

The "Cavity" Mistake

The standard decoder (Diagonal Expectation Propagation) has a built-in trick called a "cavity."

How it works: It tries to remove the part of the signal that it just sent out, so it only sees what the outside world is telling it.
The Flaw: In the uneven wall scenario, the cavity successfully removes the immediate shout it just made. However, it fails to remove the "ghost" echoes from previous shouts that are still bouncing around the uneven walls.

Because the decoder doesn't realize these "ghosts" are there, it thinks it's getting a fresh, clean signal. But it's actually getting a signal that is shifted by a predictable amount (the memory of the past). If the decoder ignores this shift, its calculations will be slightly off.

The Solution: The "Oracle" Correction

The paper proposes a theoretical fix, which they call an "Oracle State Evolution."

Think of the "Oracle" as a super-smart guide who knows the exact layout of the uneven wall and the history of every shout.

The guide looks at the messy signal the decoder received.
The guide calculates exactly how much of that signal is just a "ghost" from the past (the predictable memory).
The guide subtracts that ghost, leaving only the truly fresh, new information.

Once this "ghost" is removed, the decoder can work correctly again. However, the paper emphasizes that this is a theoretical tool to understand how the system works. It is not a practical recipe for building a real-world decoder today, because calculating the "ghost" requires knowing the entire history and the exact wall layout in a way that is too complex for current computers to do efficiently.

Summary of Key Takeaways

The Old Rule: If the noise is uniform, the decoder gets fresh, independent clues every time. Math is simple.
The New Reality: If the noise has an uneven pattern (variance profile), the decoder gets clues that are contaminated by the past. The current clue depends on previous clues.
The Consequence: The standard decoder fails to notice this dependency. It thinks it's seeing something new, but it's actually seeing a mix of new and old.
The Fix: You can mathematically separate the "new" part from the "old" part using a regression technique (like a smart filter), but this is currently a theoretical concept to explain the behavior, not a ready-to-use engineering fix.

In short: The paper shows that when the environment is uneven, the "freshness" of information breaks down, and the system develops a "memory" that standard algorithms don't account for.

Technical Summary: Gaussian-Process Dynamics of Diagonal Expectation Propagation under Variance-Profile Gaussian Measurements

1. Problem Statement

This paper investigates the asymptotic behavior of Diagonal Expectation Propagation (EP) when applied to high-dimensional linear inference problems with variance-profile Gaussian measurements. The standard linear inference model is $y = Ax + v$, where $A$ is a sensing matrix. While classical analyses of Approximate Message Passing (AMP) and EP often assume that $A$ consists of independent and identically distributed (i.i.d.) Gaussian entries or possesses unitary/rotational invariance, this work considers a more general regime where the entries of $A$ are Gaussian but their variances are prescribed by a deterministic variance profile $S = (s_{ij})$ .

The central question addressed is whether the standard "fresh-noise" principle holds in this setting. In traditional i.i.d. or rotationally invariant models, the linear module of an iterative algorithm, after an appropriate Onsager or cavity correction, delivers a fresh scalar Gaussian observation to the prior module. This allows for a rigorous State Evolution (SE) description using scalar recursions. The authors ask: under a variance profile, does the standard diagonal EP cavity still produce a fresh scalar Gaussian channel, or does the variance profile introduce a dependency on past iterations that prevents such a simple decoupling?

2. Methodology

The paper employs a rigorous finite-time large-system analysis ( $M, N \to \infty$ with $M/N \to \delta$ ) based on Gaussian conditioning and Random Matrix Theory (RMT). The methodology diverges from standard approaches in the following ways:

Gaussian Conditioning on Linear History: Unlike unitarily invariant models where conditioning on past iterates leaves a "fresh" Haar-random component, conditioning on the finite linear history of a variance-profile Gaussian matrix leaves a correlated Gaussian residual. The covariance of this residual is deformed by the variance profile and the revealed history.
Conditioned Matrix-Dyson Equation (MDE): To control the resolvent of the conditioned linear module, the authors utilize a regularized Matrix-Dyson Equation framework for correlated random matrices. This provides a deterministic equivalent for the linear module's covariance and response, replacing the scalar variance parameters used in standard SE.
Schur-Complement Expansion: The linear module's output is decomposed using a coordinate-wise Schur complement. This separates the instantaneous response (which the EP cavity is designed to cancel) from the residual fluctuation.
Gaussian Regression Decomposition: The authors identify that the residual fluctuation forms a coordinate-dependent Gaussian process. They apply finite-dimensional Gaussian regression to decompose this process into a predictable memory component (conditional mean given past residuals) and an orthogonal innovation (fresh noise).

3. Key Contributions

The paper makes three primary contributions:

Identification of the Conditional Gaussian Object: The authors prove that under variance-profile measurements, the linear module of diagonal EP generates a coordinate-dependent Gaussian process rather than a fresh scalar channel. The covariance of this process is governed by the variance profile and the finite linear history of the algorithm, described via a conditioned MDE response.
Characterization of the Memory Defect: The paper demonstrates that the standard diagonal EP cavity, while successfully canceling the instantaneous response, fails to remove the predictable component of the current residual that is correlated with past residuals. This results in a "memory defect," meaning the effective observation delivered to the prior module is a shifted Gaussian variable, not a fresh one.
Oracle State-Evolution Correction: By decomposing the Gaussian process into its predictable memory and fresh innovation, the authors derive an oracle state-evolution-level correction. This correction subtracts the predictable memory term, revealing the underlying fresh scalar channel. This yields a coordinate-wise state evolution that is quenched with respect to the MDE-generated environment, rather than a simple scalar recursion.

4. Main Results

The core theoretical results are summarized as follows:

Theorem 3 (General Finite-Time Dynamic Theorem): Establishes that the linear module output can be approximated by a Gaussian process with a specific covariance kernel derived from the conditioned MDE. The output is shown to be a sum of a deterministic linear response, a Gaussian process $Z_{t,j}$ , and a vanishing error term.
Theorem 4 (Memory Defect): Shows that the standard EP cavity output $h_{t,j}$ satisfies:
$h_{t,j} = \mu_{t,j} + \sqrt{\tau_{t,j}} W_{t,j} + o_{\ell^2_p}(1)$
where $\mu_{t,j}$ is the memory defect (predictable from past history) and $W_{t,j}$ is a fresh standard Gaussian. Unless the variance profile possesses specific symmetries (e.g., rotational invariance), $\mu_{t,j} \neq 0$ . Consequently, the standard cavity is not a fresh AWGN observation.
Theorem 5 (Memory-Corrected State Evolution): Defines a corrected cavity $\hat{h}_{t,j} = h_{t,j} - \mu_{t,j}$ . The theorem proves that this corrected variable behaves as a fresh scalar Gaussian observation ( $\sqrt{\tau_{t,j}} W_{t,j}$ ). This allows for a valid state evolution description, but one that requires tracking the full coordinate-wise covariance history and the MDE environment, rather than just scalar variances.
Theorem 6 (Precision Replacement): Bridges the gap between the theoretical "predictable-precision" dynamics used in the proof and the actual "adaptive-precision" diagonal EP algorithm. It proves that the empirical norms of the adaptive precisions and errors converge to their predictable counterparts, validating the theoretical results for the actual algorithm.

5. Significance and Claims

The paper claims that the standard assumption of a "fresh scalar Gaussian channel" in message-passing algorithms is not robust to variance-profile Gaussian measurements. The significance of the work lies in:

Refining the Decoupling Principle: It clarifies that while the Gaussian nature of the linear module output is preserved under variance profiles, the freshness (independence from past iterations) is generally lost. The limiting object is a Gaussian-process dynamics with profile-dependent memory.
Theoretical Limit of Diagonal EP: It establishes that for general variance profiles, the standard diagonal EP algorithm does not naturally decouple into scalar state evolution. The "memory" of the algorithm is an intrinsic feature of the variance profile, not an artifact of the algorithm's design.
Oracle vs. Practical: The authors are modest regarding the immediate practical application of their results. They explicitly state that the memory correction derived is an oracle construction (requiring knowledge of the MDE environment and past history) and is not proposed as a finite-sample algorithm. The paper focuses on characterizing the limiting dynamics and identifying the theoretical "fresh" channel hidden within the residual process.

In conclusion, the paper provides a rigorous finite-time description of diagonal EP under variance-profile measurements, replacing the conventional scalar state evolution with a more complex, memory-dependent Gaussian-process dynamics, and identifying the precise conditions under which the standard "fresh-noise" intuition fails.