Locating salient items in large data collections with compressive linear measurements

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2013 5th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2013
Pages9-12
Number of pages4
DOIs
StatePublished - 2013
Event2013 5th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2013 - Saint Martin, France
Duration: Dec 15 2013Dec 18 2013

Publication series

Name2013 5th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2013

Other

Other2013 5th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2013
CountryFrance
CitySaint Martin
Period12/15/1312/18/13

Fingerprint Dive into the research topics of 'Locating salient items in large data collections with compressive linear measurements'. Together they form a unique fingerprint.

Cite this