Minimax Optimal Sparse Signal Recovery with Poisson Statistics
arXiv:1501.05200 · doi:10.1109/TSP.2016.2529588
Abstract
We are motivated by problems that arise in a number of applications such as Online Marketing and Explosives detection, where the observations are usually modeled using Poisson statistics. We model each observation as a Poisson random variable whose mean is a sparse linear superposition of known patterns. Unlike many conventional problems observations here are not identically distributed since they are associated with different sensing modalities. We analyze the performance of a Maximum Likelihood (ML) decoder, which for our Poisson setting involves a non-linear optimization but yet is computationally tractable. We derive fundamental sample complexity bounds for sparse recovery when the measurements are contaminated with Poisson noise. In contrast to the least-squares linear regression setting with Gaussian noise, we observe that in addition to sparsity, the scale of the parameters also fundamentally impacts error in the Poisson setting. We show tightness of our upper bounds both theoretically and experimentally. In particular, we derive a minimax matching lower bound on the mean-squared error and show that our constrained ML decoder is minimax optimal for this regime.
arXiv commentSubmitted to IEEE Trans. on Signal Processing. arXiv admin note: substantial text overlap with arXiv:1307.4666
References in corpus (10)
- Simultaneous analysis of Lasso and Dantzig selector
- On the conditions used to prove oracle results for the Lasso
- A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
- Compressed sensing performance bounds under Poisson noise
- Information theoretic bounds for Compressed Sensing
- Restricted Eigenvalue Conditions on Subgaussian Random Matrices
- Performance bounds for expander-based compressed sensing in Poisson noise
- Learning Exponential Families in High-Dimensions: Strong Convexity and Sparsity
- Sparse Signal Recovery under Poisson Statistics
- The Lasso under Heteroscedasticity
Cited by in corpus (3)
- A data-dependent weighted LASSO under Poisson noise
- Reconstruction Error Bounds for Compressed Sensing under Poisson or Poisson-Gaussian Noise Using Variance Stabilization Transforms
- Reconstruction Error Bounds for Compressed Sensing under Poisson Noise using the Square Root of the Jensen-Shannon Divergence