PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Convergence of Approximate Message Passing with Arbitrary Matrices

Sundeep Rangan, Philip Schniter, Alyson K. Fletcher, Subrata Sarkar

arXiv:1402.3210v3cs.IT

TL;DR

AMP convergence for generic finite-dimensional transforms is not fully understood. The paper analyzes damped GAMP, proving global convergence for Gaussian models and local stability under strict convexity, with damping requirements tied to the transform’s singular-value profile.

  • Problem

    Convergence of AMP-related methods for generic finite-dimensional linear transforms remains insufficiently characterized, despite rigorous results for large i.i.d. Gaussian transforms.

  • Method

    The paper introduces damping into GAMP and analyzes global convergence for Gaussian distributions, local stability for strictly convex functions, and connections to PDHG.

  • Results

    Sufficient damping guarantees global convergence in the Gaussian case, while the required damping grows with the peak-to-average ratio of squared singular values; strict-convexity analysis yields local stability conditions.

  • Takeaways & Limitations

    The singular-value profile of the transform determines how much damping GAMP may require, explaining undamped convergence for large i.i.d. Gaussian matrices and stronger damping needs for ill-conditioned matrices.

  • Takeaways & Limitations

    Global convergence conditions for GAMP with general scalar estimation functions remain unresolved, and the paper does not provide a method for computing damping constants.

Abstract

from arXiv · show

Approximate message passing (AMP) methods and their variants have attracted considerable recent attention for the problem of estimating a random vector $\mathbf{x}$ observed through a linear transform $\mathbf{A}$. In the case of large i.i.d. zero-mean Gaussian $\mathbf{A}$, the methods exhibit fast convergence with precise analytic characterizations on the algorithm behavior. However, the convergence of AMP under general transforms $\mathbf{A}$ is not fully understood. In this paper, we provide sufficient conditions for the convergence of a damped version of the generalized AMP (GAMP) algorithm in the case of quadratic cost functions (i.e., Gaussian likelihood and prior). It is shown that, with sufficient damping, the algorithm is guaranteed to converge, although the amount of damping grows with peak-to-average ratio of the squared singular values of the transforms $\mathbf{A}$. This result explains the good performance of AMP on i.i.d. Gaussian transforms $\mathbf{A}$, but also their difficulties with ill-conditioned or non-zero-mean transforms $\mathbf{A}$. A related sufficient condition is then derived for the local stability of the damped GAMP method under general cost functions, assuming certain strict convexity conditions.

I. INTRODUCTION

The paper studies AMP estimation under general linear transforms, where convergence remains insufficiently characterized. It introduces damped GAMP, analyzes its convergence in Gaussian settings and local stability under strict convexity, and relates it to primal-dual methods.

  • Motivation: AMP approximates MAP or MMSE estimation through Gaussian and quadratic approximations to loopy belief propagation.Max-sum AMP targets MAP estimates, while sum-product AMP targets MMSE estimates.
  • Motivation: Convergence of GAMP for generic transforms remains unresolved, and prior work showed that it can diverge for mildly ill-conditioned or non-zero-mean matrices.Earlier analyses characterized fixed points but did not establish convergence to them.
  • Contribution: The paper proposes damping as a GAMP modification intended to improve convergence for arbitrary matrices.The modification is related to damping techniques used in Gaussian belief propagation.
  • Contribution: For Gaussian likelihoods and priors, sufficient damping guarantees convergence, while the required damping increases with the peak-to-average ratio of squared singular values.This condition explains favorable behavior for large i.i.d. Gaussian matrices and greater damping needs for ill-conditioned, low-rank, or non-zero-mean matrices.
  • Contribution: For strictly convex cost functions, the paper derives a local convergence condition involving a row-column normalized version of the transform.Numerical experiments assess the tightness of the stated convergence conditions.
  • Algorithm: GAMP reduces vector-valued MAP and MMSE estimation to scalar estimation problems in Gaussian noise without vector-valued estimations or matrix inverses.Each iteration uses matrix-vector multiplications and componentwise scalar estimations.

B. Damped GAMP

The paper presents damped GAMP alongside related optimization methods and clarifies its relationship to PDHG. Damping relaxes GAMP updates, while fixed-step scalar GAMP is closely connected to primal-dual iterations.

  • Damped GAMP: Damping updates the variables s and x more slowly when θs and θx are below one.The undamped algorithm corresponds to θs = 1 = θx.
  • Damped GAMP: Scalar-stepsize GAMP avoids multiplications by S and ST, roughly halving the per-iteration complexity.It is equivalent to vector-stepsize GAMP under a different choice of S.
  • Relation to PDHG: PDHG performs proximal gradient ascent in the dual variable and proximal gradient descent in the primal variable.The corresponding stepsizes are νp and τr.
  • Relation to PDHG: With fixed stepsizes, non-damped scalar GAMP is equivalent to the Arrow-Hurwicz case of PDHG.The equivalence holds under θ = 0 in PDHG.
  • Relation to PDHG: Damped GAMP and relaxed PDHG differ because GAMP damps both primal and dual variables, whereas PDHG relaxes only the primal variable.PDHG uses the damped primal variable only in the dual update.

A. Gaussian GAMP

The Gaussian specialization makes GAMP updates linear and permits convergence analysis for arbitrary transforms. Its stepsizes converge to damping-independent fixed points, while convergence depends on the transform’s singular-value profile and damping.

  • Gaussian specialization: Gaussian GAMP uses linear scalar estimation functions under Gaussian priors and likelihoods, with identical max-sum and sum-product updates.The paper refers to this specialization as Gaussian GAMP, or GGAMP.
  • Stepsize convergence: GGAMP stepsizes converge to unique fixed points that are invariant to the damping constants θs and θx.This holds for both vector-stepsize and scalar-stepsize versions under the stated Gaussian conditions.
  • Convergence: κ(A) < κmax(θs, θx) is the necessary and sufficient scalar GGAMP convergence condition, where κ(A) is the peak-to-average ratio of squared singular values.The condition requires κmax to exceed the transform’s peak-to-average ratio.
  • Convergence: Sufficiently small damping constants can always make scalar-stepsize GGAMP converge.The convergence rate becomes slower as the peak-to-average ratio κ(A) increases.

C. Examples of Matrices

The examples show how matrix structure affects the damping required for scalar-stepsize GGAMP: large i.i.d. and subsampled unitary matrices need no damping, whereas narrowband and low-rank structures require more.

  • a) Large i.i.d. matrices: Large i.i.d. matrices allow scalar-stepsize GGAMP to converge without damping in the large-system limit.The analysis reproduces the state-evolution result, subject to a strict aspect-ratio condition; the square case lies on the convergence boundary.
  • b) Subsampled unitary matrices: Subsampled unitary matrices have κ(A) = 1 and therefore scalar GGAMP converges with or without damping.This follows because κ(A) remains below the allowable threshold for any damping constants in (0, 1].
  • d) Low-rank matrices: Low-rank matrices slow GGAMP by a factor of min{m, n}/r relative to a full-rank matrix.The required damping increases as the relative rank r/min{m, n} decreases.

V. LOCAL STABILITY FOR STRICTLY CONVEX FUNCTIONS

For general strictly convex functions, the paper establishes a local-stability condition for GAMP with fixed vector-valued stepsizes. The condition parallels the Gaussian case through a row-column normalized matrix, while global convergence remains unresolved outside the Gaussian setting.

  • V. LOCAL STABILITY FOR STRICTLY CONVEX FUNCTIONS: In max-sum mode, strictly convex twice-differentiable functions satisfy the derivative conditions used by the stability analysis.This connects the theorem's assumptions to the important case of minimizing strictly convex functions.
  • V. LOCAL STABILITY FOR STRICTLY CONVEX FUNCTIONS: Outside the Gaussian scenario, the paper establishes local stability rather than global convergence for general scalar estimation functions.The analysis assumes arbitrary but fixed stepsize vectors.
  • V. LOCAL STABILITY FOR STRICTLY CONVEX FUNCTIONS: A related open direction is whether max-sum GAMP converges for convex optimization problems characterized by scaled diagonal dominance.Convergence was established for max-sum BP in that class, but the corresponding GAMP result is left for future work.
  • V. LOCAL STABILITY FOR STRICTLY CONVEX FUNCTIONS: Theorem 3 gives a sufficient condition for local stability at any GAMP fixed point under twice-continuously-differentiable scalar estimation functions with bounded first derivatives.The condition applies with fixed vector or scalar stepsizes.
  • V. LOCAL STABILITY FOR STRICTLY CONVEX FUNCTIONS: For Gaussian GAMP, the same condition implies global stability rather than only local stability.This extends the stability interpretation of the condition in the quadratic Gaussian case.
  • V. LOCAL STABILITY FOR STRICTLY CONVEX FUNCTIONS: The sufficient condition for vector-stepsize GAMP resembles the scalar-stepsize condition, but measures peak-to-average behavior on a row-column normalized version of A.The normalized matrix has row and column norms less than one under the stated assumptions.

VI. NUMERICAL RESULTS

The numerical section tests the paper's global-convergence and local-stability theorems using controlled matrix constructions and repeated simulations. The experiments vary spectral conditioning through the peak-to-average ratio of squared singular values.

  • VI. NUMERICAL RESULTS: The simulations are divided between global convergence of damped GGAMP and local stability of damped GAMP.This mirrors the two principal theoretical results, Theorems 2 and 3.
  • VI. NUMERICAL RESULTS: The experiments construct A = UΣV^T from the SVD of an i.i.d. Gaussian matrix, choosing geometrically spaced singular values to target κ(A).Measurements use either an AWGN model or a sign-based model.

A. Global Convergence of Damped GGAMP

The simulations test global convergence of damped GGAMP and local stability of damped GAMP across transform conditions, likelihoods, and damping levels. Results support theorems linking convergence to spectral conditions, while highlighting practical limits in choosing damping constants.

  • Global convergence: 100 realizations per damping factor were used to measure GGAMP MSE after 5000 iterations from a fixed initialization.The experiment varied θs = θx from 0.7 to 1 in steps of 0.005.
  • Local stability: For local-stability tests, each dot represents the maximum excess MSE across 20 local runs relative to the fixed-point MSE.The tests used fixed points reached by vector-stepsize GAMP and varied θs = θx across multiple realizations.
  • Global convergence: κmax(θs, θx) > κ(A) is the necessary-and-sufficient convergence condition for scalar GGAMP.The condition requires κmax(θs, θx) to exceed the peak-to-average ratio of the squared singular values of A.
  • Scope and limitations: The analysis guarantees global convergence for Gaussian distributions and local convergence for strictly convex functions, using fixed stepsizes.The required damping depends on the peak-to-average ratio of squared singular values, while computing damping constants remains unresolved.

APPENDIX A PROOF OF THEOREM 1

The proof shows that the variance updates converge by composing two functions with suitable positivity, monotonicity, and scaling properties. Both vector and scalar variance sequences converge to unique fixed points.

  • Function composition: The variance updates are represented using functions Φs and Φx, with the composition Φ := Φx ◦ Φs governing the iteration.The proof establishes properties of these functions for non-negative matrix S and positive initial variance.
  • Function composition: The composition Φ remains positive and satisfies a sublinear scaling condition, Φ(ατx) < αΦ(τx) for α > 1.The proof also bounds Φ(τx) by the initial variance τ0 for non-negative τx.
  • Convergence: Theorem 2 in implies that the updates τx^t+1 converge to a unique fixed point.The argument applies the stated properties of the composed variance-update map.
  • Convergence: The analogous argument shows that νs^t also converges to a unique fixed point.Thus, both variance-update sequences have unique limiting fixed points.

APPENDIX B LINEAR SYSTEM STABILITY CONDITION

The appendix converts GAMP stability into an eigenvalue or matrix-invertibility test for an equivalent linear system. This yields global stability criteria for Gaussian estimation functions and a local criterion for general scalar functions.

  • Stability reduction: The proofs analyze GAMP through an equivalent linear system and relate stability to an eigenvalue test on a matrix G.The linear system is stable when the eigenvalues of G lie inside the unit circle.
  • Gaussian case: For Gaussian GAMP with fixed vector stepsizes, the algorithm reduces to a linear system whose diagonal matrices Dx and Ds have entries in (0, 1).The matrices Qx and Qs are diagonal, and their entries determine Dx and Ds.
  • General functions: For general differentiable scalar estimation functions, local stability is determined by linearizing the updates around a fixed point.The linearization has the same matrix form as the Gaussian stability system, with derivatives replacing Qs and Qx.
  • Invertibility criterion: The GAMP algorithm is locally stable around a fixed point if and only if Jλ is invertible for every |λ| ≥ 1.This criterion follows after reducing the eigenvalue condition using a Schur complement.
  • Gaussian case: For Gaussian estimation functions, the local-stability condition implies global stability for vector stepsizes, while scalar-step GGAMP has its own equivalent global criterion.The scalar-step result is stated for identical variances and Gaussian scalar estimation functions.

APPENDIX C PROOF OF THEOREM 2

The proof simplifies the scalar-step stability condition by reducing it to a singular-value-dependent polynomial criterion. It then evaluates the resulting minimization and recovers the theorem’s condition.

  • Stability reduction: The scalar-step system is stable if and only if the criterion associated with Jλ is satisfied for all |λ| ≥ 1.The proof starts from Lemma 2 and simplifies its invertibility condition.
  • Singular-value reduction: Non-invertibility of Jλ is equivalent to the existence of a singular value σ of A satisfying the derived eigenvalue relation.This follows by showing that a null vector of Jλ induces an eigenvector of A^HA.
  • Polynomial criterion: Stability is therefore equivalent to requiring stable roots of a second-order polynomial for every singular value of A.The Jury stability condition reduces root stability to positivity at λ = 1 and λ = −1.
  • Minimization: The proof rescales the fixed-point equations so that minimizing over νw becomes minimizing over the scaled variable u.The minimum is achieved as u approaches zero.
  • Minimization: Lemma 5 shows that the limiting value of this minimization equals the expression in (23), for both m ≥ n and m < n.The proof treats the two cases through β = m/n and completes the theorem after evaluating the limit.

APPENDIX D PROOF OF THEOREM 3

The proof establishes local stability by showing that the relevant matrix is invertible outside the unit disk. A convex-hull argument excludes zero from the associated set under the theorem’s condition.

  • Convex-hull argument: Lemma 6 shows that zero is excluded from the convex hull of the set P for the relevant complex λ values.The proof considers λ in polar coordinates and handles nonzero-angle and endpoint cases separately.
  • Convex-hull argument: For λ with |λ| ≥ 1 and angle in (0, π), the set P satisfies the required half-plane condition because r^2 > dsdx.The same argument excludes zero from conv(P).
  • Endpoint cases: The endpoint cases θ = 0 and θ = π place all elements of P on the positive or negative real axis, respectively.These sign properties also imply that zero is not in the convex hull.
  • Conclusion: Under the theorem’s condition, the matrix Jλ is invertible for every λ with |λ| ≥ 1, proving the stated stability result.The contradiction uses diagonal entries dxj and dsj in (0, 1) together with Lemma 6.
Loading 1402.3210v3…