Detection of a sparse submatrix of a high-dimensional noisy matrix

Introduction

We observe a high-dimensional random matrix and we want to test the occurrence of a particular submatrix of much smaller size, which has elements with expected values larger than some threshold. We assume that the entries of the matrix are independent, identically distributed (i.i.d.) random variables but some underlying phenomenon can increase significantly the expected value of the random variables in the submatrix.

We have the observations that form an $N\times M$ matrix $\mathbf{Y}=\{Y_{ij}\}_{i=1,\ldots,N,j=1,\ldots,M}$:

The alternative under consideration will correspond to $n\times m$-submatrices of sizes $n\in\{1,\ldots,N\}$, $m\in\{1,\ldots,M\}$ with large enough entries. Let

and let ${\mathcal{C}}_{nm}$ be the collection of all subsets $C$ of the form (3). The set ${\mathcal{C}}_{nm}$ corresponds to the collection of all $n\times m$ submatrices in $N\times M$ matrix. For $a>0$, which may depend on $n,m,N$ and $M$. We consider the alternative

(in the Remark 2.1 below we discuss that a slightly larger alternative can be considered). The components of the matrix $\mathbf{Y}$ are independent under the alternative as well. Denote by $P_{S}$ the probability measure that corresponds to observations (1) with matrix $S=\{s_{ij}\}$ and by $E_{S}$ the expected value with respect to the measure $P_{S}$.

Let ${{\mathcal{S}}}_{nm,a}$ be the collection of all matrices $S=S_{C}$ that satisfy (4).

We discuss here only right-hand side alternatives, but, obviously, left-hand side alternatives can be treated the same way for variables $-Y_{ij}$ instead of $Y_{ij}$.

We extend our results to three different setups and sketch the proofs of the results. First, we consider errors having Gaussian distribution with unknown variance $\sigma^{2}$. We also consider other settings where the $Y_{ij}$’s come from an exponential family. Finally, in the initial case of Gaussian errors with known variance, we consider a two-sided alternative of our test problem.

We are interested here in sparse matrices, that is, the case when $n$ is much smaller than $N$ and $m$ is much smaller than $M$.

Sparsity assumptions were introduced for vectors. Estimation as well as hypothesis testing for vectors were thoroughly studied in the literature, see, for example, Bickel, Ritov and Tsybakov and references therein and Donoho and Jin .

In the context of matrices, different sparsity assumptions can be imagined. For example, matrix completion for low rank matrices with the nuclear norm penalization has been studied by Koltchinskii, Lounici and Tsybakov . Other results will be discussed later on.

We study the hypothesis testing problem under a minimax setting. A test is any measurable function of the observations, $\psi=\psi(\{Y_{ij}\})$ taking values in $$. For such a test$\psi=\psi(\{Y_{ij}\})$, we denote the probability of type-I error, the probability of type-II error under simple alternative and the maximal probability of type-II error over the set${\mathcal{S}}_{nm,a}$ by

respectively. Let the risk be the following sum:

We define the minimax risk at fixed level $\alpha\in(0,1)$ as

Similarly, let the minimax testing risk be

From now on, we assume in the asymptotics that $N\to\infty,M\to\infty$ and $n=n_{NM}\to\infty,m=m_{NM}\to\infty$. Other assumptions will be given later.

We suppose that $a>0$ is unknown. The aim of this paper is to give asymptotically sharp boundaries for minimax testing risk. It means that, first, we are interested in the conditions on $a=a_{NM}$ which guarantee distinguishability, that is, the fact that $\gamma_{nm,a}\to 0$ and $\beta_{nm,a,\alpha}\to 0$ for any $\alpha\in(0,1)$. We construct a testing procedure based on a linear statistic combined with a scan statistic. We prove the upper bounds of the minimax testing risk of this procedure. Second, we describe conditions on $a$ for which we have indistinguishability, that is, the convergence $\gamma_{nm,a}\to 1$ and $\beta_{nm,a,\alpha}\to 1-\alpha$ for any $\alpha\in(0,1)$. These results are called the lower bounds. The two sets of conditions are complementary and match in rate and constant.

Often the sizes $n,m$ of submatrix are unknown, but we know a set ${\mathcal{K}}_{NM}$ of couples of indices $(n,m)\in\{1,\ldots,N\}\times\{1,\ldots,M\}$ containing the true one. Then we consider the “adaptive” problem for the combined alternative ${{\mathcal{S}}}_{NM,{\mathbf{a}}}=\bigcup_{(n,m)\in{\mathcal{K}}_{NM}}{{\mathcal{S}}}_{nm,a_{nm}}$, which corresponds to a collection ${\mathbf{a}}=\{a_{nm},(n,m)\in{\mathcal{K}}_{NM}\}$. The quantities $\beta_{NM,\mathbf{a},\alpha},\gamma_{NM,{\mathbf{a}}}$ are defined in a similar way as above. We define a testing procedure and check that, if $a_{nm}$ satisfies the conditions for distinguishability uniformly over the collection $\mathbf{a}$, the upper bounds still hold. The adaptive lower bounds hold as an easy consequence of the minimax lower bounds.

The problem of choosing a submatrix in a Gaussian random matrix has been previously studied by Sun and Nobel . They were interested in maximal size submatrices of a matrix with increasing size in two setups. First, they consider the case when the average of the entries of the submatrix is larger than a given threshold and, second, when the entries are well-fitted by a two-way ANOVA matrix in the least-squares sense (i.e., the sum of squares of residuals is smaller than some given threshold).

The algorithm of choosing such submatrices was previously introduced in Shabalin et al. , who were also interested in finding large average submatrices. This problem is strongly motivated by the research of gene expression in microarray data. In these large matrices, it is necessary to recover biclusters, that is associations between sets of samples (rows) and sets of variables (columns). These associations together with clinical and biological information are “a first step in identifying disease subtypes and gene regulatory networks”. Many other algorithms for biclustering are discussed and compared on real-data bases concerning breast and lung cancer studies.

Similar problems were considered in Addario-Berry et al. . They use the same testing procedures for vectors of random variables, where the alternatives may have various combinatorial structures. In particular, they consider the example of detecting a clique of a certain size in a graph and they compute upper and lower bounds for the Bayesian test error. A bipartite graph of size $(N,M)$ is a graph having edges only between the $N$ vertices of one set to the $M$ vertices of a second set. A biclique is a complete bipartite subgraph of size $(n,m)$, that is, a subgraph where all $n$ vertices from the first set are connected to the $m$ vertices from the second set. We consider the problem of detecting a biclique. Our results are sharp minimax and adaptive to the size of the unknown biclique.

The plan of the paper is as follows. In Section 2.1, we give the test procedures. We state the conditions on the detection boundary $a$ such that distinguishability is possible. Under mild additional assumptions, we give the conditions on $a$ so that the alternative is indistinguishable from the null hypothesis.

In Section 2.2, we consider the adaptive setup where $(n,m)$ is unknown but belongs to some collection of sequences $\mathcal{K}_{NM}$. We compute the adaptive rates of testing of a slightly modified test procedure.

In Section 3, we perform a numerical study of the procedures that attain the sharp upper bounds. In order to compute the scan statistic, a heuristic stochastic algorithm from Shabalin et al. is used. The empirical detection boundary is very close to the one predicted by our results.

In Section 4, we give extensions of our results to Gaussian variables of unknown variance $\sigma^{2}$, to non-Gaussian matrices with distribution in an exponential family and to two-sided tests for Gaussian matrices, respectively.

We include in Section 4.4 comments to understand how our results compare to previously studied alternatives: subsets without structure and rectangular submatrices. The first case can be assimilated to detection of a sparse signal in vector observations of length $N\times M$, so the set of alternatives and the detection boundary are much larger than in our case. We summarize well-known results by Ingster , Ingster and Suslina and Donoho and Jin . The second case is the detection of rectangles in the large matrix (connected submatrices), which constitutes a set of alternatives smaller than ours. This case is studied in Arias-Castro et al. and for other geometric shapes of clusters. In order to be self-contained, we state and prove sharp upper and lower bounds, for the rectangular clusters.

Section 5 is mainly concerned with the proof of the lower bounds stated in Section 2.1.2. The Appendix contains the proofs of the other results of the paper.

Main results

We denote by $n=n_{NM},m=m_{NM}$ and $a=a_{N,M}$.

Denote also $p=n/N,q=m/M$. From now on, we suppose that

For general sequences $\{u_{n}\}_{n\geq 1}$ and $\{v_{n}\}_{n\geq 1}$ of real numbers, such that $v_{n}>0$ for $n$ large enough, we say that the sequences are asymptotically equivalent, $u_{n}\sim v_{n}$, if $\lim_{n\to\infty}u_{n}/v_{n}=1$. Moreover, we say that the sequences are asymptotically of the same order, $u_{n}\asymp v_{n}$, if there exists two constants $0<c\leq C<\infty$ such that $c\leq\liminf_{n\to\infty}u_{n}/v_{n}$ and $\limsup_{n\to\infty}u_{n}/v_{n}\leq C$.

In a minimax setup, we suppose that for each $N,M$ we know $n$ and $m$.

where $T_{nm}=\sqrt{2\log(G_{nm})},G_{nm}=\#({\mathcal{C}}_{nm})={N\choose n}{M\choose m}$. The computation of this statistic is discussed in Section 3.

The following theorem gives sufficient conditions for the detection boundary $a$ such that distinguishability holds. The test procedure which attains these bounds is

Assume (5) and let $a$ be such that at least one of the following conditions hold

Then $\psi^{*}$ with $H\to\infty$ and such that $H\leq ca\sqrt{nmpq},c<1$ when (8) holds, satisfies $\gamma_{nm,a}(\psi^{*})\to 0$.

Formally, the procedure has a simple structure. Nevertheless, there are difficulties for computation of the scan statistic in the matrix case. Indeed, in the vector case, it is enough to order increasingly all the elements and take the sum of the largest values. In the matrix case, we have no such simple ordering. We shall discuss in the numerical study below the empirical algorithm used to compute the scan statistic.

Let us also note that this procedure assumes that $n$ and $m$ are known. An adaptive version of the scan test will be given in the next section.

1.2 Lower bounds

In this section, we obtain matching lower bounds that apply to all tests under additional assumptions on the matrix and submatrix sizes. We discuss these assumptions after the theorem.

and that the following two conditions are satisfied:

Then the distinguishability is impossible, that is, $\gamma_{nm,a}\to 1$ and $\beta_{nm,a,\alpha}\to 1-\alpha$ for any $\alpha\in(0,1)$.

These results for the upper and the lower bounds can be interpreted as follows. Under the conditions (5), (10) and (11), a sharp detection boundary $a^{*}$ is defined via the relations

in the problem with known $(n,m)$. Note that the detection boundary can be written as

The additional assumptions (10) and (11) appearing in the previous lower bounds are satisfied, for example, in the case where $n\sim cm$, for some $0<c<\infty$, and for $N\sim n^{A}$ and $M\sim m^{B}$ for $A$ and $B$ larger than 1. In this case, the detection boundary is of the form:

The particular case when $A=B>1,c=1$ is the case of asymptotically squared matrices and submatrices, and we get

We can state the alternative hypothesis in a more general form:

Indeed, our probabilities of error depend on the elements of the submatrix $C$ only through the sum of its elements. Therefore, the previous test procedure will attain the same rates and the same lower bound techniques will give the previous results for this more general test problem.

2 Adaptation to the size of the submatrix

If the size $(n,m)$ of the submatrix $C$ with significantly large elements under the alternative (4) is unknown, we suppose that it belongs to the set $\mathcal{K}_{NM}$, for each $N$ and $M$. The alternative hypothesis can be written

Additionally, we suppose that the sequence of sets $\{\mathcal{K}_{NM}\}_{N,M}$ is such that

The set $\mathcal{K}_{NM}$ contains sizes of submatrices that we have to explore in order to test in an adaptive way. Therefore, previous assumption insure, on the one hand, that $p\to 0$ and $q\to 0$ uniformly over $(n,m)\in\mathcal{K}_{NM}$ as $N,M\to\infty$ and, on the other hand, that the least size of the submatrices still grows to infinity with $N$ and $M$.

The adaptive test will reject the null hypothesis as soon as at least one between the linear test or the scan tests associated to each $(n,m)\in\mathcal{K}_{NM}$ rejects.

Assume (5) and let the set ${\mathcal{K}}_{NM}$ be such that condition (15) holds.

Upper bounds. Let $\mathbf{a}=\mathbf{a}_{NM}=\{a_{nm},(n,m)\in{\mathcal{K}}_{NM}\}$ be detection boundaries such that at least one of the following conditions hold

Then, $\psi^{*}_{NM}$ with $H\to\infty$ such that $H\leq c\min_{(n,m)\in{\mathcal{K}}_{NM}}a_{nm}\sqrt{nmpq}$ for some $0<c<1$ when (16) holds, is such that $\gamma_{NM,\mathbf{a}}(\psi^{*}_{NM})\to 0$.

The previous theorem actually shows that the test procedure is adaptive to the size $(n,m)$ of the submatrix as far as the assumptions hold uniformly. Indeed, the linear procedure is free of the size of the submatrix and the scan statistic adapts to $(n,m)$ without any loss in the rate.

The lower bounds in the adaptive setup are an obvious consequence of Theorem 2.2. Let us state the adaptive lower bounds: Suppose that for each $N$, $M$ there exists $(n^{*},m^{*})$ in the collection ${\mathcal{K}}_{NM}$ such that

and that ${n^{*}}\log(N/n^{*})\asymp m^{*}\log(M/m^{*}),$ as $N\to\infty$ and $M\to\infty$. Let $\mathbf{a}=\mathbf{a}_{NM}=\{a_{nm},(n,m)\in{\mathcal{K}}_{NM}\}$ be such that

Then $\gamma_{NM,\mathbf{a}}\to 1$ and $\beta_{NM,\mathbf{a},\alpha}\to 1-\alpha$ for any $\alpha\in(0,1)$.

Simulations

Let us briefly recall this algorithm: we choose randomly a set of $n$ rows out of $N$. Then, we sum in every column the elements of the previously selected rows. We select now the columns corresponding to the $m$ largest sums obtained in this way. We sum, next, in every row the elements belonging to the selected columns and select the rows corresponding to the $n$ largest sums. We repeat the algorithm until the sum of elements $Y_{ij}$ of the selected submatrix does not increase anymore. As the procedure can stop at a local maximum, we repeat the procedure $K$ times, where $K$ is large (in our simulation $K=10\,000$). We take the maximum value of the outputs. This replication is needed to enforce that with high probability the output approaches the global maximum.

We have simulated matrices of size $N\times M$ of i.i.d. standard Gaussian random variables for $N=M=200$ and $N=M=500$.

We plot the estimated second-type error probabilities for different values of $a$ in the neighborhood of the detection boundary predicted by our theorems, for different values of $n$ and $m$. The results in Figure 1 correspond to $N=M=200$, while in Figure 2 to $N=M=500$.

Figures 1 and 2 show that the empirical detection boundary is very close to $a^{*}$ which is predicted by out theoretical results. Indeed, the second-type error probability is close to 0.5 at some point close to $a^{*}$. The plots also show very fast decay of this probability on a small vicinity of $a^{*}$. This means that the test is very powerful for values of $a$ slightly larger than the detection boundary $a^{*}$. Note also that, for fixed $N$ and $M$, $a^{*}$ decreases to 0 as $n$ and $m$ increase.

Extensions

We extend our results in different directions. First, we consider matrices of i.i.d. random variables having Gaussian law with unknown variance $\sigma$, next, random variables having a distribution belonging to the exponential family (not necessarily Gaussian) and, finally, test problem with two-sided alternative for the Gaussian matrices.

Sharp results in Theorems 2.1 and 2.2 still hold if the random variables $Y_{ij}$ have unknown variance $\sigma$, under a mild additional assumption. We sketch here the test procedure and proof of the upper bounds.

We estimate the unknown variance $\sigma^{2}$ of our data by $\hat{\sigma}^{2}$, where

This estimator is unbiased under the null hypothesis, but biased under the alternative.

for T_{nm,\delta}=\sqrt{(2+\delta)\log\bigl{(}{N\choose n}{M\choose m}\bigr{)}} and some $\delta>0$ small enough. Recall that T_{nm}=\sqrt{2\log\bigl{(}{N\choose n}{M\choose m}\bigr{)}}.

Assume (5). We suppose that alternatives under consideration are such that

If the quantity $a$ is such that one of the following conditions hold

2 Extension to general law from an exponential family

In many applications, we do not have Gaussian observations. Instead, we have observations $X_{ij}$, i.i.d. with probability density $g_{\theta_{ij}}$ from an exponential family, for all $i=1,\ldots,N,$ and $j=1,\ldots,M$. We explain here how to use the previous testing procedures in order to deal with such setups and check that results similar to the case of Gaussian variables hold in this case. The exponential model will behave like a Gaussian model when the number of data is large, by asymptotic equivalence. We expect that the optimal detection boundary is the one for the Gaussian model properly rescaled.

We assume that the laws belong to an exponential family in the general form

for the dominating measure $\mu$, where $\eta$ is supposed 2 times continuously differentiable and strictly increasing on $\Theta$, that is, $\eta^{\prime}(\theta)>0$.

We consider a point $\theta^{0}$ interior to $\Theta$ and test, based on $X_{ij}$’s, the null hypothesis $H_{0}\colon\ \theta_{ij}=\theta^{0}\mbox{ for all }i=1,\ldots,N,j=1,\ldots,M,$ against the alternative

In order to build the test procedure as previously, we will rescale the observations as follows. First, put the exponential model in the canonical form, then change variables to $Y_{ij}=(T(X_{ij})-m^{0})/\sigma^{0}$, with $m^{0}=E_{\theta^{0}}(T(X))$ and $\sigma^{0}=\sqrt{\operatorname{Var}_{\theta^{0}}(T(X))}$ computed under the null hypothesis. Let us denote the common density of $Y_{ij}$’s by

where $s=\eta(\theta)\sigma_{0}$ and $A(s)=B(s/\sigma^{0})-sm_{0}/\sigma_{0}$ and $B(\eta(\theta))=C(\theta)$. Here, we have $A^{\prime}(s^{0})=0$, $A^{\prime\prime}(s^{0})=1$ and

In this way, the original problem corresponds to testing, based on $Y_{ij}$’s, the null hypothesis $H_{0}\colon\ s_{ij}=s^{0}\mbox{ for all }i=1,\ldots,N,j=1,\ldots,M,$ against the alternative

We have the following results for exponential models.

Upper bounds. If $a$ is such that one of the following conditions hold

then $\psi^{*}$, with $H\to\infty$ such that $H\leq cA^{\prime}(s^{0}+a)\sqrt{nmpq}$ for some $0<c<1$ and with $T_{nm}$ replaced by $T_{nm,\delta}$ for some $\delta>0$ small enough, is such that $\gamma_{nm,a}(\psi^{*})\to 0$.

Lower bounds. Assume, moreover, that conditions (10) and (11) hold. If $a$ is such that the conditions (12) and (13) are satisfied, then $\gamma_{nm,a}\to 1$ and $\beta_{nm,a,\alpha}\to 1-\alpha$ for any $\alpha\in(0,1)$.

Proof of the upper bounds is given in Appendix .8.

The proof of the lower bounds uses the relation (22) and follows exactly the same lines as the proof of Theorem 2.2 in Section 5 except that we have to consider $T_{kl}^{2}\sim(2+\delta)(k\log(p^{-1})+l\log(q^{-1}))$ for some small $\delta>0$ instead of thresholds in (28).

Under the assumption (23), the detection boundary $a^{*}\to 0$. Therefore,

as $d^{*}\to 0$. It is well known that the Fisher information at $\theta^{0}$ in model (20) is $I(\theta_{0})=(\sigma^{0}\eta^{\prime}(\theta^{0}))^{2}$. In this way, we deduce the sharp asymptotic detection boundary for alternative (21) from Theorem 4.2: $d^{*}=a^{*}/\sqrt{I(\theta^{0})}.$

Examples of such calculations for most popular probability distributions in the exponential family are given in Table 1.

3 Extension to two-sided alternative

Let us consider model (1) and the same null hypothesis (2), against the two-sided alternative:

Let us consider the following test procedures

Upper bounds. If $a$ is such that one of the following conditions hold

Lower bounds. Assume, moreover, that conditions (10) and (11) hold. If $a$ is such that the following two conditions are satisfied:

then $\gamma_{nm,a}\to 1$ and $\beta_{nm,a,\alpha}\to 1-\alpha$ for any $\alpha\in(0,1)$.

4 Related testing problems

Let us consider again the model (1) and the null hypothesis (2). We shall see how our alternative which locates signal in submatrices of the large matrix compares to other alternatives. We consider first the alternatives where the signal is located anywhere (no structure: larger alternative) and then where the signal is located in block-submatrices (smaller alternative).

Let ${{\mathcal{D}}}_{k}$ consists of all subsets $D\subset\{1,\ldots,N\}\times\{1,\ldots,M\}$ of cardinality $\#(D)=k$ and let $k=nm$. Let us consider the alternative

(we do not suppose that the set $D$ is of product structure). Clearly, we can consider the matrix $\{Y_{ij}\}$ as a vector of dimension $P=NM$, and the problem is well studied as $P\to\infty$, see Ingster , Ingster and Suslina , Donoho and Jin .

Let $\beta\in(1/2,1)$. Then the detection boundary is determined by the relation

4.2 Block-structured submatrices

Let ${\mathcal{E}}_{nm}$ consist of all rectangles of size $n\times m$, that is, of the sets $E_{kl}=\{k+1,\ldots,k+n\}\times\{l+1,\ldots,l+m\},0\leq k\leq N-n,0\leq l\leq M-m$, and the alternative is of the form

Similar problems were studied recently in Arias-Castro et al. and for other related geometrically-shaped clusters. Note that Arias-Castro et al. also deals with detection of rectangular shapes in a square matrix.

The detection boundary for (25) is determined by

Let us consider the test $\psi_{Z}$ based on the scan statistic over a particular set of possible rectangles, which is a suitable “grid” on ${\mathcal{E}}_{nm}$ constructed as follows.

Take $\eta_{nm}=\eta>0$. Put $n_{k}=(k-1)n\eta,k=1,\ldots,K,m_{l}=(l-1)m\eta,l=1,\ldots,L,$ where $K,L$ are such that $N-n(1+\eta)\leq n_{K}\leq N-n,M-m(1+\eta)\leq m_{L}\leq M-m$, which yield $K\sim N/(\eta n),L\sim M/(\eta m)$. Put

In this construction, we scan over a number $K\times L$ of rectangles which is much smaller than the cardinality of ${\mathcal{E}}_{nm}$ (for technical reasons) and which is also much larger than the set of non-overlapping rectangles (this set would not be large enough).

Then $\gamma_{nm,a}\to 1,\beta_{nm,a,\alpha}\to 1-\alpha$ for any $\alpha\in(0,1)$.

Note that, the separation rates, that is, the asymptotics of $a$ that provide distinguishability for the alternative (4), are intermediate between the fast separation rates for the alternative (25) and the slow rates for the alternative without structure (24).

Let us consider the particular case of squared matrices ($N=M$) and squared submatrices ($n=m$) such that $n=N^{1-\beta}$ for some $\beta\in(0,1)$. The sharp asymptotic rates of the detection boundaries can be compared in Table 2.

Proof of Theorem 2.2

In the first part, we give the proof of the theorem and the other parts of this section are dedicated to proofs of intermediate results. More lemmas are in the Appendix.

We prove the lower bounds by first reducing the minimax testing error to a Bayesian testing risk with uniform prior over the set of parameters. Typically, one studies the likelihood ratio under the prior with respect to the law $P_{0}$ under the null hypothesis and proves that it tends to 1 in quadratic mean (under $P_{0}$). Nevertheless, this does not work as the covariance of the likelihood ratio is too large. Therefore, we truncate the likelihood ratio in a convenient way.

Let $S_{C}=\{s_{ij}\}$ be the matrix such that $s_{ij}=0,(i,j)\notin C,s_{ij}=a,(i,j)\in C$. Let us consider the prior on the set of matrices:

and let $P_{\pi}$ be the mixture of likelihoods $P_{\pi}=G_{nm}^{-1}\sum_{C\in{\mathcal{C}}_{nm}}P_{S_{C}}.$ Let us consider the likelihood ratio

here and below we set $b^{2}\,{\stackrel{{\scriptstyle\Delta}}{{=}}}\,a^{2}nm$, and, for submatrix $C$ of the size $n\times m$, the statistics $Y_{C}$ are defined by (6). Since $\pi({\mathcal{S}}_{nm})=1$, in order to obtain indistinguishability: $\gamma_{nm,a}\to 1,\beta_{nm,a,\alpha}\to 1-\alpha,\forall\alpha\in(0,1)$, it suffices to show

where $\psi^{*}(Y)=\mathbh{1}_{L_{\pi}(Y)>1}$ is the likelihood ratio test. Therefore, (26) implies by Fatou’s lemma that

that is, $\gamma_{nm,a}\to 1$. It is easy to deduce that $\beta_{nm,a,\alpha}\to 1-\alpha.$

Let us replace the statistics $L_{\pi}(Y)$ by their truncated version

where the events $\Gamma_{C}$ are determined as follows. Set

Take small $\delta_{1}>0$ (which will be specified later) and set $k_{0}=\delta_{1}n,l_{0}=\delta_{1}m$. Let ${\mathcal{C}}_{kl,C}=\{V\in{\mathcal{C}}_{kl}\colon\ V\subset C\}$ be the submatrices of $C\in{\mathcal{C}}_{nm}$ which are in ${\mathcal{C}}_{kl}$. Then we set

By (1), under conditions on $k,l$ in (27) (and similarly to the equivalent of $T^{2}_{nm}$) we have

Indeed, when looking at second-order moments of the likelihood ratio $L_{\pi}(Y)$ a large contribution comes from overlapping submatrices $C_{1}$ and $C_{2}$ inducing correlated random variables $Y_{C_{1}}$ and $Y_{C_{2}}$. Our idea is to truncate $Y_{V}$, for submatrices $V$ of size close to $(k,l)$, at its expected maximal value in order to reduce the contribution of these correlations.

Set $\Gamma_{nm}=\bigcap_{C\in{\mathcal{C}}_{nm}}\Gamma_{C}$. Then, under the assumptions of Theorem 2.2, $P_{0}(\Gamma_{nm})\to 1.$

and in place of (26) it suffices to check that

In order to get (29) it suffices to verify two relations:

Under the assumptions of Theorem 2.2, we have

Under the assumptions of Theorem 2.2, we have

The remaining part of this section is devoted to obtaining the Proposition 5.3.

2 Proof of Proposition 5.3

We deal with the second order moment of the truncated likelihood ratio. We have

We note that the expected value in the previous sum does not depend on $C_{1}$ and $C_{2}$ but merely on the size of their common submatrix. Let $C_{1}=A_{1}\times B_{1},C_{2}=A_{2}\times B_{2}$ and set

and see that we can rewrite (30) as follows:

Notation. Set $z_{kl}^{2}=a^{2}kl,\rho_{kl}=kl/nm$ and recall that $b^{2}=a^{2}nm$. Note that it means also that $b^{2}=z^{2}_{mn}$ and that $z^{2}_{kl}=b^{2}\rho_{kl}$.

Let $k\geq\delta_{1}n,l\geq\delta_{1}m$, and $T_{kl}\leq 2z_{kl}$. Then

Proof of Lemma 5.1 is given in Appendix .5.

Observe that the right-hand side of (30) is the expectation of $g(X_{1},X_{2})$ over $X_{1},X_{2}$ which are independent and having hypergeometric distributions ${{\mathcal{HG}}}_{1}={{\mathcal{HG}}}(N,n,n),{{\mathcal{HG}}}_{2}={{\mathcal{HG}}}(M,m,m)$, respectively, that is,

This yields, for any non-decreasing function $g$,

The first claim corresponds to Lemma 3 in Arias-Castro et al. . The second claim follows from the Abel’s transform of the series for the expectation. ∎

2.2 Evaluation of the expectation

Take any small $\delta>0$. The detection boundary $a$ satisfies assumption (13), where the worst-case is when the limit is close to 1. It suffices, therefore, to consider the case

In order to evaluate the right-hand side of (34), let us firstly divide the expectation into two parts $E_{{{\mathcal{HG}}}_{1}\times{{\mathcal{HG}}}_{2}}(g(X_{1},X_{2}))=E_{1}+E_{2}$, where

Observe that, for some $B>0$ under constraint $X_{1}a^{2}\leq 1$,

Taking the expectation over $X_{1}$, we get similarly

In order to evaluate $E_{2}$, we use the assumption (11) and write

instead of (36). Therefore, we can take $\delta_{1}>0$ small enough such that $\delta_{1}a^{2}m\leq\log(p^{-1})/2$ and $\delta_{1}a^{2}n\leq\log(q^{-1})/2$ for $N,M,n$ and $m$ large enough.

Divide $E_{2}$ into two parts $E_{2}=E_{21}+E_{22}$, where

Observe that under the constraints in the sum,

In order to evaluate the item $E_{22}$, we divide it in two parts as well: $E_{22}=I_{1}+I_{2}$,

Let us divide the set ${\mathcal{H}}=\{(k,l)\colon\ k/n\geq\delta_{1},l/m\geq\delta_{1}\}$, appearing in $I_{2}$, into two parts:

This yields the division of $I_{2}$ into $I_{2}=I_{12}+I_{22}$. Observe that $\rho_{kl}\geq\delta_{1}^{2}$ for $(k,l)\in{\mathcal{H}}$.

Let us consider $I_{12}$. Recalling ((2)), observe that we can take $\delta>0$ small enough in (35) such that $t=T_{nm}-b(1+\rho_{kl})<0.$ Applying ((2)) and Lemma 5.3 for $P_{N,n,n}(k),P_{M,m,m}(l)$, we get

Note that for $\delta>0$ small enough in (35) one can take $\delta_{2}=\delta_{2}(\delta)>0$ such that $(T_{nm}-b)^{2}\geq\delta_{2}T_{nm}^{2}$ for the first item in the exponent. Denote

and $T_{nm}^{2}=2\log(G_{nm})\sim 2(A+B)$ by (1). Observe that $2(A+B)\rho_{kl}\leq A\frac{k}{n}+B\frac{l}{m}$ for $(k,l)\in\mathcal{H}_{1}$.

The following terms in the power of the exponential above can be bounded on the set $\mathcal{H}_{1}$ as follows

Applying ((3)) and Lemma 5.3 for $P_{N,n,n}(k),P_{M,m,m}(l)$, we similarly get

Since $k\log(p^{-1})+l\log(q^{-1})\sim T_{kl}^{2}/2$, the power in the exponent is of the form

Under (35), we can see that $(T_{kl}-z_{kl})^{2}\geq\delta_{2}T_{kl}^{2}$ for some $\delta_{2}>0$ and $N,M$ large enough. In fact, recalling $A>0,B>0,k/n\in(\delta_{1},1],l/m\in(\delta_{1},1]$ before we have

Appendix

Observe that $Y_{C}\sim{\mathcal{N}}(0,1)$ under $P_{0}$ and, since $G_{nm}\to\infty$ and $\Phi(-T)\asymp\exp(-T^{2}/2)/T$ as $T\to\infty$, we get

Let $S_{C}\in{\mathcal{S}}_{nm,a}$. Then $Y_{C}\sim{\mathcal{N}}(g_{S_{C}},1)$ under $P_{S_{C}}$-probability with

.2 Proof of Theorem 2.3

.3 Proof of Proposition 5.1

It suffices to check that $P_{0}(\Gamma_{nm}^{c})\to 0$, where $A^{c}$ states for the complement of the event $A$. We have

.4 Proof of Proposition 5.2

In view of symmetry in $C$, it suffices to check that, for any fixed $C\in{\mathcal{C}}_{nm}$,

or, equivalently, $P_{S_{C}}(\Gamma_{C}^{c})\to 0$. Set $z_{kl}^{2}=a^{2}kl$. Since $Y_{V}\sim{\mathcal{N}}(z_{kl},1)$ under $P_{S_{C}}$ for $V\in{\mathcal{C}}_{kl,C}$, we have

where $G_{kl}^{mn}=\#({\mathcal{C}}_{kl,C})={n\choose k}{m\choose l}$. Under assumptions (10) and (13) there exists $\delta>0$ such that

.5 Proof of Lemma 5.1

The first inequalities in (31)–((3)) are evident, and we will prove the second ones. The proofs are based on the well-known relation: if $X\sim{\mathcal{N}}(0,1)$, then

Let $V_{1}=C_{1}\setminus C_{2},V_{2}=C_{2}\setminus C_{1},V=C_{1}\cap C_{2}$, and observe that the sets $V_{1},V_{2},V$ are disjoint, $C_{1}=V_{1}\cup V,C_{2}=V_{2}\cup V$ and $\#(V_{1})=\#(V_{2})=nm-kl,\#(V)=kl$.

Let $0<kl<nm$. Let us write the statistics $Y_{C_{1}},Y_{C_{2}}$ in a more convenient form

where as above, for $U\subset\{1,\ldots,N\}\times\{1,\ldots,M\},\#(U)>0$ we set

Observe that $Y_{V_{1}},Y_{V_{2}},Y_{V}$ are standard Gaussian and independent under $P_{0}$.

Recall that $b=a\sqrt{nm}$ and put $c=b\sqrt{1-\rho_{kl}}$. It is obvious that $b^{2}=c^{2}+z_{kl}^{2}$. Moreover, by applying (4), we get

If $kl=0$ or $kl=nm$, we can prove this in a similar way. Lemma 5.1 (31) follows.

In order to get the second inequality, observe that, for $0<kl<nm$ and for any $h\geq 0$,

Taking $h=b-T_{nm}/(1+\rho_{kl})$, we get the second inequality. If $kl=0$ or $kl=nm$, we can prove this in a similar way. Lemma 5.1 ((2)) follows.

In order to get the third inequality, for $0<kl<nm$ and for $h\geq 0$, we have

Taking $h=2z_{kl}-T_{kl}$, we get the third inequality. If $kl=nm$, we can prove this in a similar way. Lemma 5.1 ((3)) follows.

.6 Proof of Lemma 5.3

Recalling $P_{n,p}(k)={n\choose k}p^{k}(1-p)^{n-k}$. Using well-known inequality ${n\choose k}\leq(ne/k)^{k}$, we get

.7 Proof of Theorem 4.1

Let us see that $E_{0}(\hat{\sigma}^{2})=\sigma^{2}$ and that $\operatorname{Var}_{0}(\hat{\sigma}^{2})=2\sigma^{4}/(NM)$. Denote by

for our choice of $T_{nm,\delta}$ and by the second assumption (19) (compare with the proof of Theorem 2.1). These implies $\beta_{nm,a}(\hat{\psi}^{*})\to 0$. Thus $\gamma_{nm,a}(\hat{\psi}^{*})\to 0$.

.8 Proof of the upper bound of Theorem 4.2

It follows the same lines as that of Theorem 2.1. We use Markov inequality and bound from above exponential moments of our test statistics (as they are not having Gaussian distribution in this case).

We use repeatedly the well-known facts that, $A^{\prime}(s^{0})=0$ and $A^{\prime\prime}(s^{0})=1$ for centered and reduced random variable at $s^{0}$. Moreover,

On the one hand, $A(s^{0}-\frac{1}{\sqrt{NM}})-A(s^{0})\sim-\frac{1}{2NM}$. On the other hand, it is easy to check that $A^{\prime\prime}(s)\geq 0$. Thus, $A$ is a convex function and $A^{\prime}$ is increasing. This implies $A(s_{ij}-\frac{1}{\sqrt{NM}})-A(s_{ij})\leq-\frac{1}{\sqrt{NM}}A^{\prime}(s_{ij})$ which is less or equal than $-\frac{1}{\sqrt{NM}}A^{\prime}(s^{0}+a)$ under the alternative. Finally,

As $T_{nm,\delta}/\sqrt{nm}\asymp(\log(p^{-1})/m+\log(q^{-1})/n)^{1/2}\to 0$, we have $A(s^{0}+T_{nm,\delta}/\sqrt{nm})-A(s^{0})\asymp T^{2}_{nm,\delta}/(2nm)$ and this gives

by the choice of $\delta>0$ small enough.

.9 Proof of Theorem 4.3

Therefore, if $a^{2}\sqrt{nmpq}\to\infty$, we have

In conclusion, if $\liminf a^{4}nm/(4(n\log(p^{-1})+m\log(q^{-1})))>1$ we have

.9.2 Proof of the lower bounds

We follow the lines of the proof of Theorem 2.2. The prior on the set of matrices is $\pi=G_{nm}^{-1}\sum_{C\in\mathcal{C}_{nm}}\pi_{C}$, where, under $\pi_{C}$, the matrix $S=S_{C}$ has $s_{ij}=0$ with probability 1 for all $(i,j)\notin C$ and $s_{ij}$ is either $a$ and $-a$ with probability $1/2$, for all $(i,j)\in C$.

Let $P_{S_{C}}$ denote the likelihood of the random variables in $\mathbf{Y}$ when $S=S_{C}$ and $P_{\pi}$ denote the mixture of likelihoods $P_{\pi}=G_{nm}^{-1}\sum_{C\in\mathcal{C}_{nm}}P_{S_{C}}$. Therefore, the likelihood ratio $L_{\pi}(Y)$ is

We can show, as in the proof of (31), that

where $V_{1},V_{2}$ and $V$ are defined in the proof of Lemma 5.1.

The relations ((2)) and ((3)) could be replaced by the following:

where $b^{2}=nma^{4}/2,z_{kl}^{2}=b^{2}\rho_{kl}$, under the same constraints. The inspection of the proofs of ((2)) and ((3)) shows that, in order to prove (6) and (7), one could use the following relation in place of (4):

Together with the first relation in (9), this ends the proof of (8).

.10 Proof of Theorem 4.4

Let $K=[N/n],L=[M/m]$ and consider only non-overlapping rectangles

Let $S_{kl}$ be the matrix with the elements $s_{ij}=0$ if $(i,j)\notin R_{kl}$ and $s_{ij}=a$ if $(i,j)\in R_{kl}$. Consider the prior

By construction, $\pi(\{S_{kl},k,l\})=1$. The likelihood ratio is of the form

Note that $Z_{kl}\sim{\mathcal{N}}(0,1)$ under $P_{0}$ and are independent in $k,l$. It is sufficient to check that $L(Y)\to 1$ in $P_{0}$-probability. Let us consider the truncated likelihood ratio

Observe now that $T_{KL}-b\to\infty$ under the assumptions of the theorem, and it suffices to consider the case $b>cT_{kl}$ for some $c\in(1/2,1)$. We have

Proof of the lower bounds in Theorem 4.4.

.10.2 Proof of the upper bounds

Set $T_{KL}=\sqrt{2\log(KL)}$ and observe that, by the choice of $\eta$ and since $pq\to 0$, we have

Let the alternative $S_{E}$ correspond to the matrix with entry $a>0$ at positions in $E=E_{k^{*}l^{*}}$ and 0 elsewhere. As previously, $E=E_{k^{*}l^{*}},0\leq k^{*}\leq N-n,0\leq l^{*}\leq M-m$ consists of $(i,j)$ such that $k^{*}<i\leq k^{*}+n,l^{*}<i\leq l^{*}+m$. By construction, we can take $k,l,1\leq k\leq K,1\leq l\leq L$ such that $|n_{k}-k^{*}|\leq n\eta,|m_{l}-l^{*}|\leq m\eta$. Therefore, the matrix $E_{k^{*}l^{*}}$ will overlap with the matrix $E_{n_{k}m_{l}}$ from our test procedure significantly:

under assumptions of theorem. Proof of the upper bounds in Theorem 4.4 follows.

Acknowledgements

Research was partially supported by RFBR Grant 11-01-00577 and by the Grant NSh–4472.2010.1. The author acknowledges support from the CNRS for his visit to the University Paris-Est Marne-la-Vallée.

References