PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient High-Dimensional Inference in the Multiple Measurement Vector Problem

Justin Ziniel, Philip Schniter

arXiv:1111.5272v3cs.IT

TL;DR

The paper addresses limitations in MMV algorithms that do not account for temporal amplitude correlations. It proposes AMP-MMV, an efficient Bayesian message-passing method whose reported performance approaches an oracle bound and offers a strong performance-complexity tradeoff.

  • Problem

    Many MMV algorithms cannot account for amplitude correlations in the non-zero signal coefficients.

  • Method

    AMP-MMV extends approximate message passing to amplitude-correlated MMV, exploits temporal amplitude correlation, learns signal and noise statistics, and has complexity linear in the problem dimensions.

  • Results

    AMP-MMV performs near the oracle performance bound across a wide range of settings and nearly matches SKS despite crude hyperparameter initialization.

  • Takeaways & Limitations

    AMP-MMV offers an unrivaled performance-complexity tradeoff and is particularly suited to high-dimensional MMV problems.

Abstract

from arXiv · show

In this work, a Bayesian approximate message passing algorithm is proposed for solving the multiple measurement vector (MMV) problem in compressive sensing, in which a collection of sparse signal vectors that share a common support are recovered from undersampled noisy measurements. The algorithm, AMP-MMV, is capable of exploiting temporal correlations in the amplitudes of non-zero coefficients, and provides soft estimates of the signal vectors as well as the underlying support. Central to the proposed approach is an extension of recently developed approximate message passing techniques to the amplitude-correlated MMV setting. Aided by these techniques, AMP-MMV offers a computational complexity that is linear in all problem dimensions. In order to allow for automatic parameter tuning, an expectation-maximization algorithm that complements AMP-MMV is described. Finally, a detailed numerical study demonstrates the power of the proposed approach and its particular suitability for application to high-dimensional problems.

I. INTRODUCTION

The paper develops AMP-MMV for jointly sparse MMV recovery, targeting temporal amplitude correlations and high-dimensional efficiency. It combines Bayesian recovery with learned statistics, linear complexity, and strong performance near an oracle benchmark.

  • I. INTRODUCTION: Separately solving MMV instances as independent SMV problems ignores temporal structure that can improve recovery performance.
  • I. INTRODUCTION: Joint sparsity allows recovery-failure probability to decay exponentially as the number of timesteps T grows under mild conditions.
  • I. INTRODUCTION: AMP-MMV exploits temporal amplitude correlations while preserving Bayesian recovery performance and linear complexity in all problem dimensions.The algorithm learns signal and noise statistics directly from data and is designed for high-dimensional problems.
  • I. INTRODUCTION: AMP-MMV extends AMP to amplitude-correlated MMV models and supports soft signal and support estimates with automatic parameter learning.The approach combines turbo AMP with EM-based hyperparameter learning.
  • I. INTRODUCTION: Numerically, AMP-MMV performs near the oracle support-aware Kalman smoother across a wide range of settings and suits high-dimensional problems.The study compares AMP-MMV with three state-of-the-art MMV algorithms and uses the smoother as an absolute performance benchmark.
  • I. INTRODUCTION: Time-varying measurement operators can significantly improve reconstruction performance, motivating their use whenever possible.The algorithm accommodates time-varying measurement matrices, implicit operators, and complex-valued quantities.

A. Notation

The signal model separates sparse support from temporally correlated amplitudes and uses a linear noisy measurement model for complex-valued signals.

  • A. Notation: The notation distinguishes timesteps, coefficients, measurements, vector and matrix quantities, diagonal operators, and complex normal distributions.Superscripts in parentheses denote timesteps, whereas unparenthesized superscripts can index algorithmic iterations.
  • A. Notation: Each signal vector is observed through a linear operator with additive circularly symmetric complex white Gaussian noise.The model uses x^(t) ∈ C^N, y^(t) ∈ C^M, and A ∈ C^(M×N).
  • A. Notation: Signal coefficients are decomposed into binary support variables and amplitude variables, x^(t)_n = s_nθ^(t)_n.The support indicator is time-invariant, while amplitudes evolve over time.
  • A. Notation: Sparsity is modeled with Bernoulli support indicators having activation probabilities λ_n < 1, yielding a spike-and-slab prior.The prior includes a point mass at zero and a Gaussian component for active coefficients.

III. THE SUPPORT-AWARE KALMAN SMOOTHER

The support-aware Kalman smoother is an oracle-aided MMSE estimator that uses known support to infer temporally evolving amplitudes from noisy linear measurements.

  • III. THE SUPPORT-AWARE KALMAN SMOOTHER: Given the true support, the support-aware Kalman smoother provides the appropriate oracle-aided MMSE estimator for the amplitude states.It concentrates estimation on the amplitudes associated with the known active support.
  • III. THE SUPPORT-AWARE KALMAN SMOOTHER: The state-space model treats amplitudes as partially observable because the support-dependent operator D(s) masks inactive components.Noisy measurements of x^(t) are used to infer the latent state θ^(t).
  • III. THE SUPPORT-AWARE KALMAN SMOOTHER: Only amplitudes associated with indices in the support are observable and identifiable, so their posterior distributions are meaningful.Inactive components do not provide identifiable amplitude states under the model.
  • III. THE SUPPORT-AWARE KALMAN SMOOTHER: Because SKS performs optimal MMSE estimation with known support, it supplies a lower bound for support-agnostic Bayesian algorithms.This bound applies to methods estimating the signal vectors under MMSE loss.

IV. THE AMP-MMV ALGORITHM

AMP-MMV extends message passing to the factorized MMV signal model, using scheduled exchanges across frames to infer signal values, support, and temporally correlated amplitudes.

  • IV. THE AMP-MMV ALGORITHM: AMP-MMV approximates sum-product message passing on the cyclic factor graph while retaining scalable inference over the MMV model.The factor graph represents support, amplitudes, signal variables, and their temporal connections.
  • IV. THE AMP-MMV ALGORITHM: The algorithm produces marginal posterior distributions for soft signal estimation and soft support detection.Messages convey beliefs about the support and amplitude variables before updating signal estimates.
  • IV. THE AMP-MMV ALGORITHM: Its four phases are into, within, out, and across: messages enter a frame, update within-frame beliefs, leave the frame, and propagate temporal information.The within phase estimates x^(t), while the across phase conveys amplitude correlation across time.
  • IV. THE AMP-MMV ALGORITHM: The parallel schedule processes all frames together before exchanging amplitude information forward and backward across time.Repeated forward/backward passes produce a smoothed signal estimate when smoothing is permitted.
  • IV. THE AMP-MMV ALGORITHM: The serial schedule processes frames sequentially, enabling causal MMV processing and optional backward smoothing.Both schedules initialize messages and iterate until convergence or a maximum iteration count.

B. Implementing the Message Passes

The message-passing implementation uses AMP to approximate dense, high-dimensional computations while preserving the MMV model’s joint sparsity and amplitude correlations. This yields linear scaling in the problem dimensions and supports both serial and parallel schedules.

  • B. Implementing the Message Passes: AMP replaces exponentially costly message integrals with Gaussian-approximated messages whose updates use means and variances.The approximation relies on sufficiently high dimensionality and appropriately scaled measurement-matrix entries.
  • B. Implementing the Message Passes: The iterative thresholding algorithm includes a first-order correction that maintains Gaussianity and residual-error independence across iterations.
  • B. Implementing the Message Passes: The AMP iteration costs O(MN) flops, and the iteration count does not scale with M or N under the stated state-evolution behavior.
  • B. Implementing the Message Passes: AMP-MMV models joint sparsity and amplitude correlation through hidden support and state variables, enabling conditional independence of signal coefficients.The resulting local Bernoulli-Gaussian prior determines the AMP soft-thresholding functions.
  • B. Implementing the Message Passes: O(TMN) overall complexity follows because the message phases repeat O(T) times, with O(N) costs for several phases and O(MN) for the AMP phase.The dominant per-iteration operations are matrix-vector products with A and A^H.
  • B. Implementing the Message Passes: Fast implicit measurement operators can reduce AMP-MMV complexity from O(TMN) to O(TN log2 N), as with an FFT implementation.

V. ESTIMATING THE MODEL PARAMETERS

The paper uses expectation-maximization to learn signal-model parameters while AMP-MMV estimates the signals and support. The procedure reuses AMP-MMV posteriors, but initialization and update scheduling affect convergence.

  • V. ESTIMATING THE MODEL PARAMETERS: The EM algorithm learns model parameters while simultaneously estimating the signal and its support.
  • V. ESTIMATING THE MODEL PARAMETERS: EM increases the data likelihood at every iteration until convergence, but multimodal likelihoods can leave it at a local rather than global maximum.Judicious initialization can help reach the global maximum.
  • V. ESTIMATING THE MODEL PARAMETERS: The EM expectation step is essentially free because it reuses quantities already computed during AMP-MMV.
  • V. ESTIMATING THE MODEL PARAMETERS: AMP-MMV supplies marginal and pairwise posterior distributions that allow the EM expectation and maximization steps to be performed in closed form.
  • V. ESTIMATING THE MODEL PARAMETERS: Updating α and ρ together can cause oscillatory EM behavior when their initial values are too small, so the implementation avoids simultaneous updates.

VI. NUMERICAL STUDY

The numerical study evaluates AMP-MMV against Bayesian, greedy, and support-aware methods using synthetic MMV data and metrics for reconstruction, support recovery, and runtime. It also uses an oracle-aided smoother as a lower-bound reference.

  • VI. NUMERICAL STUDY: The study compares AMP-MMV with MSBL, T-MSBL, SA-MUSIC, and the support-aware Kalman smoother.The SKS provides a lower bound on achievable MSE under known support.
  • VI. NUMERICAL STUDY: Experiments use synthetic datasets averaged over 250 independent trials, with Gaussian measurement matrices, T = 4 vectors, and SNR 25 dB unless stated otherwise.
  • VI. NUMERICAL STUDY: Performance is measured by TNMSE, normalized support error rate, and runtime.TNMSE evaluates time-averaged normalized reconstruction error, while NSER measures support disagreement.
  • VI. NUMERICAL STUDY: The experiments include oracle-aided and non-oracle support estimation, with AMP-MMV using posterior support probabilities for the latter.
  • VI. NUMERICAL STUDY: AMP-MMV refines imperfect initial signal-model parameters using the EM update procedure during simulations.

A. Performance Versus Sparsity, M/K

Performance depends strongly on the measurements-to-active-coefficients ratio and temporal amplitude correlation. AMP-MMV is competitive in reconstruction and support recovery over favorable ratios while offering substantially lower runtime.

  • A. Performance Versus Sparsity, M/K: When M/K ≥ 2, AMP-MMV and T-MSBL have TNMSE performance almost identical to the oracle-aided SKS.For M/K < 2, their performance deteriorates relative to the SKS.
  • A. Performance Versus Sparsity, M/K: When M/K < 1.50, all algorithms perform poorly compared with the SKS, although T-MSBL is best among the four non-SKS methods.
  • A. Performance Versus Sparsity, M/K: AMP-MMV provides superior NSER over much of the tested range, including posterior-probability support estimation without prior knowledge of K.
  • A. Performance Versus Sparsity, M/K: AMP-MMV’s runtime is more than one order of magnitude below SA-MUSIC and two orders below T-MSBL or MSBL where AMP-MMV performs well.
  • A. Performance Versus Sparsity, M/K: At increased amplitude correlation of 1 − α = 0.99, AMP-MMV and T-MSBL remain comparable to the SKS for M/K ≥ 2.50, while MSBL and SA-MUSIC degrade.
  • A. Performance Versus Sparsity, M/K: For M/K < 2.5 under increased correlation, AMP-MMV and T-MSBL decay sharply and all methods perform poorly relative to the SKS.

B. Performance Versus T

As the number of measurement vectors changes, AMP-MMV and T-MSBL maintain comparable performance, while AMP-MMV uses substantially lower complexity.

  • MSBL’s performance is strongly impacted by the reduced number of measurements in this experiment.
  • AMP-MMV and T-MSBL perform more-or-less equivalently across the range of T, while AMP-MMV requires an order-of-magnitude less complexity.
  • The SKS TNMSE bound is insensitive to the number of measurement vectors acquired.

C. Performance Versus SNR

Across SNR and undersampling conditions, AMP-MMV remains close to the SKS benchmark over broad regimes and can outperform alternatives under severe undersampling, though convergence may require more smoothing iterations.

  • AMP-MMV operates approximately 5 dB from the SKS at SNRs up to 10 dB and approaches the SKS as SNR increases.
  • AMP-MMV’s posterior-based support estimate is comparable to the K-largest-trajectory-norm method at high SNR and slightly better at low SNR.
  • AMP-MMV runtime can increase when its noise-variance initialization is substantially inaccurate, but a more appropriate initialization can drastically improve runtime.
  • At N/M ≤20, AMP-MMV, T-MSBL, and SA-MUSIC remain close to the performance bound, whereas at N/M = 25 T-MSBL outperforms AMP-MMV and SA-MUSIC.
  • Under severe undersampling, AMP-MMV often requires 50−100 smoothing iterations rather than the roughly five sufficient in other tests.

E. Performance Versus Signal Dimension, N

AMP-MMV scales favorably with signal dimension: it approaches the SKS performance bound and remains fast on large problems, while measurement diversity can enable recovery in otherwise impossible regimes.

  • A single AMP-MMV iteration has O(TNM) complexity, giving linear scaling with the problem dimensions.
  • As N grows from 100 to 1000, AMP-MMV and T-MSBL converge in TNMSE performance to the SKS bound.
  • A problem with NT = 40000 unknowns can be solved accurately by AMP-MMV in just under 30 seconds.
  • AMP-MMV is slower than MSBL and SA-MUSIC at small dimensions but scales more favorably as dimensions increase.
  • At N = 10000, AMP-MMV runs at least two orders-of-magnitude faster than the other methods.
  • With β < 0.03 AMP-MMV fails to recover the signal, but at β ≥0.10 it performs nearly at the noise level; modest measurement diversity enables accurate reconstruction otherwise impossible.

APPENDIX A

Appendix A describes a second-order Taylor approximation used to approximate a two-dimensional function around a reference point.

  • The appendix approximates f̃(θ_r, θ_i) with a two-dimensional second-order Taylor expansion around φ.
  • Because ε ≪1, the approximation further neglects second-order derivative terms whose contribution is O(ε^2).
  • The appendix provides the associated pseudocode implementation for the approximation.
Loading 1111.5272v3…