In an era of ubiquitous large-scale streaming data, the availability of data far exceeds the capacity of expert human analysts. In many settings, such data is either discarded or stored unprocessed in data centers. This paper proposes a method of online data thinning, in which large-scale streaming datasets are winnowed to preserve unique, anomalous, or salient elements for timely expert analysis. At the heart of this proposed approach is an online anomaly detection method based on dynamic, low-rank Gaussian mixture models. Specifically, the high-dimensional covariance matrices associated with the Gaussian components are associated with low-rank models. According to this model, most observations lie near a union of subspaces. The low-rank modeling mitigates the curse of dimensionality associated with anomaly detection for high-dimensional data, and recent advances in subspace clustering and subspace tracking allow the proposed method to adapt to dynamic environments. Furthermore, the proposed method allows subsampling, is robust to missing data, and uses a mini-batch online optimization approach. The resulting algorithms are scalable, efficient, and are capable of operating in real time. Experiments on wide-area motion imagery and e-mail databases illustrate the efficacy of the proposed approach.

Sparse linear inverse problems appear in a variety of settings, but often the noise contaminating observations cannot accurately be described as bounded by or arising from a Gaussian distribution. Poisson observations in particular are a characteristic feature of several real-world applications. Previous work on sparse Poisson inverse problems encountered several limiting technical hurdles. This paper describes a novel alternative analysis approach for sparse Poisson inverse problems that 1) sidesteps the technical challenges present in previous work, 2) admits estimators that can readily be computed using off-the-shelf LASSO algorithms, and 3) hints at a general framework for broad classes of noise in sparse linear inverse problems. At the heart of this new approach lies a weighted LASSO estimator for which data-dependent weights are based on Poisson concentration inequalities. Unlike previous analyses of the weighted LASSO, the proposed analysis depends on conditions which can be checked or shown to hold in general settings with high probability. 2000 Math Subject Classification: 60E15, 62G05, 62G08, and 94A12.

This paper considers fundamental limits for solving sparse inverse problems in the presence of Poisson noise with physical constraints. Such problems arise in a variety of applications, including photon-limited imaging systems based on compressed sensing (CS). Most prior theoretical results in CS and related inverse problems apply to idealized settings where the noise is independent identically distributed and do not account for signal-dependent noise and physical sensing constraints. Prior results on Poisson CS with signal-dependent noise and physical constraints provided upper bounds on mean-squared error (MSE) performance for a specific class of estimators. However, it was unknown whether those bounds were tight or if other estimators could achieve significantly better performance. This paper provides minimax lower bounds on MSE for sparse Poisson inverse problems under physical constraints. The lower bounds are complemented by minimax upper bounds which match the lower bounds for certain problem sizes and noise levels. The source of the mismatch between upper and lower bounds for other problem sizes and noise levels is discussed. The upper and lower bounds reveal that due to the interplay between the Poisson noise model, the sparsity constraint and the physical constraints: 1) the MSE upper bound does not depend on the sample size n other than to ensure the sensing matrix satisfies Restricted Isometry Property-like conditions and the intensity T of the input signal plays a critical role and 2) the MSE upper bound has two distinct regimes, corresponding to low and high intensities, and the transition point from the low-intensity to high-intensity regime depends on the sparsifying basis D. In the low-intensity regime, the MSE upper bound is independent of T while in the high-intensity regime, the MSE upper bound scales as (slog p/T), where s is the sparsity level, p is the number of pixels or parameters, and T is the signal intensity.