PaperlayerView exact revision on arXiv

Source-linked AI summary

Type I and Type II Bayesian Methods for Sparse Signal Recovery using Scale Mixtures

Ritwik Giri, Bhaskar D. Rao

arXiv:1507.05087v1cs.LGstat.ML

TL;DR

Sparse signal recovery seeks sparse representations from underdetermined measurements, and the paper examines how Type I and Type II Bayesian methods relate for this task. It uses the PESM family to unify established methods and develop Type II algorithms, including reweighted ℓ1. The reported experiments show better support recovery for Type II methods than their Type I counterparts.

Abstract

from arXiv · show

In this paper, we propose a generalized scale mixture family of distributions, namely the Power Exponential Scale Mixture (PESM) family, to model the sparsity inducing priors currently in use for sparse signal recovery (SSR). We show that the successful and popular methods such as LASSO, Reweighted $\ell_1$ and Reweighted $\ell_2$ methods can be formulated in an unified manner in a maximum a posteriori (MAP) or Type I Bayesian framework using an appropriate member of the PESM family as the sparsity inducing prior. In addition, exploiting the natural hierarchical framework induced by the PESM family, we utilize these priors in a Type II framework and develop the corresponding EM based estimation algorithms. Some insight into the differences between Type I and Type II methods is provided and of particular interest in the algorithmic development is the Type II variant of the popular and successful reweighted $\ell_1$ method. Extensive empirical results are provided and they show that the Type II methods exhibit better support recovery than the corresponding Type I methods.

I. INTRODUCTION

Sparse signal recovery seeks sparse solutions to underdetermined, often noisy systems, but the ideal sparsest-solution formulation is computationally intractable. The paper places established recovery methods in a generalized Bayesian scale-mixture framework and develops Type II counterparts, including reweighted ℓ1.

A. Problem Formulation

  • Because an underdetermined system admits infinitely many solutions, SSR seeks a sparse one; the ideal ℓ0 formulation is NP-hard and noise motivates a modified objective.Surrogate penalties make computation tractable and connect to reweighted norm methods.Source: A. Problem Formulation · p. 1

B. Related Literature

  • Prior work includes ℓ1 methods such as Basis Pursuit and LASSO, reweighted ℓ1 and ℓ2 methods, and Bayesian Type I and Type II approaches.Reweighted methods had empirically shown better recovery than ℓ1 minimization; the paper builds on earlier Type II work while seeking further insight into the two frameworks.Source: B. Related Literature · pp. 1–2

C. Contributions of the Paper

  • PESM generalizes scale-mixture representations and provides a unified view of ℓ1 and ℓ2 frameworks used for sparse recovery.The framework includes GSM and LSM as special cases and represents many super-Gaussian densities used in practice.Source: B. Related Literature · p. 2, C. Contributions of the Paper • · p. 2
  • The paper unifies three diversity-minimization algorithms in PESM and derives Type I and Type II versions, including Type II reweighted ℓ1.It also treats ℓ1- and ℓ2-based approaches in a unified manner.Source: C. Contributions of the Paper • · p. 2
  • The paper analyzes differences between Type I and Type II inference and reports experiments supporting better recovery by Type II methods.The analysis is offered as a potential explanation for the empirical performance difference.Source: C. Contributions of the Paper • · p. 2

D. Article Organization

The article moves from scale-mixture distributions to Bayesian algorithms for sparse recovery and then to experiments and conclusions. Its PESM family generalizes GSM and LSM and supplies a hierarchical representation for prior modeling.

D. Article Organization

  • The article proceeds from scale-mixture distributions to Type I/MAP and Type II methods, then experiments and conclusions.The Type II section develops EM inference for coefficients and hyperparameters, including a reweighted ℓ1 counterpart.Source: D. Article Organization · p. 2

II. SCALE MIXTURE DISTRIBUTIONS

  • Scale mixtures represent heavy-tailed super-Gaussian distributions hierarchically, and their use in regression is motivated in part by modeling data outliers.Source: §II · p. 2

A. Power Exponential Scale Mixture (PESM) distribution

B. An example of PESM: Generalized t Distribution

The generalized t distribution is a flexible PESM example whose parameters cover several sparse priors used in SSR. In the Type I framework, choosing a sparse prior yields a MAP estimate, and PESM unifies scale-mixture approaches associated with ℓ1- and ℓ2-based algorithms.

B. An example of PESM: Generalized t Distribution

  • Inverse generalized gamma mixing in the PESM hierarchy yields a generalized t distribution encompassing GDP, Laplacian, and Student-t priors used in practice.The shape parameters p and q control tail behavior: larger values correspond to thinner tails, and smaller values to heavier tails.Source: B. An example of PESM: Generalized t… · p. 3
  • PESM can represent both supergaussian and subgaussian densities, including thin-tailed generalized t distributions when p > 2.It treats Laplacian and Gaussian scale mixtures in a unified framework for ℓ1- and ℓ2-based algorithms.Source: B. An example of PESM: Generalized t… · p. 3

A. Background on MAP Estimation (Type I methods)

  • Type I estimation uses a chosen sparsity-enforcing prior to obtain a MAP estimate, with the prior narrowing candidate solutions according to application-specific assumptions.For a PESM prior, Type I integrates out the hyperparameter γ.Source: A. Background on MAP Estimation (Type… · p. 4

B. Unified Type I Inference Procedure

The unified Type I EM procedure treats PESM scale variables as hidden variables while estimating the signal. It alternates conditional-expectation-based weight updates with weighted norm minimization until convergence.

B. Unified Type I Inference Procedure

  • The procedure treats each scale variable γ_i as hidden and uses EM to obtain a MAP estimate of x under a PESM prior.The separable prior gives each x_i an independent scale-mixture representation.Source: B. Unified Type I Inference Procedure · p. 4
  • The E-step uses p(γ|x), rather than p(γ|x,y), because the hierarchy has the Markov property γ → x → y.Only the complete-data term log p(x|γ) depends on γ_i and is needed for this expectation.Source: B. Unified Type I Inference Procedure · p. 4
  • The algorithm iterates between computing weights in the E-step and solving a weighted norm minimization in the M-step until convergence.The complete-data log-likelihood is log p(y|x) + log p(x|γ) + log p(γ).Source: B. Unified Type I Inference Procedure · p. 4

C. Special cases of Type I using Generalized t distribution

Specializing the Type I procedure to generalized t priors recovers LASSO, reweighted ℓ1, and reweighted ℓ2 methods. The parameter choices determine whether the weights remain fixed or change with the previous estimate.

C. Special cases of Type I using Generalized t distribution

  • For q → ∞, p = 1, and σ = 1, the weights are fixed at 1, so the M-step reduces to a single ℓ1-penalized regression, equivalent to LASSO.The generalized t prior becomes Laplacian in this limit.Source: 1) LASSO (ℓ1-minimization) · p. 5
  • With q = ϵ, p = 1, and σ = 1, generalized t yields reweighted ℓ1 minimization with weights (1+ϵ)/(ϵ+|x_i|) based on the previous estimate.These are the weights obtained in using a majorization-minimization approach; this generalized t special case is also called GDP.Source: 2) Reweighted ℓ1-minimization (Candes… · p. 5
  • For p = 1, generalized t is a Laplacian scale mixture with mixing density GG(γ; −1, 1, ϵ), yielding GT(1, 1, ϵ) as its marginal.This connects the generalized t specialization to the unified Type I EM procedure.Source: C. Special cases of Type I using… · p. 4, 2) Reweighted ℓ1-minimization (Candes… · p. 5
  • A Student-t prior with 2ϵ degrees of freedom gives reweighted ℓ2 minimization, with smaller ϵ corresponding to heavier tails.The associated diversity penalty is g(x_i) = log(x_i^2 + ϵ).Source: 3) Reweighted ℓ2-minimization · p. 5

IV. B-SSR: TYPE II (EVIDENCE MAXIMIZATION)

The Type II framework estimates PESM hyperparameters by evidence maximization rather than integrating them out. The paper develops Type II versions of three Type I algorithms and analyzes differences between the approaches.

IV. B-SSR: TYPE II (EVIDENCE MAXIMIZATION)

  • The paper explores Type II counterparts of the three Type I algorithms and analyzes their differences to provide insight into superior recovery performance.Source: §IV · p. 5
  • Type II estimates the hyperparameters γ by evidence maximization instead of integrating them out as in Type I.The framework integrates over x to obtain p(y|γ), weights this evidence by p(γ), and maximizes over γ.Source: §IV · p. 5
  • After estimating γ, the framework approximates p(x|y), often as p(x|y; γ̂), and uses its mean as a point estimate.The passage states that sparsity is achieved by many γ_i being zero.Source: §IV · p. 5

A. Unified Type II EM algorithm

The unified Type II procedure uses EM to update hyperparameters under a sparse PESM prior, while the paper contrasts Type II posterior-mass estimation with Type I mode estimation. It also discusses robustness and parameter tying in hierarchical inference.

A. Unified Type II EM algorithm

  • The unified Type II EM algorithm treats x as hidden under a sparse PESM prior and Gaussian measurement noise, then updates γ by maximizing the Q function.For a noninformative hyperprior p(γ_i)=1, the update follows by differentiating the Q function with respect to γ_i.Source: A. Unified Type II EM algorithm · pp. 5–6
  • The E-step requires a conditional expectation, which may be obtained in closed form or computed using MCMC.The M-step focuses on terms involving γ.Source: A. Unified Type II EM algorithm · p. 6

B. Difference between Type I and Type II inference methods

  • As zero variances approach zero, their Gaussian coefficient distributions become Dirac delta functions in the derivation of posterior mass over active subspaces.The derivation uses this limit when evaluating the integral over coefficients.Source: B. Difference between Type I and Type… · p. 6
  • Type II maximizes posterior mass over subspaces indexed by nonzero hyperparameters, approximating the true posterior rather than using its mode as Type I does.The resulting approximation is p(x|y; γ̂), with γ̂ chosen by maximizing posterior mass over those subspaces.Source: B. Difference between Type I and Type… · p. 6
  • Hierarchical Type II inference is described as more robust to prior misspecification, and parameter tying can reduce the search space, especially for MMV and block-sparse problems.The cited discussion says hyperparameter posteriors are less affected by wrong prior choices than parameter posteriors.Source: B. Difference between Type I and Type… · p. 6

C. Special case of Unified Type II with different choices of p

The section specializes the unified Type II framework to different PESM choices, including tractable Gaussian-scale-mixture cases and a reweighted ℓ1 hierarchy. It also identifies computational challenges for direct Laplacian-scale-mixture inference and assumes known SNR for simplicity.

C. Special case of Unified Type II with different choices of p

  • With p=2, PESM is a Gaussian scale mixture, giving a Gaussian posterior and a tractable E-step based on the second moment.The hyperparameter updates depend on the mixing density; the posterior mean and covariance depend on estimated hyperparameters.Source: 1) Choice of p = 2 · p. 7
  • The p=2 hierarchy yields a Student t prior; the paper relates its Type II Reweighted ℓ2 formulation to SBL, while noting that ε=0 in Type I increases local minima.The Student t correspondence is given as GT(2, 2, ε) ≃ Student-t(2ε).Source: 1) Choice of p = 2 · p. 7
  • Direct p=1 Laplacian-scale-mixture inference lacks a feasible closed-form E-step and simple posterior, leaving efficient numerical inference as future work.The required E-step includes E(|x_i|; y, γ^(k)); the paper instead notes that the Laplacian family is contained within the Gaussian scale mixture family.Source: 2) Choice of p = 1 · p. 7
  • A three-layer hierarchy for the Type I Reweighted ℓ1 prior yields a closed-form Gaussian posterior; for p=1 versus p=2, the difference lies in hyperparameter estimation.The Type II Reweighted ℓ1 variant is developed using this hierarchy.Source: 2) Choice of p = 1 · p. 7
  • The Type II Reweighted ℓ1 construction represents the Laplacian prior in a three-layer hierarchy and uses EM to estimate γ and λ.Its E-step uses the second moment through the Gaussian scale mixture representation.Source: 2) Choice of p = 1 · pp. 7–8
  • For simplicity, the experiments assume the environment’s SNR is known beforehand, although the paper notes that measurement-noise variance can also be estimated.Source: 2) Choice of p = 1 · p. 8

V. NUMERICAL EXPERIMENTS

The experiments compare hierarchical Type II methods with regularization-based Type I methods for sparse signal recovery. One illustrated case reconstructs uniform spikes with k=13 using three estimates alongside the original signal.

V. NUMERICAL EXPERIMENTS

  • The experiments evaluate Type II hierarchical methods against Type I regularization methods for sparse signal recovery.The paper describes the setup as standard and widely used in sparse signal recovery literature.Source: §V · p. 8
  • Figure 5 shows a uniform-spike reconstruction at k=13, with the original signal and three method estimates.Source: Figure 5 · p. 9
  • The displayed estimates are ℓ1 minimization Type I, Type II ℓ1 minimization, and Candes et al. Type I Reweighted ℓ1 minimization.Source: Figure 5 · p. 9

A. Problem Specification

The problem specification generates sparse signals and synthetic measurements from a random Gaussian dictionary, then evaluates recovery across support sizes. It reports 500 trials per fixed support cardinality and observes declining success as support grows.

A. Problem Specification

  • A 50 × 250 dictionary has i.i.d. normal entries, and each length-250 signal has k randomly located nonzeros.Source: A. Problem Specification · p. 9
  • The nonzero coefficients are drawn from uniform ±1, zero-mean unit-variance Gaussian, or Student t distributions with 3 degrees of freedom.Measurements are generated as y = Φx_gen and supplied with the dictionary to the algorithms.Source: A. Problem Specification · p. 9
  • Across 500 trials for each fixed k, the probability of successful recovery decreases as support cardinality increases.Source: A. Problem Specification · p. 9

B. Recovery Performance

The study compares Type II versions of three norm-minimization algorithms with their Type I counterparts. Type II methods perform better across the tested coefficient distributions, while the conclusion attributes their stronger recovery to how they approximate the posterior.

1) Competing Algorithms:

  • The experiments compare Type II versions of three norm-minimization Type I algorithms with their Type I counterparts.The study includes Type I Reweighted ℓ2 minimization with an ε-regularized optimal update.Source: 1) Competing Algorithms · p. 9

2) Performance Comparison:

  • Across Gaussian, Student-t, and sub-Gaussian coefficients, Type II methods outperform Type I, with a less significant advantage for sub-Gaussian coefficients.The comparison uses recovery-performance plots for each coefficient distribution.Source: Figure 6 · p. 9, Figure 7 · p. 9, 2) Performance Comparison · pp. 9–10
  • For Gaussian coefficients, all Type II versions outperform their Type I counterparts; the difference is significant for ℓ1 minimization.Type I Reweighted ℓ2 performs better than the other two Type I methods, and its heuristic ε update helps it get away from local minima.Source: 2) Performance Comparison · p. 9
  • For Student-t coefficients with 3 degrees of freedom, Type II methods again outperform Type I; Reweighted ℓ2 improves significantly over the other methods.The authors suggest this may reflect a match between the assumed and true prior tail behavior.Source: 2) Performance Comparison · p. 10
  • For sub-Gaussian coefficients, Type II still outperforms Type I, but the improvement is less significant than in the Gaussian and Student-t cases.The authors suggest that super-Gaussian assumed priors are difficult to match to the sub-Gaussian coefficient distribution.Source: 2) Performance Comparison · p. 10

VI. CONCLUSION AND DISCUSSION

  • The paper presents PESM as a framework for Bayesian SSR and identifies unified ℓ1/ℓ2 treatments and Type II Reweighted ℓ1 as contributions.The work formulates SSR in Type I and Type II Bayesian frameworks.Source: §VI · p. 10
  • Type II methods seek an approximate posterior that maximizes true-posterior mass over the subspace spanned by nonzero indexes.The authors identify this as the reason for Type II methods’ superior empirical results and note their robustness to the choice of hyperparameter prior.Source: §VI · p. 10

Related papers

Loading 1507.05087v1…