We are motivated by problems that arise in a number of applications such as explosives detection and online Marketing, where the observations are governed by Poisson statistics. Here each observation is 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 analyse the performance of a Maximum Likelihood (ML) decoder, which for our Poisson setting is computationally tractable. We derive fundamental sample complexity bounds for sparse recovery in the high-dimensional setting. We show that when the sensing matrix satisfies the so-called Restricted Eigenvalue (RE) condition the l1 regularized ML decoder is consistent. Moreover, it converges exponentially fast in terms of number of observations. Our results apply to both deterministic and random sensing matrices and we present several results for both cases.
@cite_0: 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 p n → 0, a line of recent work has studied models with various types of structure (e.g., sparse vectors; block-structured matrices; low-rank matrices; Markov assumptions). In such settings, a general approach to estimation is to solve a regularized convex program (known as a regularized M-estimator) which combines a loss function (measuring how well the model fits the data) with some regularization function that encourages the assumed structure. The goal of this paper is to provide 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 several existing results, and also to obtain several new results on consistency and convergence rates. Our analysis also identifies two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure the corresponding regularized M-estimators have fast convergence rates.
@cite_18: The observations in many applications consist of counts of discrete events, such as photons hitting a dector, which cannot be effectively modeled using an additive bounded or Gaussian noise model, and instead require a Poisson noise model. As a result, accurate reconstruction of a spatially or temporally distributed phenomenon (f) from Poisson data (y) cannot be accomplished by minimizing a conventional l 2 - l 1 objective function. The problem addressed in this paper is the estimation of f from y in an inverse problem setting, where (a) the number of unknowns may potentially be larger than the number of observations and (b) f admits a sparse approximation in some basis. The optimization formulation considered in this paper uses a negative Poisson log-likelihood objective function with nonnegativity constraints (since Poisson intensities are naturally nonnegative). This paper describes computational methods for solving the constrained sparse Poisson inverse problem. In particular, the proposed approach incorporates key ideas of using quadratic separable approximations to the objective function at each iteration and computationally efficient partition-based multiscale estimation methods.
@cite_20: 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).
@cite_8: 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 when the optimal parameter vector is sparse. This work characterizes a certain strong convexity property of general exponential families, which allows their generalization ability to be quantified. In particular, we show how this property can be used to analyze generic exponential families under L1 regularization.
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_8 @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 has the form: In contrast, in the setting we are interested in, the observations are modeled as follows: and the log likelihood function has the form: