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 @math 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.
Parameter estimation for non-identical Poisson distributions has been studied in the context of Generalized Linear Models (GLMs). However, our model is inherently different from the exponential family of GLM models that has been studied in @cite_0 @cite_18 @cite_9 @cite_20 . In particular the GLM model corresponding to the Poisson distributed data studied in the literature has the following form: Therefore, the log likelihood takes the following form: In contrast, in the setting we are interested in, the observations are modeled as follows: and the log likelihood function has the form:
@cite_0 @cite_9 @cite_18 @cite_20
2950190315 1555163866 2127357443 2076313409
High-dimensional statistical inference deals with models in which the the number of parameters p is comparable to or larger than the sample size n. Since it is usually impossible to obtain consistent procedures unless @math , a line of recent work has studied models with various types of low-dimensional structure, including sparse vectors, sparse and structured matrices, low-rank matrices and combinations thereof. In such settings, a general approach to estimation is to solve a regularized optimization problem, which combines a loss function measuring how well the model fits the data with some regularization function that encourages the assumed structure. This paper provides a unified framework for establishing consistency and convergence rates for such regularized M-estimators under high-dimensional scaling. We state one main theorem and show how it can be used to re-derive some existing results, and also to obtain a number of new results on consistency and convergence rates, in both @math -error and related norms. Our analysis also identifies two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure corresponding regularized M-estimators have fast convergence rates and which are optimal in many well-studied cases. The versatility of exponential families, along with their attendant convexity properties, make them a popular and effective statistical model. A central issue is learning these models in high-dimensions, such as when there is some sparsity pattern of the optimal parameter. This work characterizes a certain strong convexity property of general exponential families, which allow their generalization ability to be quantified. In particular, we show how this property can be used to analyze generic exponential families under L_1 regularization. The problem of sparse signal recovery from a relatively small number of noisy measurements has been studied extensively in the recent literature on compressed sensing. However, the focus of those studies appears to be limited to the case of linear projections disturbed by Gaussian noise, and the sparse signal reconstruction problem is treated as linear regression with l 1 -norm regularization constraint. A natural question to ask is whether one can accurately recover sparse signals under different noise assumptions. Herein, we extend the results of [13] to the more general case of exponential-family noise that includes Gaussian noise as a particular case, and yields l 1 -regularized Generalized Linear Model (GLM) regression problem. We show that, under standard restricted isometry property (RIP) assumptions on the design matrix, l 1 -minimization can provide stable recovery of a sparse signal in presence of the exponential-family noise, provided that certain sufficient conditions on the noise distribution are satisfied. Consider a sample of size n from a regular exponential family in Pn dimensions. Let 6, denote the maximum likelihood estimator, and consider the case where Pn tends to infinity with n and where (On is a sequence of parameter values in RP-. Moment conditions are provided under which II6 0,JI = O?( p(, n) and On6n On Xnll = Op (p, n), where Xn is the sample mean. The latter result provides normal approximation results when p2 n 0. It is shown by example that even for a single coordinate of (6, in), pn2 n -? 0 may be needed for normal approximation. However, if pn3 2 n O 0, the likelihood ratio test statistic A for a simple hypothesis has a chi-square approximation in the sense that (2 log A pn ) 2Pn D A(0, 1).