PaperlayerView exact revision on arXiv

Source-linked AI summary

Compressed sensing performance bounds under Poisson noise

Maxim Raginsky, Rebecca M. Willett, Zachary T. Harmany, Roummel F. Marcia

arXiv:0910.5146v3cs.IT

TL;DR

The paper addresses compressed sensing of nonnegative, sparse or compressible intensities under Poisson noise, where standard noise assumptions, sensing matrices, and ℓ2–ℓ1 fitting are unsuitable. It constructs physically feasible sensing matrices and analyzes penalized Poisson-likelihood reconstruction. The resulting bounds decay with increasing signal intensity but, at fixed intensity, their signal-dependent component grows with the number of sensors.

  • Problem

    Poisson noise and optical constraints make standard compressed sensing models unsuitable for reconstructing nonnegative sparse or compressible intensities.

  • Method

    The paper constructs positivity- and flux-preserving sensing matrices and uses penalized Poisson log-likelihood reconstruction with Kraft-compliant sparsity penalties.

  • Results

    The derived error bounds decay with increasing total intensity but have a signal-dependent term that grows with the number of measurements at fixed intensity.

  • Takeaways & Limitations

    Photon-limited compressed sensing has fundamentally different performance behavior from Gaussian or bounded-noise settings because feasible optical measurements introduce intensity-dependent noise.

Abstract

from arXiv · show

This paper describes performance bounds for compressed sensing (CS) where the underlying sparse or compressible (sparsely approximable) signal is a vector of nonnegative intensities whose measurements are corrupted by Poisson noise. In this setting, standard CS techniques cannot be applied directly for several reasons. First, the usual signal-independent and/or bounded noise models do not apply to Poisson noise, which is non-additive and signal-dependent. Second, the CS matrices typically considered are not feasible in real optical systems because they do not adhere to important constraints, such as nonnegativity and photon flux preservation. Third, the typical $\ell_2$--$\ell_1$ minimization leads to overfitting in the high-intensity regions and oversmoothing in the low-intensity areas. In this paper, we describe how a feasible positivity- and flux-preserving sensing matrix can be constructed, and then analyze the performance of a CS reconstruction approach for Poisson data that minimizes an objective function consisting of a negative Poisson log likelihood term and a penalty term which measures signal sparsity. We show that, as the overall intensity of the underlying signal increases, an upper bound on the reconstruction error decays at an appropriate rate (depending on the compressibility of the signal), but that for a fixed signal intensity, the signal-dependent part of the error bound actually grows with the number of measurements or sensors. This surprising fact is both proved theoretically and justified based on physical intuition.

I. INTRODUCTION

The paper develops compressed sensing methods for photon-limited imaging, where Poisson noise and physical optical constraints make standard CS models inadequate. It proposes feasible sensing and penalized-likelihood reconstruction, then derives error bounds whose intensity and measurement-count dependence can differ substantially from conventional CS guarantees.

  • Motivation: Photon-limited imaging offers few detected photons relative to the pixels or voxels to be estimated, motivating compressed sensing to reduce detector requirements.Applications include infrared imaging, nuclear medicine, astronomy, and night vision.
  • Motivation: Poisson noise violates the signal-independent or bounded-noise assumptions used by standard compressed sensing analyses.Because Poisson variance depends on signal intensity, conventional ℓ2 data fitting can overfit bright regions and oversmooth dim regions.
  • Measurement model: Physically realizable optical sensing requires positivity preservation and photon-flux preservation, constraints that conventional random CS matrices generally do not satisfy.For nonnegative f, the projected signal Af must remain nonnegative, and observed total intensity cannot exceed incident intensity.
  • Bounds and contributions: The paper derives upper bounds describing how reconstruction error scales with total intensity, signal size, measurement count, and compressibility.Theoretical support includes ℓ0-based penalties and, more generally, penalty schemes satisfying the Kraft inequality.
  • Main result: At fixed total intensity, increasing the number of measurements can increase the signal-dependent error term because photons are spread across more sensors and compressed measurements cannot be naturally binned.Increasing total intensity yields error decay at a rate tied to signal compressibility, provided the measurement count is sufficiently large.
  • Reconstruction approach: The paper proposes a penalized Poisson-likelihood reconstruction objective as an alternative to standard ℓ2–ℓ1 optimization.The penalty can measure sparsity in a transform-domain representation while the likelihood models the Poisson observations.

C. Organization of the paper

The paper formulates Poisson compressed sensing with a feasible nonnegative sensing matrix and develops its structural and norm-preservation properties. It then connects the construction to near-isometric behavior on suitable subsets and empirical reconstruction guarantees.

  • The sensing model uses a nonnegative signal f* and Poisson observations Af* collected by an N × m positivity- and flux-preserving matrix.
  • The matrix is constructed from i.i.d. random entries, shifted and scaled so that negative entries become physically realizable measurements.
  • The paper organizes these properties around feasible optical sensing rather than the physically unrealizable signed matrices used in standard compressed sensing.
  • Each matrix entry is either 0 or 1/N, ensuring positivity preservation and photon-flux preservation for nonnegative inputs.
  • The centered random matrix has a RIP-like near-isometry property on selected subsets, supporting performance guarantees for the sensing design.

B. DC offset and noise

The sensing construction introduces a DC offset that makes signed compressed-sensing measurements physically feasible but increases Poisson noise. The paper therefore uses penalized likelihood reconstruction and derives bounds under a known-total-intensity formulation.

  • The informative component of each measurement is accompanied by a DC offset proportional to the total intensity I.
  • Because the offset makes each measurement’s intensity and variance proportional to I, it can overwhelm the informative component when that component is small.
  • The resulting Poisson noise variance produces performance guarantees unlike those typically reported for standard compressed sensing.
  • The estimator minimizes a negative Poisson log-likelihood together with a nonnegative penalty over a countable feasible set satisfying the Kraft inequality.
  • The analysis targets f*/I, treating the total intensity I as known to focus on estimating the intensity distribution rather than its overall scale.

D. Summary of notation

The notation defines normalized risk, the feasible sensing and estimator classes, and the oracle-style framework used for the paper’s risk bounds. The framework also captures tuning and measurement-number effects on expected risk.

  • The signal dimension is m, while the known total intensity of f* is I.
  • The random matrix Z has i.i.d. entries controlled by the tunable parameter p, and eA denotes its scaled version with norm-preservation properties.
  • The physical sensing matrix A is obtained by shifting and scaling eA, producing positivity and flux preservation.
  • The risk is R(f*, f) = ∥f* − f∥2^2/I^2, measuring normalized squared reconstruction error.
  • The estimator bf is the penalized maximum-likelihood solution over the feasible candidate set Γ.
  • The oracle inequality compares expected estimator risk with the best penalized risk available over candidate classes, while the risk-bound terms depend on measurement number and sparsity-related structure.
  • The parameter p is optimized at p = 1/2 for both CN,p and ζp, although changing p trades off observed photons against measurement noise variance.
  • Increasing N can create a threshold effect because one risk factor increases with N while another decreases, alongside an O(N^-1 log(m/N)) term.

B. Risk bounds for compressible signals

The paper analyzes its estimator for signals compressible in an orthonormal basis and derives risk bounds under low- and high-intensity regimes. The bounds also identify measurement-saturation conditions and an intensity-dependent decay rate.

  • Signal model: The estimator is analyzed for targets that admit sparse approximations in an orthonormal reference basis.Compressibility is represented through basis coefficients and weak-ℓq approximation assumptions.
  • Risk bound: Theorem 3 provides a high-probability risk bound for a finite candidate-estimator set with a Kraft-inequality penalty.The hidden constants depend only on p, ρ, C, and c.
  • Intensity regimes: In the low-intensity regime I ≤ m log m, the risk is bounded by the corresponding low-intensity rate.If k*(N) is below the stated threshold, the estimator saturates, although its risk remains controlled.
  • Rates: When I ≍ m and N ≍ m^(1/β) with β > 1 + 1/(2α), the error decays at rate O(m^-γ), up to logarithmic factors.Here γ = [2α − (2α+1)/β]/(2α+1) > 0.

IV. EXPERIMENTAL RESULTS

The experiments evaluate sparsity-regularized Poisson log-likelihood reconstruction using SPIRAL and partition-based penalties. They show improved reconstruction from cycle spinning, while highlighting a trade-off between measurement count and photons per measurement.

  • Method: The proposed SPIRAL approach sequentially minimizes quadratic approximations to a Poisson objective with flexible sparsity penalties.The quadratic subproblem acts as a denoising step within gradient descent and supports partition-based penalties.
  • Method: Partition-based SPIRAL methods select recursive dyadic partitions and fit models within partition cells by maximum likelihood.The optimal partition is obtained by pruning a quad-tree representation.
  • Experimental setup: The experiment uses a length-1024 signal with total intensity I = 8.2 × 10^5 and 512 noisy compressive measurements.The sensing matrix has 32 randomly distributed nonzero elements per row, with mean detector count 50.
  • Results: Cycle spinning makes the reconstruction smoother and lowers risk from 7.552 × 10^-5 for SPIRAL-RDP to 4.468 × 10^-5 for SPIRAL-RDP-TI.The latter estimate is described as smoother and more accurate.
  • Results: At fixed intensity, adding measurements provides less pronounced benefits because photons per observation decrease and measurements become noisier.Higher total intensity consistently improves performance in the reported comparisons.
  • Conclusions: The conclusions provide Poisson-noise error bounds for sparse or compressible signals and extend the theoretical result to penalties satisfying Kraft’s inequality.This supports analysis of reconstruction strategies beyond sparsity-promoting penalties.

APPENDIX A PROOF OF THEOREM 1

The appendix proves the sensing-matrix result by applying norm-preservation theorems for isotropic subgaussian ensembles. It verifies that the constructed random measurement distribution has the required isotropy and subgaussianity properties.

  • Proof strategy: The proof uses random measurement vectors and geometric norm-preservation results for finite subsets of the sphere.The required number of measurements is controlled by the complexity of the set being embedded.
  • Ensemble conditions: The relevant ensemble is required to be isotropic and subgaussian, with concentration guarantees depending on its subgaussian constant.These properties enable the cited measurement theorems.
  • Sensing construction: The constructed sensing rows are independent copies of a product distribution whose components are drawn independently from νp.The normalized matrix is formed from the random row matrix.
  • Verification: Isotropy follows from the construction, while subgaussianity is established using bounded independent summands and Hoeffding’s inequality.The argument treats p ≠ 1/2 directly and invokes symmetry for the Rademacher case p = 1/2.
  • Conclusion: Combining the ensemble verification with the geometric theorems proves Theorem 1 with the stated high-probability guarantee.The proof concludes after applying the preceding results to the constructed matrix.

APPENDIX B PROOF OF THEOREM 2

The appendix derives the risk bound by relating Poisson likelihood quantities to Hellinger-type expressions and then controlling the resulting terms with norm inequalities. The argument assumes the total intensity is known in the stated form.

  • Proof construction: The proof uses a chain of estimates connecting the Poisson model to the proposed risk bound.The intermediate expressions involve the square roots of Af* and A f-hat.
  • Inequality steps: Cauchy–Schwarz, the arithmetic-mean/geometric-mean inequality, and the sensing-matrix condition control the intermediate terms.The appendix states that straightforward algebra then yields the required bound.
  • Likelihood control: The key likelihood relation uses the Poisson Kullback–Leibler divergence and its explicit coordinatewise form.The divergence enters after rewriting the relevant likelihood comparison.
  • Assumption: The stated bound assumes the true and reconstructed signals have the same total intensity I.Without known I, additional terms proportional to I would enter the error bound.
  • Candidate class: The proof defines the best candidate risk through minimization over the candidate class before combining the preceding estimates.This quantity is denoted R*(f*, Υ*).

APPENDIX C PROOF OF THEOREM 3

The proof constructs a finite estimator class with sparsity-based penalties, verifies the coding condition, and organizes estimators by sparsity level to apply Theorem 2.

  • The estimator class Γ is formed from projections of signals onto a closed convex set and transformed back into coefficient space.
  • The penalty pen(f) increases with the number of nonzero coefficients in θ = W^T f.Its stated form is pen(f) = log2(m + 1) + (3/2)∥θ∥0 log2(m).
  • The penalty corresponds to a prefix code that encodes sparsity, coefficient locations, and quantized coefficient values.The coefficient values are quantized into √m uniformly sized bins.
  • The resulting code is uniquely decodable and therefore satisfies Kraft’s inequality.
  • For each sparsity level k, the subclass Γ_k contains estimators whose corresponding coefficients have at most k nonzero entries.The proof bounds its size and restricts k to k ≤ k*(N).
  • The proof then bounds the first term in the theorem’s right-hand side using the estimator penalty and a logarithmic complexity expression.The constant hidden by O(·) depends only on p, ρ, C, and c.

A. Proof of (25)

This proof introduces the counting measure associated with each observation component and identifies the resulting left-hand quantity as a probability-distribution divergence.

  • The proof uses ν_i as the counting measure on the ith component of y.
  • Taking logarithms produces the displayed expression used in the proof.
  • The resulting left-hand quantity is described as a divergence measure between probability distributions.The passage relates it to the work of Bhattacharyya and Chernoff.

B. Proof of (26)

The proof rewrites the likelihood notation, introduces Hellinger affinity, and combines expectation and Jensen arguments to derive an upper bound involving the affinity and penalty.

  • The proof abbreviates p(y|Af*) and p(y|Af) as p_f*(y) and p_f(y), respectively.
  • It defines the Hellinger affinity as part of the comparison between the true and candidate distributions.
  • Replacing the ratio evaluated at the selected estimator with a sum over all f ∈ Γ yields an upper bound.
  • Taking expectation under p_f*(y) and applying Jensen’s inequality advances the bound.
  • Using the definition of the selected estimator and combining the intermediate steps gives a bound involving 2E log 1/A(f*, f).
Loading 0910.5146v3…