PaperlayerView exact revision on arXiv

Source-linked AI summary

Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices

Florent Krzakala, Marc Mézard, François Sausset, Yifan Sun, Lenka Zdeborová

arXiv:1206.3953v1cond-mat.stat-mechcs.IT

TL;DR

Compressed sensing asks how to reconstruct sparse signals from as few noisy linear measurements as possible, despite underdetermination and unknown signal-model parameters. This paper combines probabilistic inference, message passing, parameter learning, asymptotic analysis, and seeded matrices, finding that BP can match optimal inference and that seeding can restore optimality where BP is suboptimal.

  • Problem

    Compressed sensing requires reconstruction from fewer measurements than unknowns, while signal statistics and measurement noise may be unknown and exact Bayesian averages are computationally intractable.

  • Method

    The paper combines probabilistic reconstruction with BP/AMP message passing, expectation-maximization learning, replica and cavity analyses, and seeded measurement matrices.

  • Results

    BP reaches the optimal reconstruction performance in some regions, while seeded matrices reduce or eliminate its suboptimality gap and remain effective with noisy measurements.

  • Takeaways & Limitations

    The approach can approach theoretically optimal compressed-sensing reconstruction using efficient message passing and seeded measurement designs, including under noise and signal-model mismatch.

Abstract

from arXiv · show

Compressed sensing is a signal processing method that acquires data directly in a compressed form. This allows one to make less measurements than what was considered necessary to record a signal, enabling faster or more precise measurement protocols in a wide range of applications. Using an interdisciplinary approach, we have recently proposed in [arXiv:1109.4424] a strategy that allows compressed sensing to be performed at acquisition rates approaching to the theoretical optimal limits. In this paper, we give a more thorough presentation of our approach, and introduce many new results. We present the probabilistic approach to reconstruction and discuss its optimality and robustness. We detail the derivation of the message passing algorithm for reconstruction and expectation max- imization learning of signal-model parameters. We further develop the asymptotic analysis of the corresponding phase diagrams with and without measurement noise, for different distribution of signals, and discuss the best possible reconstruction performances regardless of the algorithm. We also present new efficient seeding matrices, test them on synthetic data and analyze their performance asymptotically.

I. INTRODUCTION

Compressed sensing reconstructs sparse signals from fewer linear measurements than unknowns, while this paper develops probabilistic inference, message passing, asymptotic analysis, and seeded matrices to approach optimal reconstruction limits.

  • Background on compressed sensing: ℓ1 reconstruction has a sharp phase transition but is sub-optimal because exact recovery requires a measurement rate larger than the signal density.For signal density ρ, exact recovery occurs only when α exceeds αℓ1(ρ), with αℓ1(ρ) > ρ.
  • Our approach: The paper analyzes probabilistic reconstruction using BP or its AMP/G-AMP forms, expectation-maximization learning, and replica and cavity methods.These tools address reconstruction, unknown signal-model parameters, large-system behavior, and algorithm-independent theoretical limits.
  • Phase diagrams and noise: The analysis identifies a parameter region where BP is trapped below optimal reconstruction, while measurement noise can shrink and eventually eliminate this gap.In the hard region, BP iterations are blocked in a suboptimal fixed point; the noisy phase diagram shows the region persists but becomes smaller as noise grows.
  • Seeding matrices: Seeded measurement matrices are designed to remove or reduce the BP–optimality gap and can approach theoretically optimal reconstruction, including with noisy measurements.The paper introduces simpler efficient seeding constructions and studies their performance under model mismatch and noise.
  • Model mismatch: The probabilistic approach can achieve exact noiseless reconstruction even when the assumed signal model does not match the empirical signal distribution.The paper explicitly does not generally assume matching sparsity, noise variance, or signal distribution parameters.
  • Background on compressed sensing: Compressed sensing seeks to reconstruct sparse signals from an underdetermined linear system using as few measurements per variable as possible.The measurements satisfy y = Fs, with M < N possible, and sparsity makes reconstruction feasible despite fewer equations than unknowns.

A. Optimality in the noiseless case

In the noiseless limit, probabilistic reconstruction is exact above the signal density threshold under a support condition, independently of the true signal distribution. With noise, Bayes optimality instead requires the true signal and noise parameters.

  • Optimality in the noiseless case: α > ρ0 guarantees exact reconstruction in the noiseless case when φ supports every non-zero signal element.The assumed density ρ and distribution φ need not match the true values ρ0 and φ0.
  • Optimality in the noiseless case: Y∆(D) diverges as D → 0 and ∆ → 0 whenever α > ρ0 and φ is supported on all signal elements.The statement holds for every measurement matrix F and every such function φ.
  • Optimality in the noiseless case: The optimality argument suppresses all nonzero-distance solutions because the original signal has the largest number of zero elements.Only configurations satisfying all M linear equations contribute to the auxiliary partition function.
  • Optimality in the noiseless case: For any ρ0-dense signal, the posterior probability of the original signal tends to one as ∆ → 0 when α > ρ0 and the ℓ0 minimizer is the signal.This remains independent of φ0, including cases where the signal entries are not iid.
  • Bayesian optimality with noise: With measurement noise, posterior sampling is generally not optimal when the true density, noise variance, and signal distribution are unknown.The noiseless arbitrary-signal optimality result does not extend automatically to this mismatched noisy setting.
  • Bayesian optimality with noise: When the true density, noise variance, and signal distribution are known, posterior inference is Bayes-optimal for mean-squared error.The estimator is obtained from posterior averages of the coordinate variables.

C. Expectation maximization learning

The paper learns unknown signal-model and noise parameters by maximizing the partition function, while approximating otherwise intractable posterior averages with belief propagation. The resulting iterative procedure combines BP reconstruction with parameter updates.

  • Expectation maximization learning: Unknown signal density, noise variance, and signal distribution parameters can be learned within the Bayesian approach using expectation-maximization-like updates.The posterior over parameters is defined from the partition function with the candidate parameter set.
  • Expectation maximization learning: Maximizing the partition function is the parameter-learning objective because it scales exponentially with system size.The paper derives stationary equations for the partition function or its logarithm.
  • Expectation maximization learning: Exact posterior averages require exponential time, so the method approximates them with a belief propagation variant related to AMP and generalized AMP.The paper motivates message passing as efficient in both precision and speed for compressed sensing.
  • Expectation maximization learning: Canonical BP uses 2MN probability-distribution messages, which are simplified through large-N scaling of the measurement-matrix elements.The Hubbard–Stratonovich transformation and expansion in small matrix elements lead to scalar mean and variance messages.
  • Expectation maximization learning: The noiseless setting is represented by ∆µ = 0, while local beliefs use means ai and variances vi of the marginal distributions.Perfect reconstruction corresponds to ai = si and vi = 0.

B. The TAP form of the message passing algorithm

The BP equations are compressed into a TAP representation with far fewer messages by exploiting dense, large-N measurement matrices. The resulting equations are asymptotically equivalent to BP and correspond to AMP in compressed sensing.

  • The TAP form of the message passing algorithm: N + M messages replace 2MN BP messages when F is dense and its entries scale as O(1/√N).The TAP equations neglect only o(1) terms in the large-N limit.
  • The TAP form of the message passing algorithm: The TAP derivation retains Onsager reaction terms because variable-to-measurement messages remain weakly dependent on the measurement index.Corrections linear in Fµi must be kept when expressing ai→µ through ai.
  • The TAP form of the message passing algorithm: The closed TAP system uses only matrix multiplication and is equivalent to generalized approximate message passing.The signal prior enters through the functions fa and fc.
  • The TAP form of the message passing algorithm: The TAP iterations can be initialized with a practical starting point and solved iteratively for reconstruction.The section presents an explicit initialization for the iterative equations.

C. Further simplification for measurement matrices with random entries

For iid random matrices, TAP equations simplify by replacing squared matrix entries with their variance, reducing the algorithm to a small number of variables. Related block-matrix simplifications support structured noise and signal-model implementations.

  • Further simplification for measurement matrices with random entries: F²µi can be replaced by 1/N for iid zero-mean entries of variance 1/N in the large-N limit.The replacement follows because the average is order one while the variance is order 1/N.
  • Further simplification for measurement matrices with random entries: The simplified iid-matrix algorithm uses 2(M + N + 1) variables and costs O(NM) steps per iteration for a general matrix.Recursively computable matrices reduce the message-passing loop to O(M + N) steps.
  • Further simplification for measurement matrices with random entries: Block measurement matrices admit simplified TAP equations when noise is constant within each measurement block.The formulation uses block variances Jq,p/N and block-specific noise ∆q.
  • Further simplification for measurement matrices with random entries: The practical implementation uses a Gauss-Bernoulli signal model with Gaussian nonzero components.The associated functions fa and fc are available in closed form.
  • Further simplification for measurement matrices with random entries: Signal and noise parameters are learned by stationary conditions of the Bethe free entropy, including an explicit condition for homogeneous noise variance.The resulting equations support iterative expectation-maximization-style learning.

IV. ASYMPTOTIC ANALYSIS: STATE EVOLUTION AND REPLICAS

The paper analyzes belief propagation through density evolution and uses replicas to characterize both algorithmic behavior and optimal reconstruction. Density evolution tracks error and variance parameters, while replica fixed points provide broader physical and information-theoretic interpretation.

  • State evolution: Density evolution describes how belief-propagation message distributions evolve in the large-system limit using a small set of order parameters.The analysis is also called the cavity method, density evolution, or state evolution, depending on the field.
  • State evolution: The evolution is represented by the mean-squared error E and average belief variance V, which are updated across BP iterations.For the considered initialization, these equations also describe TAP equations because O(1/N) factors are neglected.
  • Phase behavior: At high measurement density, the noiseless dynamics has a unique fixed point E = V = 0; below a critical point, an attractive fixed point with E > 0 and V > 0 appears.The second fixed point can attract uninformed initial conditions, preventing exact reconstruction by the iteration.
  • Replica analysis: Replica calculations reproduce the density-evolution fixed-point equations and assign physical meaning even to fixed points that BP iteration does not reach.BP fixed points are stationary points of the free entropy.
  • Replica analysis: The global free-entropy maximum characterizes uniform sampling, while the free entropy restricted to signal distance D helps visualize where BP reconstruction fails.Near the signal, the free entropy diverges in the noiseless limit when α > ρ0.

C. Analysis of Bayes-optimal inference

In the Bayes-optimal setting, the assumed signal and noise models match the true distributions, making probabilistic inference information-theoretically optimal. Nishimori identities reduce the asymptotic analysis to a single mean-squared-error parameter.

  • Bayes-optimal setting: Bayes-optimal inference uses the true signal density, nonzero-element distribution, and measurement-noise variance.This corresponds to ρ = ρ0, φ = φ0, and Δ = Δ0.
  • Bayes-optimal setting: Exact sampling from the posterior measure gives the best possible reconstruction performance regardless of the algorithm.The replica-symmetric calculation is exact in this matched-model setting.
  • Nishimori reduction: The Nishimori conditions q = m, Q = ρs2, and E = V collapse the density evolution to a single parameter, the mean-squared error E.The mean-squared distance from the signal to a sampled configuration is D = 2E.
  • Nishimori reduction: At the free-entropy global maximum, E equals the Bayes-optimal reconstruction error, whereas BP may instead stop at a local suboptimal maximum.Which maximum BP reaches depends on α, ρ, and the assumed signal distribution.

D. Density evolution with parameter learning

When the assumed signal model is mismatched, expectation-maximization learning can update model parameters alongside BP. The resulting procedure is analyzed through augmented density-evolution equations, including noise-variance learning.

  • Parameter learning: Expectation maximization can learn signal-model parameters when the BP model differs from the signal’s true density or nonzero-element distribution.The modified BP procedure with parameter learning is studied using density evolution.
  • Parameter learning: The learned parameters are incorporated by complementing the density-evolution updates for E and V with parameter-update equations.The implementation initializes ρ, x, and σ2 before iterating the coupled system.
  • Parameter learning: With measurement noise, the noise variance can also be learned through an additional update equation.The paper treats homogeneous noise with a common variance across measurements.

E. Density evolution for block matrices

For block measurement matrices, the paper extends density evolution and replica analysis across measurement blocks. In the matched Bayesian case, blockwise Nishimori identities reduce the dynamics to one error parameter per block.

  • Block-matrix analysis: The density-evolution and replica derivations extend to block measurement matrices, with results stated in terms of block-specific order parameters.The derivation is generalized from the homogeneous-matrix case.
  • Block-matrix analysis: For each block p, the relevant parameters are the mean-squared error Ep and variance Vp, giving 2Lc order parameters overall.These parameters are defined from the blockwise overlaps and self-overlaps.
  • Block-matrix analysis: The blockwise stationarity equations are exactly the density-evolution equations when interpreted as an iterative mapping between order parameters.The mapping updates conjugate parameters first and then obtains the next order parameters.
  • Bayes-optimal blocks: Expectation-maximization learning can be combined with block matrices, yielding density-evolution equations for the learned Gauss-Bernoulli parameters.The paper gives the corresponding parameter updates explicitly.
  • Bayes-optimal blocks: In the optimal Bayesian approach, blockwise Nishimori conditions imply Ep = Vp for every block.This produces a closed density-evolution system involving only the vector of block errors Ep.

V. THE PHASE DIAGRAMS

This section converts the belief-propagation reconstruction equations into phase diagrams for noiseless compressed sensing with random homogeneous measurement matrices.

  • V. THE PHASE DIAGRAMS: The analysis focuses on noiseless compressed sensing with random homogeneous measurement matrices as a benchmark for belief propagation and ℓ1 reconstruction.The matrices have iid entries with zero mean and variance 1/N.
  • V. THE PHASE DIAGRAMS: The phase diagrams display reconstruction performance as a function of measurement rate and signal sparsity.
  • V. THE PHASE DIAGRAMS: The approach uses iid measurement matrices whose entries have zero mean and variance 1/N.

A. Noiseless measurements and the optimal Bayes case

In noiseless compressed sensing, Bayesian inference can reach the information-theoretical limit, while BP may be blocked by a spinodal barrier; EM learning improves robustness when the signal model is mismatched.

  • A. Noiseless measurements and the optimal Bayes case: α = ρ0 is the information-theoretical threshold for exact Bayesian reconstruction, but BP requires α > αBP when a secondary free-entropy maximum traps its dynamics.The BP threshold is the smallest α for which the free entropy becomes monotonic.
  • A. Noiseless measurements and the optimal Bayes case: The BP spinodal transition is discontinuous, unlike the continuous ℓ1 transition, reflecting a first-order phase-transition structure with metastable states.Below the spinodal point, the system is trapped in a metastable state and the MSE does not converge to zero.
  • A. Noiseless measurements and the optimal Bayes case: αBP(ρ0 = 0.4) ≈0.59, whereas ℓ1 reconstruction becomes exact only for α ≳0.75; below αBP, BP still achieves lower MSE than ℓ1.The BP convergence time diverges as α approaches αBP.
  • A. Noiseless measurements and the optimal Bayes case: For a mixture of narrow Gaussians, BP reaches α = ρ0 when ρ0 ≳0.8, whereas the ℓ1 transition is independent of the signal distribution.The phase diagrams compare BP with the Donoho–Tanner transition and the exact-reconstruction limit.
  • B. Noiseless measurements and the mismatching signal model: With a mismatched signal model, probabilistic reconstruction remains optimal in principle for α > ρ0, but the BP spinodal line depends on both assumed and actual signal distributions.The position of the algorithmic barrier changes with the model mismatch.
  • B. Noiseless measurements and the mismatching signal model: EM-BP learns signal parameters and improves on pure BP and ℓ1 reconstruction in many cases, although ℓ1 can be better for a narrow binary-signal region.For Gaussian signal elements, the correct mean and variance are learned even where exact reconstruction is impossible.

C. Phase diagram for noisy measurements

With measurement noise, reconstruction exhibits phase transitions whose structure depends on noise strength. BP is suboptimal in an intermediate sampling region, while seeding can improve performance there.

  • Exact reconstruction is impossible with noisy measurements because the optimal MSE remains nonzero.
  • For α > αd, BP reaches a single low-MSE maximum comparable to ∆; for α < αs, only a much higher-MSE maximum remains.
  • For αd > α > αc, free entropy has two maxima, with the lower-MSE maximum globally optimal while BP converges suboptimally.
  • Noise changes the phase diagram: for ∆≳0.00078, Gauss-Bernoulli inference has no sharp phase transition.
  • As noise increases, the region supporting a sharp phase transition shrinks, and BP's discontinuous MSE increase occurs at αd.

B. Seeding experiments for noiseless measurements

Seeding matrices enable BP reconstruction near the information-theoretic limit in noiseless compressed sensing, including mismatched signal models. Their propagation speed determines how reconstruction time scales with the number of blocks.

  • Seeded matrices achieve α → ρ0 reconstruction for signals with density ρ0 = 0.4 using noiseless BP measurements at α = 0.5.
  • Type (ii) seeding yields iteration counts linear in block number L through a localized wave moving at constant speed.
  • Type (iii) triangular seeding yields iteration counts proportional to log L because the reconstructed-region growth rate satisfies δL/δt ∼ L.
  • Numerical BP reconstruction agrees very well with the N →∞ density-evolution prediction for seeded matrices.
  • Seeding approaches α → ρ0 even when the true signal has components 0, ±1 but BP uses a Gauss-Bernoulli model.
  • With additive noise, seeded fronts can propagate at finite speed and attain final MSE of order ∆, but propagation stops when αbulk < αc.

Appendix A: Derivation of the replica analysis for block matrices

The appendix derives replica-based equations for block seeding matrices and compares probabilistic BP reconstruction with ℓ1 reconstruction. It concludes that seeding gains arise specifically from combining Bayes inference, message passing with parameter learning, and seeded measurement design.

  • Replica derivation: The replica calculation introduces block-specific order parameters and uses Gaussian averages, Dirac-delta representations, and replica symmetry to derive the free entropy.For block p, the appendix defines variables including rp, Ep, ˆµp, and ˆrp; the resulting free entropy is given in Eq. (136).
  • Seeding analysis: The seeded-matrix comparison evaluates both probabilistic reconstruction and ℓ1 reconstruction, including ℓ1 optimization over coupling parameters J1 and J2.The table reports reconstruction thresholds ρ0 at the same α values for probabilistic BP and seeded ℓ1.
  • Replica derivation: For L = 1, the saddle-point equations reduce to a closed system in α and λ that gives the critical α for a specified ρ0.These equations recover the canonical-matrix transition equations associated with prior analyses.
  • Seeding analysis: For L ≥ 2, the asymptotic saddle-point equations are independent of the nonzero-element distribution when the signal distribution is symmetric.The analysis therefore uses a centered unit-variance Gaussian signal distribution for seeded matrices.
  • Comparison and conclusion: ℓ1 reconstruction with optimized J1 and J2 is slightly worse than ℓ1 reconstruction with a single block, whereas the seeded performance gain is specific to Bayes inference.The paper attributes the best performance to the combination of probabilistic reconstruction, message passing with parameter learning, and seeded measurement design.

Appendix C: Equations for a mixture of Gaussians

The appendix specializes the BP density-evolution equations to signals modeled as mixtures of Gaussians. Gaussian-mixture structure reduces the required integrals and, under optimal Bayesian matching, simplifies the system further.

  • Signal model: The signal model is defined as a mixture of G Gaussians with non-negative weights wa summing to one.The corresponding mixture components provide the functions required by the BP algorithm.
  • Density evolution: For a signal that is itself a Gaussian mixture, the density-evolution equations simplify to equations involving single Gaussian integrals.The simplification uses integration by parts and combines Gaussian variables through sums of their means and variances.
  • Density evolution: Under optimal Bayesian inference with matching signal and assumed distributions, equal sparsity, and equal noise variances, the two-equation system reduces further.The stated matching conditions are φ0(x) = φ(x), ρ0 = ρ, and Δ = Δ0.
Loading 1206.3953v1…