SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

Open Access Research

Target detection performance bounds in compressive imaging

Kalyani Krishnamurthy1*, Rebecca Willett1 and Maxim Raginsky2

Author Affiliations

1 Department of Electrical and Computer Engineering, Duke University, Durham, NC 27708, USA

2 Department of Electrical and Computer Engineering and Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA

For all author emails, please log on.

EURASIP Journal on Advances in Signal Processing 2012, 2012:205  doi:10.1186/1687-6180-2012-205

The electronic version of this article is the complete one and can be found online at: http://asp.eurasipjournals.com/content/2012/1/205


Received:2 December 2011
Accepted:28 August 2012
Published:25 September 2012

© 2012 Krishnamurthy et al.; licensee Springer.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License(http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

This article describes computationally efficient approaches and associated theoretical performance guarantees for the detection of known targets and anomalies from few projection measurements of the underlying signals. The proposed approaches accommodate signals of different strengths contaminated by a colored Gaussian background, and perform detection without reconstructing the underlying signals from the observations. The theoretical performance bounds of the target detector highlight fundamental tradeoffs among the number of measurements collected, amount of background signal present, signal-to-noise ratio, and similarity among potential targets coming from a known dictionary. The anomaly detector is designed to control the number of false discoveries. The proposed approach does not depend on a known sparse representation of targets; rather, the theoretical performance bounds exploit the structure of a known dictionary of targets and the distance preservation property of the measurement matrix. Simulation experiments illustrate the practicality and effectiveness of the proposed approaches.

Keywords:
Target detection; Anomaly detection; False discovery rate; ip-value; Incoherent projections; Compressive sensing

Introduction

The theory of compressive sensing (CS) has shown that it is possible to accurately reconstruct a sparse signal from few (relative to the signal dimension) projection measurements [1,2]. Though such a reconstruction is crucial to visually inspect the signal, there are many instances where one is solely interested in identifying whether the underlying signal is one of several possible signals of interest. In such situations, a complete reconstruction is computationally expensive and does not optimize the correct performance metric. Recently, CS ideas have been exploited in [3-5] to perform target detection and classification from projection measurements, without reconstructing the underlying signal of interest. In [3,5], the authors propose nearest-neighbor based methods to classify a signal <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M1">View MathML</a> to one of m known signals given projection measurements of the form <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M2">View MathML</a> for KN, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M3">View MathML</a> is a known projection operator and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M4">View MathML</a> is the additive Gaussian noise. This model is simple to analyze, but is impractical, since in reality, a signal is always corrupted by some kind of interference or background noise. Extension of the methods in [3,5] to handle background noise is nontrivial. Though, Duarte et al. [4] provides a way to account for background contamination, it makes a strong assumption that the signal of interest and the background are sparse in bases that are incoherent. This might not always be true in many applications. Recent works on CS [6,7] allow for the input signal f to be corrupted by some pre-measurement noise <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M5">View MathML</a> such that one observes y=A(f + b) + n, and study reconstruction performance as a function of the number of measurements, pre- and post-measurement noise statistics and the dimension of the input signal. In this work, however, we are interested in performing target detection without an intermediate reconstruction step. Furthermore, the increased utility of high-dimensional imaging techniques such as spectral imaging or videography in applications like remote sensing, biomedical imaging and astronomical imaging [8-15] necessitates the extension of compressive target detection ideas to such imaging modalities to achieve reliable target detection from fewer measurements relative to the ambient signal dimensions.

For example, recent advances in CS have led to the development of new spectral imaging platforms which attempt to address challenges in conventional imaging platforms related to system size, resolution, and noise by acquiring fewer compressive measurements than spatiospectral voxels [16-21]. However, these system designs have a number of degrees of freedom which influence subsequent data analysis. For instance, the single-shot compressive spectral imager discussed in [18] collects one coded projection of each spectrum in the scene. One projection per spectrum is sufficient for reconstructing spatially homogeneous spectral images, since projections of neighboring locations can be combined to infer each spectrum. Significantly more projections are required for detecting targets of unknown strengths without the benefit of spatial homogeneity. We are interested in investigating how several such systems can be used in parallel to reliably detect spectral targets and anomalies from different coded projections.

In general, we consider a broadly applicable framework that allows us to account for background and sensor noise, and perform target detection directly from projection measurements of signals obtained at different spatial or temporal locations. The precise problem formulation is provided below.

Problem formulation

Let us assume access to a dictionary of possible targets of interest <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M6">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M7">View MathML</a> for j=1,…,m is unit-norm. Our measurements are of the form

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M8">View MathML</a>

(1)

where

• i∈{1,…,M} indexes the spatial or temporal locations at which data are collected;

• αi≥0 is a measure of the signal-to-noise ratio at location i, which is either known or estimated from observations;

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M9">View MathML</a> for K < N, is a measurement matrix to be specified in Section “Whitening compressive observations”;

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M10">View MathML</a>• is the background noise vector, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M11">View MathML</a> is the i.i.d. sensor noise.

For example, in the case of spectral imaging <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M12">View MathML</a> represents the spectrum at the ith spatial location, and in video sequences <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M13">View MathML</a> represents the vectorized image frame obtained at the ith time interval. In this article we consider the following target detection problems:

(1) Dictionary signal detection (DSD): Here we assume that each <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M14">View MathML</a> for i∈{1,…,M}, and our task is to detect all instances of one target signal <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M15">View MathML</a> for some unknown j∈{1,…,m}, i.e., to locate <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M16">View MathML</a>. DSD is useful in contexts in which we know the makeup of a scene and wish to focus our attention on the locations of a particular signal. For instance, in spectral imaging, DSD is used to study a scene of interest by classifying every spectrum in the scene to different known classes [11,22]. In a video setup, DSD could be used to classify video segments to one of several categories (such as news, weather, sports, etc.) by projecting the video sequence to an appropriate feature space and comparing the feature vectors to the ones in a known dictionary [23].

(2) Anomalous signal detection (ASD): Here, our task is to detect all signals which are not members of our dictionary, i.e., detect <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M17">View MathML</a> (this is akin to anomaly detection methods in the literature which are based on nominal, nonanomalous training samples [24,25]). For instance, ASD may be used when we know most components of a spectral image and wish to identify all spectra which deviate from this model [26].

Our goal is to accurately perform DSD or ASD without reconstructing the spectral input <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M18">View MathML</a> from zi for i∈{1,…,M}. Accounting for background is a crucial issue. Typically, the background corresponding to the scene of interest and the sensor noise are modeled together by a colored multivariate Gaussian distribution [27]. However, in our case, it is important to distinguish the two because of the presence of the projection operator Φ. The projection operator acts upon the background spectrum in the same way as on the target spectrum, but it does not affect the sensor noise. We assume that biand wiare independent of each other, and the prior probabilities of different targets in the dictionary <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M19">View MathML</a> for j∈{1,⋯,m} are known in advance. If these probabilities are unknown, then the targets can be considered equally likely. Given this setup, our goal is to develop suitable target and anomaly detection approaches, and provide theoretical guarantees on their performances.

In this article, we develop detection performance bounds which show how performance scales with the number of detectors in a compressive setting as a function of SNR, the similarity between potential targets in a known dictionary, and their prior probabilities. Our bounds are based on a detection strategy which operates directly on the collected data as opposed to first reconstructing each <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M20">View MathML</a> and then performing detection on the estimated signals. Reconstruction as an intermediate step in detection may be appealing to end users who wish to visually inspect spectral images instead of relying entirely on an automatic detection algorithm. However, using this intermediate step has two potential pitfalls. First, the Rao–Blackwell theorem [28] tells us that an optimal detection algorithm operating on the processed data (i.e., not sufficient statistics) cannot perform better than an optimal detection algorithm operating on the raw data. In other words, optimal performance is possible on the raw data, but we have no such performance guarantee for the reconstructed signals. Second, the relationship between reconstruction errors and detection performance is not well understood in many settings. Although we do not reconstruct the underlying signals, our performance bounds are intimately related to the signal resolution needed to achieve the signal diversity present in our dictionary. Since we have many fewer observations than the signals at this resolution, we adopt the “compressive” terminology.

Performance metric

To assess the performance of our detection strategies, we consider the false discovery rate (FDR) metric and related quantities developed for multiple hypothesis testing problems [29]. Since we collect M independent observations of potentially different signals, we are simultaneously conducting M hypothesis tests when we search for targets. Unlike the probability of false alarm, which measures the probability of falsely declaring a target for a single test, the FDR measures the fraction of declared targets that are false alarms, that is, it provides information about the entire set of M hypotheses instead of just one. More formally, the FDR is given by,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M21">View MathML</a>

where V is the number of falsely rejected null hypotheses, and R is the total number of rejected null hypotheses. Controlling the FDR in a multiple hypothesis testing framework is akin to designing a constant false alarm rate (CFAR) detector in spectral target detection applications that keeps the false alarm rate at a desired level irrespective of the background interference and sensor noise statistics [22].

Previous investigations

Much of the classical target detection literature [30-34] assume that each target lies in a P-dimensional subspace of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M22">View MathML</a> for P < N. The subspace in which the target lies is often assumed to be known or specified by the user, and the variability of the background is modeled using a probability distribution. Given knowledge of the target subspace, background statistics and sensor noise statistics, detection methods based on LRTs (likelihood ratio tests) and GLRTs (generalized likelihood ratio tests) have been proposed in [30-35]. A subspace model is optimal if the subspace in which targets lie is known in advance. However, in many applications, such subspaces might be hard to characterize. An alternative, and a more flexible option is to assume that the high-dimensional target exhibits some low-dimensional structure that can be exploited to perform efficient target detection. This approach is utilized in this work and in [5] where the target signal in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M23">View MathML</a> is assumed to come from a dictionary of m known signals such that m≪N, and in [3], where the targets are assumed to lie in a low-dimensional manifold embedded in high-dimensional target space.

Recently, several methods for target or anomaly detection that rely on recovering the full spatiospectral data from projection measurements [36,37] have been proposed. However, they are computationally intensive and the detection performance associated with these reconstructions is unknown. Other researchers have exploited CS to perform target detection and classification without reconstructing the underlying signal [3-5]. Duarte et al. [4] propose a matching pursuit based algorithm, called the incoherent detection and estimation algorithm (IDEA), to detect the presence of a signal of interest against a strong interfering signal from noisy projection measurements. The algorithm is shown to perform well on experimental data sets under some strong assumptions on the sparsity of the signal of interest and the interfering signal. Davenport et al. [3] develop a classification algorithm called the smashed filter to classify an image in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M24">View MathML</a> to one of m known classes from K projections of the signal, where K < N. The underlying image is assumed to lie on a low-dimensional manifold, and the algorithm finds the closest match from the m known classes by performing a nearest neighbor search over the m different manifolds. The projection measurements are chosen to preserve the distances among the manifolds. Though Davenport et al. [3] offers theoretical bounds on the number of measurements necessary to preserve distances among different manifolds, it is not clear how the performance scales with K or how to incorporate background models into this setup. Moreover, this approach may be computationally intensive since it involves learning and searching over different manifolds. Haupt et al. [5] use a nearest-neighbor classifier to classify an N-dimensional signal to one of m equally likely target classes based on K < N random projections, and provide theoretical guarantees on the detector performance. While the method discussed in [5] is computationally efficient, it is nontrivial to extend to the case of target detection with colored background noise and nonequiprobable targets. Furthermore, their performance guarantees cannot be directly extended to our problem since we focus on error measures that let us analyze the performance of multiple hypothesis tests simultaneously as opposed to the above methods that consider compressive classification performance for a single hypothesis test.

The authors of a more recent work [38] extend the classical RX anomaly detector [39] to directly detect anomalies from random, orthonormal projection measurements without an intermediate reconstruction step. They numerically show how the detection probability improves as a function of the signal-to-noise ratio when the number of measurements changes. Though probability of detection is a good performance measure, in many applications controlling the false discoveries below a desired level is more crucial. As a result, in our work, we propose an anomaly detection method that controls the FDR below a desired level.

Contributions

This article makes the following contributions to the above literature:

• A compressive target detection approach, which (a) is computationally efficient, (b) allows for the signal strengths of the targets to vary with spatial location, (c) allows for backgrounds mixed with potential targets, (d) considers targets with different a priori probabilities, and (e) yields theoretical guarantees on detector performance. This article unifies preliminary work by the authors [40,41], presents previously unpublished aspects of the proofs, and contains updated experimental results.

• A computationally efficient anomaly detection method that detects anomalies of different strengths from projection measurements and also controls the FDR at a desired level.

• A whitening filter approach to compressive measurements of signals with background contamination, and associated analysis leading to bounds on the amount of background to which our detection procedure is robust.

The above theoretical results, which are the main focus of this article, are supported with simulation studies in Section “Experimental results”. Classical detection methods described in [22,26,27,30-35,39,42-45] do not establish performance bounds as a function of signal resolution or target dictionary properties and rely on relatively direct observation models which we show to be suboptimal when the detector size is limited. The methods in [3,4] do not contain performance analysis, and our analysis builds upon the analysis in [5] to account for several specific aspects of the compressive target detection problem.

Whitening compressive observations

Before we present our detection methods for DSD and ASD problems, respectively, we briefly discuss a whitening step that is common to both our problems of interest.

Let us suppose that there are enough background training data available to estimate the background mean μb and covariance matrix Σb. We can assume without loss of generality that μb=0since Φμb can be subtracted from y. Given the knowledge of the background statistics, we can transform the background and sensor noise model <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M25">View MathML</a> discussed in (1) to a simple white Gaussian noise model by multiplying the observations zi, i∈{1,…,M}, by the whitening filterCΦ≜(ΦΣbΦT + σ2I)−1/2. This whitening transformation reduces the observation model in (1) to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M26">View MathML</a>

(2)

where

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M27">View MathML</a>

(3)

and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M28">View MathML</a>. To verify that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M29">View MathML</a>, observe that

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M30">View MathML</a>

We can now choose Φ so that the corresponding Ahas certain desirable properties as detailed in Sections “Dictionary signal detection” and “Anomalous signal detection”.

For a given A, the following theorem provides a construction of Φthat satisfies (3) and a bound on the maximum tolerable background contamination:

Theorem 1

Let B=IAΣbAT. If the largest eigenvalue of Σb satisfies

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M31">View MathML</a>

(4)

where ∥A∥ is the spectral norm of A, then B is positive definite and ΦB−1/2Ais a sensing matrix, which can be used in conjunction with a whitening filter to produce observations modeled in (2).

The proof of this theorem is provided in Appendix 1. This theorem draws an interesting relationship between the maximum background perturbation that the system can tolerate and the spectral norm of the measurement matrix, which in turn varies with K and N. Hardware designs such as those in [17,19] use spatial light modulators and digital micro mirrors, which allow the measurement matrix Φ to be adjusted easily in response to changing background statistics and other operating conditions.

In the sections that follow, we consider collecting measurements of the form <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M32">View MathML</a> given in (2), where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M33">View MathML</a> is the target of interest for i=1,…,M, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M34">View MathML</a> is a sensing matrix that satisfies (3). It is assumed that any background contamination has been eliminated with the whitening procedure described in this section.

Dictionary signal detection

Suppose that the end user wants to test for the presence of one known target versus the rest, but it is not known a priori which target from <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M35">View MathML</a> the user wants to detect. In this case, let us cast the DSD problem as a multiple hypothesis testing problem of the form

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M36">View MathML</a>

(5)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M37">View MathML</a> is the target of interest and i=1,…,M.

Decision rule

We define our decision rule corresponding to target <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M38','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M38">View MathML</a> in terms of a set of significance regions <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M39">View MathML</a> such that one rejects the ith null hypothesis if its test statistic yi falls in the ith significance region. Specifically, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M40">View MathML</a> is defined according to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M41">View MathML</a>

(6)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M42','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M42">View MathML</a> is the logarithm of the a posteriori probability density of the target f(j) at the ith spatial location given the observations yi, the signal-to-noise ratio αiand the sensing matrix A, and p(j) is the a priori probability of target class j. Note that the process of determining these decision regions involves a sequence of nearest-neighbor calculations, so the computational complexity scales with the number of classes m. In this work, we operate under the assumption that m is much smaller than the dimensionality of the datasets we consider. For example, if we consider spectral images, then the number of objects (signal classes) that make up a scene of interest is often smaller than the number of voxels in the image. This assumption is not unrealistic and has been exploited in earlier work such as [22] and the references therein. In most of the prior work we have surveyed [46,47], the number of signal classes is less than 35, which doesn’t make our approach intractable.

The decision rule can be formally expressed in terms of the significance regions as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M43','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M43">View MathML</a>

(7)

We analyze this detector by extending the positive FDR (pFDR) error measure introduced by Storey to characterize the errors encountered in performing multiple, independent and nonidentical hypothesis tests simultaneously [48]. The pFDR, discussed formally below, is the fraction of falsely rejected null hypotheses among the total number of rejected null hypotheses, subject to the positivity condition that one rejects at least one null hypothesis. The pFDR is similar to the FDR except that the positivity condition is enforced here. In our context, the positivity condition means that we declare at least one signal to be a nontarget, which in turn implies that the scene of interest is composed of more than one object in the case of spectral imaging, or that the scene is not static in the case of video imaging.

Consider a collection of significance regions <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M44','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M44">View MathML</a>, such that one declares <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M45','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M45">View MathML</a> if the test statistic <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M46','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M46">View MathML</a>. The pFDR for multiple, nonidentical hypothesis tests can be defined in terms of the significance regions as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M47','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M47">View MathML</a>

(8)

where

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M48','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M48">View MathML</a>

(9)

is the number of falsely rejected null hypotheses,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M49','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M49">View MathML</a>

(10)

is the total number of rejected null hypotheses, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M50">View MathML</a> if event E is true and 0 otherwise. In our setup, the pFDR corresponds to the expected ratio of the number of missed targets to the number of signals declared to be nontargets subject to the condition that at least one signal is declared to be a nontarget (note that this ratio is traditionally referred to as the positive false nondiscovery rate (pFNR), but is technically the pFDR in this context because of our definitions of the null and alternate hypotheses). The theorem below presents our main result:

Theorem 2

Given observations of the form (2), if one performs multiple, independent, nonidentical hypothesis tests of the form (5) and decides according to (7), then the worst-case pFDR given by pFDRmax=maxj∈{1,…,m}pFDR(j)(Γ), satisfies the following bound:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M51','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M51">View MathML</a>

(11)

where

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M52','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M52">View MathML</a>

(12)

The proof of this theorem is detailed in Appendix 2. A key element of our proof is the adaptation of the techniques from [48] to nonidentical independent hypothesis tests.

An achievable bound on the worst-case pFDR

Theorem 2 in the preceding section shows that, for a given A, the worst-case pFDR is bounded from above by a function of the worst-case misclassification probability. In this section, we use this theorem to establish an achievable bound on the worst-case pFDR that explicitly depends on the number of observations K, signal strengths <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M53','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M53">View MathML</a>, similarity among different targets of interest, and a priori target probabilities.

Let us first define the quantities

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M54','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M54">View MathML</a>

Then we have the following theorem, whose proof is given in Appendix 3:

Theorem 3

Let λmax denote the largest eigenvalue of Σb. For a given 0 < ε < 1−pmax, assume that K and N are sufficiently large so that the following conditions hold:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M55','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M55">View MathML</a>

(13a)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M56','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M56">View MathML</a>

(13b)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M57','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M57">View MathML</a>

(13c)

Then there exists a K×N sensing matrix Athat satisfies the condition of Theorem 1, and for which

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M58','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M58">View MathML</a>

(14)

This result has the following implications and consequences:

(1) For a given N, the upper bound (13b) on λmaxincreases as K increases, which implies that the system can tolerate more background perturbation if we collect more measurements.

(2) The pFDR bound (14) decays with the increase in the values of K, dminand αmin, and increases as pmindecreases. For a fixed pmax, pmin, αminand dmin, the bound in (14) enables one to choose a value of K to guarantee a desired pFDR value.

(3) The dominant part of the bound (14) is independent of N, and is only a function of K, pmax, pmin, αmin, and dmin. The lack of dependence on N is not unexpected. Indeed, when we are interested in preserving pairwise distances among the members of a fixed dictionary of size m, the Johnson–Lindenstrauss lemma [49] says that, with high probability, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M59','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M59">View MathML</a> random Gaussian projections suffice, regardless of the ambient dimension N. This is precisely the regime we are working with here.

(4) The bound on K given in (13c) increases logarithmically with the increase in the difference between pmax and pmin. This is to be expected since one would need more measurements to detect a less probable target as our decision rule weights each target by its a priori probability. If all targets are equally likely, then pmax=pmin=1/m, and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M60','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M60">View MathML</a> is sufficient provided <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M61','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M61">View MathML</a> is sufficiently large such that

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M62','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M62">View MathML</a>

(where the first inequality holds since K < N). In addition, the lower bound on K also illustrates the interplay between the signal strength of the targets, the similarity among different targets in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M63','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M63">View MathML</a>, and the number of measurements collected. A small value of dmin suggests that the targets in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M64','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M64">View MathML</a> are very similar to each other, and thus αminand K need to be high enough so that similar targets can still be distinguished. The experimental results discussed in Section “Experimental results” illustrate the tightness of the theoretical results discussed here.

Inspection of the proof shows that if Ais generated according to a Gaussian distribution, then the conditions of Theorem 3 will be met with high probability.

Extension to a manifold-based target detection framework

The DSD problem formulation in Section “ASD problem formulation” is accurate if the signals in the dictionary are faithful representations of the target signals that we observe. In reality, however, the target signals will differ from the dictionary signals owing to the differences in the experimental conditions under which they are collected. For instance, in spectral imaging applications, the observed spectrum of any material will not match the reference spectrum of the same material observed in a laboratory because of the differences in atmospheric and illumination conditions. To overcome this problem, one could form a large dictionary to account for such uncertainties in the target signals and perform target detection according to the approaches discussed in Sections “Whitening compressive observations” and “Dictionary signal detection”. A potential drawback with this approach is that our theoretical performance bound increases with the size of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M65">View MathML</a> through pmin and dmin. Instead, one could reasonably model the target signals observed under different experimental conditions to lie in a low-dimensional submanifold of the high-dimensional ambient signal space as shown to be true for spectral images in [50]. We can exploit this result to extend our analysis to a much broader framework that accounts for uncertainties in our dictionary.

Let us consider a dictionary of manifolds <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M66','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M66">View MathML</a> corresponding to m different target classes, and that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M67">View MathML</a> for i∈{1,…,M} is in one of the manifolds in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M68','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M68">View MathML</a>. Considering an observation model of the form given in (2), our goal is to determine <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M69','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M69">View MathML</a>, where j∈{1,…,m} is the target class of interest. Let us assume that all target classes are equally likely to keep the presentation simple, though the analysis extends to the case where the targets classes have different a priori probabilities. Suppose that we collect independent sets of measurements <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M70','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M70">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M71','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M71">View MathML</a>. Then, we can use the following two-step procedure to extend our DSD method to this manifold-based framework:

(1) Given {yi}, form a data-dependent dictionary <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M72','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M72">View MathML</a> corresponding to each yi by finding its nearest-neighbor in each manifold:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M73','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M73">View MathML</a>

for ℓ∈{1,…,m} and i=1,…,M.

(2) Given <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M74','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M74">View MathML</a> and corresponding <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M75','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M75">View MathML</a>, find

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M76">View MathML</a>

and declare that the ith observed spectrum corresponds to class j if <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M77','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M77">View MathML</a>.

This two-step procedure is studied in [3] for the case <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M78','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M78">View MathML</a> where the authors provide bounds on the number of projection measurements needed to preserve distances among manifolds. However, they do not offer associated target detection performance guarantees. Our analysis and the theoretical performance bounds extend directly to this framework, if we collect two sets of observations as discussed above. Specifically, the hypothesis tests corresponding to the second step can be written as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M79','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M79">View MathML</a>

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M80">View MathML</a> for i=1,…,M. Since the dictionary in this case changes with i, these tests are nonidentical. This is another instance where our extension of pFDR-based analysis towards simultaneous testing of multiple, independent, and nonidentical hypothesis tests (8) is very significant. Following the proof techniques discussed in the appendix, we can straightforwardly show that the bound in (14) in this manifold setting holds with pmin=pmax=1/m since all target classes are assumed to be equally likely here, and dmin=mini∈{1,…,M}diwhere

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M81','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M81">View MathML</a>

Anomalous signal detection

The target detection approach discussed above assumes that the target signal of interest resides in a dictionary that is available to the user. However, in some applications (such as military applications and surveillance), one might be interested in detecting objects not in the dictionary. In other words, the target signals of interest are anomalous and are not available to the user. In this section, we show how the target detection methods discussed above can be extended to anomaly detection. In particular, we exploit the distance preservation property of the sensing matrix A to detect anomalous targets from projection measurements.

ASD problem formulation

Given observations of the form in (2), we are interested in detecting whether <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M82','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M82">View MathML</a> or fis anomalous. Let us write the anomaly detection problem as the following multiple hypothesis test:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M83','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M83">View MathML</a>

(15a)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M84','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M84">View MathML</a>

(15b)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M85','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M85">View MathML</a> is a user-defined threshold that encapsulates our uncertainty about the accuracy with which we know the dictionary.a In particular, τ controls how different a signal needs to be from every dictionary element to truly be considered anomalous. In the absence of any prior knowledge on the targets of interest, τ can simply be set to zero. The null hypothesis in this setting models the normal behavior, while the alternative hypothesis models the abnormal or anomalous behavior. This formulation is consistent with the literature [26,38].

Note that the definition of the hypotheses given in (15a) and (15b) matches the definition in (5) for the special case where the dictionary contains just one signal. In this special case, the signal input f is in the dictionary under the null hypothesis in both DSD and ASD problem formulations.b

Anomaly detection approach

Our anomaly detection approach and the associated theoretical analysis are based on a “distance preservation” property of A, which is stated formally in (18). We propose an anomaly detection method that controls the FDR below a desired level δ for different background and sensor noise statistics. In other words, we control the expected ratio of falsely declared anomalies to the total number of signals declared to be anomalous. Note that here we work with the FDR as opposed to the pFDR, since it is possible for a scene to not contain any anomalies at all. We let V/R=0 for R=V=0 since one does not declare any signal to be anomalous in this case. In [29], Benjamini and Hochberg discuss a p-value based procedure, “BH procedure”, that controls the FDR of M independent hypothesis tests below a desired level. Let,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M86">View MathML</a>

(16)

be the test statistic at the ith location. The p-value can be defined in terms of our test statistic as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M87','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M87">View MathML</a>

(17)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M88','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M88">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M89','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M89">View MathML</a> is independent of ni. This is the probability under the null hypothesis, of acquiring a test statistic at least as extreme as the one observed. Let us denote the ordered set of p-values by p(1)≤p(2)≤⋯≤p(M) and let <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M90','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M90">View MathML</a> be the null hypothesis corresponding to (i)thp-value. The BH procedure says that if we reject all <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M91','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M91">View MathML</a> for i=1,…,t where t is the largest i for which p(i)≤iδ/M, then the FDR is controlled at δ.

To apply this procedure in our setting, we need to find a tractable expression for the p-value at every location. This can be accomplished when A satisfies the distance-preservation condition stated below. Let <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M92">View MathML</a> be the set of all signals in the dictionary and the ones whose projections are measured. Note that |V|≤M + m. For a given ε∈(0,1), a projection operator <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M93">View MathML</a>, K≤N, is distance-preserving on V if the following holds for all u,v∈V:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M94','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M94">View MathML</a>

(18)

The existence of such projection operators is guaranteed by the celebrated Johnson and Lindenstrauss (JL) lemma [49], which says that there exists random constructions of A for which (18) holds with probability at least 1−2|V|2e−Kc(ε)provided <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M95','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M95">View MathML</a>, where c(ε)=ε2/16−ε3/48 [51,52]. Examples of such constructions are: (a) Gaussian matrices whose entries are drawn from <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M96','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M96">View MathML</a>, (b) Bernoulli matrices whose entries are <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M97','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M97">View MathML</a> with probability 1/2, (c) random matrices whose entries are <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M98','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M98">View MathML</a> with probability 1/6 and zero with probability 2/3 [51,52], and (d) matrices that satisfy the restricted isometry property (RIP) where the signs of the entries in each column are randomized [53].

We now state our main theorem that gives a tight upper bound on the p-value at every location when {αi} are unknown and are estimated from the observations. Let <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M99">View MathML</a> be the estimates of {αi} that satisfy

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M100','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M100">View MathML</a>

(19)

for i=1,…,M where ζ∈[0,1] is a measure of the accuracy of the estimation procedure.

Theorem 4

If the ith hypothesis test is defined according to (15a) and (15b), the projection matrix A satisfies (18) for a given ε∈(0,1), and the estimates <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M101">View MathML</a> satisfy (19) for some ζ∈[0,1], then the bound

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M102','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M102">View MathML</a>

(20)

holds for all i=1,…,M where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M103','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M103">View MathML</a> is the CDF of a noncentral χ2random variable with K degrees of freedom and noncentrality parameter ν [54].

The proof of this theorem is given in Appendix 4. We find the p-value upper bounds at every location and use the BH procedure to perform anomaly detection. The performance of this procedure depends on the values of K, {αi}, τ and ε. The parameter ε is a measure of the accuracy with which the projection matrix A preserves the distances between any two vectors in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M104','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M104">View MathML</a>. A value of ε close to zero implies that the distances are preserved fairly accurately. When {αi} are unknown and estimated from the observations, the performance depends on the accuracy of the estimation procedure, which is reflected in our bounds in (20) through ζ.

One can easily estimate {αi} from {yi} for some choices of A. For instance, if the entries of the projection matrix Aare drawn from <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M105','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M105">View MathML</a>, the {αi} can be estimated using a maximum likelihood estimator (MLE) by exploiting the statistics of the projection matrix and noise. Note that the jth element of the ith measured spectrum is <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M106','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M106">View MathML</a> for j∈{1,…,K}. Since <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M107','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M107">View MathML</a> according to our problem formulation, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M108','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M108">View MathML</a>. The MLE of αi given by <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M109','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M109">View MathML</a> then reduces to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M110','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M110">View MathML</a>

(21)

In practice, we use <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M111','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M111">View MathML</a> where the (a) + =a if a≥0 and 0 otherwise to ensure that ∥yi2−K is nonnegative. We can use concentration inequalities to show that with high probability, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M112','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M112">View MathML</a> is tightly concentrated around its mean <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M113','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M113">View MathML</a>. Since <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M114','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M114">View MathML</a>, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M115','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M115">View MathML</a>. From ( [55], Lemma 2.2), and ( [56], Proposition 1 and Remark 1), for any t > 0

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M116','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M116">View MathML</a>

(22)

for some absolute constants C,c > 0. This result shows that with high probability, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M117','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M117">View MathML</a> is nonnegative.

The experimental results discussed in Section “Experimental results” demonstrate the performance of this detector as a function of K, {αi} and τ when {αi} are known and as a function of K, τ and ζ when {αi} are estimated.

Experimental results

In the experiments that follow, the entries of Aare drawn from <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M118','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M118">View MathML</a>.

Dictionary signal detection

To test the effectiveness of our approach, we formed a dictionary <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M119','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M119">View MathML</a> of nine spectra (corresponding to different kinds of trees, grass, water bodies and roads) obtained from a labeled HyMap (Hyperspectral Mapper) remote sensing data set [57], and simulated a realistic dataset using the spectra from this dictionary. Each HyMap spectrum is of length N=106. We generated projection measurements of these data such that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M120','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M120">View MathML</a> according to (1), where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M121','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M121">View MathML</a>, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M122','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M122">View MathML</a> for i=1,…,8100, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M123','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M123">View MathML</a> such that Σb satisfies the condition in (4), and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M124','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M124">View MathML</a> where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M125','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M125">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M126','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M126">View MathML</a> denotes uniform distribution. We let σ2=5 and model {αi} to be proportional to <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M127','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M127">View MathML</a> to account for the fact that the total observed signal energy increases as the number of detectors increases. We transform the ziby a series of operations to arrive at a model of the form discussed in (2), which is <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M128','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M128">View MathML</a>. For this dataset, pmin=0.04938, pmax=0.1481, and dmin=0.04341.

We evaluate the performance of our detector (7) on the transformed observations, relative to the number of measurements K, by comparing the detection results to the ground truth. Our MAP detector returns a label <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M129','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M129">View MathML</a> for every observed spectrum which is determined according to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M130','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M130">View MathML</a>

where m is the number of signals in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M131','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M131">View MathML</a>, and p(ℓ) is the a priori probability of target class ℓ. In our experiments we evaluate the performance of our classifier when (a) {αi} are known (AK) and (b) {αi} are unknown (AU) and must be estimated from y, respectively. The empirical pFDR(j)for each target spectrum j is calculated as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M132','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M132">View MathML</a>

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M133','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M133">View MathML</a> denote the ground truth labels. The empirical pFDR(·)is the ratio of the number of missed targets to the total number of signals that were declared to be nontargets. The plots in Figure 1a show the results obtained using our target detection approach under the AK case (shown by a dark gray dashed line) and the AU case (shown by a light gray dashed line), compared to the theoretical upper bound (shown by a solid line). These results are obtained by averaging the pFDR values obtained over 1000 different noise, sensing matrix and background realizations. Note that theoretical results only apply to the AK case since they were derived under the assumption of {αi} being known. The experimental results are shown for both AK and AU cases to provide a comparison between the two scenarios. In both these cases, the worst-case empirical pFDR curves decay with the increase in the values of K. In the AK case, in particular, the worst-case empirical pFDR curve decays at the same rate as the upper bound. In this experiment, for a fixed αminand dmin, we chose K to satisfy (13c). The theory is somewhat conservative, and in practice the method works well even when the values of K are below the bound in (13c).

thumbnailFigure 1. Compressive target detection results under the AK (} known) and AU ({αi} unknown) cases respectively as a function of K.(a) Comparison of the worst-case empirical pFDR curves with the theoretical bounds when SNR is high. (b) Comparison of the results obtained by the proposed method using projection measurements using Φdesigned according to (24), Φchosen at random, and the ones using downsampled measurements (DM) when the SNR is low.

In the experiment that follows, we let <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M134','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M134">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M135','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M135">View MathML</a> denotes a uniform random variable, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M136','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M136">View MathML</a> and evaluate the performance of our detector for different values of K that are not necessarily chosen to satisfy (13c). In addition, we also compare the performance of our detection method to that of a MAP based target detector operating on downsampled versions of our simulated spectral input image. The reason behind such a comparison is to show what kinds of measurements yield better results given a fixed number of detectors.

For an input spectrum <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M137','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M137">View MathML</a>, we let <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M138','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M138">View MathML</a> denote its downsampled approximation. Specifically, the jth element of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M139','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M139">View MathML</a> is <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M140','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M140">View MathML</a> where r=⌈N/K⌉. Let us consider making observations of the form

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M141','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M141">View MathML</a>

(23)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M142','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M142">View MathML</a> is the K-dimensional downsampled version of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M143','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M143">View MathML</a> for KN, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M144','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M144">View MathML</a> for σ2=5 and c is a constant that is chosen to preserve the mean signal-to-noise ratio corresponding to the downsampled and projection measurements. The MAP-based detector operating on the downsampled data returns a label <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M145','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M145">View MathML</a> for every observed spectrum which is determined according to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M146','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M146">View MathML</a>

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M147','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M147">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M148','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M148">View MathML</a> is the covariance matrix obtained from the downsampled versions of the background training data and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M149','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M149">View MathML</a> is the downsampled version of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M150','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M150">View MathML</a>. The algorithm declares that target spectrum <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M151','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M151">View MathML</a> is present in the ith location if <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M152','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M152">View MathML</a>. In order to illustrate the advantages of using a Φdesigned according to (24), we compare the performances of the proposed anomaly detector when Φis chosen to be a random Gaussian matrix whose entries are drawn from <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M153','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M153">View MathML</a> and when Φ is chosen according to (24). Figure 1b shows a comparison of the results obtained using the projection measurements obtained using Φ designed according to (24), Φ chosen at random, and the downsampled measurements under the AK case. These results show that the detection algorithm operating on projection measurements using Φdesigned using background and sensor noise statistics yield significantly better results than the one operating on the downsampled data, and that the empirical pFDR values in our method decays with K. The improvement in performance using projection measurements comes from the distance-preservation property of the projection operator A. While a Gaussian sensing matrix Apreserves distances between any pair of vectors from a finite collection of vectors with high probability [51,52], downsampling loses some of the fine differences between similar-looking spectra in the dictionary. Furthermore, when Φ is chosen at random, the resulting whitened transformation matrix is not necessarily distance-preserving. This may worsen the performance as illustrated in Figure 1b.

Anomaly detection

In this section, we evaluate the performance of our anomaly detection method on (a) a simulated dataset and provide a comparison of the results obtained using the proposed projection measurements and the ones obtained using downsampled measurements, and (b) real AVIRIS (Airborne Visible InfraRed Imaging Spectrometer) dataset.

Experiments on simulated data

We simulate a spectral image fcomposed of 8100 spectra, where each of them is either drawn from a dictionary <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M154','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M154">View MathML</a> consisting of five labeled spectra from the HyMap data that correspond to a natural landscape (trees, grass and lakes) or is anomalous. The anomalous spectrum is extracted from unlabeled AVIRIS data, and the minimum distance between the anomalous spectrum f(a) and any of the spectra in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M155','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M155">View MathML</a> is <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M156','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M156">View MathML</a>. The simulated data has 625 locations that contain the anomalous spectrum. Our goal is to find the spatial locations that contain the anomalous AVIRIS spectrum given noisy measurements of the form <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M157','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M157">View MathML</a> where bi∼(μb,Σb), Φ is designed according to (24), <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M158','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M158">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M159','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M159">View MathML</a> under <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M160','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M160">View MathML</a>. As discussed in Section “Anomalous signal detection”, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M161','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M161">View MathML</a> is anomalous under <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M162','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M162">View MathML</a>, and our goal is to control the FDR below a user-specified false discovery level δ. We simulate <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M163','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M163">View MathML</a> where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M164','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M164">View MathML</a>. In this experiment we assume the availability of background training data to estimate the background statistics and the sensor noise variance σ2. Given the knowledge of the background statistics, we perform the whitening transformation discussed in Section “Whitening compressive observations” and evaluate the detection performance on the preprocessed observations given by (2).

For a fixed τ=0.1 and ε=0.1, we evaluate the performance of the detector as the number of measurements K increases under the AK and AU cases respectively, by comparing the pseudo-ROC (receiver operating characteristic) curves obtained by plotting the empirical FDR against 1−FNR, where FNR is the false nondiscovery rate. Note that 1−FNR is the expected ratio of the number of null hypotheses that are correctly rejected to the number of declared null hypotheses. The empirical FDR and FNR are computed according to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M165','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M165">View MathML</a>

where ptis the p-value threshold such that the BH procedure rejects all null hypotheses for which pipt, and the ground truth label <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M166','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M166">View MathML</a> if the ith spectrum is not anomalous, and 1 otherwise. In this experiment, we consider three different values of K approximately given by K∈{N/6,N/3,N/2} where N=106, and evaluate the performance of our detector for each K. Furthermore, in our experiments with simulated data, we declare a spectrum to be anomalous if diη where η is a user-specified threshold and diis defined in (16). We use the p-value upper bound in (20) in our experiments with real data where the ground truth is unknown.

We compare the performance of our method to a generalized likelihood ratio test (GLRT)-based procedure operating on downsampled data, where we collect measurements of the form in (23) and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M167','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M167">View MathML</a> under <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M168','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M168">View MathML</a>. Observe that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M169','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M169">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M170','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M170">View MathML</a> refers to the downsampled version of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M171','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M171">View MathML</a>. In this experiment we assume that each spectrum in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M172','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M172">View MathML</a> is equally likely under <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M173','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M173">View MathML</a> for i=1,…,M. The GLRT-based approach declares the ith spectrum to be anomalous if

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M174','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M174">View MathML</a>

for i=1,…,M, where η is a user-specified threshold [26]. While our anomaly detection method is designed to control the FDR below a user-specified threshold, the GLRT-based method is designed to increase the probability of detection while keeping the probability of false alarm as low as possible. To facilitate a fair evaluation of these methods, we compare the pseudo-ROC curves (FDR versus 1−FNR) and the actual ROC curves (probability of false alarm pfversus probability of detection pd) corresponding to these methods obtained by averaging the empirical FDR, FNR, pd and pf over 1,000 different noise and sensing matrix realizations for different values of K. We also compare the performance of the proposed method when Φis chosen according to (24) and when it is chosen at random, as discussed in the previous section. Figure 2a,e show the pseudo-ROC plots and the conventional ROC plots obtained using the GLRT-based method operating on downsampled data when {αi} are known. Figure 2b,f show the results obtained by using a random Gaussian Φ instead of the Φ in (24). Figure 2c,g show the pseudo-ROC plots and the conventional ROC plots obtained using our method when {αi} are known. These plots show that performing anomaly detection from our designed projection measurements yields better results than performing anomaly detection on downsampled measurements and on measurements obtained using a random Gaussian Φ. This is largely due to the fact that carefully chosen projection measurements preserve distances (up to a constant factor) among pairs of vectors in a finite collection, where as the downsampled measurements fail to preserve distances among vectors that are very similar to each other. Similarly, a random projection matrix Φ is not necessarily distance-preserving post-whitening transformation, which leads to poor performance as illustrated in Figure 2b,f. Figure 2d,h shows the pseudo-ROC plots and the conventional ROC plots obtained using our method when {αi} are unknown, and are estimated from the measurements. Note that the value of ζ decreases as K increases since the estimation accuracy of {αi} increases with increase in K. These plots show that the performance improves as we collect more observations, and that, as expected, the performance under the AK case is better than the performance under the AU case.

thumbnailFigure 2. Comparison of the performances of the proposed anomaly detector using a random Φ, the proposed anomaly detector using the designed Φin (24) and the GLRT-based method operating on downsampled data for different values of Kwhen <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M177','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M177">View MathML</a> and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M178','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M178">View MathML</a>.

Experiments on real AVIRIS data

To test the performance of our anomaly detector on a real dataset, we consider the unlabeled AVIRIS Jasper Ridge dataset <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M179','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M179">View MathML</a>, which is publicly available from the NASA AVIRIS website, http://aviris.jpl.nasa.gov/html/aviris.freedata.html webcite. We split this data spatially to form equisized training and validation datasets, gt and gv respectively, each of which is of size 128×128×197. Figure 3a,b show images of the AVIRIS training and validation data summed through the spectral coordinates. The training data are comprised of a rocky terrain with a small patch of trees. The validation data seems to be made of a similar rocky terrain, but also contain an anomalous lake-like structure. The goal is to evaluate the performance of the detector in detecting the anomalous region in the validation data for different values of K. We cluster the spectral targets in the normalized training data to eight different clusters using the K-means clustering algorithm and form a dictionary <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M180','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M180">View MathML</a> comprising of the cluster centroids. Given the dictionary and the validation data, we find the ground truth by labeling the ith validation spectrum as anomalous if <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M181','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M181">View MathML</a>. Since the statistics of the possible background contamination in the data could not be learned in this experiment because of the lack of labeled training data, the dictionary might be background contaminated as well. The parameter τencapsulates this uncertainty in our knowledge of the dictionary. In this experiment, we set τ=0.2.

thumbnailFigure 3. Anomaly detection results corresponding to real AVIRIS data for a fixed FDR control of 0.01.

We generate measurements of the form <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M182','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M182">View MathML</a> for i=1,…,128×128, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M183','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M183">View MathML</a>. The <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M184','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M184">View MathML</a> factor indicates that the observed signal strength increases with K. For a fixed FDR control value of 0.01, Figure 3c,d shows the results obtained for KN/5 and KN/2, respectively. Figure 3e shows how the probability of error decays as a function of the number of measurements K. The results presented here are obtained by averaging over 1,000 different noise and sensing matrix realizations. From these results, we can see that the number of detected anomalies increases with K and the number of misclassifications decrease with K.

Conclusion

This work presents computationally efficient approaches for detecting known targets and anomalies of different strengths from projection measurements without performing a complete reconstruction of the underlying signals, and offers theoretical bounds on the worst-case target detector performance. This article treats each signal as independent of its spatial or temporal neighbors. This assumption is reasonable in many contexts, especially when the spatial or temporal resolution is low relative to the spatial homogeneity of the environment or the pace with which a scene changes. However, emerging technologies in computational optical systems continue to improve the resolution of spectral imagers. In our future work we will build upon the methods that we have discussed here to exploit the spatial or temporal correlations in the data.

Appendix 1: Proof of Theorem 1

Using linear algebra and matrix theory, it is possible to show that if B=IAΣbAT is positive definite, then

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M185','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M185">View MathML</a>

(24)

satisfies (3).c In particular, we can substitute (24) in (3) to verify that the proposed construction of Φ satisfies (3). Observe that CΦ=(ΦΣbΦT + σ2I)−1/2 can be written in terms of (24) as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M186','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M186">View MathML</a>

(25)

where the third-to-last equation follows from the definition of B and (25) follows from the fact that B is symmetric and positive definite. If B is positive definite, then B−1 is positive definite as well and can be decomposed as B−1=(B−1/2)TB−1/2, where the matrix square root B−1/2is symmetric and positive definite. By substituting (25) and (24) in (3), we have CΦΦ=σ−1B1/2σB−1/2A=A. A sufficient condition for Bto be positive definite can be derived as follows.

To ensure positive definiteness of B, we must have

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M187','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M187">View MathML</a>

(26)

for any nonzero <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M188','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M188">View MathML</a>. Note that since Σb is positive semidefinite, xT(AΣbAT)x≥0. However, the right hand side of (26) is > 0 only if the spectral norm of AΣbATis < 1, since <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M189','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M189">View MathML</a>. The norm of AΣbAT is in turn bounded above by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M190','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M190">View MathML</a>

since ∥A∥=∥AT∥ and ∥Σb∥=λmax, where λmax is the largest eigenvalue of Σb. To ensure ∥AΣbAT∥ < 1, ∥A2λmax has to be < 1, which leads to the result of Theorem 1.

Appendix 2: Proof of Theorem 2

The proof of Theorem 2 adapts the proof techniques from [48] to nonidentical independent hypothesis tests. We begin by expanding the pFDR definition in (8) as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M191','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M191">View MathML</a>

Observe that R(Γ)=k implies that there exists some subset Sk={u1,…,uk}⊆{1,…,M} of size k such that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M192','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M192">View MathML</a> for =1,…,k and <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M193','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M193">View MathML</a> for all iSk. To simplify the notation, let <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M194','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M194">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M195','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M195">View MathML</a> is the complement of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M196','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M196">View MathML</a>, denote the significance region that corresponds to set Sk, and T=(y1,…,yM) be a set of test statistics corresponding to each hypothesis test. Considering all such subsets we have

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M197','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M197">View MathML</a>

(27)

By plugging in the definition of V({Γi}) from (9), we have

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M198','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M198">View MathML</a>

(28)

for all uSk since the tests are independent of each other given A. The posterior probability <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M199','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M199">View MathML</a> for the ithhypothesis test can be expanded using Bayes’ rule as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M200','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M200">View MathML</a>

(29)

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M201','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M201">View MathML</a>. To upper bound the numerator of (29), consider the probability of misclassification given by <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M202','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M202">View MathML</a> where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M203','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M203">View MathML</a>, which can be expanded as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M204','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M204">View MathML</a>

(30)

The denominator term in (29) can be expanded as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M205','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M205">View MathML</a>

Observe that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M206','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M206">View MathML</a> is nonnegative, and

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M207','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M207">View MathML</a>

Thus

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M208','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M208">View MathML</a>

(31)

Substituting (30) and (31) in (29),

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M209','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M209">View MathML</a>

(32)

By substituting (32) in (27) and (28) we have:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M210','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M210">View MathML</a>

since <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M211','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M211">View MathML</a>. The result of Theorem 2 is obtained by finding an upper bound on the worst-case pFDR given by

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M212','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M212">View MathML</a>

where pmax=max∈{1,…,m}p().

Appendix 3: Proof of Theorem 3

The proof is via a random selection technique, similar to random coding arguments common in information theory. Specifically, we will draw a K×N sensing matrix A at random from a particular distribution and then show that, for ε, N, and K satisfying the conditions of the theorem, the probability that the conclusions of the theorem will fail to hold for this randomly chosen Ais strictly smaller than unity. This will imply that the conclusions of the theorem must be true for at least one (deterministic) realization of A.

We begin by specifying all the relevant random variables:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M213','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M213">View MathML</a> are i.i.d. random variables taking values in the dictionary <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M214','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M214">View MathML</a> with probabilities <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M215','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M215">View MathML</a>;

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M216','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M216">View MathML</a> ;

Gis a random K×Nmatrix with i.i.d. <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M217','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M217">View MathML</a> entries.

We assume that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M218','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M218">View MathML</a>, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M219','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M219">View MathML</a>, and Gare mutually independent, and we will denote by P their joint probability distribution. Finally, we let <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M220','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M220">View MathML</a> and consider the observation model

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M221','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M221">View MathML</a>

(33)

where α1,…,αM > 0 are the given signal strengths.

We first consider the case when α1=⋯=αM=α. Given ε, N, and K, we define the following two error events:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M222','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M222">View MathML</a>

where, for each i∈{1,…,M}, <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M223','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M223">View MathML</a> is defined according to (12). Note that, since we have assumed that the αi’s are equal and all the pairs <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M224','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M224">View MathML</a>, are i.i.d.,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M225','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M225">View MathML</a>

(34)

We will now prove that

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M226','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M226">View MathML</a>

(35)

The union bound gives <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M227','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M227">View MathML</a>. First, we bound <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M228','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M228">View MathML</a>. To do that, we use the following concentration result for Gaussian random matrices [58]: for any t≥0,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M229','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M229">View MathML</a>

Letting <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M230','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M230">View MathML</a> and using the fact that t2≥(K + N)ε2, we get

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M231','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M231">View MathML</a>

(36)

Next, we bound <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M232','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M232">View MathML</a>. To that end, we use the following result, which is a straightforward extension of ( [5], Theorem 1) to nonequiprobable dictionary elements:

Lemma 1 (Compressive classification error)

Consider the problem of classifying a signal of interest <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M233','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M233">View MathML</a> to one of m known target classes by making observations of the form y=αAf + n where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M234','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M234">View MathML</a>, given the knowledge of the dictionary <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M235','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M235">View MathML</a>, prior probabilities p(j)for j∈{1,⋯,m}, sensing matrix A, and the noise variance σ2. If the entries of A are drawn i.i.d. from <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M236','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M236">View MathML</a> independently of f and n, and the estimate <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M237','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M237">View MathML</a> is obtained according to (12), then

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M238','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M238">View MathML</a>

where the probability is taken with respect to the distributions underlying f, A, and n.

Using the above lemma, we have

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M239','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M239">View MathML</a>

(37)

Combining (36) and (37), we get (35).

Because of (13a), the right-hand side of (35) is less than 1−εpmax, which is strictly positive by hypothesis. Thus, from the fact that

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M240','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M240">View MathML</a>

and from (34), it follows that there exists at least one deterministic choice of the K×N sensing matrix A, such that:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M241','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M241">View MathML</a>

(38a)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M242','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M242">View MathML</a>

(38b)

where, for a given choice of A, (Pe)max(A) denotes the maximum probability of error defined in Theorem 2.

Next, from (38a) and (13b) it follows that Asatisfies the conditions of Theorem 1. Finally, we use (11) to bound the worst-case pFDR achievable with A. First of all, we note that the function <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M243','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M243">View MathML</a> is twice differentiable and convex on the interval [0,1−pmax]. Therefore, for any x∈[0,1−pmax] and any h > 0 small enough so that x + h∈[0,1−pmax], we have

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M244','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M244">View MathML</a>

(39)

Let us choose

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M245','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M245">View MathML</a>

Then from (13a) we have x + h≤1−εpmax < 1−pmax, and from (13c) we have x + h≥0. Hence, using (39) and simplifying, we obtain the bound

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M246','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M246">View MathML</a>

This proves the theorem for the case α1=⋯=αM=α.

To handle the case when the αi’s are distinct, we simply let

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M247','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M247">View MathML</a>

and replace the definition of the error event <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M248','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M248">View MathML</a> with <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M249','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M249">View MathML</a>. Then the same argument goes through, except that instead of (34) we use the bound

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M250','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M250">View MathML</a>

which follows from the following argument. First of all, we can replace the observation model with the equivalent model

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M251','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M251">View MathML</a>

where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M252','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M252">View MathML</a>. Secondly, from the fact that αiαiαminfor any ii it follows that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M253','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M253">View MathML</a> is equal in distribution to <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M254','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M254">View MathML</a>, where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M255','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M255">View MathML</a> is independent of <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M256','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M256">View MathML</a>. This implies that the ith observation is the noisiest, and the corresponding MAP estimate <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M257','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M257">View MathML</a> has the largest probability of error.

Appendix 4: Proof of Theorem 4

We first prove this theorem assuming that {αi} are known and later extend to the case where <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M258','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M258">View MathML</a> are estimated from the observations. Let <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M259','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M259">View MathML</a>. The p-value expression in (17) can be expanded as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M260','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M260">View MathML</a>

(40)

Note that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M261','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M261">View MathML</a> is a noncentral χ2random variable with K degrees of freedom and a noncentrality parameter <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M262','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M262">View MathML</a>. Thus (40) can be written in terms of a noncentral χ2CDF <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M263','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M263">View MathML</a> with parameter <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M264','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M264">View MathML</a>. The upper and lower bounds on νican be obtained using the properties of the projection matrix A. Applying (18), we see that

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M265','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M265">View MathML</a>

with high probability. Thus,

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M266','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M266">View MathML</a>

(41)

since <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M267','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M267">View MathML</a> for all <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M268','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M268">View MathML</a> under <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M269','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M269">View MathML</a>.

When {αi} are estimated from the observations such that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M270','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M270">View MathML</a> satisfy (19), we can write the p-value expression in (41) as follows:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M271','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M271">View MathML</a>

(42)

where (42) is due to the distance preservation property of A given in (18). Observe that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M272','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M272">View MathML</a> can be upper bounded as shown below:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M273','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M273">View MathML</a>

where third-to-last equation is due to the triangle inequality, second-to-last equation comes from the assumption that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M274','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M274">View MathML</a>, and the last inequality is due to (19). By applying this result to (42) and exploiting the fact that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M275','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M275">View MathML</a> under <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M276','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M276">View MathML</a> for some <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M277','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M277">View MathML</a>, we have

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M278','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M278">View MathML</a>

Endnotes

a Note that τ cannot exceed <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M279','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M279">View MathML</a> because we assume that all targets of interest, including those in <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/205/mathml/M280','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/205/mathml/M280">View MathML</a> and the actual target f, are unit-norm.b The anomaly detection problem discussed here is more accurately described as target detection in the classical detection theory vocabulary. However, in recent works [24,25], the authors assume that the nominal distribution is obtained from training data and a test sample is declared to be anomalous if it falls outside of the nominal distribution learned form the training data. Our work is in a similar spirit where we learn our dictionary from training data and label any test spectrum that does not correspond to our dictionary as being anomalous.c The authors would like to thank Prof. Roummel Marcia for fruitful discussions related to this point.

Competing interest

The authors declare that they have no competing interests.

Acknowledgements

This work was supported by the NSF Award No. DMS-08-11062, DARPA Grant No. HR0011-09-1-0036, and AFRL Grant No. FA8650-07-D-1221.

References

  1. EJ Candès, T Tao, Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406–5425 (2006)

  2. D Donoho, Compressed sensing. IEEE Trans. Info. Theory 52(4), 1289–1306 (2006)

  3. M Davenport, M Duarte, M Wakin, J Laska, D Takhar, K Kelly, R Baraniuk, The smashed filter for compressive classification and target recognition. Proceedings of SPIE, vol. 6498 ((San Jose, CA, 2007), pp), . 142–153 OpenURL

  4. MF Duarte, MA Davenport, MB Wakin, RG Baraniuk, Sparse signal detection from incoherent projections. IEEE International Conference on Acoustics, Speech and Signal Processing, vol. 3 ((Toulouse, France, 2006), pp), . 305–308 OpenURL

  5. J Haupt, R Castro, R Nowak, G Fudge, A Yeh, in Compressive sampling for signal classification. Fortieth Asilomar Conference on Signals, Systems and Computers, (2006, pp), . 1430–1434 OpenURL

  6. S Aeron, V Saligrama, M Zhao, Information theoretic bounds for compressed sensing. Inf. IEEE Trans. Theory 56(10), 5111–5130 (2010)

  7. E Arias-Castro, Y Eldar, Noise folding in compressed sensing. IEEE Signal Process. Lett 18, 478–481 (2011)

  8. J Han, B Bhanu, Fusion of color and infrared video for moving human detection. Pattern Recogn 40(6), 1771–1784 (2007). Publisher Full Text OpenURL

  9. W Johnson, D Wilson, W Fink, M Humayun, G Bearman, Snapshot hyperspectral imaging in ophthalmology. J. Biomed. Optics 12(1), 014036–1–014036-7 (2007). Publisher Full Text OpenURL

  10. R Lin, B Dennis, A Benz, in The Reuven Ramaty High-Energy Solar Spectrscopic Imager (RHESSI) - Mission Description and Early Results (Kluwer Academic Publishers, Dordrecht, 2003) OpenURL

  11. M Martin, S Newman, J Aber, R Congalton, Determining forest species composition using high spectral resolution remote sensing data. Remote Sens. Envir 65(3), 249–254 (1998). Publisher Full Text OpenURL

  12. M Martin, M Wabuyele, K Chen, P Kasili, M Panjehpour, M Phan, B Overholt, G Cunningham, D Wilson, R DeNovo, T Vo-Dinh, Development of an advanced hyperspectral imaging (HSI) system with applications for cancer detection. Ann. Biomed. Eng 34(6), 1061–1068 (2006). PubMed Abstract | Publisher Full Text OpenURL

  13. J Miller, C Elvidge, B Rock, J Freemantle, An airborne perspective on vegetation phenology from the analysis of AVRIS data sets over the Jasper ridge biological preserve. Geoscience and Remote Sensing Symposium (IGARSS’90): Remote sensing for the nineties ((College Park, MD, 20–24 May 1990), pp), . 565–568 OpenURL

  14. C Stellman, G Hazel, F Bucholtz, J Michalowicz, A Stocker, W Schaaf, Real-time hyperspectral detection and cuing. Opt. Eng 39, 1928–1935 (2000). Publisher Full Text OpenURL

  15. K Zuzak, S Naik, G Alexandrakis, D Hawkins, K Behbehani, E Livingston, Intraoperative bile duct visualization using near-infrared hyperspectral video imaging. Am. J. Surg 195(4), 491–497 (2008). PubMed Abstract | Publisher Full Text OpenURL

  16. D Brady, M Gehm, Compressive imaging spectrometers using coded apertures. Proc. of SPIE, vol. 6246 ((Kissimmee, Florida, 2006), pp), . 62460A-1–62460A-9 OpenURL

  17. RA DeVerse, RR Coifman, AC Coppi, WG Fateley, F Geshwind, RM Hammaker, S Valenti, FJ Warner, GL Davis, Application of Spatial Light Modulators for New Modalities in Spectrometry and Imaging. Spectral Imaging: Instrumentation, Applications, and Analysis II, vol. 4959, ed. by RM Levenson, GH Bearman, A Mahadevan-Jansen ((2003), pp), . 12–22 OpenURL

  18. M Gehm, R John, D Brady, R Willett, T Schulz, Single-shot compressive spectral imaging with a dual-disperser architecture. Opt. Express 15(21), 14013–14027 (2007). PubMed Abstract | Publisher Full Text OpenURL

  19. D Takhar, J Laska, MB Wakin, MF Duarte, D Baron, S Sarvotham, K Kelly, RG Baraniuk, A new compressive imaging camera architecture using optical-domain compression. Proc. IS&T/SPIE Symposium on Electronic Imaging ((San Jose, CA, 2006), pp), . 43–52 PubMed Abstract | Publisher Full Text OpenURL

  20. A Wagadarikar, R John, R Willett, D Brady, Single disperser design for coded aperture snapshot spectral imaging. Appl. Opt 47(10), B44–B51 (2008). PubMed Abstract | Publisher Full Text OpenURL

  21. F Woolfe, M Maggioni, G Davis, F Warner, R Coifman, S Zucker, Hyper-spectral microscopic discrimination between normal and cancerous colon biopsies Manuscript (2006)

  22. D Manolakis, D Marden, G Shaw, Hyperspectral image processing for automatic target detection applications. Lincoln Laboratory J 14(1), 79–116 (2003)

  23. G Wei, L Agnihotri, N Dimitrova, TV program classification based on face and text processing. 2000 IEEE International Conference on Multimedia and Expo, ICME 2000, vol. 3 ((2000), pp), . 1345–1348 OpenURL

  24. AO Hero, Geometric entropy minimization (GEM) for anomaly detection and localization. Proc. Advances in Neural Information Processing Systems (NIPS) ((MIT Press, Vancouver, Canada, 2006), pp), . 585–592 OpenURL

  25. I Steinwart, D Hush, C Scovel, A classification framework for anomaly detection. J. Mach. Learn. Res 6, 211–232 (2005)

  26. D Stein, S Beaven, L Hoff, E Winter, A Schaum, A Stocker, Anomaly detection from hyperspectral imagery. IEEE Signal Process. Mag 19(1), 58–69 (2002). Publisher Full Text OpenURL

  27. D Manolakis, G Shaw, Detection algorithms for hyperspectral imaging applications. IEEE Signal Process. Mag 19(1), 29–43 (2002). Publisher Full Text OpenURL

  28. JO Berger, in Statistical Decision Theory and Bayesian Analysis, (Springer, New York, 1985) OpenURL

  29. Y Benjamini, Y Hochberg, Controlling the false discovery rate: a practical and powerful approach to multiple testing. J. R. Stat. Soc. Ser. B (Methodological) 57(1), 289–300 (1995)

  30. X Jin, S Paswaters, H Cline, A comparative study of target detection algorithms for hyperspectral imagery. Proceedings of SPIE, vol. 7334 ((2009), p), . 73341W OpenURL

  31. E Kelly, An adaptive detection algorithm. IEEE Trans. Aerospace Electron. Syst. AES- 22(2), 115–127 (1986)

  32. S Kraut, L Scharf, L McWhorter, Adaptive subspace detectors. IEEE Trans. Signal Processing 49(1), 1–16 (2001). Publisher Full Text OpenURL

  33. L Scharf, B Friedlander, Matched subspace detectors. IEEE Trans. Signal Process 42(8), 2146–2157 (1994). Publisher Full Text OpenURL

  34. H Kwon, N Nasrabadi, Kernel matched subspace detectors for hyperspectral target detection. IEEE Trans. Pattern Anal. Mach. Intell 28(2), 178–194 (2006). PubMed Abstract | Publisher Full Text OpenURL

  35. LL Scharf, LT McWhorter, Adaptive matched subspace detectors and adaptive coherence estimators. Conference Record of the Thirtieth Asilomar Conference on Signals, Systems and Computers ((Pacific Grove, CA, 1996), pp), . 1114–1117 OpenURL

  36. M Parmar, S Lansel, B Wandell, Spatio-spectral reconstruction of the multispectral datacube using sparse recovery. 15th IEEE International Conference on Image Processing ((San Diego, CA, 2008), pp), . 473–476 OpenURL

  37. R Willett, M Gehm, D Brady, Multiscale reconstruction for computational spectral imaging. Comput. Imag. V 6498, 64980L–1–64980L-15 (2007)

  38. J Fowler, Q Du, Anomaly detection and reconstruction from random projections. IEEE Trans. Image Process 21(1), 184–195 (2012). PubMed Abstract | Publisher Full Text OpenURL

  39. I Reed, X Yu, Adaptive multiple-band CFAR detection of an optical pattern with unknown spectral distribution. IEEE Trans. Acoust. Speech Signal Process 38(10), 1760–1770 (1990). Publisher Full Text OpenURL

  40. K Krishnamurthy, M Raginsky, R Willett, Hyperspectral target detection from incoherent projections. IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP) ((Dallas, TX, 2010), pp), . 3550–3553 OpenURL

  41. K Krishnamurthy, M Raginsky, R Willett, Hyperspectral target detection from incoherent projections: nonequiprobable targets and inhomogenous SNR. 17th IEEE International Conference on Image Processing (ICIP) ((Hongkong, 2010), pp), . 1357–1360 OpenURL

  42. JW Boardman, in Spectral Angle Mapping: A Rapid Measure of Spectral Similarity (AVIRIS, 1993) OpenURL

  43. Z Guo, S Osher, Template matching via L1 minimization and its application to hyperspectral data Accepted to Inverse Problems and Imaging (IPI), 2009

  44. H Kwon, N Nasrabadi, Kernel RX-algorithm: a nonlinear anomaly detector for hyperspectral imagery. IEEE Trans. Geosci. Remote Sens 43(2), 388–397 (2005)

  45. A Szlam, Z Guo, S Osher, A split Bregman method for non-negative sparsity penalized least squares with applications to hyperspectral demixing. IEEE 17th International Conference on Image Processing (ICIP) ((Hongkong, 2010), pp), . 1917–1920 OpenURL

  46. C Chang, Virtual dimensionality for hyperspectral imagery. SPIE Newsroom 10(2.1200909), 1749 (2009)

  47. C Chang, Q Du, Estimation of number of spectrally distinct signal sources in hyperspectral imagery. IEEE Trans. Geosci. Remote Sens 42(3), 608–619 (2004). Publisher Full Text OpenURL

  48. J Storey, The positive false discovery rate: a Bayesian interpretation and the q-value. Ann. Stat, 2013–2035 (2003)

  49. W Johnson, J Lindenstrauss, Extensions of Lipschitz maps into a Hilbert space. Contemp. Math 26, 189–206 (1984)

  50. G Healey, D Slater, Models and methods for automated material identification in hyperspectral imagery acquired under unknown illumination and atmospheric conditions. IEEE Trans. Geosci. Remote Sens 37(6), 2706–2717 (1999). Publisher Full Text OpenURL

  51. D Achlioptas, Database-friendly random projections. Proc. 20th ACM Symp. Principles of Database Systems ((ACM Press, New York, NY 2001), pp), . 274–281 OpenURL

  52. R Baraniuk, M Davenport, R DeVore, M Wakin, A simple proof of the restricted isometry property for random matrices. Constructive Approx 28(3), 253–263 (2008). Publisher Full Text OpenURL

  53. F Krahmer, R Ward, New and improved johnson-lindenstrauss embeddings via the restricted isometry property. SIAM Journal on Mathematical Analysis 43(3), 1269–1281 (Arxiv preprint arXiv:1009, 2011), . 0744, 2010 Publisher Full Text OpenURL

  54. L Wasserman, in All of Statistics: A Concise Course in Statistical Inference (Springer, New York, NY 2004) OpenURL

  55. T Tao, V Vu, On random±1 matrices: singularity and determinant. Random Struct. Algor 28(1), 1–23 (2006). Publisher Full Text OpenURL

  56. T Tao, Talagrand’s concentration inequality, (http://terrytao), . wordpress.com/2009/06/09/talagrands-concentration-inequality/ webcite. Accessed on 08/03/2012

  57. FA Kruse, JW Boardman, AB Lefkoff, JM Young, KS Kierein-Young, TD Cocks, R Jensen, PA Cocks, HyMap: an Australian hyperspectral sensor solving global problems-results from USA HyMap data acquisitions. Proc. of the 10th Australasian Remote Sensing and Photogrammetry Conference ((Adelaide, Australia, 2000), pp), . 18–23 OpenURL

  58. KR Davidson, SJ Szarek, Local operator theory, random matrices and Banach spaces. ((North-Holland, Amsterdam, 2001), pp), . 317–366