Innovated higher criticism for detecting sparse signals in correlated noise

Introduction.

Donoho and Jin DJ04 developed Tukey’s Tukey proposal for “higher criticism” (HC), showing that a method based on the statistical significance of a large number of statistically significant test results could be used very effectively to detect the presence of very sparsely distributed signals. They demonstrated that HC is capable of optimally detecting the presence of signals that are so weak and so sparse that the signal cannot be consistently estimated. Applications include the problem of signal detection against cosmic microwave background radiation (Cayon, Jin and Treaster Cayon2 , Cruz et al. Cruz , Jin Jin04 , Jin06 , Jin07 , Jin et al. Starck ). Related work includes that of Cai, Jin and Low CJL , Hall, Pittelkow and Ghosh HPG and Meinshausen and Rice Rice .

The context of Donoho and Jin’s DJ04 work was that where the noise is white, although a small number of investigations have been made of the case of correlated noise (Hall, Pittelkow and Ghosh HPG , Hall and Jin HJ08 , Delaigle and Hall DH ). However, that research has focused on the ability of standard HC, applied in the form that is appropriate for independent data, to accommodate the nonindependent case. In this paper we address the problem of how to modify HC by developing innovated higher criticism (iHC) and showing how to optimize performance for correlated noise.

Curiously, it turns out that when using the iHC method tuned to give optimal performance, the case of independence is the most difficult of all, statistically speaking. To appreciate why this result is reasonable, note that if the noise is correlated then it does not vary so much from one location to a nearby location, and so is a little easier to identify. In an extreme case, if the noise is perfectly correlated at different locations then it is constant, and in this instance it can be easily removed.

On the other hand, standard HC does not perform well in the case of correlated noise, because it utilizes only the marginal information in the data without much attention to the correlation structure. Innovated HC is designed to exploit the advantages offered by correlation and gives good performance across a wide range of settings.

The concept of the “detection boundary” was introduced by Donoho and Jin DJ04 in the context of white noise. In this paper, we extend it to the correlated case. In brief, the detection boundary describes the relationship between signal sparsity and signal strength that characterizes the boundary between cases where the signal can be detected and cases where it cannot. In the setting of dependent data, this watershed depends on the correlation structure of the noise as well as on the sparsity and strength of the signal. When correlation decays at a polynomial rate we are able to characterize the detection boundary quite precisely. In particular, we show how to construct concise lower/upper bounds to the detection boundary, based on the diagonal components of the inverse of the correlation matrix, $\Sigma_{n}$. A special case is where $\Sigma_{n}$ is Toeplitz; there the upper and the lower bounds to the detection boundary are asymptotically the same. In the Toeplitz case, the iHC is optimal for signal detection but standard HC is not.

There is a particularly extensive literature on multiple hypothesis testing under conditions of dependence. It includes contributions to the control of family-wise error rate and false discovery rate, and work of Abramovich et al. ABDJ , Benjamini and Hochberg BenHoch , Benjamini and Yekutieli BenYek , Brown and Russel Brown , Cai and Sun CaiSun , Clarke and Hall Clarke , Cohen, Sackrowitz and Xu Cohen , Donoho and Jin DJ06 , Dunnett and Tamhane Dunn , Efron Efron , Finner and Roters Finn , Genovese and Wasserman Gen , Jin and Cai JC , Olejnik et al. Ole , Rom Rom , Sarkar and Chang Sar and Wu Wu . Work of Kuelbs and Vidyashankar Kuelbs is also related. Our contributions differ from those of these authors in that we point to the advantages, rather than the disadvantages, of dependence, and show how the advantages can be exploited. In particular, as noted above, the problem of denoising dependent data is actually simpler than in the case of independence. We show how to exploit dependence and obtain improvements in performance relative to what is possible in the context of independence and also relative to the inferior performance that is obtained if a method that is designed for the case of independence is applied inappropriately to dependent data. In contrast, earlier work has tended to try to minimize the problems caused by dependence rather than to capitalise on the advantages that are available.

The paper is organized as follows. Section 2 introduces the sparse signal model followed by a brief review of the uncorrelated case. Section 3 establishes lower bounds to the detection boundary in correlated settings. Section 4 introduces innovated HC and establishes an upper bound to the detection boundary. Section 5 applies the main results in Sections 3 and 4 to the case where the $\Sigma_{n}$’s are Toeplitz. In this case, the lower bound coincides with the upper bound and innovated HC is optimal for detection. Section 6 discusses a case where the signals have a more complicated structure. Section 7 investigates a case of strong dependence. Simulations are given in Section 8, and discussion is given in Section 9. Section 10 and the Appendix give proofs of theorems and lemmas, respectively.

Sparse signal model and review of HC.

Consider an $n$-dimensional Gaussian vector,

with the mean vector $\mu$ unknown and the dimension $n$ large. In most parts of the paper, we assume that $\Sigma=\Sigma_{n}$ is known and has unit diagonal elements (the case where $\Sigma_{n}$ is unknown is discussed in Section 4.4 and Section 9). We are interested in testing whether no signal exists (i.e., $\mu=0$) or there is a sparse and faint signal.

Formulae (2) and (5), below, introduce quantities $m$ and $A_{n}$ that represent signal sparsity and signal strength, respectively. In particular, as $m$ increases the amount of sparsity decreases, and as $A_{n}$ increases the strength of the signal increases. Of course, an increase in either $m$ or $A_{n}$ leads to an increase in the ease with which the signal can be detected and read. It would be possible to connect $m$ and $A_{n}$ by a formula, and use that relationship to adjust the signal, but we feel that the influence of the key elements of sparsity and strength are most clearly presented by treating them separately. In particular, we model the number of nonzero entries of $\mu$ as

These assumptions are made throughout the paper, in cases where $\Sigma$ is relatively general as well as in cases (see Sections 2.2 and 2.3, below) where the noise variables are assumed uncorrelated and so $\Sigma$ is the identity. Variations of this model give similar results. For example, if we take the $j$th nonzero signal to equal $W_{j}\sqrt{2\log n}$, where the $W_{j}$’s are independent random variables with a common, nonnegative distribution that has an upper endpoint $r^{1/2}$ satisfying $P(W\leq r^{1/2})=1$ and $P(W>r^{1/2}-\varepsilon)>0$ for all $\varepsilon>0$, then the results are identical to their counterparts when signal strength is given by (5).

We are interested in testing which of the following two hypotheses is true:

This testing problem was found to be delicate even in the uncorrelated case where $\Sigma_{n}=I_{n}$. See DJ04 (also CJL , Ingster97 , Ingster99 , Jin04 , Rice ) for details.

The testing problem is characterized by the curve $r=\rho^{*}(\beta)$ in the $\beta$–$r$ plane where

and we call $r=\rho^{*}(\beta)$ the detection boundary. The detection boundary partitions the $\beta$–$r$ plane into two sub-regions: the undetectable region below the boundary and the detectable region above the boundary (see Figure 1). In the interior of the undetectable region, the signals are so sparse and so faint that no test is able to successfully separate the alternative hypothesis from the null hypothesis in (6): the sum of types I and II errors of any test tends to $1$ as $n$ diverges to infinity. In the interior of the detectable region, it is possible to have a test such that as $n$ diverges to infinity, the type I error tends to zero and the power tends to $1$. [In fact, Neyman–Pearson’s Likelihood Ratio Test (LRT) is such a test.] See DJ04 , Ingster97 , Jin04 , for example.

The drawback of LRT is that it needs detailed information about the unknown parameters $(\beta,r)$. In practice, we need a test that does not need such information; this is where HC comes in.

Consider the higher criticism test which rejects the null hypothesis when

It follows from (9) that the type I error tends to zero as $n$ diverges to infinity. For any parameters $(\beta,r)$ that fall in the interior of the detectable region, the type II error also tends to zero. This is the following theorem.

That is, the higher criticism test adapts to unknown parameters $(\beta,r)$ and yields asymptotically full power for detection throughout the entire detectable region. We call this the optimal adaptivity of higher criticism DJ04 .

Theorem 2.1 is closely related to DJ04 , Theorem 1.2, where a mixture model is used. The mixture model reduces approximately to the current model if we randomly shuffle the coordinates of $X$. However, despite its appealing technical convenience, it is not clear how to generalize the mixture model from the uncorrelated case to general correlated settings. Theorem 2.1 is a special case of Theorem 4.2.

We now turn to the correlated case. In this case, the exact “detection boundary” may depend on $\Sigma_{n}$ in a complicated manner, but it is possible to establish both a tight lower bound and a tight upper bound. We discuss the lower bound first.

Lower bound to detectability.

To establish the lower bound, a key element is the theory in comparison of experiments (e.g., Strasser ) where a useful guideline is that adding noise always makes the inference more difficult. Thus we can alter the model by either adding or subtracting a certain amount of noise so that the difficulty level (measured by the Hellinger distance, or the $\chi^{2}$-distance, etc., between the null density and the alternative density) of the original problem is sandwiched by those of the two adjusted models. The correlation matrices in the latter have a simpler form and hence are much easier to analyze. Another key element is the recent development of matrix characterizations based on polynomial off-diagonal decay where it shows that the inverse of a matrix with this property shares the same rate of decay as the original matrix.

We begin by comparing two experiments that have the same mean, but where the data from one experiment are more noisy than those from the other. Intuitively, it is more difficult to make inference in the first experiment than in the other. Specifically, consider the two Gaussian models

where $\mu$ is an $n$-vector that is generated according to some distribution $G=G_{n}$. The second model is more noisy than the first, in the sense that $\Sigma^{*}\geq\Sigma$. Here, given two matrices, $A$ and $B$, we write $A\geq B$ if $A-B$ is positive semi-definite.

See Section 10 for a proof. [The Hellinger distance between distributions with densities $f$ and $g$ equals $\frac{1}{2}\int(f^{1/2}-g^{1/2})^{2}$.]

2 Matrices having polynomial off-diagonal decay.

Next, we review results concerning matrices with polynomial off-diagonal decay. The main message is that, under mild conditions, if a matrix has polynomial off-diagonal decay, then its inverse as well as its Cholesky factorization (which is unique if we require the diagonal entries to be positive) also have polynomial off-diagonal decay, and with the same rate. This beautiful result was recently obtained by Jaffard Jaffard (see also Grochenig1 , Sun1 ).

In detail, writing $\Theta_{n}$ for the set of $n\times n$ correlation matrices, we introduce, for $\lambda>1$,

This is the set of matrices which have a given rate of polynomial off-diagonal decay and where the operator norm is uniformly bounded from below. Consider a sequence of matrices $\{\Sigma_{n}\}_{n=1}^{\infty}$ such that $\Sigma_{n}\in\Theta_{n}^{*}(\lambda,c_{0},M)$ for each $n$. It turns out that the inverses (as well as the Cholesky factorizations) of such sequences enjoy polynomial off-diagonal decay with the same rate as that of the matrices themselves. See the Appendix for the proof.

3 Lower bound to detectability.

Consider a sequence of matrices $\{\Sigma_{n}\}_{n=1}^{\infty}$ such that $\Sigma_{n}\in\Theta_{n}^{*}(\lambda,c_{0},M)$ for each $n$. Suppose the extreme diagonal entries of $\Sigma_{n}^{-1}$ have an upper limit $\bar{\gamma}_{0}$ in the range $0<\bar{\gamma}_{0}<\infty$; that is,

Recall that the detection boundary in the uncorrelated case is defined by $r<\rho^{*}(\beta)$. The following theorem asserts that, in the presence of correlation, if we change the definition to $r<\bar{\gamma}_{0}^{-1}\cdot\rho^{*}(\beta)$, then we obtain at least a lower bound to the detection boundary.

Fix $\beta\in(1/2,1)$, $r\in(0,1)$, $\lambda>1$, $c_{0}>0$, and $M>0$. Consider a sequence of correlation matrices $\Sigma_{n}\in\Theta_{n}^{*}(\lambda,c_{0},M)$ that satisfy (14). If $r<\bar{\gamma}_{0}^{-1}\rho^{*}(\beta)$, then the null hypothesis and alternative hypothesis in (6) merge asymptotically, and the sum of types I and II errors of any test converges to $1$ as $n$ diverges to infinity.

We now turn to the upper bound. The key is to adapt the higher criticism to correlated noise and form a new statistic—innovated higher criticism.

Innovated higher criticism, upper bound to detectability.

Originally designed for the independent case, standard HC is not really appropriate for dependent data for the following reasons. First, HC only summarizes the information that resides in the marginal effects of each coordinate and neglects the correlation structure of the data. Second, HC remains the same if we randomly shuffle different coordinates of $X$. Such shuffling does not have an effect if $\Sigma_{n}=I_{n}$, but does otherwise. In this section we build the correlation into the standard higher criticism and form a new statistic—innovated higher criticism (iHC). We then use iHC to establish an upper bound to detectability. The iHC is intimately connected to the well-known notion of innovation in time series Brock [see (15) below], hence the name innovated higher criticism.

Below, we begin by discussing the role of correlation in the detection problem.

Consider model (1) in the two cases $\Sigma_{n}=I_{n}$ and $\Sigma_{n}\neq I_{n}$. Which is the more difficult detection problem?

Here is one way to look at it. Since the mean vectors are the same in the two cases, the problem where the noise vector contains more “uncertainty” is more difficult than the other. In information theory, the total amount of uncertainty is measured by the differential entropy, which in the Gaussian case is proportional to the determinant of the correlation matrix Cover . As the determinant of a correlation matrix is largest when and only when it is the identity matrix, the uncorrelated case contains the largest amount of “uncertainty” and therefore gives the most difficult detection problem. In a sense, the correlation is a “blessing” rather than a “curse” as one might have expected.

Here is another way to look at it. For any positive definite matrix $\Sigma_{n}$, denote the inverse of its Cholesky factorization by $U_{n}$, a function of $\Sigma_{n}$ (so that $U_{n}\Sigma_{n}U_{n}^{\prime}=I_{n}$). Model (1) is equivalent to

(In the literature of time series Brock , $U_{n}X$ is intimately connected to the notion of innovation.) Compared to the uncorrelated case, that is,

Two key observations are as follows. First, since $\Sigma_{n}$ has unit diagonal entries, every diagonal entry of $U_{n}$ is greater than or equal to $1$, especially

Next we make the argument more precise. Fix a positive sequence $\{\delta_{n}\dvtx n\geq 1\}$ that tends to zero as $n$ diverges to infinity, and a sequence of integers $\{b_{n}\dvtx n\geq 1\}$ that satisfy $1\leq b_{n}\leq n$. Recall that $U_{n}$ is the function of $\Sigma_{n}$ defined by $U_{n}\Sigma_{n}U_{n}^{\prime}=I_{n}$, and let

Generally, directly applying standard HC to $X$ does not yield the same result (e.g., HJ08 ).

2 Innovated higher criticism: Higher criticism based on innovations.

We have learned that applying standard HC to $U_{n}X$ yields better results than applying it to $X$ directly. Is this the best we can do? No, there is still space for improvement. In fact, HC applied to $U_{n}X$ is a special case of innovated higher criticism to be elaborated in this section. Innovated higher criticism is even more powerful in detection.

To begin, we revisit the vector $U_{n}\mu$ via an example. Fix $n=100$; let $\Sigma_{n}$ be a symmetric tri-diagonal matrix with $1$ on the main diagonal, $0.4$ on two sub-diagonals and zero elsewhere; and let $\mu$ be the vector with $1$ at coordinates $27$, $50$, $71$ and zero elsewhere. Figure 2 compares $\mu$ and $U_{n}\mu$. Especially, the nonzero coordinates of $U_{n}\mu$ appear in three visible clusters, each of which corresponds to a different nonzero entry of $\mu$. Also, at coordinates $27$, $50$, $71$, $U_{n}\mu$ approximately equals to $1.2$, but $\mu$ equals $1$. To interpret the figure caption, recall that $U_{n}$ is the function of $\Sigma_{n}$ defined by $U_{n}\Sigma_{n}U_{n}^{\prime}=I_{n}$.

Now we can either simply apply standard HC to $U_{n}X$ as before, or we can first linearly transform each cluster of signals to a singleton and then apply the standard HC. Note that in the second approach, we may have fewer signals, but each of them is much stronger than those in $U_{n}X$. Since the HC test is more sensitive to signal strength than to the number of signals, we expect that the second approach yields greater power for detection than the first.

Finally, we apply standard higher criticism to $V_{n}(b_{n})X$, and call the resulting statistic innovated higher criticism,

3 Upper bound to detectability.

We now establish an upper bound to detectability. Suppose the diagonal entries of $\Sigma_{n}^{-1}$ have a lower limit as follows:

Recall that the nonzero coordinates of $\mu$ are modeled as $A_{n}=\sqrt{2r\log n}$. If we let $b_{n}=\log n$ then it can be proved that the vector $V_{n}(b_{n})\cdot X$ has at least $m$ nonzero coordinates, each of which is as large as $\sqrt{\underline{\gamma_{0}}}A_{n}=\sqrt{2\underline{\gamma_{0}}\cdot r\cdot\log n}$. (See Lemma .3.) Note that a larger $b_{n}$ cannot improve the signal strength significantly, but may yield a much stronger correlation in $V_{n}(b_{n})Z$. Therefore, a smaller bandwidth is preferred. The choice $b_{n}=\log n$ is mainly for convenience, and can be modified.

The cut-off value $(\log n)^{2}$ can be replaced by other logarithmically large terms that tend to infinity faster than $(\log n)^{3/2}$. For finite $n$, this cut-off value may be conservative. In Section 8 [i.e., experiment (a)], we suggest an alternative where we select the cut-off value by simulation.

In summary, a lower bound and an upper bound are established as $r=\bar{\gamma}_{0}^{-1}\rho^{*}(\beta)$ and $r=\underline{\gamma_{0}}^{-1}\rho^{*}(\beta)$, respectively, under reasonably weak off-diagonal decay conditions. When $\bar{\gamma}_{0}=\underline{\gamma_{0}}$, the gap between the two bounds disappears, and iHC is optimal for detection. Below in Sections 5–7, we investigate several Toeplitz cases, ranging from weak dependence to strong dependence; for these cases, iHC is optimal in detection.

So far, we have assumed that the covariance matrix $\Sigma_{n}$ is known. When $\Sigma_{n}$ is unknown, we could still use iHC if $\Sigma_{n}$ could be estimated. We now briefly comment on the effect of estimating $\Sigma_{n}$.

In practical problems where iHC methodology would be used, noise could reasonably be represented as a time series, and its characteristics estimated from data. In particular, the time series might be an autoregression, and data over a longer period than that for which the current dataset was recorded could be used to deduce properties of the noise. Examples include detection of xenon byproducts as evidence of a nuclear explosion, early detection of bioweapons and detection of covert communications.

If data are gathered over a time period of length $p$, if the signal is present at no more than $m=n^{1-\beta}$ points where $\beta\in(1/2,1)$ and if the maximum size of the signal is no greater than a constant multiple of $(\log n)^{1/2}$, then it is typically possible to estimate the components of $U_{n}$ at rate $(p^{-1}\log p)^{1/2}$ uniformly in all components. From this property it can be proved that the difference between $U_{n}\mu$ and its empirical form equals $O_{p}[\{n^{2-\beta}p^{-1}(\log n)(\log p)\}^{1/2}]$, uniformly in all components. Similarly, if the noise process is conventional (e.g., an autoregression) then the distance between $U_{n}Z$ and its empirical form can be shown to equal $O_{p}(n^{1+\varepsilon}/p)$ for all $\varepsilon>0$. Therefore the effects of variance estimation will be asymptotically negligible if, for some $\varepsilon>1-\beta$, $n^{1+\varepsilon}/p\to 0$ converges to zero as $n\to\infty$.

To appreciate the extent to which this condition is restrictive, consider the case where the signals are particularly sparse, that is, $\beta$ is close to 1; say, $\beta=1-\eta_{1}$ where $\eta_{1}>0$ is small. Then the condition holds if $p$ is at least as large as $n^{1+\eta_{2}}$ for some $\eta_{2}>\eta_{1}$. That is, the amount of time for which data have to be acquired in order to estimate $\Sigma_{n}$ with sufficient accuracy need only be a factor $n^{\varepsilon}$ greater than $n$, for $\varepsilon>0$ relatively small. As the prevalence of the signal increased, the size of $\varepsilon$ would have to too.

Application of our methods to other problems, such as those involving genomic data, can be inhibited by the difficulty of estimating $\Sigma_{n}$ without information from outside the dataset. However, while there is sometimes evidence of strong dependence in genomic data, from other viewpoints the overall level of correlation is often quite low. For example, Messer and Arndt Messer argue that correlation decays from about 0.08, at a separation of approximately two base pairs, to about $0.01$ for a separation of ten base pairs. Work of Mansilla et al. Mansilla corroborates these figures. Results such as these, together with the upper tail independence property which is generally available for light-tailed distributions, suggest that for genomic data it is possible to work effectively under the assumption that expression levels are statistically independent, even when they are not. Details are given by Delaigle and Hall DH , who use the fact that in the case of genomic data the variables are typically $t$-statistics.

Application in the Toeplitz case.

In this section, we discuss the case where $\Sigma_{n}$ is a (truncated) Toeplitz matrix that is generated by a spectral density $f$ defined over $(-\pi,\pi)$. In detail, let $a_{k}=(2\pi)^{-1}\int_{|\theta|<\pi}f(\theta)e^{-ik\theta}\,d\theta$ be the $k$th Fourier coefficient of $f$. The $n$th truncated Toeplitz matrix generated by $f$ is the matrix $\Sigma_{n}(f)$ of which the $(j,k)$th element is $a_{j-k}$, for $1\leq j,k\leq n$.

We assume that $f$ is symmetric and positive, that is,

First, note that $f$ is a density, so $a_{0}=1$ and $\Sigma_{n}(f)$ has unit diagonal entries. Second, from the symmetry of $f$, it can be seen that $\Sigma_{n}(f)$ is a real-valued symmetric matrix. Last, it is well known Bottcher that the smallest eigenvalue of $\Sigma_{n}(f)$ is no smaller than $c_{0}(f)$, so $\Sigma_{n}(f)$ is positive definite. Putting all these together, $\Sigma_{n}(f)$ is seen to be a correlation matrix.

Toeplitz matrices enjoy convenient asymptotic properties. In detail, let $\lambda>1$ and suppose that additionally $f$ has at least $\lambda$ bounded derivatives [meaning, if $\lambda$ is a positive integer, that $|f^{(j)}|$ is bounded for $0\leq j\leq\lambda$, and, if $\lambda$ is not an integer, that $|f^{(j)}|$ is bounded for $0\leq j<\lambda$ and $|f^{(\lambda^{\prime})}(\theta_{1})-f^{(\lambda^{\prime})}(\theta_{2})|/|\theta_{1}-\theta_{2}|^{\lambda-\lambda^{\prime}}$ is bounded, where $\lambda^{\prime}$ denotes the largest integer less than $\lambda$]. Then by elementary Fourier analysis, there is a constant $M_{0}=M_{0}(f)>0$ such that

Comparing (24) and (25) with the definition of $\Theta_{n}^{*}$, we conclude that

In addition, it is known that the inverse of $\Sigma_{n}(f)$ is typically asymptotically equivalent to the Toeplitz matrix generated by $1/f$. The diagonal entries of $\Sigma_{n}(1/f)$ are the well-known Wiener interpolation rates Wiener ,

From this property and a result of Bottcher , Theorem 2.15, it can be proved that

Comparing this with (14) and (23) we deuce that

Combining (26) and (28), the following theorem is a direct result of Theorems 3.1 and 4.1 (the proof is omitted).

The curve $r=C(f)^{-1}\rho^{*}(\beta)$ partitions the $\beta$–$r$ plane into the undetectable region and the detectable region, similarly to the uncorrelated case. The regions of the current case can be viewed as the corresponding regions in the uncorrelated squeezed vertically by a factor of $1/C(f)$. See Figure 3.

[Note that $C(f)\geq 1$, with equality if and only if $f\equiv 1$, which corresponds to the uncorrelated case.]

Extension: When signals appear in clusters.

In the preceding sections [see, e.g., (2.1) in Section 2], the $m$ locations of signals were generated randomly from $\{1,2,\ldots,n\}$. Since $m\ll\sqrt{n}$, the signals appear as singletons with overwhelming probabilities. In this section we investigate an extension where the signals may appear in clusters.

We consider a setting where the signals appear in a total of $m$ clusters, whose locations are randomly generated from $\{1,2,\ldots,n\}$. Each cluster contains a total of $K$ consecutive signals, whose strengths are $g_{0}A_{n}$, $g_{1}A_{n},\ldots,g_{K-1}A_{n}$, from right to left. Here, $A_{n}=\sqrt{2r\log n}$ as before, $K\geq 1$ is a fixed integer and $g_{i}$ are constants. Approximately, the signal vector can be modeled as follows.

Thus $\nu$ is comprised of $m$ clusters, each of which contains $K$ consecutive signals. Let $g$ be the function $g(\theta)=\sum_{0\leq k\leq K-1}g_{k}e^{-ik\theta}$. We note that $\sum_{0\leq k\leq K-1}g_{k}B^{k}$ is the lower triangular Toeplitz matrix generated by $g$. With the same spectral density $f$, we consider an extension of that in Section 5 by considering the following model:

with $f$ denoting the spectral density in Section 5.

We note that the model can be equivalently viewed as

with $\bar{g}$ denoting the complex conjugate of $g$. Asymptotically,

where the diagonal entries of $\Sigma_{n}(|g|^{2}/f)$ are

If $\bar{\gamma}_{0}$ and $\underline{\gamma_{0}}$ are as defined in (14) and (23), then $\underline{\gamma_{0}}=\bar{\gamma}_{0}=C(f,g)$, and we expect the detection boundary to be $r=C(f,g)^{-1}\cdot\rho^{*}(\beta)$. This is affirmed by the following theorem which is proved in Section 10.

The case of strong dependence.

So far, we have only discussed weakly dependent cases. In this section, we investigate the case of strong dependence.

with $\alpha>0$ and $0<\alpha_{0}\leq\alpha$. The range of dependence can be calibrated in terms of $k_{0}=k_{0}(n;\alpha,\alpha_{0})$, denoting the largest integer by $k<n^{\alpha_{0}/\alpha}$. Clearly, $k_{0}\approx n^{\alpha_{0}/\alpha}$. Seemingly, the most interesting range is $0<\alpha_{0}\leq\alpha\leq 1$.

Condition (30) is more restrictive than similar assumptions in other places in this paper. There are at least two reasons. First, the constants in the definition of the detection boundary turn out to depend intimately on the value of $\alpha$ used in the definition of $\Sigma_{n}$ at (30), and so we need to make an assumption which is driven by that parameter. Secondly, a significantly more general definition of $\Sigma_{n}$ would need to satisfy the positive definiteness property which (as can be seen from Lemma .12) is somewhat delicate.

Model (30) has been studied in detail by Hall and Jin HJ08 who showed that the detectability of standard HC is seriously damaged by strong dependence. However, it remains open as to what is the detection boundary, and how to adapt HC to overcome the strong dependence and obtain optimal detection. This is what we address in the current section.

The key idea is to decompose the correlation matrix as the product of three matrices each of which is relatively easy to handle. To begin with we introduce a spectral density,

[Note that the Fourier coefficients of $f_{\alpha}(\theta)$ satisfy the decay condition in (25) with $\lambda=2-\alpha$.] Next, let

This is a special case of the cluster model we considered in Section 6 with $f=f_{\alpha}$ and $g=g_{0}$, except that the signal strength has been re-scaled by $\sqrt{a_{n}}$. Therefore, if we calibrate the nonzero entries in $\mu$ as

then the detection boundary for the model is succinctly characterized by

See Figure 4 for the display of $C(f_{\alpha},g_{0})$. The

following theorem is proved in Section 10.

Simulation study.

We conducted a small-scale empirical study to compare the performance of iHC and standard HC. For iHC, we investigate two choices of bandwidth: $b_{n}=1$ and $b_{n}=\log n$. In this section, we denote standard HC, iHC with $b_{n}=1$, and iHC with $b_{n}=\log n$ by HC, HC-a and HC-b correspondingly.

In experiment (a), we took $n=1000$ and $\Sigma_{n}(\rho)$ as the tri-diagonal Toeplitz matrix generated by $f(\theta)=1+2\rho\cos(\theta)$, $|\rho|<1/2$. The corresponding detection boundary was $r=\rho^{*}(\beta)/C(f)$ with $C(f)=(2\pi)^{-1}\int_{-\pi}^{\pi}[1-2\rho\cos(\theta)]^{-1}\,d\theta$. Consider all $\rho$ that range from $-0.45$ to $0.45$ with an increment of $0.05$, and four pairs of parameters $(\beta,r)=(0.5,0.2)$, $(0.5,0.25)$, $(0.55,0.2)$ and $(0.55,0.25)$. [Note that the corresponding parameters $(m,A_{n})$ are $(32,1.66)$, $(32,2.63)$, $(22,1.66)$ and $(22,2.63)$]. For each triple $(\beta,r,\rho)$, we generated data according to (1)–(4), applied HC, HC-a and HC-b to both $Z$ and $X$ and repeated the whole process independently $500$ times. As a result, for each triple $(\beta,r,\rho)$ and each procedure, we got $500$ HC scores that corresponded to the null hypothesis and $500$ HC scores that corresponded to the alternative hypothesis.

We report the results in two different ways. First, we report the minimum sum of types I and II errors (i.e., the minimum of the sum across all possible cut-off values) (see Figure 5). Second, we pick the upper $10\%$ percentile of the $500$ HC scores corresponding to the null hypothesis as a threshold (for later references, we call this threshold the empirical threshold) and calculate the empirical power of the test (i.e., the fraction of HC scores corresponding to the alternative hypothesis that exceeds the threshold). The empirical thresholds are displayed in Table 1 (to save space, only part of the thresholds are reported), and the power is displayed in Figure 6. Recall that in Theorem 4.2 we recommend $(\log n)^{2}$ as a cut-off point in the asymptotic setting. For moderately large $n$, this cut-off point is conservative, and we recommend the empirical threshold instead.

The results suggest that (1) iHC-b outperforms iHC-a, and iHC-a outperforms HC. (2) As $|\rho|$ increases (note that a larger $|\rho|$ means a stronger correlation), the detection problem is increasingly easier, and the advantage of iHC is increasingly prominent. (3) Under the null hypothesis, the HC-b scores are usually smaller than those of HC and HC-a. This is mainly due to the normalization term $\sqrt{2b_{n}-1}$ in the definition of iHC [see (4.2)].

We set the cut-off value as the $10\%$ percentile only for convenience. Replacing $10\%$ by other percentage gives similar conclusion. See Figure 7 for details.

In experiment (b), we took $\Sigma_{n}$ to be the Toeplitz matrix generated by $f(\theta)=1+\frac{1}{2}\cos(\theta)+2\rho\cos(2\theta)$ where $\rho$ ranged from $-0.2$ to $0.45$ with an increment of $0.05$. (The matrix $\Sigma_{n}$ is positive definite when $\rho$ is in this range.) Other parameters are the same as in experiment (a). The minimum sums of types I and II errors are reported in Figure 8. The results suggest similarly that HC-b outperforms HC-a, and HC-a outperforms HC.

In experiment (c), we investigated the behavior of HC-a/HC-b/HC for larger $n$. We took $(\beta,r)=(0.5,0.25)$, $n=500\times(1,2,3,4,5)$ and $\Sigma_{n}$ as the tri-diagonal matrix in experiment (a) with $\rho=0.4$. The sum of types I and II errors is reported in Table 2. The results suggest that the performance of HC-a/HC-h/HC improve when $n$ gets larger. (Investigation of the case where $n$ was much larger than $2500$ needed much greater computer memory, and so we omitted it.)

Discussion.

We have extended standard HC to innovated HC by building in the correlation structure. The extreme diagonal entries of $\Sigma_{n}^{-1}$ play a key role in the testing problem. If the extreme value has finite upper and lower limits, $\bar{\gamma}_{0}$ and $\underline{\gamma_{0}}$, then in the $\beta$–$r$ plane, the detection boundary is bounded by the curves $r=\underline{\gamma_{0}}^{-1}\cdot\rho^{*}(\beta)$ from above and $r=\bar{\gamma}_{0}^{-1}\cdot\rho^{*}(\beta)$ from below. When the correlation matrix is Toeplitz, the upper and lower limits merge and equal the Wiener interpolation rate $C(f)$. The detection boundary is therefore $r=C(f)^{-1}\cdot\rho^{*}(\beta)$. The detection boundary partitions the $\beta$–$r$ plane into a detectable region and an undetectable region. Innovated HC has asymptotically full power for detection whenever $(\beta,r)$ falls into the interior of the detectable region (we note, however, neither $\beta$ nor $r$ is used to construct iHC). We call this the optimally adaptivity of innovated higher criticism.

The work complements that ofDonoho and Jin DJ04 and Hall and Jin HJ08 . The focus of DJ04 is standard HC and its performance in the uncorrelated case. The focus of HJ08 is how strong dependence may harm the effectiveness of standard HC; what could be a remedy was, however, not explored. The innovated HC proposed in the current paper is optimal for both the model in DJ04 and that in HJ08 .

The work is related to that of Jager and Wellner Wellner where the authors proposed a family of goodness-of-fit statistics for detecting sparse normal mixtures. The work is also related to that of Meinshausen and Rice Rice and of Cai, Jin and Low CJL , where the authors focused on how to estimate $\varepsilon_{n}$—the proportion of nonnull effects.

Recently, HC was also found to be useful for feature selection in high-dimensional classification. See Donoho and Jin DJ08a , DJ08b , Hall, Pittelkow and Ghosh HPG and Jin JinPNAS . The work concerned the situation where there are relatively few samples containing a very large number of features, out of which only a small fraction is useful, and each useful feature contributes weakly to the classification problem. In a related setting, Delaigle and Hall DH investigated HC for classification when the data is non-Gaussian or dependent.

2 Future work.

The work is also intimately connected to recent literature on estimating covariance matrices. While the study is focused more on situations where the correlation matrices can be estimated using other approaches (e.g., Hongyu1 , Goeman1 , Goeman2 ), it can be generalized to cases where the correlation matrix is unknown but can be estimated from data. Cases where data on the covariance structure are available from other time periods were discussed in Section 4.4, but even if we stay within the confines of the current data, progress can be made. In particular, it is noteworthy that it was shown in Bickel and Levina Bickel that when the correlation matrix has polynomial off-diagonal decay, the matrix and its inverse can be estimated accurately in terms of the spectral norm. In such situations we expect the proposed approach to perform well once we combine it with that in Bickel .

Another interesting direction is to explore cases where the correlation matrix does not have polynomial off-diagonal decay, but is sparse in an unspecified pattern. This is a more challenging situation as relatively little is known about the inverse of the correlation matrix.

Our study also opens opportunities for improving other recent procedures. Take the aforementioned work on classification DJ08a , DJ08b , HPG , JinPNAS , for example. The approach derived in this paper suggests ways of incorporating correlation structure into feature selection, and therefore raises hopes for better classifiers. For reasons of space, we leave explorations along these directions to future study.

Proofs of main results.

Note that by Hölder’s inequality, $\sqrt{E[f]E[g]}\geq E[\sqrt{fg}]$ for any positive and integrable functions $f$ and $g$. Using Fubini’s theorem, $h(\Sigma,\Delta,G)$ is not less than

Note that $\int\sqrt{E_{G}f(x-\mu-\xi)f(x-\xi)}\,dx\equiv\int\sqrt{E_{G}f(x-\mu)f(x)}\,dx$ for any fixed $\xi$. It follows that

where the last term is the Hellinger distance corresponds to the first model of (3.1). Combining these results gives the claim.

2 Proof of Theorem 3.1.

The key to the proof is to compare model (34) with the following model:

3 Proof of Theorem 4.1.

Recall that $U_{n}$ is the function of $\Sigma_{n}$ defined by $U_{n}\Sigma_{n}U_{n}^{\prime}=I_{n}$. Put $Y=U_{n}X$, $\nu=U_{n}\mu$ and $Z=U_{n}z$. Model (15) reduces to

The key to the proof is to compare model (36) with

Intuitively, standard HC applied to model (36) is no “less” than that applied to model (37).

respectively. The key fact is now that the family of noncentral $\chi^{2}$-distribution $\{\chi_{1}^{2}(\delta),\delta\geq 0\}$ is a monotone likelihood ratio family (MLR), that is, for any fixed $x$ and $\delta_{2}\geq\delta_{1}\geq 0$, $P\{\chi_{1}^{2}(\delta_{2})\geq x\}\geq P\{\chi^{2}_{1}(\delta_{1})\geq x\}$. Consequently, it follows from (38) and mathematical induction that for any $x$ and $t$, $P\{\bar{F}_{n}^{*}(t)\geq x\}\geq P\{\bar{F}_{n}(t)\geq x\}$. Therefore, for any fixed $x>0$,

Finally, by an argument similar to that of Donoho and Jin DJ04 , Section 5.1, the second term in (39) with $x=(1+a)\sqrt{2\log\log n}$ tends to zero as $n$ diverges to infinity. This implies the claim.

4 Proof of Theorem 4.2.

Let $\bar{F}_{n}(t)$ and $\bar{F}_{0}(t)$ be the empirical survival function of $\{Y_{k}^{2}\}_{k=1}^{n}$ and the survival function of $\chi^{2}_{1}(0)$, respectively. Let $q=q(\beta,r)=\break\min\{(\beta+\bar{\gamma}_{0}r)^{2}/(4\bar{\gamma}_{0}r),4\bar{\gamma}_{0}r\}$ and set $t_{n}^{*}=\sqrt{2q\log n}$. Since $\bar{\gamma}_{0}r<\rho^{*}(\beta)$, then it can be shown that $0<q<1$ and $n^{-1}\leq\bar{F}_{0}(t_{n}^{*})\leq 1/2$ for sufficiently large $n$. Using an argument similar to that in the proof of Theorem 4.1,

It remains to show that the right-hand side of (41) is algebraically small. The proof needs detailed calculations summarized in Lemma .11 which is stated and proved in the Appendix.

5 Proof of Theorem 6.1.

Inspection of the proof of Theorems 3.1 and 4.2 reveals that the condition that $\Sigma_{n}$ is a correlation matrix and that $\Sigma_{n}\in\Theta_{n}^{*}(\lambda,c_{0}$, $M)$ in those theorems can be relaxed. In particular, $\Sigma_{n}$ need not have equal diagonal entries, and the decay condition on $\Sigma_{n}$ can be replaced by a weaker condition that concerns the decay of $U_{n}$ (the inverse of the Cholesky factorization of $\Sigma_{n}$), specifically

By Bottcher , Theorem 2.15, for any $\sqrt{n}\leq k\leq n-\sqrt{n}$, $k-K\leq j\leq k+K$ and $1\leq\lambda^{\prime}<\lambda$,

6 Proof of Theorem 7.1.

By the monotonicity of Hellinger distance at (12), it suffices to show that the Hellinger distance between $X^{*}$ and $Z^{*}$ tends to zero as $n$ diverges to infinity.

where $X(2\dvtx n)$ denotes the vector $X$ with the first entry removed. Dividing both sides by $\sqrt{1-\delta}$, this reduces to the following model:

which is in fact model (29) considered in Section 6. It follows from (33) that $\sqrt{a_{n}}\cdot\mu(2\dvtx n)/\sqrt{1-\delta}$ has $m$ nonzero coordinates each of which equals $\sqrt{2(1-\delta)^{-1}r\log n}$. Comparing model (10.6) with model (29) and recalling that $(1-\delta)^{-1}\cdot r\cdot C(f_{\alpha},g_{0})<\rho^{*}(\beta)$, the claim follows from Theorem 6.1.

Consider the second claim. Since $C(f_{\alpha},g_{0})\cdot r>\rho^{*}(\beta)$, then there is a small constant $\delta>0$ such that $(1-\delta)\cdot r\cdot C(f_{\alpha},g_{0})>\rho^{*}(\beta)$. Let $U_{n}$ be the inverse of the Cholesky factorization of $\Sigma_{n}$, and let $\bar{U}_{n}(b_{n})$ and $V_{n}(b_{n})$ be as defined right below (19). Write model (30) equivalently as

We now show (10.6). First, by Lemma .3 and (33), except for an event with negligible probability,

and by the way $\bar{\Sigma}_{n}$ is defined and Lemma .6, for sufficiently large $n$,

Last, by Bottcher , Theorem 2.15, $|(\Sigma_{n}(g_{0})\cdot\bar{\Sigma}_{n}^{-1}\cdot\Sigma_{n}(\bar{g}_{0}))(k,k)-C(f_{\alpha},g_{0})|=o(1)$ when $\min\{k,n-k\}$ is sufficiently large. Combining these results gives (10.6) with $r^{\prime}=(1-\delta)\cdot r\cdot C(f_{\alpha},g_{0})$, and the claim follows directly.

Appendix

Fix $\lambda>1$, $c_{0}>0$, and $M>0$. For any sequence of matrices $\Sigma_{n}$, $n\geq 1$, such that $\Sigma_{n}\in\Theta_{n}^{*}(\lambda,c_{0},M)$, let $U_{n}$ be the inverse of the Cholesky factorization of $\Sigma_{n}$. Then there is a constant $C=C(\lambda,c_{0},M)>0$ such that, for any $n$ and any $1\leq j,k\leq n$,

When $\lambda=1$, the first inequality continues to hold, and the second holds if we adjoin a $\log n$ factor to the right-hand side.

Fix $\lambda>1$, $c_{0}>0$, and $M>0$. For any matrix $A\in\Theta_{\infty}(\lambda,M)$, there is a constant $C>0$, depending only on $\lambda$, $M$ and $c_{0}$, such that $|A^{-1}(j,k)|\leq C\cdot(1+|j-k|)^{-\lambda}$.

Next we consider the first claim in Lemma .1. Construct an infinite matrix $\Sigma_{\infty}$ by arranging the finite matrices along the diagonal, and note that the inverse of $\Sigma_{\infty}$ is the matrix formed by arranging the inverse of the finite matrices along the diagonal. Since $\Sigma_{\infty}(i,j)\leq M(1+|i-j|^{\lambda})^{-1}$, then applying Lemma .2 gives the claim.

Consider the second claim. It suffices to show that $|U_{n}(k,j)|\leq C/(1+|k-j|^{\lambda})$ for all $1\leq j<k\leq n$. Denote the first $k\times k$ main diagonal sub-matrix of $\Sigma_{n}$ by $\Sigma_{(k)}$, the $k$th row of $\Sigma_{(k)}$ by $(\xi_{k-1}^{\prime},1)$, and the $k$th row of $U_{n}$ by $u_{k}^{\prime}$. It follows from direct calculations that

At the same time, by (2) and basic algebra,

Now, by Lemma .2, $|\Sigma_{(k-1)}^{-1}(j,s)|\leq C(1+|j-s|^{\lambda})^{-1}$ for all $1\leq i,j\leq k-1$. Note that $|\xi_{k-1}(s)|\leq C(1+|s-k|^{\lambda})^{-1}$, $1\leq s\leq n$ and $\lambda>1$. It follows from basic algebra that

.8 Statement and proof of Lemma .3.

for all $\Sigma_{n}\in\Theta_{n}^{*}(\lambda,c_{0},M)$, where $o(1)$ tends to zero algebraically fast.

First, $U^{\prime}U=\Sigma^{-1}$, $\sum_{j=k}^{n}u_{jk}^{2}=(U^{\prime}U)(k,k)=(\Sigma^{-1})(k,k)$. Second, by the polynomial off-diagonal decay of $U$ and basic calculus,

Last, note that the quantities $\Sigma^{-1}(k,k)$ are uniformly bounded away from zero and infinity. Combining these results gives

where $o(1)$ is algebraically small. Moreover, by the inequality,

.9 Statement and proof of Lemma .4.

Let $p_{1},\ldots,p_{N}$ be $N$ independent and identically distributed data from $U(0,1)$, and $F_{N}(t)$ be the empirical cdf. The normalized uniform stochastic process is defined as

There is a generic constant $C>0$ such that for sufficiently large $n$,

where $C>0$ are generic constants. Noting that $1/\sqrt{t(1-t)}\leq\sqrt{n}\leq C\sqrt{N\log N}$ when $1/n\leq t\leq 1/2$, it follows that

At the same time, by Wellnerbook , page 446,

Combining (.9) and (10), taking $x=C\log N$ and using the triangle inequality, we deduce the lemma.

.10 Statement and proof of Lemma .5.

Let $\bar{F}_{n}(t)$ and $\bar{F}_{0}(t)$ be as in the proof of Theorem 4.1, and let

Note that $\bar{F}_{n}(t)=\frac{1}{2b_{n}-1}\sum_{j=1}^{2b_{n}-1}\bar{F}_{n,j}(t)$. By arguments similar to that of Donoho and Jin DJ04 and basic algebra, it follows that

Finally, since $\bar{F}_{n,j}$’s are the empirical survival functions of $N$ independent samples from $\chi_{1}^{2}(0)$, then

Taking $x=C(\log n)^{3/2}$, the claim follows from Lemma .4.

.11 Statement and proof of Lemma .6.

and $\Sigma^{*}$ is a symmetric matrix with unit diagonal entries and with the following on the $k$th sub-diagonal:

Note that $\Sigma_{n-1}(g_{0})$ and $\Sigma^{*}$ share the $2k_{0}(n)-1$ sub-diagonals that are closest to the main diagonal (including the main diagonal). Let $H_{1}$ be the matrix containing all other sub-diagonals of $\Sigma_{n-1}(g_{0})$, and let $H_{2}$ be the matrix which contains the $k_{0}(n)$th and the $(k_{0}(n)+1)$th diagonals (upper and lower) of $\Sigma^{*}$. It is seen that

.12 Statement and proof of Lemma .7.

Fix $\beta\in(\frac{1}{2},1)$, $r\in(0,1)$ and $\delta\in(0,1)$ such that $\bar{\gamma}_{0}(1-\delta)^{-2}r<\rho^{*}(\beta)$. As $n$ tends to infinity the Hellinger distance associated with model (35) tends to zero.

The following lemma is proved in Section .13.

By direct calculation, $P\{D_{n}^{c}\}=o(1)$, and so by Hölder’s inequality,

Combining this result and (16) we deduce that $E(W_{n}^{*{1/2}})=E(W_{n}^{1/2}1_{\{D_{n}\}})+o(1)$, and comparing this property with the desired result we see that it is is sufficient to show that

The key to (18) is the following lemma, which is proved in Section .14.

Consider the model (13) where $U_{1}$ and $\mu$ satisfy (I)–(III). As $n\to\infty$, $E(W_{n}1_{\{D_{n}\}})=1+o(1)$, and $E(W_{n}^{2}1_{\{D_{n}\}})=1+o(1)$.

Combining (.12) with Lemma .9 gives (18).

.13 Proof of Lemma .8.

The last claim follows once (a)–(c) are proved. Consider (a)–(b) first. Fixing $K\geq 1$, we have

.14 Proof of Lemma .9.

We need the following lemma, proved in Section .15.

Consider a bivariate zero mean normal variable $(X,Y)^{\prime}$ that satisfies $\operatorname{Var}(X)=\sigma_{1}^{2}$, $\operatorname{Var}(Y)=\sigma_{2}^{2}$ and $\operatorname{corr}(X,Y)=\varrho$, where $c_{0}\leq\sigma_{1},\sigma_{2}\leq 1$ for some constant $c_{0}\in(0,1)$. Then there is a constant $C>0$ such that, for sufficiently large $n$,

where $d(r)=\min\{2r,1-2(1-\sqrt{r})^{2}\}$.

In view of the definition of $Y_{j}$ and $\sigma_{j}$ [see (17)], we can rewrite $W_{n}$ as

By Lemma .10, the right-hand side is no greater than $Cn^{-(1-\sqrt{r})^{2}}$. Therefore,

By the definition of $\rho^{*}(\beta)$ and the assumption of the lemma, $r<\rho^{*}(\beta)\leq(1-\sqrt{1-\beta})^{2}$, and so the first claim follows directly from (.14).

Here, in the first inequality, we have used the fact that

in the second inequality, we have utilized the independence and the fact that

and in the third equality, we have used again the independence. Moreover, in view of the definition of $U_{1}$, and Lemma .1, there is a constant $c_{0}\in(0,1)$ such that $\sigma_{j}\in[c_{0},1]$. Using Lemma .10, for sufficiently large $n$ and each $1\leq j\leq N$,

with $d(r)$ being as in Lemma .10. Combining (.14) and (.14) gives

Substituting (.14) and (30) into (28) and recalling that $m=n^{1-\beta}$, we deduce that

where the last term does not exceed $\sum_{N=0}^{\infty}(N!)^{-1}[C(\log^{2}n)n^{1+d(r)-2\beta}]^{N}$. By the assumption of the lemma,

thus it can be seen that $1+d(r)-2\beta<0$ for all fixed $\beta$ and $r\in(0,\rho^{*}(\beta))$. Combining this with (.14) gives the second claim.

.15 Proof of Lemma .10.

Write $W=(W-\rho V)+\rho V$, and note that $(1-\rho)^{2}+\rho^{2}\leq 1$. It is seen that

Since $\bar{\Phi}(x)\leq C\phi(x)$ for all $x>0$,

We now establish the second claim. By Hölder’s inequality, it suffices to show that

Since $\Phi(x)\leq C\phi(x)$ for all $x<0$ and $\Phi(x)\leq 1$ for all $x\geq 0$,

In view of the definition of $d(r)$, $e^{\sigma_{1}^{2}A_{n}^{2}}\Phi(T_{n}-2\sigma_{1}A_{n})\leq Cn^{d(\sigma_{1}^{2}r)}$. Since that $\sigma_{1}\leq 1$ and that $d(r)$ is a monotonely increasing function, we have $d(\sigma_{1}^{2}r)\leq d(r)$. Combining these results gives the claim.

.16 Statement and proof of Lemma .11.

Under the conditions of Theorem 4.2, the right-hand side of (41) converges to zero algebraically fast as $n$ diverges to infinity.

where $\nu^{*}$ has $m$ nonzero entries of equal strength $(1-\delta_{n})A_{n}$ whose locations are randomly drawn from $\{1,2,\ldots,n\}$ without replacement.

Let $\bar{F}_{n}^{*}(t)$ be the empirical survival function of $\{(Y_{k}^{*})^{2}\}_{k=1}^{n}$, and let $\bar{F}(t)=E[\bar{F}_{n}(t)]$ and $\bar{F}^{*}(t)=E[\bar{F}_{n}^{*}(t)]$. Recall that the family of noncentral $\chi^{2}$-distributions has monotone likelihood ratio. Then $\bar{F}(t)\geq\bar{F}^{*}(t)\geq\bar{F}_{0}(t)$. Now, first, since the $Y_{k}$’s are block-wise dependent with a block size $\leq 2b_{n}-1$, it follows by direct calculations that

Second, by $\bar{F}(t)\geq\bar{F}_{n}^{*}(t)$,

where the right-hand side diverges to infinity algebraically fast by an argument similar to that in DJ04 . Combining Chebyshev’s inequality, the identity $b_{n}=\log n$ and calculations of the mean and variance of $h_{n}(t)$, we deduce that

It remains to show that the last term in (35) is algebraically small. We discuss separately the cases $\bar{F}(t)/\bar{F}_{0}(t)\geq 2$ and $\bar{F}(t)/\bar{F}_{0}(t)<2$. For the first case,

which is algebraically small since $t=\sqrt{2q\log n}$ and $0<q<1$. For the second case,

which is seen to be algebraically small by comparing it to the right-hand side of (.16).

.17 Statement and proof of Lemma .12.

Let $\Sigma_{n}$ be as in (30). For sufficiently large $n$, necessary and sufficient conditions for $\Sigma_{n}$ to be positive definite are, respectively, $0\leq\alpha\leq 2$ and $0<\alpha_{0}\leq\alpha\leq 1$.

We begin by establishing the first claim. Suppose such an autoregressive structure exists for $\alpha\geq\alpha_{0}>0$. Let

Clearly, $\operatorname{var}(Y_{k})=1$. At the same time, direct calculation shows that the correlation between $Y_{1}$ and $Y_{j+1}$ equals to $[(j+1)^{\alpha}+(j-1)^{\alpha}-2j^{\alpha}]/2$ for all $1\leq j\leq n-2$, which is no larger than $1$. Taking $j=2$ yields $(3^{\alpha}+1-2\cdot 2^{\alpha})/2\leq 1$, and hence $\alpha\leq 2$.

Consider the second claim. For any $k\geq 1$, define the partial sum $S_{k}(t)=1+2\sum_{j=1}^{k}(1-\frac{j^{\alpha}}{n^{\alpha_{0}}})^{+}\cos(kt)$. By a well-known result in trigonometry Zygmund , to establish the positive-definiteness of $\Sigma_{n}$, it suffices to show that

Here, $k_{0}=k_{0}(n;\alpha,\alpha_{0})$ is the largest integer $k$ such that $k^{\alpha}\leq n^{\alpha_{0}}$.

We now derive (.17). Using a result from Zygmund , page 183, if we let $a_{0}=2$, and $a_{j}=2(1-\frac{j^{\alpha}}{n^{\alpha_{0}}})^{+}$, $1\leq j\leq n-1$, then $S_{k_{0}+1}(t)=\sum_{j=0}^{k_{0}-1}(j+1)\Delta^{2}a_{j}K_{j}(t)+(k_{0}+1)K_{k_{0}}(t)\Delta a_{k_{0}}+D_{n}(t)a_{k_{0}+1}$. Here, $\Delta a_{j}=a_{j}-a_{j+1}$, $\Delta^{2}a_{j}=a_{j}+a_{j+2}-2a_{j+1}$, and $D_{j}(t)$ and $K_{j}(t)$ are the Dirichlet’s kernel and the Fejér’s kernel, respectively,

In view of the definition of $k_{0}$, $a_{k_{0}+1}=(1-\frac{(k_{0}+1)^{\alpha}}{n^{\alpha_{0}}})^{+}=0$. Also, by the monotonicity of $\{a_{j}\}$, $\Delta a_{k_{0}}=a_{k_{0}}-a_{k_{0}+1}\geq 0$. Therefore, $S_{k_{0}+1}(t)\geq\sum_{j=0}^{k_{0}-1}(j+1)\Delta^{2}a_{j}K_{j}(t)$.

We claim that the sequence $\{a_{0},a_{1},\ldots,a_{n-1}\}$ is convex. In detail, since $\alpha\leq 1$, the sequence $\{j^{\alpha}\}$ is concave. As a result, the sequence $\{(1-\frac{j^{\alpha}}{n^{\alpha_{0}}})\}$ is convex, and so is the sequence $\{(1-j^{\alpha}/n^{\alpha_{0}})^{+}\}$. In view of the definition of $a_{j}$, the claim follows directly. The convexity of the $a_{j}$’s implies that $\Delta^{2}a_{j}\geq 0$, $0\leq j\leq n-2$. Therefore, $S_{k_{0}+1}(t)\geq 0$. This proves the first part of (.17).