PaperlayerView exact revision on arXiv

Source-linked AI summary

Vector Approximate Message Passing

Sundeep Rangan, Philip Schniter, Alyson K. Fletcher

arXiv:1610.03082v2cs.IT

TL;DR

AMP has rigorous scalar state evolution under large i.i.d. sub-Gaussian matrices but is fragile to deviations from that model. The paper proposes VAMP, establishes scalar state evolution for large right-orthogonally invariant matrices, and finds consistency with replica MMSE predictions.

  • Problem

    The paper asks whether an AMP-like algorithm can retain rigorous state-evolution analysis for a broader matrix class than i.i.d. sub-Gaussian matrices.

  • Method

    The paper proposes VAMP, analyzes its scalar state evolution for large right-orthogonally invariant matrices, and derives it as an approximation to belief propagation with vector-valued nodes.

  • Results

    VAMP’s state-evolution fixed points are consistent with replica MMSE predictions, and numerical behavior matches state-evolution predictions at moderate dimensions.

  • Takeaways & Limitations

    VAMP provides an AMP-like approach that is more robust to matrix construction while retaining comparable per-iteration complexity after an initial SVD.

  • Takeaways & Limitations

    AMP’s established state-evolution analysis is limited to large i.i.d. sub-Gaussian matrices, and AMP can diverge for mildly ill-conditioned or non-zero-mean matrices.

Abstract

from arXiv · show

The standard linear regression (SLR) problem is to recover a vector $\mathbf{x}^0$ from noisy linear observations $\mathbf{y}=\mathbf{Ax}^0+\mathbf{w}$. The approximate message passing (AMP) algorithm recently proposed by Donoho, Maleki, and Montanari is a computationally efficient iterative approach to SLR that has a remarkable property: for large i.i.d.\ sub-Gaussian matrices $\mathbf{A}$, its per-iteration behavior is rigorously characterized by a scalar state-evolution whose fixed points, when unique, are Bayes optimal. The AMP algorithm, however, is fragile in that even small deviations from the i.i.d.\ sub-Gaussian model can cause the algorithm to diverge. This paper considers a "vector AMP" (VAMP) algorithm and shows that VAMP has a rigorous scalar state-evolution that holds under a much broader class of large random matrices $\mathbf{A}$: those that are right-orthogonally invariant. After performing an initial singular value decomposition (SVD) of $\mathbf{A}$, the per-iteration complexity of VAMP can be made similar to that of AMP. In addition, the fixed points of VAMP's state evolution are consistent with the replica prediction of the minimum mean-squared error recently derived by Tulino, Caire, Verdú, and Shamai. Numerical experiments are used to confirm the effectiveness of VAMP and its consistency with state-evolution predictions.

I. INTRODUCTION

The paper introduces VAMP to address AMP’s fragility outside the i.i.d. sub-Gaussian matrix model, establishing scalar state evolution for a broader class of matrices and linking its fixed points to replica MMSE predictions.

  • B. Approximate Message Passing: AMP is a computationally efficient iterative method whose behavior is rigorously characterized by scalar state evolution for large i.i.d. sub-Gaussian matrices.Its state evolution applies in the large-system limit under mild regularity conditions.
  • C. Limitations, Modifications, and Alternatives to AMP: AMP can diverge for mildly ill-conditioned or non-zero-mean matrices, while common stabilization strategies have limited effectiveness.The limitation concerns robustness to the construction of A rather than AMP’s behavior under its standard matrix assumptions.
  • D. Contributions: VAMP is a computationally efficient iterative algorithm derived using belief propagation with vector-valued variable nodes.The algorithm is designed for estimating x0 from noisy linear measurements.
  • D. Contributions: VAMP’s scalar state evolution is established for large right-orthogonally invariant matrices and separable Lipschitz denoisers.This matrix class allows arbitrary singular values and arbitrary left singular vectors.
  • D. Discussion: VAMP’s fixed points agree with replica MMSE predictions when priors are matched, and numerical results show close agreement with state-evolution predictions at moderate dimensions.The reported simulations include highly ill-conditioned and non-zero-mean matrices.
  • D. Contributions: After one SVD, VAMP has per-iteration cost dominated by O(RN) flops, with further reductions possible when matrix-vector multiplications have fast implementations.The SVD is computed once rather than at every iteration and may be computed offline.

F. Notation

This section establishes notation and reviews AMP as background for VAMP. It defines Bayesian denoisers, their interpretation, and AMP’s relation to IST and state evolution.

  • AMP background: AMP applies scalar denoisers to estimate components of x from noisy linear measurements under Bayesian MAP or MMSE formulations.For MMSE estimation, the denoiser uses the conditional density of each component given its noisy scalar input.
  • AMP background: The iteration parameter γk can be interpreted as an estimate of the inverse variance τk^-1 of the effective noise entering AMP.When τk is known, the matched assignment yields scalar MAP and MMSE denoisers.
  • AMP background: Removing AMP’s Onsager term leaves the iterative soft thresholding algorithm, while the Onsager correction enables the stated behavior for large i.i.d. sub-Gaussian matrices.Under those matrices, AMP can converge much faster than ISTA.
  • AMP background: AMP can be derived through loopy belief propagation, free-energy methods, expectation propagation, or expectation consistent approximation.These derivations connect message passing with stationary-point and approximate-inference frameworks.
  • Notation and VAMP setup: VAMP is specified in an SVD-form algorithm using a denoiser, precision updates, and a fixed iteration loop.The notation includes componentwise squaring and diagonal matrices formed from vectors; IST convergence is guaranteed when ∥A∥2 < 1.

A. Relation of VAMP to AMP

VAMP shares AMP’s denoising, divergence, Onsager, and matrix-vector structure while extending rigorous state evolution to right-orthogonally invariant matrices. Its EP-style derivation uses vector-valued nodes and yields equivalent SVD and LMMSE forms.

  • Algorithmic relation: VAMP and AMP both use denoising, divergence, Onsager correction, and two matrix-vector multiplications per iteration.The shared computational structure makes VAMP’s per-iteration complexity similar to AMP’s after matrix preprocessing.
  • Algorithmic relation: For suitable large random A, the VAMP input rk behaves as the true signal x0 corrupted by white Gaussian noise with trackable variance τk.The precision γk can be interpreted as an estimate of τk^-1.
  • Algorithmic relation: VAMP’s scalar state evolution holds when the right singular-vector matrix V is uniformly distributed over orthogonal matrices, with arbitrary deterministic U and singular values under mild conditions.This matrix class is broader than the i.i.d. sub-Gaussian setting required for AMP’s state evolution.
  • EP derivation: VAMP is derived by splitting x into identical vector variables and applying EP-like message passing on a non-loopy factor graph.Approximate beliefs are Gaussian, variable-to-factor messages use belief-to-message ratios, and factor-to-variable messages integrate over other variables.
  • Equivalent formulations: The LMMSE-form algorithm is equivalent to the SVD-form algorithm and exposes a symmetric alternation between denoising and LMMSE estimation, each followed by Onsager correction.The equivalence follows by substituting the economy SVD and identifying the corresponding variables and precisions.
  • Implementation: Finite-dimensional implementations clip precisions, optionally damp updates for ill-conditioned matrices, and stop when successive inputs differ below a tolerance.The reported settings include γmin = 1 × 10^-11, γmax = 1 × 10^11, ρ = 0.97, and τ = 1 × 10^-4.
  • Implementation: VAMP requires the measurement-noise precision and denoiser to be chosen, although EM-VAMP can estimate unknown noise precision and prior information online.The numerical results in this paper assume the true noise precision and prior are known.

IV. STATE EVOLUTION

The state-evolution analysis models VAMP for right-orthogonally invariant transforms, separable denoisers, and convergent empirical signal and singular-value sequences. It defines scalar error and sensitivity quantities for denoising and LMMSE estimation.

  • Model assumptions: The analysis studies a sequence of high-dimensional problems with a true vector observed through a known transform and Gaussian noise.The true noise precision γw0 is distinguished from the estimator’s postulated precision γw.
  • Model assumptions: The transform A is right-orthogonally invariant when its SVD has deterministic U, Haar-distributed V, and an allowed singular-value distribution.The square-matrix assumption can represent wide or tall rectangular transforms through SVD manipulations.
  • Model assumptions: The denoiser is assumed separable and subject to Lipschitz-type regularity, without requiring it to be MAP or MMSE for a particular prior.The signal and initial denoiser input may be deterministic sequences whose empirical distributions converge with bounded second moments.
  • Error functions: The denoiser and LMMSE error functions represent mean-squared errors under Gaussian-noise inputs.The LMMSE error function can also be expressed using the limiting singular-value random variable S under matched conditions.
  • Error and sensitivity functions: Under matched MMSE conditions, the denoiser error function is the conditional variance, and the sensitivity function is related to conditional variance divided by measurement variance.Corresponding LMMSE sensitivity formulas are also established.

C. Sensitivity Functions

VAMP’s state evolution replaces high-dimensional iterates with scalar equivalent models whose variances evolve recursively. These models predict asymptotic MSE and other componentwise distortion metrics.

  • State evolution: The main result establishes scalar state-evolution equations for VAMP under the stated matrix, denoiser, and convergence assumptions.The equations recursively define the variance terms governing the scalar equivalent models.
  • Scalar equivalent model: Each denoiser input component asymptotically behaves as the corresponding true signal component plus Gaussian noise, with the estimate given by scalar denoising.Thus the joint empirical behavior of signal, input, and estimate matches a simple scalar system.
  • Scalar equivalent model: The LMMSE step likewise admits a scalar equivalent model involving independent random variables, the singular-value distribution, and a recursively defined variance.The theorem gives almost-sure empirical convergence for the relevant transformed quantities at fixed iterations.
  • Performance prediction: The scalar equivalent model predicts the asymptotic MSE of VAMP iterates through the denoiser and LMMSE error functions.The same approach computes any pseudo-Lipschitz order-two componentwise distortion metric by taking its scalar-model expectation.

F. Contractiveness of the Denoiser

The analysis requires a denoiser sensitivity condition ensuring valid VAMP variance updates. Strong log-concavity provides this condition, while mismatched non-log-concave settings may invalidate the updates; matched MMSE denoising connects VAMP fixed points to replica predictions.

  • Failure mode: If the increasing-contraction property fails, γ2k may become negative and subsequent VAMP updates become invalid.This issue can arise when the prior is not log-concave or the denoiser is not perfectly matched.
  • Contractiveness condition: VAMP requires the denoiser sensitivity α1k to lie in (0, 1) for valid state-evolution updates.The denoiser must be increasing and contractive in the relevant average.
  • Sufficient condition: Strongly log-concave priors guarantee the required contraction property for MAP and MMSE denoisers.Under these priors, the sensitivity α1k is provably in the valid range.
  • Matched MMSE case: With matched MMSE denoising and matched noise precision, the VAMP state-evolution equations simplify and their fixed points satisfy the replica fixed-point equation.The fixed-point relation is established through the inverse-MSE representation and the corresponding state-evolution equations.
  • Bayes-optimal implication: If the replica equations have a unique fixed point, VAMP achieves the Bayes-optimal MSE predicted by the replica method, conditional on replica correctness.The replica method is heuristic in general, although its prediction is proven for i.i.d. Gaussian matrices.

VI. NUMERICAL EXPERIMENTS

Numerical experiments compare VAMP with AMP-family methods, state evolution, replica predictions, and an oracle estimator under matrix perturbations. VAMP remains accurate and convergent across severe ill-conditioning and mean perturbations, while AMP-family methods can diverge or converge poorly.

  • Ill-conditioned A: VAMP’s NMSE stayed close to the replica prediction across condition numbers from 1 to 1 × 10^6.The comparison used medians over 500 realizations; the remaining gap was attributed to finite-dimensional effects.
  • Ill-conditioned A: AMP and S-AMP diverged for even mildly ill-conditioned matrices, while adaptive damping extended AMP’s operating range only modestly.The oracle bound was close to the replica prediction at small condition numbers but not at large ones.
  • Ill-conditioned A: VAMP’s trajectory stayed close to VAMP state evolution at every iteration for κ(A) = 1 and κ(A) = 1000.VAMP converged somewhat faster than AMP, S-AMP, and AD-GAMP at κ(A) = 1, with convergence relatively insensitive to conditioning.
  • Non-zero-mean A: VAMP and mean-removed AD-GAMP closely matched the replica prediction for all tested mean parameters, whereas AMP and S-AMP diverged under mild mean perturbations.The experiments used 200 realizations and mean parameters between 0.001 and 10.
  • Row-orthogonal A: VAMP and S-AMP had nearly identical NMSE across 10 dB, 20 dB, and 30 dB for row-orthogonal matrices, while VAMP outperformed AMP at low SNR.The replica prediction was about 3% lower, or −0.15 dB, than VAMP’s empirical NMSE at each SNR.
  • Discussion: Good fixed points do not guarantee convergence: S-AMP has replica-matching fixed points for right-orthogonally invariant matrices but converges only for a narrower spectral class.The favorable class has singular-value spectra similar to or flatter than those of i.i.d. Gaussian matrices.
  • Discussion: In the large-system limit with matched priors, VAMP is guaranteed to converge to a replica-equation fixed point, and finite simulations attain NMSEs close to the replica prediction.The simulations used finite 512 × 1024 right-orthogonally invariant matrices.

APPENDIX A MESSAGE-PASSING DERIVATION OF VAMP

The appendix derives VAMP through vector-valued message passing and relates its updates to conditional means, sensitivities, and Gaussian beliefs. It also develops orthogonal-invariance lemmas supporting the state-evolution analysis.

  • Message initialization and iteration: The message-passing derivation initializes Gaussian messages and repeats alternating updates across the two vector variables.The iteration index k is repeated over successive message-passing cycles.
  • Denoising module: For an i.i.d. prior, the first-module belief mean is the conditional-mean denoiser g1(r1k,n, γ1k).Its conditional covariance uses the denoiser derivative g′1(r1k,n, γ1k), producing the sensitivity-related update.
  • Inter-module transfer: The message passed from the first module to the second uses r2k = (bx1kη1k − r1kγ1k)/(η1k − γ1k) and γ2k = η1k − γ1k.The second-side belief is then formed from this Gaussian message.
  • Linear module: The linear module forms a Gaussian belief with covariance (γwATA + γ2kI)^−1, whose average diagonal yields the precision-related update.This covariance relation explains the corresponding linear-module steps in the algorithm.
  • State-evolution framework: The appendix defines pseudo-Lipschitz functions and empirical convergence so component averages converge to expectations under the limiting random variable.The convergence applies pointwise to pseudo-Lipschitz test functions when the required moments exist.
  • Orthogonal-matrix lemmas: For Haar-distributed orthogonal matrices under linear constraints, the conditional residual matrix remains Haar distributed and independent of the constraint event.This invariance is established through orthogonal-transform invariance of the conditional density.
  • Gaussianization lemma: An isotropically distributed vector transformed by a suitable orthogonal matrix has components that converge empirically to a Gaussian random variable.The proof represents the isotropic vector using normalized Gaussian variables and an orthogonal completion.

APPENDIX E A GENERAL CONVERGENCE RESULT

The appendix analyzes a general recursion driven by a Haar-distributed orthogonal matrix and establishes scalar state-evolution limits under regularity assumptions. For every fixed iteration, the recursion’s component vectors converge empirically almost surely to Gaussian-variable descriptions.

  • Setup: The general recursion uses an orthogonal matrix V, an initial vector, disturbance vectors, separable update functions, and scalar parameter updates.The matrix V is uniformly distributed over orthogonal matrices and independent of deterministic initial and disturbance sequences.
  • Assumptions: Theorem 4 assumes convergence of the state-evolution parameters and uniform Lipschitz continuity of both update functions and their derivatives.These conditions are imposed at the state-evolution parameter values for each iteration.
  • State evolution: For any fixed k, the components of (wp, p0, ..., pk) converge almost surely to a limit involving Wp and a jointly Gaussian vector (P0, ..., Pk).The Gaussian vector is independent of Wp, with its variances and covariances determined by the state-evolution equations.
  • State evolution: For any fixed k, the components of (wq, q0, ..., qk) likewise converge almost surely to a limit involving Wq and a jointly Gaussian vector (Q0, ..., Qk).The limiting Gaussian vector is independent of Wq, with moments specified by the state evolution.

APPENDIX F PROOF OF THEOREM 4

The proof establishes Theorem 4 by induction over the recursion iterations. It verifies the base case using Haar orthogonal invariance and advances the induction through continuity, Lipschitz, and empirical-convergence arguments.

  • Induction: The induction hypothesis tracks the validity of both theorem parts through successive p- and q-recursion iterations.The proof advances through the implications Hk,k−1 ⇒ Hk,k and Hk,k ⇒ Hk+1,k.
  • Base case: The base case follows because p0 = Vu0 is orthogonally invariant when V is Haar distributed and independent of the deterministic initial vector.This yields empirical convergence of p0 to a Gaussian variable and establishes the corresponding independence from Wp.
  • Induction step: The p-update induction step uses continuity of Γ1 and uniform Lipschitz continuity of fp and its derivative at the state-evolution parameters.These properties establish the required convergence for the next p-state.

C. The Induction Recursion

The induction recursion decomposes each q-update into deterministic and random parts, analyzes their asymptotic limits, and combines them to obtain the jointly Gaussian state-evolution law.

  • C. The Induction Recursion: Conditioning on prior iterates leaves the orthogonal matrix Haar distributed over matrices satisfying linear constraints imposed by the recursion history.This conditional representation separates the matrix action into constrained and orthogonal-complement components.
  • C. The Induction Recursion: The q-update is written as deterministic and random terms, whose asymptotic distributions are evaluated by separate lemmas.The deterministic term becomes a linear combination of previous Gaussian limits, while the random term contributes an independent Gaussian component.
  • C. The Induction Recursion: The random component converges to Uk ∼ N(0, ρk), independent of (Wq, Q0, ..., Qk−1), completing the Gaussian recursion for Qk.Together with the deterministic component, this proves that (Q0, ..., Qk) is jointly Gaussian.
  • C. The Induction Recursion: The proof verifies that the variance of Qk equals τ2k from the state-evolution equations, completing the induction implication Hk,k−1 ⇒ Hk,k.The argument uses orthogonality of V, empirical convergence, the update definition, and Stein’s Lemma.

APPENDIX G PROOF OF THEOREM 1

The proof of Theorem 1 rewrites VAMP as an instance of the general recursion in Theorem 4. It then verifies the update identities and the continuity and Lipschitz conditions required for the general convergence result.

  • APPENDIX G PROOF OF THEOREM 1: VAMP’s recursion is mapped to the general framework by defining disturbance terms and componentwise update functions.Under this mapping, the state-evolution equations and empirical limits of Theorem 1 follow as special cases of Theorem 4.
  • APPENDIX G PROOF OF THEOREM 1: The required continuity assumptions follow from positive γik, bounded singular values, and the assumed uniform Lipschitz continuity of the denoiser.These conditions ensure continuity of Ci and Γi and uniform Lipschitz continuity of fq and the denoiser at the relevant parameters.
  • APPENDIX G PROOF OF THEOREM 1: The LMMSE and denoising updates are algebraically rewritten using the SVD, orthogonality of V, and the definitions of the transformed variables.The resulting identities establish all updates in equation (120).
  • APPENDIX G PROOF OF THEOREM 1: The update identities in (120) prove that VAMP satisfies the general recursion, completing the proof of Theorem 1.The proof concludes after deriving the remaining vk updates and combining the established identities.

APPENDIX H PROOF OF THEOREM 2

The appendix proves Theorem 2 by induction, establishing the stated relations through previously derived equations and a matched condition.

  • Inductive proof: The intermediate steps use equations (50a), (44), and (36), along with equation (50c).
  • Inductive proof: The proof proceeds by induction on k.It assumes the result for a given k before deriving the next identities.
  • Inductive proof: One step follows from equation (128) and the matched condition.
  • Inductive proof: Canceling terms in a fraction and using an additional stated fact yields another part of the result.
  • Conclusion: The argument establishes (56a), while a similar argument establishes (56b).
  • Conclusion: Finally, (56c) follows from equations (56) and (55).
Loading 1610.03082v2…