Locating salient items in large data collections with compressive linear measurements

Recent advances in compressive sensing (CS) have established that high-dimensional signals that possess sparse representations in some basis or dictionary can be accurately recovered from relatively few linear measurements. As a result, CS strategies have been proposed and developed in a number of application domains where sensing resource efficiency is of primary importance. This paper examines a class of compressive anomaly detection tasks, where the aim is to identify the locations of a nominally small number of outliers in a large collection of data (which may be scalar or multivariate) using a small number of observations of the form of linear combinations of subsets of the data. We introduce a generalized notion of sparsity termed here as saliency, and establish that a novel sensing and inference technique called Compressive Saliency Sensing (CSS), comprised of a randomized linear sensing strategy and associated computationally efficient inference procedure based on techniques from group testing, can accurately identify the locations of k outliers in a collection of n items from only m = O(k log n) linear measurements. We describe several inference tasks to which our approach is suited, including “traditional” k-sparse support recovery problems; identification of k outliers in the “simple” signal model of Donoho and Tanner, characterized by nominally binary vectors having k entries strictly in (0, 1); and identification of vectors that are outliers from a common (low-dimensional) linear subspace.