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 $\ell_2$ error in the Poisson setting. We show that our upper bounds are tight under suitable regularity conditions. Specifically, 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.
Introduction
In the field of compressed sensing and sparse recovery, standard theoretical frameworks often assume Gaussian noise. However, many real-world physical and digital processes—ranging from photon counting in explosives detection to tracking website traffic—are more accurately modeled by Poisson statistics. This paper addresses the fundamental limits of recovering sparse signals from observations corrupted by Poisson noise.
The primary challenge in this regime is that Poisson noise is "heteroscedastic," meaning the noise level depends on the signal's intensity (the mean equals the variance). This introduces non-linearity into the relationship between the signal and the log-likelihood and creates a unique "scale dependence." Unlike standard linear regression where increasing signal strength typically improves recovery, in the Poisson regime, a higher signal scale can flatten the likelihood function's curvature, making it harder to distinguish between similar signals.
Methodology
The authors model observations as $y_i \sim \text{Poisson}(\lambda_{0,i} + \mathbf{a}_i^\top \mathbf{w}^*)$, where $\mathbf{w}^*$ is a sparse vector of weights and $\mathbf{a}_i$ represents known sensing patterns. To recover the signal, they propose an $\ell_1$-constrained Maximum Likelihood Estimator (MLE). Although the Poisson log-likelihood is non-linear, its convexity ensures that the optimization remains computationally tractable.
The theoretical analysis establishes both upper and lower bounds on estimation error:
- Upper Bounds: Utilizing the Restricted Eigenvalue (RE) condition, the authors prove that the estimation error is bounded with high probability.
- Lower Bounds: Using Fano’s Inequality and the Gilbert-Varshamov bound, they establish a theoretical "floor" for the error.
- Minimax Optimality: By demonstrating that these bounds match in terms of scaling, the authors prove that their estimator is minimax optimal—no other algorithm can perform better in the worst-case scenario.
Key Insights and Empirical Validation
A critical finding of this work is that the curvature of the Poisson log-likelihood function decreases as the signal scale ($s = \|\mathbf{w}^*\|_1$) increases. This leads to a loss of "identifiability" at high intensities. Consequently, the estimation error scales as $O(\sqrt{sk/n})$, where $s$ is the signal scale, $k$ is the sparsity, and $n$ is the number of measurements. This explicitly demonstrates how signal scale, rather than just sparsity, fundamentally limits performance in the Poisson setting.
Synthetic experiments confirmed these theoretical predictions, showing that error grows with the square root of scale $s$ and sparsity $k$, while shrinking with the square root of $n$. Furthermore, the regularized ML method significantly outperformed "rescaled LASSO" (which approximates Poisson noise as Gaussian), particularly in high-signal-to-noise (SNR) regimes.
Real-World Applications
The utility of this model is demonstrated through applications in explosives detection and online marketing. In the eMarketing domain, the model was used to analyze web traffic data for clothing brands, linking brand visits to various advertising and social media sources.
In this application, the model revealed a significant shift in digital influence: Social Media Marketing (SMM) has steadily overtaken Search Engine Marketing (SEM) in driving traffic to clothing brands since approximately 2012.
Conclusion
This research establishes the fundamental limits of sparse signal recovery under Poisson noise. By proving the minimax optimality of an $\ell_1$-constrained ML decoder, the authors provide a robust framework for applications where count data is prevalent. While the results rely on the Restricted Eigenvalue condition and assume known background noise levels, they offer a significant advancement over standard Gaussian-based methods. Future work may explore simultaneous estimation of background noise and extensions to more general signal settings.
Summary updated