Submitted
arXiv: 1509.07566

DETECTING SPARSE MIXTURES: RATE OF DECAY OF
ERROR PROBABILITY ¶

arXiv:1509.07566v2 [] 24 Dec 2016

By Jonathan G. Ligok , George V. Moustakides†† and Venugopal
V. Veeravallik
University of Illinois at Urbana-Champaignk , University of Patras†† and
Rutgers University††
We study the rate of decay of the probability of error for distinguishing between a sparse signal with noise, modeled as a sparse
mixture, from pure noise. This problem has many applications in signal processing, evolutionary biology, bioinformatics, astrophysics and
feature selection for machine learning. We let the mixture probability tend to zero as the number of observations tends to infinity and
derive oracle rates at which the error probability can be driven to
zero for a general class of signal and noise distributions via the likelihood ratio test. In contrast to the problem of detection of non-sparse
signals, we see the log-probability of error decays sublinearly rather
than linearly and is characterized through the χ2 -divergence rather
than the Kullback-Leibler divergence for “weak” signals and can be
independent of divergence for “strong” signals. Our contribution is
the first characterization of the rate of decay of the error probability
for this problem for both the false alarm and miss probabilities.

1. Introduction. We consider the problem of detecting a sparse signal
in noise, modeled as a mixture, where the unknown sparsity level decreases
as the number of samples collected increases. Of particular interest is the
case where the unknown signal strength relative to the noise power is very
small. This problem has many natural applications. In signal processing, applications include detecting a signal in a multi-channel system [10, 16] and
detecting covert communications [11]. In evolutionary biology, the problem
manifests in the reconstruction of phylogenetic trees in the multi-species
coalescent model [20]. In bioinformatics, the problem arises in the context
of determining gene expression from gene ontology datasets [15]. In astrophysics, detection of sparse mixtures is used to compare models of the cosmic
microwave background to observed data [5]. Also, statistics developed from
the study of this problem have been applied in machine learning to anomaly
¶

Supported by the US National Science Foundation under grants CIF 1514245 and
CIF 1513373. This paper was partially presented at the 41st IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2016 as [19].
MSC 2010 subject classifications: Primary 62G10; secondary 62G20
Keywords and phrases: likelihood ratio test, sparse mixture, error exponents

1

2

J. G. LIGO ET AL.

detection on graphs [22] and high-dimensional feature selection when useful
features are rare and weak [12].
Prior work on detecting a sparse signal in noise has been primarily focused
on Gaussian signal and noise models, with the goal of determining the tradeoff in signal strength with sparsity required for detection with vanishing
probability of error. In contrast, this work considers a fairly general class
of signal and noise models. Moreover, in this general class of sparse signal
and noise models, we provide the first analysis of the rate at which the false
alarm (Type-I) and miss detection (Type-II) error probabilities vanish with
sample size. We also provide simple to verify conditions for detectability,
which are derived using simpler tools than previously used. In the problem
of testing between n i.i.d. samples from two known distributions, it is well
known that the rate at which the error probability decays is e−cn for some
constant c > 0 bounded by the Kullback-Leibler divergence between the
two distributions [6, 8]. In this work, we show for the problem of detecting a
sparse signal in noise that the error probability for an oracle detector decays
at a slower rate determined by the sparsity level and the χ2 -divergence
between the signal and noise distributions, with different behaviors possible
depending on the signal strength. In addition to determining the optimal
trade-off between signal strength and sparsity for consistent detection, an
important contribution in prior work has been the construction of adaptive
(and, to some extent, distribution-free) tests that achieve the optimal tradeoff without knowing the model parameters [1, 3, 4, 11, 16, 17, 23]. We discuss
prior work in more detail in Sec. 2.1. However, the adaptive tests that have
been proposed in these papers are not amenable to an analysis of the rate at
which the error probability goes to zero. We show that in a Gaussian signal
and noise model that an adaptive test based on the sample maximum has
miss detection probability that vanishes at the optimal rate when the sparse
signal is sufficiently strong.
2. Problem Setup. Let {f0,n (x)}, {f1,n (x)} be sequences of probability
density functions (PDFs) for real valued random-variables.
We consider the following sequence of composite hypothesis testing problems with sample size n, called the (sparse) mixture detection problem:
(2.1)

H0,n : X1 , . . . , Xn ∼ f0,n (x) i.i.d. (null)

(2.2)

H1,n : X1 , . . . , Xn ∼ (1 − n )f0,n (x) + n f1,n (x) i.i.d. (alternative)

where {f0,n (x)} is known, {f1,n (x)} is from some known family F of sequences
of PDFs, and {n } is a sequence of positive numbers such that n → 0. We
will also assume nn → ∞ so that a typical realization of the alternative is
distinguishable from the null.

DETECTING SPARSE MIXTURES

3

Let P0,n , P1,n denote the probability measure under H0,n , H1,n respectively,
and let E0,n , E1,n be the corresponding expectations, with respect to the
particular {f0,n (x)}, {f1,n (x)} and {n }. When convenient, we will drop the
f (x)
subscript n. Let Ln , f1,n
. When f0,n (x) = f0 (x) and f1,n (x) = f0 (x − µn ),
0,n (x)
we say that the model is a location model. For the purposes of presentation,
we will assume that {µn } is a positive and monotone sequence. When f0 (x)
is a standard normal PDF, we call the location model a Gaussian location
model. The distributions of the alternative in a location model are described
by the set of sequences {(n , µn )}.
The location model can be considered as one where the null corresponds
to pure noise, while the alternative corresponds to a sparse signal (controlled by n ), with signal strength µn contaminated by additive noise. The
relationship between n and µn determines the signal-to-noise ratio (SNR),
and characterizes when the hypotheses can be distinguished with vanishing
probability of error. In the general case, f0,n (x) can be thought of as the
noise and f1,n (x) as the signal distribution.
We define the probability of false alarm for a hypothesis test δn between
H0,n and H1,n as
(2.3)

PFA (n) , P0,n [δn = 1]

and the probability of missed detection as
(2.4)

PMD (n) , P1,n [δn = 0].

A sequence of hypothesis tests {δn } is consistent if PFA (n), PMD (n) → 0 as
n → ∞. We say we have a rate characterization for a sequence of consistent
hypothesis tests {δn } if we can write
(2.5)

lim

n→∞

log PFA (n)
= −c,
g0 (n)

lim

n→∞

log PMD (n)
= −d,
g1 (n)

where g0 (n), g1 (n) → ∞ as n → ∞ and 0 < c, d < ∞. The rate characterization describes decay of the error probabilities for large sample sizes.
All logarithms are natural. For the problem of testing between i.i.d. samples
from two fixed distributions, g0 (n) = g1 (n) = n, and c, d are called the error
exponents [6]. In the mixture detection problem, g0 (n) and g1 (n) will be
sublinear functions of n.
The log-likelihood ratio between the corresponding probability measures
of H1,n and H0,n is
(2.6)

LLR(n) =

n
X
i=1


log 1 − n + n Ln (Xi ) .

4

J. G. LIGO ET AL.

In order to perform an oracle rate characterization for the mixture detection
problem, we consider the sequence of oracle likelihood ratio tests (LRTs)
between H0,n and H1,n (i.e. with n , f0,n , f1,n known):
(
1 LLR(n) ≥ 0
(2.7)
δn (X1 , . . . , Xn ) ,
.
0 otherwise
It is well known that (2.7) is optimal for testing between H0,n and H1,n in the
MD (n)
sense of minimizing PFA (n)+P
, which is the average probability of error
2
when the null and alternative are assumed to be equally likely [18, 21]. It is
valuable to analyze PFA (n) and PMD (n) separately since many applications
incur different costs associated with false alarms and missed detections.
Location Model: The detectable region for a location model is the set
of sequences {(n , µn )} such that a sequence of consistent oracle tests {δn }
exist. For convenience of analysis, we introduce the parameterization
(2.8)

n = n−β

where β ∈ (0, 1) as necessary. Following the terminology of [1], when β ∈
(0, 12 ), the mixture is said to be a “dense mixture”. If β ∈ ( 21 , 1), the mixture
is said to be a “sparse mixture”.
2.1. Related Work. Prior work on mixture detection has been focused
primarily on the Gaussian location model. The main goals in these works
have been to determine the detectable region and construct optimally adaptive tests (i.e. those which are consistent independent of knowledge of {(n ,
µn )}, whenever possible). The study of detection of mixtures where the
mixture probability tends to zero was initiated by Ingster for the Gaussian
location model [16]. Ingster characterized the detectable region, and showed
that outside the detectable region the sum of the probabilities of false alarm
and missed detection is bounded away from zero for any test. Since the
generalized likelihood statistic tends to infinity under the null, Ingster developed an increasing sequence of simple hypothesis tests that are optimally
adaptive.
Donoho and Jin introduced the Higher Criticism test, which is optimally
adaptive and is computationally efficient relative to Ingster’s sequence of hypothesis tests, and also discussed some extensions to Subbotin distributions
and χ2 -distributions [11]. Cai et al. extended these results to the case where
f0,n (x) is standard normal and f1,n (x) is a normal distribution with positive
variance, derived limiting expressions for the distribution of LLR(n) under
both hypotheses, and showed that the Higher Criticism test is optimally

DETECTING SPARSE MIXTURES

5

adaptive in this case [3]. Jager and Wellner proposed a family of tests based
on φ-divergences and showed that they attain the full detectable region in
the Gaussian location model [17]. Arias-Castro and Wang studied a location model where f0,n (x) is some fixed but unknown symmetric distribution,
and constructed an optimally adaptive test that relies only on the symmetry of the distribution when µn > 0 [1]. In a separate paper, Arias-Castro
and Wang also considered mixtures of Poisson distributions and showed the
problem had similar detectability behavior to the Gaussian location model
[2].
Cai and Wu gave an information-theoretic characterization of the detectable region via an analysis of the sharp asymptotics of the Hellinger distance for a wide variety of distributions, and established a strong converse
result showing that reliable detection is impossible outside the detectable region in many cases if (2.7) is not consistent [4]. This work also gave general
conditions for the Higher Criticism test to be consistent. Our work complements [4] by providing conditions for consistency (as well as asymptotic
estimates of error probabilities) for optimal tests, with simple to verify conditions for a fairly general class of models. While the Hellinger distance
used in [4] provides bounds on PFA (n) + PMD (n) for the test specified in
(2.7), our analysis treats PFA (n), PMD (n) separately as they may have different rates at which they tend to zero and different acceptable tolerances
in applications. As we will show in Sec. 3.2 and Sec. 4, there are cases where
PFA (n)  PMD (n) for adaptive tests and PFA (n)  PMD (n) for an oracle
test.
Walther numerically showed that while the popular Higher Criticism
statistic is consistent, there exist optimally adaptive tests with significantly
higher power for a given sample size at different sparsity levels [23]. Our
work complements [23] by providing a benchmark to meaningfully compare
the sample size and sparsity trade-offs of different tests with an oracle test.
It should be noted that all of the work except [1, 3] has focused on the case
where β > 12 , and no prior work has provided an analysis of the rate at
which PFA (n), PMD (n) can be driven to zero with sample size.
3. Main Results for Rate Analysis.
3.1. General Case. Our main result is a characterization of the oracle
rate via the test given in (2.7). The sufficient conditions required for the
rate characterization are applicable to a broad range of parameters in the
Gaussian location model (Sec. 3.2).
We first look at the behavior of “weak signals”, where Ln has suitably
controlled tails under the null hypothesis. In the Gaussian location model

6

J. G. LIGO ET AL.

in Sec. 3.2, this theorem is applicable to small detectable µn .
Theorem 3.1. Let γ0 ∈ (0, 1) and assume that for all γ ∈ (0, γ0 ) the
following conditions are satisfied:


(Ln − 1)2
(3.1)
lim E0
1{Ln ≥1+ γ } = 0
n→∞
n
Dn2
(3.2)
n Dn → 0
√
(3.3)
nn Dn → ∞
where
(3.4)

Dn2 = E0 [(Ln − 1)2 ] < ∞.

Then for the test specified by (2.7),
(3.5)

log PFA (n)
1
=− .
2
2
n→∞
nn Dn
8
lim

Moreover, (3.5) holds if we replace PFA (n) with PMD (n).
The quantity Dn2 is known as the χ2 -divergence between f0,n (x) and f1,n (x)
[14]. In contrast to the problem of testing between i.i.d. samples from two
fixed distributions [8], the rate is not characterized by the Kullback-Leibler
divergence for the mixture detection problem.
Proof. We provide a sketch of the proof for PFA (n), and leave the details
to Supplemental Material. We first establish that
(3.6)

lim sup
n→∞

log PFA (n)
1
≤−
n2n Dn2
8

By the Chernoff bound applied to PFA (n) and noting X1 , . . . , Xn are i.i.d.,





s  n
PFA (n) = P0 LLR(n) ≥ 0 ≤ min E0 1 − n + n Ln (X1 )
0≤s≤1
 hp
in
(3.7)
≤ E0
1 − n + n Ln (X1 )
By direct computation, we see E0 [Ln (X1 )−1] = 0, and the following sequence

DETECTING SPARSE MIXTURES

7

of inequalities hold:
"
#
hp
i
1
2n (Ln (X1 ) − 1)2
E0
1 − n + n Ln (X1 ) = 1 − E0
p
2
2
1 + 1 + n (Ln (X1 ) − 1)
"
#
(Ln (X1 ) − 1)2
2n
p
≤ 1 − E0
1{n (Ln (X1 )−1)≤γ}
2
(1 + 1 + n (Ln (X1 ) − 1))2


(Ln (X1 ) − 1)2
2n Dn2
γ
√
E0
≤1−
1{Ln (X1 )≤1+  }
n
Dn2
2(1 + 1 + γ)2



2
2
2
(Ln (X1 ) − 1)
n Dn
√
1 − E0
=1−
1{Ln (X1 )≥1+ γ }
n
Dn2
2(1 + 1 + γ)2
Since the expectation in the previous line tends to zero by (3.1), for sufficiently large n it will become smaller than γ. Therefore we have by (3.7)


1
2n Dn2
log PFA (n)
√
≤ log 1 −
(1 − γ) .
n
2 (1 + 1 + γ)2
Dividing both sides by 2n Dn2 and taking the lim sup using (3.2),(3.3) estab(n)
1−γ
lishes lim supn→∞ lognP2FA
. Since γ can be arbitrarily small,
≤ − 21 (1+√
2
1+γ)2
n Dn
(3.6) is established.
We now establish that
log PFA (n)
1
(3.8)
lim inf
≥− .
2
2
n→∞
nn Dn
8
The proof of (3.8) is similar to that of Cramer’s theorem (Theorem I.4, [9]).
The key difference from Cramer’s theorem is that LLR(n) is the sum of
i.i.d. random variables for each n, but the distributions of the summands
defining LLR(n) in (2.6) change for each n under either hypothesis. Thus, we
modify the proof of Cramer’s theorem by introducing a n-dependent tilted
distribution, and replacing the standard central limit theorem (CLT) with
the Lindeberg-Feller CLT for triangular arrays (Theorem 3.4.5, [13]).
We introduce the tilted distribution f̃n (x) corresponding to f0,n (x) by
s
1 − n + n Ln (x) n
(3.9)
f̃n (x) =
f0,n (x)
Λn (sn )

s 
where Λn (s) = E0 1 − n + n Ln (X1 ) , which is convex with Λn (0) =
Λn (1) = 1, and sn = arg min0≤s≤1 Λn (s). Let P̃, Ẽ denote the tilted measure and expectation, respectively (where we suppress the n for clarity). A
standard dominated convergence argument (Lemma 2.2.5, [8]) shows that


(3.10)
Ẽ log 1 − n + n Ln (X1 ) = 0.

8

J. G. LIGO ET AL.

Define the variance of the log-likelihood ratio for one sample as
h
2 i
(3.11)
σn2 = Ẽ log 1 + n (Ln (X1 ) − 1)
.
For sufficiently large n such that Lemma 7.1 (proved in Supplementary Material) holds, namely that C1 2n Dn2 ≥ σn2 ≥ C2 2n Dn2 , we have:


PFA (n) = P0 [LLR(n) ≥ 0] = E0 1{LLR(n)≥0}
h
i
= (Λn (sn ))n Ẽ e−LLR(n) 1{LLR(n)≥0}
h
i
= (Λn (sn ))n Ẽ e−LLR(n) |LLR(n) ≥ 0 P̃ [LLR(n) ≥ 0]
(3.12)

≥ (Λn (sn ))n e−Ẽ[LLR(n)|LLR(n)≥0] P̃ [LLR(n) ≥ 0]
Ẽ[LLR(n)1{LLR(n)≥0} ]
n −
P̃[LLR(n)≥0]
= (Λn (sn )) e
P̃ [LLR(n) ≥ 0]

(3.13)

≥ (Λn (sn ))n e

(3.14)

−

√

n −

≥ (Λn (sn )) e

−

≥ (Λn (sn ))n e

Ẽ[(LLR(n))2 ]

2
nσn
P̃[LLR(n)≥0]

√
−

P̃ [LLR(n) ≥ 0]

P̃[LLR(n)≥0]

√

= (Λn (sn ))n e
(3.15)

Ẽ[|LLR(n)|]
P̃[LLR(n)≥0]

2
nC1 2
n Dn
P̃[LLR(n)≥0]

P̃ [LLR(n) ≥ 0]

P̃ [LLR(n) ≥ 0]
P̃ [LLR(n) ≥ 0]

where (3.12) follows from Jensen’s inequality, (3.13) by LLR(n)1{LLR(n)>0}
≤ |LLR(n)|, (3.14) by Jensen’s inequality, and (3.15) by Lemma 7.1 proved
in the Supplementary Material.
Taking logarithms and dividing through by n2n Dn2 gives
√
log PFA (n)
1
log Λn (sn )
C1
log P̃ [LLR(n) ≥ 0]
√
≥
−
.
+
2
2
2
2
nn Dn
n Dn
n2n Dn2
P̃ [LLR(n) ≥ 0] nn Dn
Taking lim inf and applying Lemma 7.2, in which it is established that
P̃[LLR(n) ≥ 0] → 21 , and Lemma 7.4 in which it is established that
n (sn )
lim inf n→∞ logΛ
≥ − 18 , (see Supplementary Material), along with the
2 D2
n

n

(n)
assumption n2n Dn2 → ∞ establishes that lim inf n→∞ lognP2FA
≥ − 18 .
2
n Dn
The analysis under H1,n for PMD (n) relies on the fact that the Xi are
i.i.d. with pdf (1 − n + n Ln )f0,n (x), which allows the use of 1 − n + n Ln
to change the measure from the alternative to the null. The upper bound is

DETECTING SPARSE MIXTURES

9

established identically, by noting that the Chernoff bound furnishes
"
#!n


1
PMD (n) = P1,n − LLR(n) > 0 ≤ E1 p
1 − n + n Ln (X1 )
in
 hp
1 − n + n Ln (X1 )
= E0
Similarly, the previous analysis can be applied to show that (3.8) holds with
PFA (n) replaced with PMD (n).
In order to study the behavior of tests when Thm 3.1 does not hold, we
rely on the following bounds for PMD (n), PFA (n):
Theorem 3.2.

(a) Let {δn } be any sequence of tests such that
lim sup PFA (n) < 1,
n→∞

then,
(3.16)

lim inf
n→∞

log PMD (n)
≥ −1.
nn

(b) The following upper and lower bounds for PFA (n) hold for the test specified by (2.7):
(3.17)
(3.18)

PFA (n) ≤ 1 − (P0 [Ln ≤ 1])n
" n
#
X

PFA (n) ≥ P0
log max 1 − n , n Ln (Xi ) ≥ 0 .
i=1

These bounds are easily proved by noting if all observations under H1,n
come from f0,n , then a miss detection occurs (a), and at least one sample
must have Ln ≥ 1 in order to raise a false alarm (b).
Note that these are universal bounds in the sense that they impose no
conditions on f1,n (x), f0,n (x) and n . Also note that the bound of Thm 3.2(a)
is independent of any divergences between f0,n (x) and f1,n (x), and it holds
for any consistent sequence of tests because PFA (n) → 0. This is in contrast
to the problem of testing between i.i.d. samples from fixed distributions,
where the rate is a function of divergence [8].
When the conditions of Thm 3.1 do not hold, we have the following rate
characterization for “strong signals”, where Ln is under the f1,n (x) distribution in an appropriate sense. In the Gaussian location model in Sec. 3.2, this
theorem is applicable to large detectable µn .

10

J. G. LIGO ET AL.

Theorem 3.3. Let M0 > 1, and assume that for all M > M0 , the
following condition is satisified:
h
i
(3.19)
E0 Ln 1{Ln >1+ M } → 1.
n

Then for the test specified by (2.7),
(3.20)
(3.21)

log PFA (n)
≤ −1
nn
n→∞
log PMD (n)
lim
= −1.
n→∞
nn

lim sup

Proof. We first prove (3.20). Let
φ(x) = 1 + sx − (1 + x)s .
By Taylor’s theorem, we see for s ∈ (0, 1) and x ≥ −1 that φ(x) ≥ 0. Since
E0 [Ln − 1] = 0,
E0 [(1 − n + n Ln (X1 ))s ] = 1 − E0 [φ(n (Ln (X1 ) − 1))].
Note this implies E0 [φ(n (Ln (X1 ) − 1))] ∈ [0, 1] since E0 [(1 − n + n Ln (X1 ))s ]
is convex in s and is 1 for s = 0, 1. As in the proof of Thm 3.1, by the Chernoff
bound,
PFA (n) ≤ (E0 [(1 − n + n Ln (X1 ))s ])n
for any s ∈ (0, 1). Thus, supressing the dependence on X1 , and assuming
M > M0 , we have
log PFA (n)
≤ log E0 [(1 − n + n Ln (X1 ))s ]
n
= log(1 − E0 [φ(n (Ln − 1))])
(3.22)
(3.23)

(3.24)

(3.25)

≤ −E0 [φ(n (Ln − 1))]


≤ −E0 φ(n (Ln − 1))1{n (Ln −1)≥M }


= −E0 (1 + sn (Ln − 1) − (1 + n (Ln − 1))s ) 1{n (Ln −1)≥M }


≤ −E0 (sn (Ln − 1) − (1 + n (Ln − 1))s ) 1{n (Ln −1)≥M }


≤ −E0 (sn (Ln − 1) − 2s sn (Ln − 1)s ) 1{n (Ln −1)≥M }




2s
= −E0 n (Ln − 1) s −
1{n (Ln −1)≥M }
(n (Ln − 1))1−s




2
≤ −E0 n (Ln − 1) s − 1−s 1{n (Ln −1)≥M }
M

11

DETECTING SPARSE MIXTURES


= −n s −



2
M 1−s



E0 Ln
 "



1
1−
Ln



1{n (Ln −1)≥M }



!
#
1
1{n (Ln −1)≥M }
≤ −n s − 1−s E0 Ln 1 −
M
1+ M
n
!




2
1
1−
E
L
1
= −n s − 1−s
0
n
{
(L
−1)≥M
}
n
n
M
1+ M
n


2

where (3.22) follows from log(1 − x) ≤ −x for x ≤ 1, (3.23) follows from
φ(x) ≥ 0, (3.24) follows from (1 + x)s ≤ 2s xs for x ≥ 1 and taking M > M0 ,
(3.25) follows from s ∈ (0, 1). Dividing both sides of the inequality by n
and taking a lim supn→∞ establishes
lim sup
n→∞

log PFA
2
≤ −s + 1−s .
nn
M

Letting M → ∞ and optimizing over s ∈ (0, 1) establishes the (3.20). By a
change of measure between the alternative and null hypotheses, we see that
(3.20) also holds with PFA (n) replaced with PMD (n). Combining this with
Thm 3.2 establishes (3.21).
Theorem 3.3 shows that the rate of miss detection is controlled by the average number of observations drawn from f1,n (x) under H1,n , independent of
any divergence between f1,n (x) and f0,n (x) when (3.19) holds. Interestingly,
so long as the condition of Thm 3.3 holds, by Thm 3.2(a), no non-trivial
sequence of tests (i.e. lim supn→∞ PFA (n), PMD (n) < 1) can achieve a better
rate than (2.7) under H1,n . This is different from the case of testing i.i.d.
observations from two fixed distributions, where allowing for a slower rate
of decay for PFA (n) can allow for a faster rate of decay for PMD (n) (Sec. 3.4,
[8]).
In Sec. 3.2, we will show that Thm 3.3 is not always tight under H0,n ,
and the true behavior can depend on divergence between f0,n (x) and f1,n (x),
using the upper and lower bounds of Thm 3.2(b).
3.1.1. Comparison to Related Work. Cai and Wu [4] consider a model
which is essentially as general as ours, and characterize the detection boundary for many cases of interest, but do not perform a rate analysis. Note that
our rate characterization (3.5) depends on Dn , the χ2 -divergence between
f0,n and f1,n . While the Hellinger distance used in [4] can be upper bounded
in terms of the χ2 -divergence, a corresponding lower bound does not exist in
general [14], and so our results cannot be derived using the methods of [4]. In
fact, our results complement [4] in giving precise bounds on the error decay

12

J. G. LIGO ET AL.

for this problem once the detectable region boundary has been established.
Furthermore, as we will show in Thm 4.1, there are cases where the rates
derived by analyzing the likelihood ratio test are essentially achievable.
3.2. Gaussian Location Model. In this section, we specialize Thm 3.1
and 3.3 to the Gaussian location model. The rate characterization proved is
summarized in Fig. 1. We first recall some results from the literature for the
detectable region for this model.
Theorem 3.4. The boundary of the detectable region (in {(n , µn )} space)
is given by (with n = n−β ):
1

1. If 0 < β ≤ 12 , then µcrit,n = nβ− 2 . (Dense)
q
3
1
2. If 2 < β < 4 , then µcrit,n = 2(β − 12 ) log n. (Moderately Sparse)
p
√
3. If 34 ≤ β < 1, then µcrit,n = 2(1 − 1 − β)2 log n. (Very Sparse)
If in the dense case µn = nr , then the LRT (2.7) is consistent if r > β − 12 .

(a) Detectable
region (r versus β) where
√
µn = 2r log n, n = n−β

(b) Detectable region (r versus β) where
µn = nr , n = n−β

Fig 1: Detectable regions for the Gaussian location model. Unshaded regions
have PMD (n) + PFA (n) → 1 for any test (i.e. reliable detection is impossible). Green regions are where corollaries 3.5 and 3.6 provide an exact rate
characterization. The red region is where Thm 3.8 provides an upper bound
on the rate, but no lower bound. The blue region is where Cor. 3.7 holds,
and provides an upper bound on the rate for PFA (n) and an exact rate
characterization for PMD (n).

13

DETECTING SPARSE MIXTURES

Moreover, if r < β − 12 , then PFA (n) + P√MD (n) → 1 for any sequence of tests
as n → ∞. If in the sparse cases, µn = 2r log n, then the LRT is consistent
if µn > µcrit,n . Moreover, if µn < µcrit,n , then PFA (n) + PMD (n) → 1 for
any sequence of tests as n → ∞.
Proof. For the proof see [1, 3, 11].
We call the set of {(n , µn )} sequences where (2.7) is consistent the interior
of the detectable region. We now begin proving a rate characterization for
the Gaussian location model by specializing Thm 3.1. Note that Ln (x) =
1 2
2
eµn x− 2 µn and Dn2 = eµn −1. A simple computation shows that the conditions
in the theorem can be re-written as:
For all γ > 0 sufficiently small:
(3.26)



n 


Q − 23 µn + µ1n log 1 + γn
+ µ21
Q − 32 µn + µ1n log 1 + γn
n


 e −1

 o
γ
1
1
−2Q − 2 µn + µn log 1 + n
+ Q 12 µn + µ1n log 1 + γn
→0
2

(3.27)

2n (eµn − 1) → 0

(3.28)

n2n (eµn − 1) → ∞

where Q(x) =

2

R∞
x

1 2
√1 e− 2 x dx.
2π

Corollary 3.5.
where h(n) → ∞ and

(3.29)

(Dense case) If n = n−β for β ∈ (0, 12 ) and µn =
lim supn→∞ q 2 µn
β log n
3

h(n)
1

n 2 −β

< 1, then

1
log PFA (n)
=− .
2
µ
2
n→∞ n (e n − 1)
8
n
lim

If µn → 0, (3.29) can be rewritten as
(3.30)

lim

n→∞

log PFA (n)
1
=− .
n2n µ2n
8

This result holds when replacing PFA (n) with PMD (n).
Proof. It is easy to verify (3.27) and (3.28) directly, and (3.26) if µn
does not tend to zero. To verify (3.26) it suffices to show: If µn → 0, for
any α ∈ R, then

Q(αµn + µ1 log(1+ γ ))
n
2

eµn −1

n

→ 0. Since ex − 1 ≥ x, it suffices to

14

J. G. LIGO ET AL.

show that

Q(αµn + µ1 log(1+ γ ))
n
n
µ2n
1 2
−2x

→ 0. This can be verified by the standard

bound Q(x) ≤ e
for x > 0, and noting that αµn +
for sufficiently large n and that exx−1 → 1 as x → 0.

1
µn

log(1 +

γ
n )

>0

The implication of this corollary is that our rate characterization of the
probabilities of error holds for a large portion of the detectable region up
to the detection boundary, as h(n) can be taken such that h(n)
→ 0 for any
nξ
ξ > 0, making it negligible with respect to µcrit,n in Thm 3.4.
Corollary 3.6. (Moderately sparse case) If n = n−β for β ∈ ( 12 , 43 )
q
then
and µn = 2(β + 12 + ξ) log n for any 0 < ξ < 3−4β
6
(3.31)

lim

n→∞

log PFA (n)
1
=−
2
µ
2
n
8
nn (e − 1)

and the same result holds replacing PFA (n) with PMD (n).
Proof. It is easy to verify (3.27) and (3.28) directly. To verify (3.26),
note since Q(·) ≤ 1 and µn → ∞, we need
1


n 

−
Q − 32 µn + µ1n log 1 + γn




+ Q 12 µn +
2Q − 12 µn + µ1n log 1 + γn

2
eµn −1

1
µn


log 1 +

γ
n

 o

→ 0.


Thus, it suffices to show thatQ − 23 µn + µ1n log(1 + γn ) → 0, or equivalently,
that − 23 µn + µ1n log(1 + γn ) → ∞ for any fixed γ > 0. Applying log(1 + γn ) ≥
log( γn ) = β log n + log γ shows that

log 1 + γn ≥
q
3
β log n + log γ
−
2(β − 12 + ξ) log n + q
2
2(β − 12 + ξ) log n
q

p
β
log γ
= − 32 2(β − 21 + ξ) + q
log n + q
2(β − 21 + ξ)
2(β − 12 + ξ) log n

(3.31)

− 32 µn +

1
µn

where the last
√ term tends to 0 with n. Thus, (3.31) tends to infinity if the
coefficient of log n is positive, i.e. if 12 (1−2ξ) < β < 14 (3−6ξ) , which holds
by the definition of ξ. Thus, (3.31) tends to infinity and (3.26) is proved.

15

DETECTING SPARSE MIXTURES

Note that ξ can be replaced with an appropriatelyq
chosen sequence tending to 0 such that (3.27) and (3.28) hold. For µn > 23 β log n, (3.26) does
not hold. However, Thm 3.3 and Thm 3.2 provide
√ a partial rate characterization for the case where µn grows faster than 2β log n which we present
in the following corollary.
Corollary 3.7.
then

If n = n−β for β ∈ (0, 1) and lim inf n→∞

(3.33)
If

nn
µ2n

lim

n→∞

√ µn
2β log n

> 1,

log PMD (n)
= −1.
nn

→ ∞, then

(3.34)

lim sup
n→∞

Otherwise, if

nn
µ2n

log PFA (n)
= −1
nn

→ 0, then

(3.35)

lim sup
n→∞

log PFA (n)
1
≤− .
µ2n
8

Proof. The condition for Thm 3.3 given by (3.19) is

 1 
Q µ1n log 1 + M
n − 2 µn → 1.
This holds if

1
µn

log(1 +

M
n )

− 12 µn → −∞, which is true if r > β.

(n)
n
≥ −1 if n
To show that lim inf n→∞ log PnFA
→ ∞, we can apply
µ2n
n
a similar argument to the lower bound for Thm 3.1 to the lower bound
given by (3.18) and is thus omitted. Instead, we show a short proof of
(n)
lim inf n→∞ log PnFA
≥ −C for C ≥ 1 using (3.18). Note that we can loosen
n
(3.18) to
" k
#
n
X
X

PFA (n) ≥ P0
log (1 − n ) +
log n Ln (Xi ) ≥ 0
i=1

i=k+1

for any k and explicitly compute a lower bound to PFA (n) in terms of the
standard normal cumulative distribution function. Optimizing this bound
(n)
≥ −C for some
over the choice of k establishes that lim inf n→∞ log PnFA
n
µ
n
√
constant C ≥ 1 (with C = 1 if log n → ∞). The lower bounding of (3.18)
in a manner similar to (3.1) recovers the correct constant when µn scales as
√
2r log n.

16

J. G. LIGO ET AL.

To see that the log-false alarm probability scales faster than nn when
→ 0, one can apply (3.17). In this case,

nn
µ2n

n 
log PFA (n) ≤ log 1 − 1 − Q( 12 µn )
.
Applying the standard approximation
1 2

1 2

√

(3.36)

we see lim supn→∞

e− 2 x
xe− 2 x
≤ Q(x) ≤ √
for x > 0,
2π(1 + x2 )
x 2π

log PFA (n)
µ2n

≤ − 18 .

Note that (3.35) shows an asymmetry between the rates for the miss
detection and false alarm probabilities, since there is a fundamental lower
bound due to the sparsity under the alternative for the miss probability, but
not under the null.
√
Theorems 3.1 and 3.3 do not hold when √
n = n−β and µn = 2r log n
where r ∈ ( β3 , β) for β ∈ (0, 34 ) or r ∈ ((1 − 1 − β)2 , β) for β ∈ ( 34 , 1). For
the remainder of the detectable region, we have an upper bound on the rate
derived specifically for the Gaussian location setting. One can think of this
as a case of “moderate signals”.


√
Theorem 3.8. Let n = n−β and µn = 2r log n where r ∈ β3 , β for
√
β ∈ (0, 43 ) or r ∈ ((1 − 1 − β)2 , β) for β ∈ ( 34 , 1). Then,
(3.37)

lim sup
n→∞

log PFA (n)
1

 ≤− .

β
16
n2n e Φ 2r
− 32 µn
µ2n

Rx
2
where Φ(x) = 1 − Q(x) = −∞ √12π e−x /2 dx denotes the standard normal
cumulative distribution function.
Moreover, (3.37) holds replacing PFA with PMD .
Proof. The proof is based on a Chernoff bound with s = 21 . Details are
given in the Supplemental Material.

2
β
It is useful to note that n2n eµn Φ ( 2r
− 32 )µn behaves on the order of
2

n1−2β+2r−r(1.5−β/2r)
√
2r log n

for large n in Thm 3.8.

DETECTING SPARSE MIXTURES

17

4. Rates and Adaptive Testing in the Gaussian Location Model.
No adaptive tests prior to this work have had precise rate characterization.
Moreover, optimally adaptive tests for 0 < β < 1 such as the Higher Criticism (HC) [11] test or the sign test of Arias-Castro and Wang (ACW) ([1],
Sec. 1.4)1 are not amenable to rate analysis based on current analysis techniques. This is due to the fact that the consistency proofs of these tests
follow from constructing functions of order statistics that grow slowly under
the null and slightly quicker under the alternative via a result of Darling
and Erdös [7]. We therefore analyze the max test:
(
1 maxi=1,...,n Xi ≥ τn
(4.1)
δmax (X1 , . . . , Xn ) ,
0 otherwise
where τn is a sequence of test thresholds.
While the max test is not consistent everywhere (2.7) is [1, 11], it has a few
advantages over other tests that are adaptive to all {(n , µn )} possible (i.e.
optimally adaptive). The first advantage is a practical perspective; the max
test requires a linear search and trivial storage complexity to find the largest
element in a sample, whereas computing the HC or ACW test requires on
the order of n log n operations to compute the order statistics of a sample of
size n (which may lead to non-trivial auxiliary storage requirements), along
with computations depending on Q-functions or partial sums of the signs of
the data. Moreover, the max test has been shown to work in applications
such as astrophysics [5]. It does not require specifying the null distribution,
which allows it to be applied to the Subbotin location models as in [1]. The
second advantage is analytical, as the cumulative distribution function of the
maximum of an i.i.d. sample of size n with cumulative distribution function
F (x) has the simple form of F (x)n . This also provides a simple way to set
the test threshold to meet a pre-specified false alarm probability for a given
sample size n. As most applications focus on the regime where n = n−β
for β > 21 , the following theorem shows the max test provides a simple test
with rate guarantees for almost the entire detectable region in this case.
√ Theorem 4.1. For the max test given by (4.1) with threshold τn =
2 log n:
The rate under the null is given by
(4.2)
1

lim

n→∞

log PFA (n)
1
=− .
log log n
2

We avoid the use of the acronym CUSUM since it is reserved for the most popular
test for the quickest change detection problem in Sequential Analysis.

18

J. G. LIGO ET AL.

Under the alternative, if lim inf n→∞ √

(4.3)

> 1 with n = n−β ,

log PMD (n)
√
= −1.
n→∞ nn Q( 2 log n − µn )
lim

In particular, if lim inf n→∞
rate under the alternative
(4.4)

µn
√
2(1− 1−β)2 log n

√ µn
2 log n

lim

n→∞

> 1, the max test achieves the optimal

log PMD (n)
= −1.
nn

Otherwise, the max test is not consistent.
Proof. The error probabilities for the max test given by (4.1) with
threshold τn
(4.5)

PFA (n) = 1 − Φ(τn )n

(4.6)

n
PMD (n) = (1 − n )Φ(τn ) + n Φ(τn − µn )

follow from the cumulative distribution function of the maximum of an i.i.d.
sample. The rates (4.2),(4.3),(4.4) as well as the condition for inconsistency
are derived by applying the approximation (3.36) to (4.5) and (4.6).

Fig 2: Detectable region of the Max test. White denotes where detection is
impossible for any test. Black denotes where the max test is inconsistent.
Green denotes where the max test is consistent, but has suboptimal rate
under the alternative compared to (2.7). Blue denotes where the max test
achieves the optimal rate under the alternative. Compare to Fig. 1a.

DETECTING SPARSE MIXTURES

19

The√results of Thm. 4.1 are summarized
in Fig. 2. In particular, if we take
√
µn = 2r log n with r ∈ (1 − 1 − β)2 , 1 , we see log PMD (n) scales on the
√
1−β−(1− r)2

n √ √
. This is suboptimal compared to the rates achieved by
order of (1−
r) 2 log n
the (non-adaptive) likelihood ratio test (2.7), but is of polynomial order (up
to a sub-logarithmic factor). Note that the rate of decay of the sum error
probability can be slower than that of the miss detection probability, since
the false alarm probability is fixed by the choice of threshold, independent
of the true {(n , µn )} for adaptivity.

5. Numerical Experiments. In this section, we provide numerical
simulations to verify the rate characterization developed for the Gaussian location model as well as some results comparing the performance of adaptive
tests.
5.1. Rates for the Likelihood Ratio Test. We first consider the dense case,
with n = n−0.4 and µn = 1. The conditions of Cor. 3.5 apply here, and we
(n)
expect log2 PFA
→ − 18 . Simulations were done using direct Monte Carlo
µ2
nn (e

n −1)

simulation with 10000 trials for the errors for n ≤ 106 . Importance sampling
via the hypothesis alternate to the true hypothesis (i.e. H0,n for simulating

(a) Simulations of error probabilities in
the Gaussian location model with µn =
1, n = n−0.4 for the test (2.7). A best
fit line for log PMD (n) is given as a blue
dashed line and corresponding line for
log PFA (n) is given as a red dot-dashed
line.

(b) Simulations of error probabilities in
the Gaussian location model with µn =
p
2(0.19) log n, n = n−0.6 for the test
(2.7). A best fit line for log PMD (n) is
given as a blue dashed line and corresponding line for log PFA (n) is given as
a red dot-dashed line.

Fig 3: Simulation results for Cor. 3.5 and 3.6

20

J. G. LIGO ET AL.

PMD (n), H1,n for simulations PFA (n)) was used for 106 < n ≤ 2 × 107 with
between 10000 − 15000 data points. The performance of the test given (2.7)
is shown in Fig. 3a. The dashed lines are the best fit lines between the log2
error probabilities and n2n (eµn − 1) using data for n ≥ 350000. By Cor. 3.5,
we expect the slope of the best fit lines to be approximately − 18 . This is the
case, as the line corresponding to missed detection has slope −0.13 and the
line corresponding to false alarm has slope −0.12.
p
The moderately sparse case with n = n−0.6 and µn = 2(0.19) log n
is shown in Fig. 3b. The conditions of Cor. 3.6 apply here, and we expect
log PFA (n)
→ − 18 . Simulations were performed identically to the dense case.
2 µ2
nn (e

n −1)

The dashed lines are the best fit lines between the log-error probabilities
2
and n2n (eµn − 1) using data for n ≥ 100000. By Cor. 3.6, we expect the
slope of the best fit lines to be approximately − 18 . Both best fit lines have
slope of −0.11. It is important to note that PFA (n), PMD (n) are both large
even at n = 2 × 107 and simulation to larger sample sizes should show better
agreement with Cor. 3.6.
5.2. Adaptive Testing. In order to implement an adaptive test, the threshold for the test statistic must be chosen in order to achieve a target false
alarm probability. This can be done analytically for the max test by inverting (4.5). For other tests, which do not have tractable expressions for the
false alarm probability, we set the threshold by simulating the test statistic
under the null. The threshold is chosen such that the empirical fraction of
exceedances of the threshold matches the desired false alarm. As expected,
the adaptive tests cannot match the rate under the null with non-trivial behavior under the alternative, and therefore we report the results for adaptive
tests at the standard 0.05 and 0.10 levels. The miss detection probabilities
reported for the max test were computed analytically via (4.6). Note that
the likelihood ratio test (2.7) with threshold set to meet a given false alarm
level is the oracle test which minimizes the miss detection probability [8].
As multiple definitions of the Higher Criticism test exist in literature, we
use the following version from [3]: Given a sample X1 , . . . , Xn , let pi = Q(Xi )
for 1 ≤ i ≤ n. Let {p(i) } denote {pi } sorted in ascending order. Then, the
higher criticism statistic is given by
(5.1)

i
− p(i)
√
HC∗n = max HCn,i where HCn,i = q n
n
1≤i≤n
p(i) (1 − p(i) )

and the null hypothesis is rejected when HC∗n is large. The HC test is optimally adaptive, i.e. is consistent whenever (2.7) is.

21

DETECTING SPARSE MIXTURES

The ACW test [1] is implemented as follows: Given the samples X1 , . . . , Xn ,
let X[i] denote the i-th largest sample by absolute value. Then,
Pk

∗

(5.2)

S = max

1≤k≤n

i=1 sgn(X[i] )

√

k

and the null hypothesis is rejected when S ∗ is large. The ACW test is adaptive for β > 12 . It is unknown how the ACW test behaves for β ≤ 12 . Note
that like the Max test (and unlike the HC test), the ACW test does not exploit exact knowledge of the null distribution (but assumes continuity and
symmetry about zero).
The performance of test (2.7) is summarized in Table 1 with a comparison
of adaptive tests in the moderately sparse example from the previous section
is given in Table 2. We used 115000 realizations of the null and alternative.
The sample sizes illustrated were chosen to be comparable with applications
of sparse mixture detection, such as the WMAP data in [5] which has n ≈
7 × 104 . Thus, our simulations provide evidence for both larger and smaller
sample sizes than used in practice. We see there is a large gap in performance
between the likelihood ratio test (2.7) and the adaptive tests, but the Higher
Criticism test performs significantly better than the Max or ACW tests.
LRT
PFA (n) PMD (n)
0.307
0.388
0.258
0.320
0.213
0.256
0.166
0.193
0.119
0.134
0.074
0.084
Table
1
p
Error probabilities for µn = 2(0.19) log n, n = n−0.6 for the LRT given by (2.7).
n
10
102
103
104
105
106

PFA = 0.10
ACW
LRT
Max
HC
0.807
0.665 0.744 0.666
0.816
0.542 0.704 0.630
0.792
0.417 0.672 0.561
0.751
0.281 0.639 0.491
0.685
0.158 0.603 0.396
0.602
0.064 0.562 0.295
Table
2
p
Miss Detection probabilities for µn = 2(0.19) log n, n = n−0.6 , for
probability 0.05 and 0.10.
n
10
102
103
104
105
106

LRT
0.776
0.667
0.548
0.403
0.252
0.119

PFA = 0.05
Max
HC
0.845 0.790
0.814 0.775
0.789 0.728
0.762 0.688
0.733 0.623
0.699 0.546

ACW
0.706
0.722
0.653
0.617
0.539
0.446
False Alarm

22

J. G. LIGO ET AL.
LRT
PFA (n) PMD (n)
1.62e-1
2.75e-1
6.31e-2
1.12e-1
7.63e-3
1.36e-2
5.38e-5
8.83e-5
Table 3
p
Error probabilities for µn = 2(0.66) log n, n = n−0.6 for the LRT given by (2.7).
n
10
102
103
104

PFA = 0.10
ACW
LRT
Max
HC
5.88e-1
3.59e-1 4.36e-1 3.38e-1
4.80e-1
8.45e-2 1.61e-1 1.07e-1
1.33e-1
1.89e-3 1.80e-2 4.20e-3
4.43e-3
7.10e-8 1.32e-4 ≤ 1e-5
Table
4
p
Miss Detection probabilities for µn = 2(0.66) log n, n = n−0.6 for False
probability 0.05 and 0.10.

n
10
102
103
104

LRT
4.66e-1
1.28e-1
3.69e-3
2.12e-7

PFA = 0.05
Max
HC
5.66e-1 7.18e-1
2.56e-1 6.24e-1
4.40e-2 2.48e-2
8.08e-4 ≤ 1e-5

ACW
5.88e-1
4.80e-1
1.33e-1
1.25e-3
Alarm

p
For the case of strong signals, we calibrate as µn = 2(0.66) log n for n =
n−0.6 . This corresponds to the rates given by Thm. 3.3. The performance of
test (2.7) is summarized in Table 3 with a comparison of adaptive tests in
the moderately sparse example from the previous section is given in Table 4.
Here we used 180000 realizations of the null and alternative. As even the
max test has error probabilities sufficiently small for many applications in
this regime at moderate sample sizes (which are still on the order used in
applications [5]), we only consider sample sizes up to n = 104 . We see that
in the strong signal case, the likelihood ratio test performs better than the
adaptive tests, but all tests produce sufficiently small error probabilities for
most applications.
6. Conclusions and Future Work. In this paper, we have presented
an rate characterization for the error probability decay with sample size
in a general mixture detection problem for the likelihood ratio test. In the
Gaussian location model, we explicitly showed that the rate characterization
holds for most of the detectable region. A partial rate characterization (an
upper bound on the rate under both hypotheses and universal lower bound
on the rate under H1,n ) was provided for the remainder of the detectable
region. In contrast to usual large deviations results [6, 8] for the decay of
error probabilities, our results show that the log-probability of error decays
sublinearly with sample size.
There are several possible extensions of this work. One is to provide corresponding lower bounds for the rate in cases not covered by Thm 3.1.

DETECTING SPARSE MIXTURES

23

Another is to provide a general analysis of the behavior that is not covered
by Thm 3.1 and 3.3, present in Thm 3.8 in the Gaussian location model.
As noted in [3], in some applications it is natural to require PFA (n) ≤ α
for some fixed α > 0, rather than requiring PFA (n) → 0. While Thm 3.4
shows the detectable region is not enlarged under in the Gaussian location
model (and similarly for some general models [4]), it is conceivable that the
oracle optimal test which fixes PFA (n) (i.e. one which compares LLR(n) to
a non-zero threshold) can achieve a better rate for PMD (n). It is expected
that the techniques developed in this paper extend to the case where PFA (n)
is constrained to a level α. In the Gaussian location model, the analysis of
(2.7) constrained to level α problem has been studied in [16] via contiguity
arguments.
Finally, it is important to develop tests that are amenable to a rate analysis and are computationally simple to implement over 0 < β < 1. In the
case of weak signals in the Gaussian location model, we see that the error
probabilities for the likelihood ratio test, which establish the fundamental
limit on error probabilities, decay quite slowly even with large sample sizes.
In this case, closing the gap between the likelihood ratio test and adaptive
tests is important for applications where it is desirable to have high power
tests. In the case of strong signals, we see the miss detection probability for
even the simplest adaptive test, the max test, are very small for moderate
sample sizes at standard false alarm levels so the rate of decay is not as
important as the weak signal case for applications.
SUPPLEMENTARY MATERIAL
Supplemental Material for “Detecting Sparse Mixtures: Rate of
Decay of Error Probability”
(doi: COMPLETED BY THE TYPESETTER; .pdf). We provide details of
proofs of the main theorems.
References.
[1] Arias-Castro, E. and Wang, M. (2013). Distribution-free tests for sparse heterogeneous mixtures. arXiv preprint arXiv:1308.0346 [].
[2] Arias-Castro, E. and Wang, M. (2015). The sparse Poisson means model. Electron.
J. Statist. 9 2170–2201. MR3406276
[3] Cai, T. T., Jeng, X. J. and Jin, J. (2011). Optimal detection of heterogeneous and
heteroscedastic mixtures. Journal of the Royal Statistical Society: Series B (Statistical
Methodology) 73 629–662. MR2867452
[4] Cai, T. T. and Wu, Y. (2014). Optimal Detection of Sparse Mixtures Against a
Given Null Distribution. IEEE Trans. Info. Theory 60 2217–2232. MR3181520
[5] Cayon, L., Jin, J. and Treaster, A. (2005). Higher Criticism statistic: detecting
and identifying non-Gaussianity in the WMAP first-year data. Monthly Notices of
the Royal Astronomical Society 362 826–832.

24

J. G. LIGO ET AL.

[6] Cover, T. M. and Thomas, J. A. (2006). Elements of Information Theory. NY:
John Wiley and Sons, Inc. MR2239987
[7] Darling, D. A. and Erdös, P. (1956). A limit theorem for the maximum of normalized sums of independent random variables. Duke Math. J. 23 143–155. MR0074712
[8] Dembo, A. and Zeitouni, O. (2010). Large deviations techniques and applications
38. Springer Science & Business Media. MR2571413
[9] den Hollander, F. (2008). Large deviations 14. American Mathematical Soc.
MR1739680
[10] Dobrushin, R. L. (1958). A statistical problem arising in the theory of detection
of signals in the presence of noise in a multi-channel system and leading to stable
distribution laws. Theory of Probability & Its Applications 3 161–173.
[11] Donoho, D. and Jin, J. (2004). Higher criticism for detecting sparse heterogeneous
mixtures. Ann. Statist. 32 962–994. MR2065195
[12] Donoho, D. and Jin, J. (2008). Higher criticism thresholding: Optimal feature selection when useful features are rare and weak. Proceedings of the National Academy
of Sciences 105 14790–14795.
[13] Durrett, R. (2010). Probability: Theory and Examples, 4 ed. Cambridge University
Press. MR2722836
[14] Gibbs, A. L. and Su, F. E. (2002). On choosing and bounding probability metrics.
International statistical review 70 419–435.
[15] Goeman, J. J. and Bühlmann, P. (2007). Analyzing gene expression data in terms
of gene sets: methodological issues. Bioinformatics 23 980–987.
[16] Ingster, Y. and Suslina, I. A. (2003). Nonparametric goodness-of-fit testing under
Gaussian models 169. Springer Science & Business Media. MR1991446
[17] Jager, L. and Wellner, J. A. (2007). Goodness-of-fit tests via phi-divergences.
Ann. Statist. 35 2018–2053. MR2363962
[18] Lehmann, E. L. and Romano, J. P. (2006). Testing statistical hypotheses. Springer
Science & Business Media. MR2135927
[19] Ligo, J. G., Moustakides, G. V. and Veeravalli, V. V. (2016). Rate analysis for
detection of sparse mixtures. In 2016 IEEE International Conference on Acoustics,
Speech and Signal Processing (ICASSP) 4244-4248.
[20] Mossel, E. and Roch, S. (2015). Distance-based species tree estimation:
information-theoretic trade-off between number of loci and sequence length under
the coalescent. In Approximation, randomization, and combinatorial optimization.
Algorithms and techniques. LIPIcs. Leibniz Int. Proc. Inform. 40 931–942. Schloss
Dagstuhl. Leibniz-Zent. Inform.,Wadern,DE. MR3442006
[21] Poor, H. V. (1994). An Introduction to Signal Detection and Estimation, 2 ed.
Springer, New York, NY. MR1270019
[22] Saligrama, V. and Zhao, M. (2012). Local Anomaly Detection. In 2012 International Conference on Artificial Intelligence and Statistics (AISTATS) 969–983.
[23] Walther, G. (2013). The average likelihood ratio for large-scale multiple testing and
detecting sparse mixtures. In From probability to statistics and back: high-dimensional
models and processes. Inst. Math. Stat. (IMS) Collect. 9 317–362. Inst. Math. Statist.,
Beachwood, OH. MR3202643

DETECTING SPARSE MIXTURES
Coordinated Science Laboratory
and
Department of Electrical and
Computer Engineering
University of Illinois at
Urbana-Champaign
Urbana, IL 61801, USA
E-mail: ligo2@illinois.edu
vvv@illinois.edu

25

Department of Electrical and
Computer Engineering
University of Patras
26500 Rio, Greece
and
Department of Computer Science
Rutgers University
New Brunswick, NJ 08854, USA
E-mail: moustaki@upatras.gr

Submitted
arXiv: 1509.07566

SUPPLEMENTAL MATERIAL FOR:
“DETECTING SPARSE MIXTURES: RATE OF DECAY OF
ERROR PROBABILITY”
By Jonathan G. Ligok , George V. Moustakides†† and Venugopal
V. Veeravallik
University of Illinois at Urbana-Champaignk , University of Patras†† and
Rutgers University††
7. Weak Signals: Supporting Lemmas. In this section, we provide
the proofs of the lemmas that are necessary for establishing the validity of
Theorem 3.1.
Lemma 7.1. Under the assumptions of Theorem 3.1, there exist positive
constants C1 , C2 such that for sufficiently large n we have
C1 2n Dn2 ≥ σn2 ≥ C2 2n Dn2 ,
where σn2 is defined in (3.11).
Proof. We first show that for sufficiently large n,
(7.1)

C1 ≥

σn2 Λn (sn )
.
2n Dn2

Note that
(log (1 + x))2 (1 + x)s ≤ 2x2 for s ∈ (0, 1) , x ≥ 1.
√
This follows from 0 ≤ log (1 + x) ≤ x for x ≥ 0 and 1 ≤ (1 + x)s ≤ 2x for
x ≥ 1 and s ∈ (0, 1). Also, note Λn (0) = Λn (1) = 1 implying sn ∈ (0, 1) by
convexity of Λn (Lemma 2.2.5, [8]).
For shorthand, we will write Ln = Ln (X1 ). Then,
h
i
Λn (sn )σn2 = E0 (log (1 + n (Ln − 1)))2 (1 + n (Ln − 1))sn
h
i
= E0 (log (1 + n (Ln − 1)))2 (1 + n (Ln − 1))sn 1{n (Ln −1)>1}
h
i
(7.3)
+ E0 (log (1 + n (Ln − 1)))2 (1 + n (Ln − 1))sn 1{n (Ln −1)≤1}
(7.2)

¶
Supported by the US National Science Foundation under grants CIF 1514245 and
CIF 1513373.

1

2

J. G. LIGO ET AL.



We first consider E0 (log (1 + n (Ln − 1)))2 (1 + n (Ln − 1))sn 1{n (Ln −1)>1} .
By (7.2), we have on the event {n (Ln − 1) > 1} that
log (1 + n (Ln − 1))

2

1 + n (Ln − 1)

sn

≤ 2 n (Ln − 1)

2

.

Thus,


(7.4) E0 (log (1 + n (Ln − 1)))2 (1 + n (Ln − 1))sn 1{n (Ln −1)>1}




≤ E0 2 (n (Ln − 1))2 1{n (Ln −1)>1} ≤ 22n E0 (Ln − 1)2 = 22n Dn2 .
We now consider
h
i
E0 (log (1 + n (Ln − 1)))2 (1 + n (Ln − 1))sn 1{n (Ln −1)≤1} .
A simple calculus argument shows that (log (1 + x))2 ≤ 5x2 for x ≥ − 12 .
Note that since Ln ≥ 0, −n ≤ n (Ln − 1). Because n → 0, for sufficiently
large n we have that n < 12 and (log (1 + n (Ln − 1)))2 ≤ 5 (n (Ln − 1))2
holds. Also, (1 + n (Ln − 1))sn ≤ 2sn ≤ 2 on the event {n (Ln − 1) ≤ 1}.
Thus,
h
i
(7.5) E0 (log (1 + n (Ln − 1)))2 (1 + n (Ln − 1))sn 1{n (Ln −1)≤1}
h
i
h
i
≤ E0 10 (n (Ln − 1))2 1{n (Ln −1)≤1} ≤ 10 E0 (n (Ln − 1))2 = 10 2n Dn2 .
Using (7.4),(7.5) in (7.3), we see for sufficiently large n that
Λn (sn )σn2 ≤ 122n Dn2
establishing (7.1).
We now show that
(7.6)

C2 ≤

σn2 Λn (sn )
.
2n Dn2

DETECTING SPARSE MIXTURES”

3

Taking any γ < 12 , from Equation (3.1) of Theorem 3.1,
h
i
Λn (sn )σn2 = E0 (log (1 + n (Ln − 1)))2 (1 + n (Ln − 1))sn
h
i
≥ E0 (log (1 + n (Ln − 1)))2 (1 + n (Ln − 1))sn 1{n (Ln −1)≤γ}
 


1
(7.7)
1{n (Ln −1)≤γ}
≥ E0 (log (1 + n (Ln − 1)))2
2
h
i
1
≥ E0 (n (Ln − 1))2 1{n (Ln −1)≤γ}
(7.8)
4
"
#
(n (Ln − 1))2
Dn2
E0
1{n (Ln −1)≤γ}
=
4
Dn2
#
"
Dn2
(n (Ln − 1))2
=
E0
1{Ln ≤1+ γ }
n
4
Dn2
#!
"
Dn2 2n
(Ln − 1)2
(7.9)
=
1 − E0
1{Ln ≥1+ γ }
n
4
Dn2
Where (7.7) follows from (1 + n (Ln − 1))sn ≥ (1 − n )sn ≥ 1 − n ≥ 12 for
sufficiently large n, as sn ∈ (0, 1) and n → 0. A simple calculus argument
shows that 12 x2 ≤ (log (1 + x))2 for x ∈ [− 21 , 12 ]. This, along the fact that
with − 12 < −n ≤ n (Ln − 1) ≤ γ < 12 on the event {n (Ln − 1) ≤ γ} for
sufficiently large n establishes (7.8). The definition of Dn2 furnishes (7.9).
2
Noting that E0 [ (LnD−1)
1{Ln ≥1+ γ } ] → 0 by the assumptions of Thm 2.1 in
2
n
n
the main text, (7.6) is established.
In order to remove the Λn (sn ) factor from the bounds, note that Λn (sn ) ≤
Λn (1) ≤ 1 and that Λn (s) ≥ (1 − n )s ≥ 21 for sufficiently large n. This along
with (7.1) and (7.6) establishes the lemma.
This lemma is established identically under H1,n by applying a change of
measure to P0,n (which replaces sn with 1 − sn in the argument above).
Lemma 7.2. Under the assumptions of Theorem 3.1, if we use the tilted
measure, we have
(7.10)



1
P̃ LLR (n) ≥ 0 →
2

as n → ∞.
Proof. For the proof, we will need the Lindeberg-Feller Central Limit
Theorem whose validity is demonstrated in Theorem 3.4.5, [13]:

4

J. G. LIGO ET AL.

Theorem 7.3. For each n, let Zn,i , 1 ≤ i ≤ n, be independent zero-mean
random variables. Suppose
n
X
 2 
lim
E Zn,i
= σ2 > 0

(7.11)

n→∞

i=1

and for all γ > 0,
n
h
i
X
lim
E |Zn,i |2 1{|Zn,i |>γ} = 0

(7.12)

n→∞

i=1

Then, Sn = Zn,1 + . . . + Zn,n converges in distribution to the normal
distribution with mean zero and variance σ 2 as n → ∞.
Let us now continue with the proof of Lemma 7.2. We draw i.i.d. {Xi }ni=1
from H0,n . Define for 1 ≤ m ≤ n

ξn,i
.
ξn,i = log 1 + n Ln (Xi ) − 1 , Zn,i = √
nσn

(7.13)
Note that

n
X

(7.14)

i=1

LLR(n)
Zn,i = √
.
nσn

Pn

We show i=1 Zn,i converges to a standard normal distribution under the
2 ] = 1.
tilted measure. As stated in the main text, Ẽ [Zn,i ] = 0 and Ẽ[Zn,i
n
Thus, (7.11) is satisfied with σ 2 = 1.
It remains to check (7.12). Since for fixed n, the Zn,i are i.i.d, it suffices
to verify that
#
"
2
 2

ξn,1
Ẽ nZn,1 1{|Zn,1 |>γ} = Ẽ
1 2
→ 0,
σn2 { ξn,12 >γ 2 }
nσn

n → ∞. To simplify notation, let Ln = Ln (X1 ). By Lemma 7.1, it suffices
to show that
"
#
2
ξn,1
Ẽ 2 2 1 ξn,1
→0
2
n Dn { 2 2 >nγ 2 }
C2 n Dn

which changing to the P0 measure is equivalent to showing that for 0 < γ <
γ0
"
#
2
ξn,1
sn
→0
(7.15)
E0 2 2 (1 + n (Ln − 1)) 1 ξn,1
2
2
n Dn
{
2 2 >nγ }
C2 n Dn

DETECTING SPARSE MIXTURES”

5

since Λn (sn ) ∈ [ 12 , 1] for sufficiently large n.
We decompose (7.15) into
#
2
ξn,1
sn
(7.16) E0 2 2 (1 + n (Ln − 1)) 1 ξn,1
2
2
n Dn
{
2 >nγ }
C2 2
n Dn
"
#
2
ξn,1
= E0 2 2 (1 + n (Ln − 1))sn 1 ξn,1
2
2
n Dn
{
2 >nγ ,n (Ln −1)>1}
C2 2
n Dn
"
#
2
ξn,1
sn
+ E0 2 2 (1 + n (Ln − 1)) 1 ξn,1
2
2
n Dn
{
2 2 >nγ ,n (Ln −1)≤1}
"

C2 n Dn

and show that both parts in (7.16) tend to zero. For the first part applying
2
(7.2) and log(1 + x) ≤ x for x > 0,
"
#
2
ξn,1
sn
E0 2 2 (1 + n (Ln − 1)) 1 ξn,1
2
2
n Dn
{
2 >nγ ,n (Ln −1)>1}
C2 2
n Dn
#
"
22n (Ln − 1)2
≤ E0
1{ 2n (Ln −1)2 >nγ 2 , (L −1)>1}
n n
2n Dn2
2
C2 2
n Dn


(Ln − 1)2
√
= 2E0
1{ Ln√−1 >γ n,n (Ln −1)>1}
Dn2
Dn C2


2
(Ln − 1)
√ √
γ
1
≤ 2E0
{Ln >1+ C2 nDn n  }
n
Dn2


2
(Ln − 1)
≤ 2E0
1{Ln >1+ γ } → 0
n
Dn2
√
where the last inequality holds because
nDn n → ∞ we can conclude
√ from
√
that for sufficiently large n we have C2 nDn n ≥ 1.
We now show that the second part in (7.16) tends to zero as well. We
observe that since Ln ≥ 0 we have −n ≤ n (Ln − 1). Using (log(1 + x))2 ≤
5x2 for x ≥ − 21 , and that (1 + n (Ln − 1))sn ≤ 2sn ≤ 2 on the event

6

J. G. LIGO ET AL.

{n (Ln − 1) ≤ 1}, we see that for n sufficiently large such that n < 21 ,
"
#
2
sn
ξn,1
E0 2 2 1 + n (Ln − 1) 1 ξn,1
2
2
n Dn
{
2 >nγ ,n (Ln −1)≤1}
C2 2
n Dn
"
#
2n (Ln − 1)2
≤ 10E0
1{ 52n (Ln −1)2 >nγ 2 , (L −1)≤1}
n n
2n Dn2
2
C2 2
n Dn


2
(Ln − 1)
q
≤ 10E0
1
C2 √
{|Ln −1|>
nDn γ}
Dn2
5


2
(Ln − 1)
q
= 10E0
1
C2 √
nDn γ}
{Ln >1+
Dn2
5


2
(Ln − 1)
≤ 10E0
1{Ln >1+ γ }
n
Dn2
√
The last equality follows from the fact that nn Dn → ∞, since this im√
plies that nDnq→ ∞, which suggests that for large
enough n we cannot
q √
C2 √
C2
have 1 − Ln >
nDn γ but only Ln − 1 >
nDn γ. Finally the
5
q5 √
last inequality is true for large enough n such that C52 nDn n ≥ 1, which
is always possible since this quantity tends to infinity because of our assumption in (3.3). Thus, (7.15) holds and the Lindeberg-Feller CLT shows
√
that LLR(n)
converges to a standard normal distribution under the tilted
nσn
measure. Therefore,


LLR(n)
1
(7.17)
P̃ [LLR(n) ≥ 0] = P̃ √
≥0 →
2
nσn
as n → ∞ establishing the lemma.
Verifying the Lindeberg-Feller CLT conditions for analyzing PMD is done
by changing from the P1 to the P0 measure.
Lemma 7.4.
(7.18)

Under the assumptions of Theorem 3.1 we have
lim inf
n→∞

log Λn (sn )
1
≥− .
2n Dn2
8

Proof. Consider the function (1 + x)s for s ∈ (0, 1) and x ∈ [−γ, γ]
where 0 < γ < 1. Then
1
1 (1 − s) (2 − s) 3
x
(1 + x)s = 1 + sx + s (s − 1) x2 +
2
6 (1 + ξ)3−s
1
1
γ
(7.19)
≥ 1 + sx − x2 −
x2 = 1 + sx − ω(γ)x2 ,
8
3 (1 − γ)3

DETECTING SPARSE MIXTURES”

where we define ω(γ) =

1
8

+

γ
1
3 (1−γ)3 .

7

The first equality holds for some

ξ ∈ [−γ, γ] by the mean value form of Taylor’s theorem. The inequality is obtained by minimizing the coefficient of x2 while for the last term we observe
that since x ≥ −γ we have x3 ≥ −γx2 ; furthermore (1 + ξ)3−s ≥ (1 − γ)3
and (1 − s)(2 − s) ≤ 2. When we substitute the previous inequalities we
obtain the lower bound in (7.19).
Using this, we can lower bound Λn (s) for all s ∈ (0, 1). Fix 0 < γ < 1. As
before, we will use the shorthand Ln = Ln (X1 ). Then, for sufficiently large
n we have n < γ suggesting that −γ ≤ n (Ln − 1). Therefore using (7.19)
and assuming n sufficiently large we can write
Λn (s) = E0 [(1 + n (Ln − 1))s ]


≥ E0 (1 + n (Ln − 1))s 1{n (Ln −1)≤γ}


≥ E0 (1 + sn (Ln − 1)) 1{n (Ln −1)≤γ} − ω(γ)2n Dn2


= 1 − ω(γ)2n Dn2 − E0 (1 + sn (Ln − 1)) 1{n (Ln −1)≥γ}


≥ 1 − ω(γ)2n Dn2 − E0 (1 + n (Ln − 1)) 1{n (Ln −1)≥γ}



1
1 2
2 2
2
≥ 1 − ω(γ)n Dn − E0
+
 (Ln − 1) 1{n (Ln −1)≥γ}
γ2 γ n



(Ln − 1)2
2
γ
1{Ln ≥1+  } 2n Dn2
≥ 1 − ω(γ) + 2 E0
n
γ
Dn2


2
≥ 1 − ω(γ) + 2 γ 3 2n Dn2 ,
γ
where in the second equality we used the fact that E0 [Ln − 1] = 0 and
in the third inequality we replaced the maximum values of s = 1. In the
fourth inequality we used the property that on the set {Ln ≥ 1 + γn } we can
write γ12 2n (Ln − 1)2 ≥ 1 and γ1 2n (Ln − 1)2 ≥ n (Ln − 1). Finally in the last
inequality using the condition of Theorem 3.1 and assuming n sufficiently
large the expectation becomes smaller than γ 3 .
Using the previous result we obtain

log 1 − (ω(γ) + 2γ)2n Dn2
log Λn (sn )
lim inf
≥ lim inf
= −(ω(γ) + 2γ),
n→∞
n→∞
2n Dn2
2n Dn2
where for the equality we used the limit log(1−x)
→ −1 as x → 0 and the
x
assumption that n Dn → 0. Letting γ → 0 establishes the lemma since
ω(0) = 18 .
The proof is identical under H1,n , where the analogue of the lemma is
n)
lim inf n→∞ Λn(1−s
≥ − 18 .
2 D2
n

n

8

J. G. LIGO ET AL.

8. Moderate Signals: Gaussian Location Model. Assume
> 12 . Recall from the proof of Thm 3.1
 hp
in
(8.1)
PFA (n) ≤ E0
1 − n + n Ln (X1 )
β
2r

3
2

>

and
hp
i
1
(8.2) E0
1 − n + n Ln (X1 ) = 1− E0
2

"

#
2n (Ln (X1 ) − 1)2
p
2 .
1 + 1 + n (Ln (X1 ) − 1)

We√write the observations as a multiple of µn , X = αµn . Then, taking
µn = 2r log n, we have
2

Ln (x) = e−µn /2+µn x = nr(2α−1) .

(8.3)
In view of (8.3),

n (Ln − 1) = nr(2α−1)−β − n−β .

(8.4)

Thus, if r(2α − 1) − β > 0 we have n (Ln − 1) → ∞ and if r(2α − 1) − β < 0
we have n (Ln − 1) → 0 as n → ∞.
2
2
3
β
Let κ = 2r
+ 12 . Note (1+√x1+x)2 ≥ x4 − x8 for x ≥ −1. Thus, on the event
{X1 < κµn },
2n (Ln (X1 ) − 1)2 3n (Ln (X1 ) − 1)3
2n (Ln (X1 ) − 1)2
≥
−
p
2
4
8
1 + 1 + n (Ln (X1 ) − 1)


(1 − n−β )
2
2 1
(8.5)
≥ n (Ln (X1 ) − 1)
−
4
8
2
2
 (Ln (X1 ) − 1)
(8.6)
≥ n
8
where (8.5) follows from −1 ≤ −n ≤ n (Ln (X1 ) − 1) ≤ 1 − n−β on {X1 <
κµn }, and (8.6) follows from non-negativity of the terms involved. Then,
"
#
2n (Ln (X1 ) − 1)2
E0
p
2
1 + 1 + n (Ln (X1 ) − 1)
"
#
2n (Ln (X1 ) − 1)2
(8.7)
≥ E0
p
2 1{X1 <κµn }
1 + 1 + n (Ln (X1 ) − 1)
(8.8)
(8.9)

2n
E0 [(Ln (X1 ) − 1)2 1{X1 <κµn } ]
8

2  2
= n eµn Φ((κ − 2)µn ) − 2Φ((κ − 1)µ) + Φ(κµ)
8
≥

9

DETECTING SPARSE MIXTURES”

where (8.7) follows from non-negativity, (8.8) follows from (8.6) and Φ denotes the standard normal cumulative distribution function.
2
By the standard approximation Q(x) ≈ x√12π e−x /2 , we see that the domi2

nant term in (8.9) is 2n eµn Φ((κ−2)µn )/8 and is of the order of

β
which tends to zero by our assumption on 2r
. Thus, as in the proof of Thm
3.1, by (8.1)


log PFA (n)
2n  µ2n
≤ log 1 −
e Φ((κ − 2)µn ) − 2Φ((κ − 1)µ) + Φ(κµ) .
n
16
2

Dividing both sides by 2n eµn Φ((κ − 2)µn ) and taking a lim sup yields
lim sup
n→∞

log PFA (n)
µ
2
nn e 2n Φ((κ − 2)µn )
2

≤−

2

n−2β+2r−r(1.5−β/2r)
√
2r log n

1
.
16

For consistency, it suffices to require n2n eµn Φ((κ − 2)µn ) → ∞. Thus, it
2

√
β
suffices to require 1 − 2β + 2r − r 32 − 2r
> 0, since log n is negligible
with respect to any positive power of n. Combining the constraints −2β +
2

2

β
β
β
< 0, 1 − 2β + 2r − r 32 − 2r
> 0, 23 > 2r
> 12 gives the
2r − r 32 − 2r
desired rate characterization.
The proof for PMD is identical. Note that this bound is likely not tight
(even if it has the right order), since we neglected the event {X1 ≥ κµn } to
form the bound.

10
Coordinated Science Laboratory
and
Department of Electrical and
Computer Engineering
University of Illinois at
Urbana-Champaign
Urbana, IL 61801, USA
E-mail: ligo2@illinois.edu
vvv@illinois.edu

J. G. LIGO ET AL.
Department of Electrical and
Computer Engineering
University of Patras
26500 Rio, Greece
and
Department of Computer Science
Rutgers University
New Brunswick, NJ 08854, USA
E-mail: moustaki@upatras.gr

