PaperlayerView exact revision on arXiv

Source-linked AI summary

A GAMP Based Low Complexity Sparse Bayesian Learning Algorithm

Maher Al-Shoukairi, Philip Schniter, Bhaskar D. Rao

arXiv:1703.03044v2cs.LGstat.ML

TL;DR

Sparse signal recovery needs algorithms that remain robust for arbitrary measurement matrices without the high cost of classical SBL or the convergence problems of AMP methods. The paper replaces SBL’s matrix-inversion E-step with damped GGAMP, extends it to temporally correlated MMV signals, and reports robustness and computational advantages for the resulting algorithms.

  • Problem

    Sparse signal recovery requires methods that address GAMP’s convergence and robustness problems for generic A while avoiding the high complexity of traditional SBL.

  • Method

    The paper uses damped GGAMP to implement the E-step of EM-based SBL and extends the approach to temporally correlated MMV recovery as GGAMP-TSBL.

  • Results

    GGAMP-SBL matched original SBL’s NMSE for tested deviations from i.i.d.-Gaussian A, while GGAMP-TSBL matched TMSBL in the reported generic-matrix experiment.

  • Takeaways & Limitations

    The proposed algorithms combine SBL’s robustness to generic A with the lower complexity of message-passing methods for SMV and MMV sparse recovery.

Abstract

from arXiv · show

In this paper, we present an algorithm for the sparse signal recovery problem that incorporates damped Gaussian generalized approximate message passing (GGAMP) into Expectation-Maximization (EM)-based sparse Bayesian learning (SBL). In particular, GGAMP is used to implement the E-step in SBL in place of matrix inversion, leveraging the fact that GGAMP is guaranteed to converge with appropriate damping. The resulting GGAMP-SBL algorithm is much more robust to arbitrary measurement matrix $\boldsymbol{A}$ than the standard damped GAMP algorithm while being much lower complexity than the standard SBL algorithm. We then extend the approach from the single measurement vector (SMV) case to the temporally correlated multiple measurement vector (MMV) case, leading to the GGAMP-TSBL algorithm. We verify the robustness and computational advantages of the proposed algorithms through numerical experiments.

I. INTRODUCTION

The paper develops low-complexity Bayesian algorithms for sparse signal recovery that combine GAMP with SBL to address convergence, robustness, and computational challenges, including temporally correlated MMV recovery.

  • A. Sparse Signal Recovery: Sparse signal recovery estimates a sparse x from M ≤ N noisy linear measurements using a known measurement matrix A.The paper considers both single measurement vector and multiple measurement vector settings.
  • B. Generalized Approximate Message Passing Algorithm: GAMP uses quadratic and Taylor-series approximations to produce low-complexity Bayesian MAP or MMSE estimation algorithms.Its robustness can degrade for generic measurement matrices, including divergence or suboptimal fixed points.
  • B. Generalized Approximate Message Passing Algorithm: Damping can guarantee convergence for Gaussian GAMP when the relevant singular-value condition is not met, at the expense of slower convergence.This addresses a convergence limitation but does not by itself solve the sparse-signal recovery problem for general priors.
  • D. Paper’s Contribution 1: The proposed GGAMP-SBL algorithm replaces SBL’s matrix-inversion E-step with GAMP while retaining the GSM-based SBL framework.The Gaussian prior induced by the GSM representation enables convergence guarantees for the damped GAMP E-step with non-i.i.d.-Gaussian A.
  • D. Paper’s Contribution 1: The paper extends the approach to temporally correlated MMV signals, producing GGAMP-TSBL with linear complexity in all problem dimensions and greater robustness to generic A.The MMV formulation assumes shared support and models nonzero rows as correlated time series.

B. SBL’s EM Algorithm

EM-SBL alternates an expectation step that evaluates the posterior under the current hyperparameters with a maximization step that updates the model parameters. For the GSM prior and Gaussian noise model, this procedure yields the SBL objective and uses posterior mean and diagonal covariance quantities in the M-step.

  • EM-SBL updates: EM-SBL learns the signal variance vector γ iteratively and can also learn the noise variance σ^2, although this paper focuses on known σ^2.The hyperparameter update is based on the posterior under the previous estimate.
  • EM-SBL objective: The EM objective is to maximize p(γ|y), equivalently minimize −log p(y,γ), producing the SBL cost function for the GSM prior and additive white Gaussian noise.Bayes’ rule makes p(y) constant with respect to γ.
  • EM-SBL updates: Each EM iteration computes an expectation using p(x|y;γ_i) and then performs a maximization step.The EM algorithm increases a lower bound on log p(γ|y) at each iteration and converges to a stationary point under broad conditions.
  • E-step quantities: The Gaussian likelihood follows from additive Gaussian noise, while the GSM prior makes x conditioned on γ Gaussian.Together they make the density required for the E-step Gaussian.
  • E-step quantities: The E-step supplies the posterior mean x̂ and diagonal covariance vector τ_x, which are then used in the M-step.The mean is used as the SBL point estimate, and both quantities vary across iterations.

SBL’s M-Step:

The SBL M-step is computationally simple because it separates into scalar updates, while the E-step requires costly posterior-statistics computation. Estimates from the noise-variance update can nevertheless be highly inaccurate.

  • Posterior statistics: The E-step needs only marginal posterior means ˆx_n and variances τ_xn, not the full joint posterior.This requirement enables message-passing implementations.
  • Computational bottleneck: The E-step requires posterior means and variances obtained through matrix inversion, with complexity O(NM^2) when M ≤ N.The matrix inversion lemma can reduce the inversion dimension from N × N to M × M, but the resulting computation remains prohibitive at large dimensions.
  • M-step structure: The M-step drops terms independent of γ and reduces to N scalar optimization problems.The hyperprior rarely changes overall complexity because the E-step dominates computation.
  • Parameter updates: If σ^2 is unknown, it can be estimated during the M-step alongside the hyperparameters.The supplied update description places the noise-variance estimate after the γ update.
  • Caveat: Estimates obtained by equation (13) can be highly inaccurate, motivating experimentation with σ^2 values or application-based heuristics.This is an author-stated limitation of the noise-variance estimation procedure.

III. DAMPED GAUSSIAN GAMP SBL

Damped GGAMP replaces the matrix-inversion-based E-step of EM-SBL while leaving the M-step unchanged. The resulting algorithm has per-iteration complexity O(NM), and its runtime advantage is expected and experimentally confirmed for medium-to-large problems.

  • Algorithm: Damped GGAMP approximates the E-step quantities ˆx and τ_x, while the SBL M-step remains unchanged.The method uses quadratic approximations and Taylor expansions on the GAMP factor graph.
  • Damping: Damping factors θ_s and θ_x ∈ (0, 1] slow updates to improve convergence for non-i.i.d.-Gaussian measurement matrices.Setting θ_s = θ_x = 1 removes damping and recovers original GAMP.
  • E-step implementation: The E-step requires only scalar marginal estimates, allowing GGAMP to avoid the full posterior computation needed by matrix-inversion-based SBL.The sum-product and max-sum forms yield the same updates for the Gaussian prior and likelihood considered.
  • Complexity: O(NM) operations are required per GAMP iteration, compared with O(NM^2) for a standard SBL iteration.The GGAMP-SBL cost is dominated by multiplications involving A, A⊤, S, and S⊤.
  • Runtime: GGAMP-SBL runtime is expected to be lower than SBL for medium-to-large problems, even with heavier damping.The advantage depends on the total number of inner GAMP and outer EM iterations not becoming too large.

B. GGAMP-SBL Convergence

The convergence analysis separates convergence of the damped GGAMP E-step from convergence of the overall EM procedure. Sufficient damping guarantees GGAMP convergence for generic matrices, while experiments indicate that its approximate variance estimates still decrease the SBL cost function.

  • Convergence guarantee: Damped GGAMP is globally convergent for generic A when sufficient damping is used.The analysis treats E-step convergence first and then assesses convergence of the full EM algorithm.
  • Variance updates: With fixed γ_i and an initial estimate τ_x ≥ γ_i, the variance updates converge to a unique fixed point.The stated stability condition is θ_sθ_x||Ã||^2 < 1 for the relevant fixed-point quantities.
  • Practical damping: The authors recommend fixing sufficiently small damping factors instead of constructing à and computing its spectral norm at every EM iteration.This recommendation is presented as a practical alternative to checking the formal condition directly.
  • Empirical condition: A threshold Ω(θ_s, θ_x) 10% larger than the stated bound was sufficient for convergence in the considered scenarios.This is an empirical finding rather than a general guarantee.

2) GGAMP-SBL Convergence:

GGAMP-SBL’s E-step converges to mean and variance estimates, but approximate variances leave overall EM convergence unproven. Numerical experiments nevertheless show cost reduction and behavior often matching EM-SBL.

  • Convergence guarantees: GGAMP convergence guarantees apply to the E-step, not necessarily to the overall EM algorithm or its desired SBL fixed points.Overall convergence depends on the quality of the mean and variance estimates produced by GGAMP.
  • Convergence guarantees: For arbitrary A, GGAMP’s fixed-point mean equals the true mean, while its variance matches the true posterior variance only for large i.i.d.-Gaussian A and otherwise remains approximate.The variance estimate is the diagonal of the posterior covariance in the matched case.
  • Approximation and descent: The GGAMP variance approximation differs from original EM-SBL, and the authors cannot rigorously prove that it guarantees descent of the original cost function.The generalized EM framework permits an M-step that decreases rather than fully minimizes the objective.
  • Numerical evidence: Numerical experiments suggest negligible effects on convergence and sparse recovery, with approximate variances sufficient to decrease SBL’s cost function.The experiments use Bernoulli-Gaussian signals with λ = 0.2, N = 1000, and M = 500.
  • Numerical evidence: GGAMP-SBL’s cost decreases at every iteration and eventually reaches the same minimum as original EM-SBL.The experiments support effectiveness of partial cost reduction but do not guarantee overall algorithm convergence.

B. GGAMP-TSBL Message Phases and Scheduling (E-Step)

GGAMP-TSBL extends the SMV message-passing building block to temporally correlated MMV signals through within-frame, forward-time, and backward-time updates. Its E-step schedules these phases across all time frames, with complexity dominated by matrix multiplications.

  • Message phases: The MMV extension divides message updates into within-frame, forward-time, and backward-time phases based on the corresponding factor graph.The SMV algorithm serves as the building block for the MMV procedure.
  • Within-frame phase: Within-frame updates resemble SMV GAMP, but each x(t) connects to multiple time-indexed factor nodes rather than one.This changes the output-function calculation and the mean and variance estimates for the stacked signal.
  • Scheduling: The E-step first moves forward in time, then performs within-frame updates, and finally passes messages backward in time.The resulting schedule is summarized in the GGAMP-TSBL E-step algorithm.
  • Complexity: GGAMP-TSBL removes matrix averaging and adds SMV-style damping, with computational cost dominated by A, A⊤, S, and S⊤ multiplications.The cited complexity statement gives O(MN) flops per iteration per frame before the total GAMP iteration factor.

C. GGAMP-TSBL M-Step

After E-step convergence, GGAMP-TSBL updates the hyperparameters by maximizing the expected complete-data log likelihood, using the same γ-learning rule as the related TSBL derivation.

  • Hyperparameter learning: After the E-step converges, the M-step learns γ by maximizing the expected complete-data log likelihood conditioned on the observed measurements.The hidden variable is x, and σ2 and β are included among the model parameters.
  • Hyperparameter learning: The γ update follows the SMV derivation and uses the same learning rule as TSBL under the shared AR(1) temporal model.The algorithms differ in their E-step implementations.
  • Additional parameters: When β or σ2 are unknown, the EM algorithm can estimate those parameters as well.

V. NUMERICAL RESULTS

The numerical study evaluates recovery robustness and computational complexity across several non-i.i.d.-Gaussian measurement matrices. It uses NMSE or TNMSE for recovery and runtime for complexity, comparing the proposed methods with established baselines.

  • Evaluation metrics: Recovery performance is measured by NMSE for SMV and time-averaged NMSE for MMV.The study uses these metrics to assess recovery of the sparse signal or signal sequence.
  • Evaluation metrics: Complexity is measured by the runtime required to compute the final estimate, with relative runtimes used as the computational comparison.Absolute runtimes may vary across machines, but their relationships estimate relative complexity.
  • Measurement matrices: The experiments test robustness using non-i.i.d.-Gaussian matrices, including column-correlated, low-rank product, and ill-conditioned matrices.These matrix families vary in deviation from the zero-mean i.i.d.-Gaussian case.
  • Measurement matrices: Non-zero mean matrices vary the mean μ as a deviation measure, and mean removal is included because damping does not enhance convergence in this setting.The experiments assume the noise variance rather than estimating it with the provided EM procedure.
  • Baselines and setup: The SMV comparison includes original SBL, SwAMP, and MADGAMP, with a genie-based achievable-NMSE lower bound as a benchmark.SMV signals contain exactly K randomly located nonzeros with independent zero-mean unit-variance Gaussian amplitudes under AWGN.

1) Robustness to generic matrices at high SNR:

At high SNR, GGAMP-SBL matched original SBL across strongly deviating measurement matrices while reducing complexity, including as problem dimensions increased. At lower SNR, it retained near-SBL performance and surpassed competing AMP methods as matrix deviation increased.

  • High-SNR robustness: GGAMP-SBL matched original SBL even for measurement matrices with the greatest deviation from the i.i.d.-Gaussian case.Both nearly achieved the bound except for low-rank matrices with rank ratio below 0.45.
  • High-SNR complexity: GGAMP-SBL reduced complexity and runtime relative to original SBL, even when heavier damping slowed its updates.The runtime advantage is reported for the high-SNR SMV experiment.
  • Lower-SNR robustness: At 30dB SNR, GGAMP-SBL generally matched SBL with slight degradation and surpassed MADGAMP and SwAMP as matrix deviation increased.The same lower-SNR experiment also found continued complexity reduction relative to original SBL.
  • Scaling with problem dimensions: For column-correlated matrices with ρ = 0.9, GGAMP-SBL and SBL had almost identical NMSE, while their runtime difference grew with problem dimensions.The experiment fixed M/N = 0.5, K/N = 0.2, and SNR = 60dB.
  • Undersampling: When A was column correlated, SBL and GGAMP-SBL outperformed the other algorithms in NMSE as undersampling varied.The comparison used NMSE versus M/N for i.i.d.-Gaussian and column-correlated matrices.

B. MMV GGAMP-TSBL Numerical Results

GGAMP-TSBL extends the proposed approach to temporally correlated MMV recovery with generic measurement matrices. It matched TMSBL across high- and lower-SNR experiments while offering lower complexity and improved scaling relevance.

  • Experimental scope: The proposed MMV algorithm was evaluated against TMSBL because the compared AMP MMV implementation lacked damping and diverged for the generic matrices used.The comparison was therefore restricted to TMSBL.
  • High-SNR MMV robustness: GGAMP-TSBL matched TMSBL and achieved the SKS bound across the tested generic matrices at 60dB SNR.The experiment used N = 1000, M = 500, λ = 0.2, and temporal correlation β = 0.9.
  • High-SNR MMV complexity: GGAMP-TSBL reduced complexity relative to TMSBL at 60dB SNR, although the reduction was modest for the selected problem size.The study reports that the reduction becomes more significant for larger problems or lower SNR.
  • Lower-SNR MMV robustness: At 30dB SNR, GGAMP-TSBL matched TMSBL and almost achieved the bound in most cases while retaining lower complexity.Performance and complexity were evaluated using the same data points as in the 60dB experiment.
  • Overall conclusion: The paper concludes that both proposed algorithms are more robust to generic matrices and substantially less complex than their SBL and TMSBL counterparts.This conclusion covers the SMV and MMV numerical studies, including cases with sufficient damping.

APPENDIX A DERIVATION OF GGAMP-TSBL UPDATES

The GGAMP-TSBL appendix derives its within-step updates by reducing each temporally coupled factor graph to an SMV-equivalent graph with a modified prior, then applying Gaussian message operations.

  • Message combination: The derivation combines the two messages entering each within-step factor into a single message.This makes the within-step factor graph exactly the same as the SMV factor graph.
  • SMV reduction: Combining the messages produces an SMV-equivalent factor graph for each time frame with a modified prior on x^(t)_n.The modified prior is the basis for applying the damped GAMP updates.
  • GAMP application: The appendix applies damped GAMP using the modified prior for each time frame.This transfers the SMV GAMP procedure into the temporally correlated MMV derivation.
  • η updates: Gaussian probability-density multiplication and convolution yield the η^(t)_n updates in Table II equations (E3) and (E4).These updates follow directly from the Gaussian message operations.
  • θ updates: The same Gaussian multiplication and convolution rules yield the θ^(t)_n updates in Table II equations (E13) and (E14).These complete the corresponding update derivation for the temporal model.
Loading 1703.03044v2…