PaperlayerView exact revision on arXiv

Source-linked AI summary

Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements

Keigo Takeuchi

arXiv:1701.05284v3cs.IT

TL;DR

The paper asks whether EP-based message passing can be rigorously characterized for signal recovery from unitarily invariant measurements in the large-system limit. It extends conditioning arguments to Haar matrices, proves the conjectured state evolution, and thereby establishes Bayes-optimal achievability above the BP threshold under the stated assumptions.

  • Problem

    The paper addresses the lack of a rigorous justification for the conjectured state evolution and Bayes-optimal behavior of EP-based recovery with unitarily invariant measurements.

  • Method

    The proof extends the conditioning technique used for i.i.d. Gaussian matrices to Haar matrices and analyzes their conditional distributions.

  • Results

    The paper rigorously justifies the EP state-evolution equations and implies Bayes-optimal performance when the compression rate exceeds the BP threshold.

  • Takeaways & Limitations

    The EP-based algorithm predicts the exact large-system dynamics of extrinsic variances, with Bayes-optimal performance achievable when the state-evolution fixed point is unique.

Abstract

from arXiv · show

Signal recovery from unitarily invariant measurements is investigated in this paper. A message-passing algorithm is formulated on the basis of expectation propagation (EP). A rigorous analysis is presented for the dynamics of the algorithm in the large system limit, where both input and output dimensions tend to infinity while the compression rate is kept constant. The main result is the justification of state evolution (SE) equations conjectured by Ma and Ping. This result implies that the EP-based algorithm achieves the Bayes-optimal performance that was originally derived via a non-rigorous tool in statistical physics and proved partially in a recent paper, when the compression rate is larger than a threshold. The proof is based on an extension of a conventional conditioning technique for the standard Gaussian matrix to the case of the Haar matrix.

I. INTRODUCTION

The paper studies Bayes-optimal signal recovery from unitarily invariant measurements and addresses the lack of rigorous state-evolution analysis for EP-based message passing. It extends Gaussian-matrix conditioning methods to Haar matrices and rigorously establishes the large-system dynamics under stated scope conditions.

  • A. Motivation: The problem is recovering a sparse signal from compressed noisy measurements as input and output dimensions grow with fixed compression rate.The measurement model uses an unknown i.i.d. sparse signal, a known matrix, and independent noise.
  • A. Motivation: AMP can lose convergence when measurement matrices are not i.i.d. zero-mean, motivating EP-based methods for unitarily invariant measurements.Damping may be required under broken i.i.d. Gaussian assumptions.
  • C. Related Work: The proof establishes almost-sure convergence using a strong law for dependent random variables and statistical properties of Haar matrices.Combining this work with prior results yields rigorous state evolution for general decision functions and performance measures.
  • D. Contributions: The paper rigorously justifies the EP state-evolution equations conjectured for unitarily invariant measurements.The result derives state evolution for individual signal elements in the large-system limit.
  • B. Proof Strategy: The proof extends the conditioning technique for i.i.d. Gaussian matrices by characterizing Haar matrices conditioned on observed columns.Bi-unitary invariance reduces the relevant conditional-distribution problem to a lower-dimensional Haar matrix.
  • D. Contributions: The conditioning technique applies to message-passing algorithms for unitarily invariant measurements, but simple state evolution depends on the algorithm and measurement statistics.Nonlinear processing in the measurement vector, such as quantization, is outside the stated applicability.

B. Results

This section develops probabilistic results needed for the paper’s large-system analysis, including strong laws for dependent arrays and Haar-transformed vectors. These results support the almost-sure convergence arguments used in the EP state-evolution proof.

  • Strong laws: Theorem 1 establishes a strong law for an array of complex random variables when the variance condition on partial sums holds.It concludes that (S_N−E[S_N])/N converges almost surely to zero.
  • Strong laws: The variance condition is satisfied when V[S_N]=O(N^α) for some α<2, including α=1 for uncorrelated variables.The result motivates the subsequent strong-law analysis for Haar matrices.
  • Haar-matrix law: Lemma 1 gives a strong-law result for pseudo-Lipschitz functions of arrays involving perturbations, iterates, and unitarily invariant random variables.Its assumptions include moment bounds and vanishing second moments for the perturbation vector.
  • Role in the proof: Lemma 1 is used repeatedly in the main theorem, while Corollary 1 is used in deriving the EP-based algorithm.These results provide the probabilistic foundation for the later state-evolution analysis.
  • Haar-matrix law: Corollary 1 applies the Haar-matrix result to quadratic functions of V a when V is Haar and independent of a and D.The assumptions require normalized norms and traces of a and D to converge almost surely.

III. SYSTEM MODEL

The system model assumes i.i.d. non-Gaussian signals, structured unitarily invariant measurements, and finite-moment noise. The EP-based algorithm alternates linear detection and MMSE estimation, with bounded posterior variances and an extrinsic decision function.

  • Assumptions: The signal has zero-mean i.i.d. non-Gaussian elements with unit variance and finite (2 + ǫ)th moments.These assumptions imply N −1∥x∥2 converges almost surely to 1.
  • Assumptions: The measurement matrix has a unitarily invariant Gram matrix and an empirical eigenvalue distribution converging almost surely to a compactly supported deterministic law.Its SVD yields a Haar right singular-vector matrix independent of the left singular vectors and singular values.
  • Assumptions: The noise has finite (2 + ǫ)th moments, with its asymptotic per-element power represented by σ2 under the stated matrix conditions.The assumption holds for unitarily invariant noise, including w ∼ CN(0, σ2IM), or when U is Haar.
  • EP algorithm: The detector postulates circularly symmetric complex Gaussian noise, even when that postulation is inconsistent with the true noise distribution.The algorithm also uses an extrinsic decision function whose orthogonality properties support the interaction between modules.
  • EP algorithm: The EP-based message-passing algorithm uses two modules: module A performs linear minimum mean-square error detection, while module B computes an MMSE estimator from a virtual AWGN observation.Module B returns an estimate or feeds an extrinsic mean back to module A when termination has not been reached.
  • Technical conditions: The analysis assumes bounded posterior variances, while the Bayes-optimal decision function is Lipschitz-continuous and characterized through an AWGN-based MMSE.The bounded-variance assumption is described as necessary for practical use, and the decision-function identity generalizes Stein’s lemma to complex values.

C. Error Recursion

The paper represents EP error dynamics through recursions and proves that their state-evolution description is exact in the large-system limit under Haar-matrix conditioning.

  • Error recursion: The EP error recursion is formulated using extrinsic-estimation errors, the system model, SVD updates, and a linear filter.The recursion is then represented in matrix form to analyze errors conditioned on preceding iteration history.
  • State evolution: State-evolution equations conjectured by Ma and Ping are connected to the EP update rules through the extrinsic variances.The paper states that the update rules have the same representation as the corresponding state-evolution equations.
  • Consequences and limitations: The state-evolution equations justify individual MSE behavior and imply Bayes-optimal performance when the compression rate exceeds the BP threshold and the equations have a unique fixed point.The individual MSE result is paired with a limitation: the individual MSE for module A's extrinsic estimate is not analyzed.
  • Conditioning on iteration history: Conditioning on the preceding iteration history reduces the analysis to the distribution of the Haar matrix under constraints imposed by the error recursions.The history sets encode states immediately before the module-A and module-B updates.
  • Module-wise results: Theorems for modules A and B establish Haar-matrix representations and properties at each iteration under trace-convergence conditions.The module-A theorem assumes convergence of normalized traces of powers of a diagonal matrix, while corresponding module-B properties are also stated.
  • Assumptions and proof scope: The weaker finite-subset property for the transformed noise is sufficient to prove the main theorem, although independent CSCG elements were previously postulated.The paper explicitly identifies the stronger postulate as unjustified.

V. PROOF OF THEOREM 4

The proof evaluates conditional distributions of Haar matrices and uses them to establish the algorithm’s large-system error recursions by induction.

  • Conditional-distribution analysis: The proof analyzes two conditional distributions representing the error recursions for successive message-passing iterations.It evaluates them through the conditional distribution of V given Θ and the iteration history.
  • Conditional-distribution analysis: Lemma 3 represents a conditioned Haar matrix using an independent Haar matrix of reduced dimension.The lemma applies when the observed matrix is full-rank and the observation is noiseless and compressed.
  • Inductive proof: Theorem 4 is proved by first establishing the module properties at τ = 0 and then extending them to τ = t under induction hypotheses.This induction links the conditional Haar representation to the required asymptotic properties of both modules.

B. Module A for τ = 0

The τ = 0 analysis establishes module A’s initial error, variance, moment, and orthogonality properties using the update rules, assumptions, and asymptotic lemmas.

  • Base-case setup: Module A’s initial properties follow from the definitions of b0, m0, and the conventions q0 = −x and m⊥0 = m0.The proof begins by deriving the base-case relations for the initial error variables.
  • Asymptotic limits: The unitary-invariance and Lipschitz conditions allow asymptotic lemmas to establish the required limits for module A at τ = 0.The proof verifies boundedness conditions using Cauchy–Schwarz, the definitions of D and W̃0, and the stated assumptions.
  • Asymptotic limits: The base case establishes the variance and orthogonality relations needed for the module-A state evolution.Several relations are obtained from the update rule for v0, the definition of γ0, and the state-evolution equation for module A.
  • Moment conditions: Moment boundedness follows from the finite (2 + ε)th moments of b0 together with the assumptions on the signal and system quantities.These bounds support the remaining base-case properties of the module-A error variables.

C. Module B for τ = 0

The τ = 0 analysis of module B verifies its initial conditional representation, moment conditions, and state-evolution relations using the Haar-matrix lemma and asymptotic bounds.

  • Conditional representation: Applying Lemma 3 to b0 and q0 yields the conditional Haar representation required for module B’s initial error analysis.The resulting representation is conditioned on the relevant history and uses a reduced Haar matrix independent of the conditioned quantities.
  • Initial module-B properties: The conditions of the asymptotic lemma are verified from q0 = −x, the assumptions, and the established properties of module A.This verification includes the required moment conditions and boundedness statements.
  • State-evolution relations: The posterior-variance update for module B converges to the MMSE-based state-evolution quantity in the large system limit.The proof uses bounded posterior variance, Lipschitz continuity, and the equality between expected posterior variance and MMSE.
  • State-evolution relations: The base-case proof establishes the remaining error, variance, and moment relations through Lipschitz and pseudo-Lipschitz arguments.These arguments also establish positivity and convergence properties needed for the module-B recursion.
  • Inductive transition: The τ = 0 results provide the base case for the induction proving Theorem 4.The proof then assumes correctness for all earlier iterations before treating τ = t.

D. Module A by Induction

The induction step extends module A’s asymptotic properties from earlier iterations to τ = t by combining the conditional Haar representation with pseudo-Lipschitz convergence arguments.

  • Conditional representation: The induction hypotheses imply that the matrices needed in Lemma 3 are full-rank, enabling the conditional representation of the current module-A error.The resulting current-iteration error is described using a complex Gaussian term in the large-system limit.
  • Asymptotic convergence: The assumptions of the asymptotic lemma are verified from the induction hypotheses and boundedness of the relevant quantities.This verification yields the convergence statement used to analyze current-iteration functions.
  • Asymptotic convergence: The proof derives the current-iteration limits for module A by applying the convergence result to Lipschitz functions and using earlier-iteration relations.The same strategy establishes the corresponding quadratic and trace-based limits.
  • Property preservation: The remaining variance, moment, and nondegeneracy properties follow by repeating the base-case arguments under the induction hypotheses.The proof explicitly establishes bounded moments and strict positivity of the relevant limiting norm.

E. Module B by Induction

The induction establishes the module B properties at iteration t by representing the relevant variables with Gaussian innovations and propagating pseudo-Lipschitz convergence results. Reusing the base-case arguments then yields the stated properties and state-evolution relations for τ=t.

  • Induction setup: The proof sets up a pseudo-Lipschitz test-function framework linking x_n and the iterates h_0,n,…,h_t,n through conditional expectations.The construction uses X_N, a_{τ,N}, ε_N, and E_N to apply the induction hypotheses and technical lemmas.
  • Gaussian representation: The key representation replaces the current iterate with [H_tα_t]_n plus an independent CSCG perturbation of variance ν_t.Here ν_t is defined through the large-system limit of N^-1∥m_t^⊥∥^2.
  • Induction conditions: Moment and boundedness conditions required by the technical lemma follow from Assumption 1, induction hypotheses, and the definition of h_t.The proof explicitly checks the conditions for the current and previous iterations.
  • Gaussian comparison: The conditional Gaussian comparison identifies h_t with a CSCG vector having independent elements and variance v̄_t in the large-system limit.This comparison is used to transfer the induction argument from the Gaussian surrogate to the actual iterate.

APPENDIX A PROOF OF LEMMA 1

This appendix proves Lemma 1 by combining Haar/SVD representations, moment bounds, and convergence arguments. It also distinguishes convergence in probability from the almost sure convergence needed for the result and supplies the latter through a stronger theorem.

  • Haar representation: Unitary invariance permits an SVD representation in which the relevant singular-vector directions are Haar-distributed and independent of singular values.The argument uses this representation to construct a unified form for the variables at all t≥0.
  • Unified representation: The unified representation is extended to t=0 by setting u\N=u, ε̃_N=ε_N, and Φ_E_N=I_N.This convention allows one representation to cover every iteration index.
  • Residual control: The residual term δ_N converges almost surely to zero, enabling the subsequent moment and conditional-expectation estimates.The almost sure convergence is obtained through Chebyshev’s inequality and the Borel–Cantelli lemma.
  • Almost sure convergence: The appendix notes that a prior proof established only convergence in probability, whereas this work proves the almost sure convergence required by Lemma 1.A counterexample with p_N,ε=O(N^-1) shows why convergence speed matters for an almost sure conclusion.
  • Convergence estimates: Conditional expectations are controlled using pseudo-Lipschitz bounds, Cauchy–Schwarz inequalities, moment assumptions, and uniform integrability.These estimates establish the remaining convergence relations in the lemma.

D. Proof of (15)

The proof of (15) decomposes the relevant quantities through the Haar-matrix representation and verifies each convergence component using moment assumptions, pseudo-Lipschitz bounds, and conditional-independence arguments.

  • First convergence: The proof reduces the first convergence to controlling the component Y^1_n,N through the unified representation and Theorem 1.The required conditional expectations are then bounded term by term.
  • First convergence: Cauchy–Schwarz bounds and repeated O(N^-1) estimates show that the error terms in the first convergence vanish almost surely.The argument applies the assumptions governing moments and residuals.
  • Second convergence: The second convergence follows by repeating the preceding estimates, with the first and third terms converging almost surely to zero under assumptions (7) and (9).The remaining terms are handled using the same conditional-expectation bounds.
  • Conclusion: The remaining error term converges almost surely to zero, completing the proof of all convergence statements in (15).This follows from the assumptions and the established bounds on the factors in the relevant inequalities.
  • Final convergence: The final convergence uses conditional independence and comparison with a standard complex Gaussian variable Z.The assumptions ensure boundedness and allow Theorem 1 to establish the required limit.

APPENDIX B DERIVATION OF MESSAGE-PASSING

This appendix derives the message-passing updates from expectation propagation by approximating marginal posteriors with Gaussian densities and enforcing moment matching. The large-system limit yields the stated module A and module B update rules.

  • EP approximation: Expectation propagation approximates each marginal posterior p(x_n|y,A) with a tractable factorized Gaussian density.The Gaussian approximation provides the starting point for deriving the message-passing algorithm.
  • Gaussian messages: The conjugate prior q_B→A(x_n) is proper complex Gaussian, with a common mean and variance parameter across n in the proposed algorithm.Using an identical variance simplifies the large-system derivation, while allowing different variances can improve finite-size performance.
  • Module A derivation: The large-system marginal q_A(x_n) remains Gaussian, with its parameters obtained from the joint covariance and matrix-inversion identities.The diagonal coefficients converge almost surely to the scalar limit used in the module A expressions.
  • Moment matching: EP updates the extrinsic message q_B→A(x_n) by matching the mean and variance of the tilted density p_B(x_n) proportional to q_A→B(x_n)p(x_n).These moment-matching conditions are the central EP step used to derive the message updates.
  • Update rules: Applying the Gaussian identities and moment-matching conditions produces the update rules for module A and module B.The resulting rules are equations (21), (22), (29), and (30).

APPENDIX C PROOF OF LEMMA 2

The proof establishes regularity properties of the posterior cumulant generating function and the associated estimator, then develops the unitary-matrix conditioning structure needed for the Haar-matrix argument.

  • χt is twice continuously differentiable with respect to the real and imaginary parts of z.The proof invokes Assumption 1 and dominated convergence, then computes the derivatives directly.
  • The estimator ˜ηt is Lipschitz-continuous because its first-order derivatives are almost surely bounded.Assumption 4, Lemma 4, and the Cauchy–Schwarz inequality provide the required bound.
  • The proof rewrites z∗˜η in terms of the real and imaginary components of z and ˜η.This decomposition supports subsequent derivative and expectation calculations.
  • Gaussianity of ℜ[z] and ℑ[z] enables the derivative calculation that establishes equation (33).Both components are independent, zero-mean Gaussian variables with variance vt.
  • The orthogonal complement has the block structure in (227), with ˜V unitary, and Haar invariance makes ˜V independent of V 0.This yields the stated structural lemma for the conditioned Haar matrix.
  • The Haar-matrix argument reduces conditioning on compressed observations to conditioning on selected columns after suitable coordinate rotations.Bi-unitary invariance preserves the distribution under these rotations.
Loading 1701.05284v3…