PaperlayerView exact revision on arXiv

Source-linked AI summary

Orthogonal AMP

Junjie Ma, Li Ping

arXiv:1602.06509v3cs.IT

TL;DR

AMP’s state evolution is reliable for IID Gaussian matrices but can fail for other, especially ill-conditioned, ensembles. The paper introduces OAMP with de-correlated linear estimation and divergence-free nonlinear estimation, and reports accurate state evolution for broader unitarily-invariant matrices. Optimized OAMP has a fixed point consistent with replica-method optimal performance and can outperform AMP on ill-conditioned matrices.

  • Problem

    AMP state evolution depends crucially on IID matrix entries and may become unreliable, limiting AMP for general and ill-conditioned matrix ensembles.

  • Method

    OAMP combines de-correlated linear estimation with divergence-free nonlinear estimation and derives a corresponding state-evolution procedure.

  • Results

    OAMP state evolution is reported as accurate for general unitarily-invariant matrices, while optimized OAMP’s fixed point potentially coincides with Bayes-optimal replica-method performance.

  • Takeaways & Limitations

    OAMP may support a wider range of applications than AMP, especially those involving ill-conditioned and partial orthogonal transform matrices.

  • Takeaways & Limitations

    The state-evolution analysis uses sufficient independence assumptions that are not rigorously established, and optimal OAMP choices require knowledge of the signal distribution.

Abstract

from arXiv · show

Approximate message passing (AMP) is a low-cost iterative signal recovery algorithm for linear system models. When the system transform matrix has independent identically distributed (IID) Gaussian entries, the performance of AMP can be asymptotically characterized by a simple scalar recursion called state evolution (SE). However, SE may become unreliable for other matrix ensembles, especially for ill-conditioned ones. This imposes limits on the applications of AMP. In this paper, we propose an orthogonal AMP (OAMP) algorithm based on de-correlated linear estimation (LE) and divergence-free non-linear estimation (NLE). The Onsager term in standard AMP vanishes as a result of the divergence-free constraint on NLE. We develop an SE procedure for OAMP and show numerically that the SE for OAMP is accurate for general unitarily-invariant matrices, including IID Gaussian matrices and partial orthogonal matrices. We further derive optimized options for OAMP and show that the corresponding SE fixed point coincides with the optimal performance obtained via the replica method. Our numerical results demonstrate that OAMP can be advantageous over AMP, especially for ill-conditioned matrices

I. INTRODUCTION

AMP provides a computationally tractable iterative alternative for large linear-system recovery, with state evolution accurately characterizing its behavior for IID Gaussian matrices. This paper proposes OAMP to extend reliable state-evolution analysis and AMP-style recovery to broader matrix ensembles.

  • AMP background: AMP alternates linear estimation and symbol-by-symbol nonlinear estimation, using an Onsager term to regulate correlation during iterative processing.The algorithm is computationally tractable compared with optimal MMSE recovery in general settings.
  • AMP background: For IID Gaussian matrices, AMP dynamics are characterized by a simple scalar state-evolution recursion whose fixed point coincides with large-system MMSE performance.State evolution applies without requiring sparsity in the matrix.
  • Limitations of AMP: When matrices are non-IID, especially ill-conditioned, AMP state evolution may become inaccurate and AMP may perform poorly.A partial DCT example shows unreliable state-evolution predictions, despite the matrix’s use in compressed sensing.
  • OAMP contributions: OAMP combines de-correlated linear estimation with divergence-free nonlinear estimation, allowing linear-estimation structures such as pseudo-inverse and linear MMSE estimators.The divergence-free constraint removes the need for the standard AMP Onsager term.
  • OAMP contributions: The paper derives an OAMP state-evolution procedure and reports reliable predictions across IID Gaussian, partial orthogonal, and some ill-conditioned matrix ensembles.The procedure is derived under an independence condition, while the proposed structures make errors statistically orthogonal and partially satisfy that requirement.
  • OAMP contributions: Optimized OAMP choices yield a state-evolution fixed point consistent with replica-method optimal MMSE performance, with better MSE and faster convergence than AMP for ill-conditioned matrices.The paper also reports OAMP results for non-sparse BPSK and conventional sparse signals.

C. Limitation of AMP

AMP's state evolution relies on IID matrix entries and can become inaccurate for other ensembles, including partial DCT matrices. The paper uses this limitation to motivate OAMP.

  • C. Limitation of AMP: The IID-entry assumption is crucial to AMP's state evolution theorem.The theorem's applicability depends on AMP's matrix ensemble assumptions.
  • C. Limitation of AMP: The AMP NLE example is not strictly component-wise, though the theorem can make it approximately component-wise asymptotically.The approximation follows when the normalized derivative sum converges to a constant independent of each individual input.
  • C. Limitation of AMP: SE is accurate across the tested β range for IID Gaussian matrices, with E < 10^-2.The result is consistent with the AMP state evolution theorem.
  • C. Limitation of AMP: SE is not reliable for AMP with a partial DCT matrix.The partial DCT matrix is formed by uniformly selecting rows of a DCT matrix.
  • C. Limitation of AMP: Replacing the IID-Gaussian eigenvalue distribution with the partial-DCT distribution still leaves large prediction error for β > 0.The discrepancy arises because the Onsager term was ignored; error is very small at β = 0, where that term vanishes.

A. De-correlated Linear Estimator

OAMP uses a de-correlated linear estimator within a linear estimation/nonlinear estimation pipeline. Its estimator is defined by a trace constraint and supports several linear-estimation choices.

  • A. De-correlated Linear Estimator: The linear estimator W operates on an estimate s of x in y = Ax + n.The matrix A can be a channel or sensing matrix.
  • A. De-correlated Linear Estimator: A is unitarily-invariant when its SVD factors U, V, and Σ are mutually independent, with U and V Haar-distributed.This definition describes the matrix class used in the OAMP analysis.
  • A. De-correlated Linear Estimator: A de-correlated LE satisfies tr(I − WA) = 0.Given any W-hat satisfying the base structure, the paper constructs W to meet this constraint.
  • A. De-correlated Linear Estimator: OAMP permits de-correlated LE choices beyond AMP's A^T, including pseudo-inverse and linear MMSE estimators.The paper states that these additional choices may improve efficiency.
  • A. De-correlated Linear Estimator: The divergence-free NLE constraint makes the Onsager term vanish, while a separate final estimator need not be divergence-free.The iterative NLE and final output estimator therefore have different roles.

E. Rationales for OAMP

OAMP's state evolution is motivated by replacing difficult independence requirements with orthogonality induced by de-correlated LE and divergence-free NLE structures. The resulting justification is intuitive and only partially establishes the needed conditions.

  • E. Rationales for OAMP: OAMP state evolution requires two sufficient conditions: Gaussian errors independent of x, and IID errors independent of A and n.These are stated as Assumptions 1 and 2.
  • E. Rationales for OAMP: The paper cannot prove that the two assumptions imply each other throughout the iterative process.The initial condition q0 = −x satisfies Assumption 2 at t = −1.
  • E. Rationales for OAMP: Orthogonality only partially addresses the independence requirement, so the paper presents these arguments as intuition rather than rigorous proof.Numerical results are used to assess state evolution reliability.
  • E. Rationales for OAMP: For unitarily-invariant A, a de-correlated LE makes linear-estimation errors mutually uncorrelated and uncorrelated with x under Assumption 2.This is the content of Proposition 1.
  • E. Rationales for OAMP: A divergence-free NLE makes its input and output errors orthogonal, supporting orthogonality between q_t+1 and h_t.Stein's lemma is used to establish the orthogonality property.

H. Brief Summary

The paper summarizes OAMP as an orthogonality-based framework with empirically reliable state evolution and optimized estimator choices. Its optimization analysis connects the state-evolution fixed point to replica-method MMSE performance.

  • H. Brief Summary: OAMP state evolution is reported as reliable in extensive numerical experiments, although the supporting orthogonality propositions depend on assumptions.The propositions do not ensure orthogonality for the overall process.
  • H. Brief Summary: The framework uses de-correlated LE and divergence-free NLE structures to support orthogonality between iterative error terms.The paper describes this as the rationale for OAMP.
  • H. Brief Summary: OAMP parameters can be optimized through SE, including choices of W_t and η_t.The paper also develops empirical estimators for the variance parameters used in these choices.
  • H. Brief Summary: The SE expressions specialize to closed-form asymptotic formulas for IID Gaussian matrices with MF, PINV, and LMMSE estimators.These formulas are obtained for specific estimator and matrix-ensemble combinations.
  • H. Brief Summary: The optimized OAMP fixed-point characterization is consistent with optimal MMSE performance obtained by the replica method.The paper presents this consistency as evidence of potential optimality.

B. Optimal Structure of OAMP

The paper derives optimal linear and nonlinear estimator structures within OAMP's state-evolution framework, then establishes how these choices minimize the final MSE. Computing the optimal nonlinear estimator requires knowledge of the signal distribution.

  • The optimal estimator derivation is complicated by the de-correlated constraint on the linear estimator and the divergence-free constraint on the nonlinear estimator.
  • The optimized state-evolution functions are monotonic, including the functions governing linear estimation, nonlinear estimation, and output estimation.
  • The optimization replaces the functions governing successive state-evolution stages by their local minima, reducing the final MSE.
  • Theorem 2 states that the final state-evolution MSE is minimized by the optimal linear and nonlinear estimators specified in Lemma 1.
  • The optimal nonlinear estimator depends on the signal distribution, so expectation-maximization or parametric SURE methods may be used when that prior information is unavailable.

C. Potential Optimality of OAMP

The paper connects optimized OAMP state evolution to replica-method MMSE performance and evaluates OAMP across IID Gaussian and ill-conditioned unitarily-invariant matrices. OAMP's prediction remains accurate for the tested general matrices, while estimator choice strongly affects performance.

  • C. Potential Optimality of OAMP: The optimal OAMP state variables form monotonically decreasing sequences, including the sequence of effective noise variances.
  • C. Potential Optimality of OAMP: The optimized OAMP state-evolution fixed point is consistent with the replica-method characterization of MMSE for unitarily-invariant matrices.This consistency implies that OAMP can potentially achieve optimal MSE performance despite its estimator constraints.
  • A. IID Gaussian Matrix: For IID Gaussian matrices, OAMP-PINV has stronger interference cancellation than OAMP-MF but is less robust to noise.The high-SNR Fig. 2 observation is consistent with OAMP-PINV outperforming OAMP-MF.
  • A. IID Gaussian Matrix: Good agreement is observed between simulated and predicted MSEs for all curves in the IID Gaussian experiment.AMP reaches the same convergent value as OAMP-LMMSE, while OAMP-LMMSE converges faster.
  • B. General Unitarily-invariant Matrix: For ill-conditioned matrices, AMP and OAMP-MF deteriorate, while OAMP-PINV and OAMP-LMMSE significantly outperform OAMP-MF.The AMP state-evolution prediction is noticeably different from its simulation result in this setting.
  • B. General Unitarily-invariant Matrix: OAMP state evolution accurately predicts simulations for all tested linear-estimation structures, including structures beyond MF, PINV, and LMMSE.
  • B. General Unitarily-invariant Matrix: For highly ill-conditioned scenarios, OAMP-LMMSE performs significantly better than AMP, AMP-damping, and ADMM-GAMP.ADMM-GAMP slightly outperforms OAMP-LMMSE for κ ≤100 in the reported example, while OAMP-PINV performs worse than AMP when κ ≥10.

C. Partial Orthogonal Matrix

For partial orthogonal matrices, OAMP has AMP-equivalent complexity while retaining accurate state-evolution predictions and stronger recovery performance in the reported experiments.

  • Partial orthogonal matrices: Partial orthogonal matrices make OAMP-MF, OAMP-PINV, and OAMP-LMMSE identical, with complexity equal to AMP.The constraint is AAT = N/M · I, eliminating the inversion operation for the LMMSE option.
  • Recovery performance: OAMP considerably outperforms AMP on empirical phase-transition curves for Bernoulli-Gaussian recovery with a partial DCT matrix.This remains slightly true for OAMP when AMP is increased from 50 to 500 iterations at relatively high sparsity levels.
  • State-evolution accuracy: Simulated MSEs agree well with state-evolution predictions for partial Haar, partial DCT, and partial Hadamard matrices when N is sufficiently large.The reported partial-orthogonal experiment uses N = 8192 and averages simulated MSEs over 2000 realizations.
  • State-evolution accuracy: With soft-thresholding on a partial DCT matrix, simulations and state-evolution predictions agree well for all tested values of Ct.For Ct = 3, state evolution predicts OAMP behavior even when iterative processing leads to worse MSE per iteration.
  • Scope: OAMP is intended for matrix ensembles beyond IID Gaussian matrices, especially ill-conditioned and partial orthogonal transforms.The conclusion reports relaxed requirements on eigenvalue distributions and linear-estimator structure compared with AMP.

APPENDIX A PROOF OF PROPOSITION 1

The proof establishes that de-correlation suppresses signal–error correlation and yields orthogonality properties needed by the OAMP state-evolution analysis.

  • LMMSE structure: The proof derives the singular-value-based form of the LMMSE estimator from the matrix decomposition and the chosen normalization constant.The eigenvalue and singular-value relations connect the linear-estimator design to the spectrum of A.
  • Error properties: Under the stated independence assumption, the entries of ht are uncorrelated and have identical variances.These properties support the scalar error description used in the subsequent state-evolution construction.
  • Decorrelated linear estimation: The proof reduces signal–error decorrelation to showing that x is uncorrelated with Btqt, because Wtn is independent of x.A de-correlated Wt satisfies tr(Bt) = 0, which implies E{Bt} = 0 under the Haar-distributed matrix relations.
  • Estimator optimality: The appendix identifies Lemma 3 as the key step in proving optimality for the divergence-free nonlinear estimator.The argument uses the divergence-free property and orthogonality of MMSE estimation to handle cross terms.

APPENDIX C PROOF OF LEMMA 2

The proof of Lemma 2 establishes monotonicity properties of the functions used in the OAMP fixed-point analysis through Jensen’s inequality.

  • Monotonicity of Φ⋆: Monotonicity of Φ⋆ is established by reducing the required inequality to one implied by Jensen’s inequality.The proof first rewrites the target relation and then applies Jensen’s inequality to obtain the result.
  • Monotonicity of Ψ⋆: Monotonicity of Ψ⋆ is proved similarly, again using Jensen’s inequality after invoking the stated proposition.The argument follows the same inequality-based structure as the proof for Φ⋆.

APPENDIX D PROOF OF THEOREM 3

The proof of Theorem 3 connects the OAMP state-evolution recursion to a fixed-point equation through monotonicity and transform identities.

  • Monotonicity: The sequence {v_t^2} decreases monotonically, and the sequence {τ_t^2} inherits monotonicity from it.The induction uses monotonicity of Φ⋆ and Ψ⋆ together with the state-evolution relationship.
  • Transform representation: The state-evolution equations are rewritten using the η-transform and its relationship to the R-transform of A^TA.The expectation is taken with respect to the asymptotic eigenvalue distribution of A^TA.
  • Fixed point: At the stationary point, substitution into the transformed recursion yields the desired fixed-point equation.The fixed point follows after combining the stationary-point condition with the rewritten state-evolution equations.
Loading 1602.06509v3…