Testing for correlation in Gaussian databases via local decision making

1.   Introduction

With the thriving use of smart devices and the growing popularity of big data, various institutions have been collecting more and more personal data from users, which are then either published or sold for research or profit-making purposes. Although the published data are typically anonymized (i.e., the explicit attributes of the users, such as names and dates of birth are erased), there has been increasing concern about potential privacy leakage from anonymized data, approached from juridical ^[1] and corporate ^[2] points of view. These concerns are also expressed in the literature regarding successful practical de-anonymization attacks on real data; the reader is referred to ^[3,4,5,6,7] for a non-exhaustive list. We briefly elaborate on some of these studies. In ^[4], the task of identifying users from the statistics of their behavioral patterns, based on call data records, web browsing histories, or GPS trajectories, has been studied. It was demonstrated that a large fraction of users can be easily identified, given only histograms of their data; hence, these histograms can act as users' fingerprints. In ^[6], the authors presented a class of statistical de-anonymization attacks against high-dimensional micro-data, such as individual preferences, recommendations, transaction records, and so on. Their techniques are robust to perturbation in the data and tolerate some mistakes in the adversary's background knowledge. More studies regarding practical de-anonymization attacks on real data have been conducted with a specific focus on social networks; in this case, the reader is referred to ^{[8,9,10,11,12]} and to the references therein. For example, in ^[8], a novel de-anonymization attack that exploits group membership information that is available on social networking sites was introduced. The authors showed that information about the group memberships of a user (i.e., the groups of a social network to which a user belongs) is sufficient to uniquely identify this person or at least to significantly reduce the set of possible candidates. Although being extremely valuable, these lines of work does not provide a complete rigorous understanding of the conditions under which anonymized databases are inclined to privacy attacks; thus, more fundamental research is currently missing around these topics.

Two fundamental problems of statistical inference in database models are correlation detection and alignment recovery. Correlation detection between two databases is basically a hypothesis testing problem; under the null hypothesis, the databases are independent, and under the alternative hypothesis, a permutation exists, for which the databases are correlated. In this task, the main objective is to achieve the best trade-off between type Ⅰ and type Ⅱ error probabilities. In the problem of database alignment recovery, one assumes that the two databases are correlated and wants to estimate the underlying permutation. While these two problems are intimately related, this paper is devoted solely to correlation detection.

Correlation detection of databases with $n$ sequences, each containing $d$ independent Gaussian entries, has recently been studied in ^[13,14], while correlation detection of databases with independent entries and general distributions has lately been explored in ^[15]. In the present manuscript, we continue along this line of work and analyze a simple statistical test that solves the problem of correlation detection between two Gaussian databases relatively efficiently^Ⅰ. The tester first calculates a statistic which is based on local decisions for all $n^{2}$ pairs of sequences and then makes a final decision in favor of one of the hypotheses based on this statistic. Since the proposed statistical test is based on a sum of indicator random variables which are weakly dependent, the analysis of the two error probabilities, especially the type Ⅰ probability of error, turns out to be highly non-trivial, and this is the main technical contribution of this work.

^ⅠThe proposed statistical test has a computational complexity of ${\cal O}(n^2)$, while the generalized likelihood ratio (GLR) test has a computational complexity of ${\cal O}(n^3)$. More on the GLR test can be found in Section 4.2.

We compare the performances of the proposed statistical test with those of ^[13]. The main problem in ^[13] was to identify the smallest possible correlation coefficient between each consecutive entries of the databases, as a function of $n$ and $d$, such that the sum of the type Ⅰ and type Ⅱ error probabilities can be driven to zero as $n$ and $d$ tend to infinity. While the detector that was proposed in ^[13] can also be used for non-asymptotic correlation values, we show that for a wide range of parameter choices, its performance is inferior to that of the new proposed statistical test. In addition to the comparison between the analytically derived theoretical guarantees, we also present Monte–Carlo simulation results for specific parameter values, which also demonstrate that the proposed statistical test outperforms the previous one.

1.1.   Related work

Alignment recovery of correlated databases has been investigated from an information-theoretic point of view. The database alignment problem was originally introduced by Cullina et al. ^[16]. The discrete setting was studied in ^[16], which derived achievability and converse bounds in terms of a newly introduced measure of correlation, called the cycle mutual information. Exact recovery of the underlying permutation for correlated Gaussian databases was studied in ^[17], and a follow-up work extended the results to partial recovery ^[18]. A typicality-based framework for permutation estimation was investigated in ^[19]. Database matching under random column deletions and adversarial column deletions were researched, respectively, in ^[20] and ^[21]. Theoretical guarantees for the de-anonymization of random correlated databases without prior knowledge of the data distribution were proposed in ^[22]. The problem of database matching under noisy synchronization errors was recently studied in ^[23]. The Gaussian database alignment recovery problem is equivalent to a certain idealized tracking problem studied in ^[24,25]. The recovery problem with two correlated random graphs has also been investigated in the past few years. A starting point of this problem proposed the correlated Erdős–Rényi graph model with dependent Bernoulli edge pairs ^[26]. A subsequent work studied the recovery problem in the Gaussian setting ^[27]. More recent papers investigated the corresponding detection problem for correlation between graphs ^[28,29]. It has lately been proved ^[30,31] that detecting whether Gaussian graphs are correlated is as difficult as recovering the node labels.

1.2.   Organization of this paper

The continuation of this paper is organized as follows. In Section 2, we establish the notation conventions. In Section 3, we formalize the model and formulate our main objectives. In Section 4, we state some results from previous work and discuss the GLR test. In Section 5, we state the new proposed statistical test and then provide and discuss the main results of this work. In Section 6, we introduce the novel graph-theoretic concepts that have paved the way to handling the type Ⅰ probability of error of the proposed test. In Section 7, we compare the performances of the proposed test and an existing one. Section 8 concludes the work and suggests some open avenues for future research. All the results of this work are proved in the appendices.

2.   Notation conventions

Throughout the paper, random variables will be denoted by capital letters, and the specific values they take will be denoted by the corresponding lower case letters. Random vectors and their realizations will be denoted, respectively, by capital letters and the corresponding lowercase letters, both in bold font. For example, the random vector $\boldsymbol{X} = (X_1, X_2, \ldots, X_d)$ ($d$-positive integer) may take a specific vector value $\boldsymbol{x} = (x_1, x_2, \ldots, x_d)$ in $\mathbb{R}^{d}$. When used in the linear-algebraic context, these vectors should be thought of as column vectors, so when they appear with the superscript $\mathsf{T}$, they will be transformed into row vectors by transposition. Thus, $\boldsymbol{x}^{\mathsf{T}} \boldsymbol{y}$ is the inner product of $\boldsymbol{x}$ and $\boldsymbol{y}$. The notation $\| \boldsymbol{x}\|$ will stand for the Euclidean norm of the vector $\boldsymbol{x}$. As is customary in probability theory, we write $\boldsymbol{X} = (X_{1}, \ldots, X_{d}) \sim {\cal N}(\boldsymbol{0}_{d}, {\bf{I}}_{d})$ (with $\boldsymbol{0}_{d}$ being a vector of $d$ zeros and ${\bf{I}}_{d}$ being the $d \times d$ identity matrix) to denote that the probability density function of $\boldsymbol{X}$ is

For $\boldsymbol{X} = (X_{1}, \ldots, X_{d})$ and $\boldsymbol{Y} = (Y_{1}, \ldots, Y_{d})$, we write

to denote the fact that $\boldsymbol{X}$ and $\boldsymbol{Y}$ are jointly Gaussian with independent and identically distributed (IID) pairs, where each pair $(X_i, Y_i)$, $i \in \{1, \ldots, d\}$, is a Gaussian vector with a zero mean and the specified correlation $\rho$. Logarithms are taken to the natural base. The probability of an event ${\cal E}$ will be denoted by $\mathbb{P}\{ {\cal E}\}$ and the indicator function by $\mathbb{1}\{ {\cal E}\}$. The expectation operator will be denoted by $\mathbb{E}[\cdot]$. The set of all permutations of $\{1, 2, \ldots, n\}$ is denoted by ${\cal S}_{n}$

3.   Settings and problem formulation

Let $\boldsymbol{X}^{n}$ be a database comprising the $n$ feature vectors $\{ \boldsymbol{X}_1, \ldots, \boldsymbol{X}_n\}$ and let $\boldsymbol{Y}^{n}$ be a second database comprising the $n$ feature vectors $\{ \boldsymbol{Y}_1, \ldots, \boldsymbol{Y}_n\}$. Each feature vector contains $d$ entries. We consider the following binary hypothesis testing problem. Under the null hypothesis $\mathsf{H}_{0}$, the Gaussian databases $\boldsymbol{X}^{n}$ and $\boldsymbol{Y}^{n}$ are generated independently with $\boldsymbol{X}_{1}, \ldots, \boldsymbol{X}_{n} \overset{\text{IID}}{\sim} {\cal N}(\boldsymbol{0}_{d}, {\bf{I}}_{d})$ and $\boldsymbol{Y}_{1}, \ldots, \boldsymbol{Y}_{n} \overset{\text{IID}}{\sim} {\cal N}(\boldsymbol{0}_{d}, {\bf{I}}_{d})$ (Figure 1). Let us use $\mathbb{P}_{0}$ to denote the probability distribution that governs $(\boldsymbol{X}^{n}, \boldsymbol{Y}^{n})$ under $\mathsf{H}_{0}$. Under the alternative hypothesis $\mathsf{H}_{1}$, the databases $\boldsymbol{X}^{n}$ and $\boldsymbol{Y}^{n}$ are correlated with some unknown permutation $\boldsymbol{\sigma} = (\sigma_{1}, \sigma_{2}, \ldots, \sigma_{n}) \in {\cal S}_{n}$ and some known correlation coefficient $\rho \in (0, 1)$ (Figure 2). If $\rho \in (-1, 0)$, then one considers the negation of $\boldsymbol{Y}^{n}$. Let us use $\mathbb{P}_{1| \boldsymbol{\sigma}}$ to denote the probability distribution that governs $(\boldsymbol{X}^{n}, \boldsymbol{Y}^{n})$ under $\mathsf{H}_{1}$, for some permutation $\boldsymbol{\sigma} \in {\cal S}_{n}$. In summary,

for some permutation $\boldsymbol{\sigma} \in {\cal S}_{n}$.

We would like to consider a problem of correlation detection. Given the databases $\boldsymbol{X}^{n}$ and $\boldsymbol{Y}^{n}$ (and not the permutation $\boldsymbol{\sigma}$), a statistical test $\phi: \mathbb{R}^{d \times n} \times \mathbb{R}^{d \times n} \to \{0, 1\}$ decides whether the null hypothesis or the alternative hypothesis occurred.

For a given $n$ and $d$, the type Ⅰ probability of error of a test $\phi$ is

and the type Ⅱ probability of error is

where in (3.2), FA stands for false alarm, and in (3.3), MD stands for missed detection.

For the specific statistical test that is proposed in Section 5, which solves the testing problem defined above, our main objective is to find theoretical guarantees on the two error probabilities as functions of the parameters $\rho$, $n$, and $d$.

4.   The sum and GLR tests

4.1.   The sum test

The testing problem between databases with IID Gaussian entries has already been considered in ^[13,14]. For this specific testing problem, the following statistical test was proposed in ^[13]. The statistic is defined by

and the sum test is defined by comparing $T$ with a threshold

The following result was proved in [13, Section Ⅳ].

Proposition 1. (Sum test) Let $t = \sqrt{\gamma}\tfrac{dn}{2}$ with $\gamma \in (0, 4\rho^{2})$. The error probabilities of the sum test $\phi_{\mathit{\mbox{Sum}}}$ for the binary hypothesis testing problem (3.1) are upper-bounded by

where,

4.2.   The structure and complexity of the GLR test

The GLR test is known to be an asymptotically uniformly most powerful (UMP)^Ⅱ test among all invariant tests [32, Section 6.4.2]. Although there are no general results regarding non-asymptotic properties of the GLR test, it is known to be optimal in special cases ^[33]. Since the sum test from Section 4.1, as well as the count test (which will be presented in the following section) can be proved to be invariant tests, it makes sense to also briefly present the GLR test and discuss its computational complexity. We first derive a simplified statistic for the GLR test. Since only the alternative hypothesis is composite, the GLR test is given by

^ⅡA UMP test minimizes the type Ⅱ probability of error among all tests with a constrained type Ⅰ probability of error. For example, the Neyman-Pearson test is UMP when testing between two simple hypotheses.

for some $\lambda \in \mathbb{R}$, or, more explicitly, by

By simple manipulations,

which is equivalent to

Thus, the GLR test requires us to find the solution of an assignment problem of size $n$ with the scores given by the empirical correlations. Relying on the Kuhn–Munkres algorithm ^[34,35,36] (also known as the Hungarian algorithm) and its modifications ^[37], this assignment problem can be solved with a running time of ${\cal O}(n^{3})$. It is important to note that this computational complexity holds in general, but when the optimal assignment is relatively easy to find (e.g., for a diagonal score matrix), the running time of the Hungarian algorithm is reduced to ${\cal O}(n^{2})$. In our settings, this holds when $\rho$ is close to 1.

While the GLR test has high chances of performing well in the studied testing problem, it has two main disadvantages. First, as explained above, its computational complexity grows cubically in $n$, which is discouraging from a practical point of view; second, the GLR test does not lend itself to a tractable analytical analysis (specifically, the type Ⅰ error event). These facts motivate us to propose an alternative statistical test that will be computationally efficient (relative to the GLR test) and analytically tractable, on the one hand, and perform at least as well as the existing sum test, on the other hand. The count test, which is the main theme of the next section, fulfills all these requirements.

5.   The count test

5.1.   Motivation

In order to motivate the new proposed statistical test, let us shortly consider the sum test in Section 4.1. Note that its statistic can also be written as follows:

which means that one has to first sum up all the $n$ feature vectors in each database to get the vectors $\hat{ \boldsymbol{X}}$ and $\hat{ \boldsymbol{Y}}$, and then test whether these vectors are correlated or not. The meaning of transforming each database into a single vector is obvious; one wastes the original structure of the problem and, as a consequence, valuable information is lost. One has to note that, nonetheless there is a significant advantage to such a procedure: The computational complexity of the sum test is linear in $n$. As opposed to the sum test, we would like to take advantage of the fact that each database comprises $n$ sequences. We note the following simple observation: The inner product between two independent vectors $\boldsymbol{X}, \boldsymbol{Y} \sim {\cal N}(\boldsymbol{0}_{d}, {\bf{I}}_{d})$ is typically close to zero, while the inner product between the vectors

concentrates around $\rho d$. This means that one can first test in a local manner for each pair of feature vectors and in a second step, count how many of them seem to be correlated. Ideally, under the null hypothesis, the number of detected correlated pairs is close to zero, while under the alternative hypothesis, this number should be close to $n$ times the probability of local detection, which, in turn, should be close to one. Thus, on the basis of the count of local detections, one should be able to distinguish very well between the two hypotheses. It should be noted that the computational complexity of this testing procedure is ${\cal O}(n^2)$, which is higher than that of the sum test, but still much lower than the complexity of the GLR test (${\cal O}(n^3)$).

5.2.   The proposed statistical test

According to the explanation above, an appropriate statistic is given by

where $\xi$ is some predefined threshold. While a test based on $M(\xi)$ can be analyzed, it turns out that by first normalizing the feature vectors before calculating the inner products, one can propose a test which lends itself to a much tighter analysis. We will elaborate more on this point in Section 6. In the meanwhile, we continue as follows. Denote the normalized vectors

and

and define the statistic

where $\theta \in (0, 1)$ is the local threshold.

In order to present our statistical test, we need some definitions. For two feature vectors $\boldsymbol{X}$ and $\boldsymbol{Y}$, correlated according to a given $\rho \in (0, 1)$, the local detection probability is defined by

while for two independent feature vectors (i.e., $\rho = 0$), the local false-alarm probability is defined by

Under $\mathsf{H}_{1}$, note that the expectation of $N(\theta)$ is given by

Thus, the proposed test compares $N(\theta)$ with a threshold as follows:

where $\beta \in (0, 1)$ is the global threshold.

Our proposed statistical test may be presented in a simple graphical way. One has to draw a table with $n$ rows and $n$ columns. In this table, Row $i$ stands for $\boldsymbol{X}_{i}$ and Column $j$ for $\boldsymbol{Y}_{j}$. The cell $(i, j)$ is filled with a dot only if $\tilde{ \boldsymbol{X}}_{i}^{\mathsf{T}}\tilde{ \boldsymbol{Y}}_{j} \geq \theta$. The dots are then counted and one rejects the null if the total number of dots exceeds a threshold of $\beta[nP+n(n-1)Q]$. Typical tables for $n = 10$ under $\mathsf{H}_{0}$ and under $\mathsf{H}_{1}$ with the identity permutation are given in Figure 3.

5.3.   Theoretical guarantees

While the two error probabilities of the sum test (4.1)-(4.2) were upper-bounded using standard large deviation techniques, i.e., Chernoff's bound, this cannot be similarly done with the new proposed test, since calculating the moment-generating function of the double summation in (5.6) seems to be hopeless. Thus, alternative tools from large deviation theory have to be invoked. We start with the type Ⅱ probability of error, which is given explicitly by

The main difficulty in analyzing this lower tail probability is the statistical dependencies between the indicator random variables. Nevertheless, an existing large deviation result by Janson [38, Theorem 10] provides the appropriate tool to handle the situation at hand. Other recently treated settings where tools from ^[38] proved useful can be found in [39, Appendixes B and I] and [40, Appendix A.10].

Regarding the type Ⅰ probability of error, the situation is somewhat more complicated, since no general large deviation bounds exist to assess upper tail probabilities of the form

Hence, the best we could do is to upper-bound this probability using a generalization of Chebyshev's inequality as follows:

where $\alpha > 0$ may be optimized to yield the tightest bound. In order to derive (or at least, to upper-bound) the $\alpha$-th moment in (5.15), we consider two different cases. On the one hand, when $\alpha \in (0, 1]$, we are able to upper-bound the $\alpha$-th moment using similar techniques as in the proof of the lower bound on the error exponent of the typical random code [41, p. 6229, right column]. On the other hand, for a general $\alpha > 1$, we are not able to handle the $\alpha$-th moment; hence, instead, we have considered only the $k$-th integer moments of orders $k \geq 2$. For the special case $k = 2$, the calculation is relatively straightforward, but for a general $k \geq 3$, the situation is somewhat more complicated. Thus, new techniques that rely on graph-counting considerations are developed in Appendix C to prove Theorem 2 (which is stated in Section 6).

In the following result, which is proved in Appendix B, we present upper bounds on the type Ⅰ and type Ⅱ error probabilities for a general set of parameters. Let us denote the Stirling numbers of the second kind as follows:

and define the numbers

Theorem 1. (Type Ⅰ and type Ⅱ probability bounds) Let $n, d \in \mathbb{N}$ and $\rho \in (0, 1)$ be given. Let $P = P(d, \rho, \theta)$ and $Q = Q(d, \theta)$ as defined above. Then, for any $\beta \in (0, 1)$ and $\theta \in (0, 1)$

and,

Regarding the asymptotic behavior of the bounds. One benefit of Proposition 1 (Section 4.1) with respect to Theorem 1 is the clear conclusion that when $d$ tends to infinity, the error probabilities vanish exponentially. In order to understand the asymptotic behavior of the upper bounds in Theorem 1, we first have to handle the quantities $Q(d, \theta)$ and $P(d, \rho, \theta)$. $Q(d, \theta)$ is the probability of an independent pair of Gaussian vectors having an angle larger than $\theta$, and thus, thanks to symmetry, $Q(d, \theta)$ equals the probability that a uniformly distributed vector on a $d$-dimensional hyper-sphere of a unit norm will fall within a $d$-dimensional hyper-spherical cap with a half-angle $\varphi = \arccos(\theta)$. This probability is given by the expression ^[44]

where the complete beta function is defined by

and the incomplete beta function by

The following result, which is proved in Appendix D, shows that $Q(d, \theta)$ converges exponentially fast to zero.

Lemma 1. Let $d \in \mathbb{N}$ and $\theta \in (0, 1)$. Let

and

Then,

In addition, one can prove that $P(d, \rho, \theta)$ converges to one as $d \to \infty$ for any $\theta \in (0, \rho)$. Since the proof of this result is quite long and relatively technical, we refrain from presenting it here. Going back to the bounds in Theorem 1, we conclude the following. Regarding the bound in (5.18), it can be further upper-bounded as

which vanishes exponentially fast for any fixed $n$ as $d \to \infty$. Regarding the bound in (5.19), the situation is different, because when $d \to \infty$, we find that

which is exponentially small but fixed in $n$.

Several remarks are now in order.

Remark 1. The threshold $\beta \in (0, 1)$ trades-off between the two error probabilities. When $\beta$ is relatively low, then relatively few "dots" are required to reject $\mathsf{H}_{0}$, hence the type Ⅰ error probability is high and the type Ⅱ error probability is low. When $\beta$ grows towards 1, an increasing number of dots are needed to reject $\mathsf{H}_{0}$; the type Ⅰ error probability gradually decreases while the type Ⅱ error probability increases.

Remark 2. The relatively interesting fact (at least to the writer of these lines) is the apparent dichotomy between two regions in the parameter space $\{(n, d)\}$. On the one hand, if $n^{2}Q(d, \theta)$, which is the expected number of dots under $\mathsf{H}_{0}$, is smaller than 1, then the $\alpha$-th moment in (5.15) is proportional to $n^{2}Q(d, \theta)$ for any $\alpha \in (0, 1]\cup\{2, 3, \ldots\}$. In this case, the type Ⅰ error probability is relatively small, since the typical number of "correlated" pairs of vectors is zero. On the other hand, if $(n, d)$ are such that $n^{2}Q(d, \theta) \geq 1$, then the $\alpha$-th moment in (5.15) is proportional to $[n^{2}Q(d, \theta)]^{\alpha}$. In this case, any increment in $n^{2}Q(d, \theta)$ (due to an increasing $n$ or a decreasing $d$) causes a relatively sharp increment in the type Ⅰ error probability. Such phenomena, where moments of enumerators (i.e., sums of IID or weakly dependent indicator random variables) undergo phase transitions have already been encountered multiple times, e.g., in information theory [39, Appendix B, Lemma 3], [42, p. 168], [43, Appendix A, Lemma 1.1].

Remark 3. In this manuscript, we only consider a noiseless setup. Regarding noisy setups where the data are affected by additive white Gaussian noise^Ⅲ, consider the following. Let

^ⅢObfuscation, which refers to the deliberate addition of noise to the database entries, has been suggested as an additional measure to protect privacy ^[3].

and

where ${\bf{U}}, {\bf{V}} \overset{\text{IID}}{\sim} {\cal N}(\boldsymbol{0}_{d}, \sigma^{2} {\bf{I}}_{d})$ are independent of $(\boldsymbol{X}, \boldsymbol{Y})$. We can immediately see that $(\hat{ \boldsymbol{X}}, \hat{ \boldsymbol{Y}})$ are jointly Gaussian with a correlation coefficient of $\frac{\rho}{1+ \sigma^{2}}$, and thus, the count test and its theoretical guarantees can be relied on also for this extended case.

Remark 4. Both the sum test and the count test assume perfect knowledge of $\rho$ in order to choose desired trade-offs between the type Ⅰ and type Ⅱ error probabilities. In practice, the value of $\rho$ may be unknown a-priori or only known to be in an interval of possible values. In the latter case, where $\rho \in [\rho_0, \rho_1]$, and this range is relatively narrow, the sum/count tests can still be applied with any $\rho$ in this range, with some degraded performance due to the expected mismatch between the true $\rho$ and the chosen one. Choosing $\rho$ closer to $\rho_0$ has a preference towards lower type Ⅱ error probabilities, and vice versa. The general case where $\rho$ is unknown and may take any value in $(0, 1)$ seems to be more complicated and will not be discussed here in detail; we just mention that a possible solution may be in the spirit of the GLR test (as in (4.7)), where the likelihood under $\mathsf{H}_{1}$ is now also maximized over $\rho \in (0, 1)$, in addition to the maximization over the permutations of the rows.

5.4.   On the type Ⅰ probability bound

Let us begin by presenting an explicit expression for $P(d, \rho, \theta)$, which is the probability that the angle between a pair of correlated Gaussian vectors crosses a threshold. We first make a few definitions. For $\rho \in (0, 1)$ and $\theta \in (0, 1)$, define the constants

and the functions

Moreover, for any $d\in \mathbb{N}$, we define the two probability density functions

and

The following lemma is proved in Appendix E.

Lemma 2. Let $d \in \mathbb{N}$, $\rho \in (0, 1)$, and $\theta \in (0, 1)$. Let

and

Then,

Regarding the bound on the type Ⅰ error probability, which appears in (5.18), and is given as a minimization between three competing terms, it is definitely not obvious that all of these terms are required to achieve the best performance. In order to show that all of them are indeed required, let us compare

and

In Figure 4 below, we present plots of $E_{\mbox{ frac}}(\beta)$ (solid line) and $E_{\mbox{ sec}}(\beta)$ (dashed line) for the parameters $n = 200$, $d = 50$, $\rho = 0.4$, and $\theta = 0.6$. The quantity $Q(d, \theta)$ is calculated numerically using (5.20), and $P(d, \rho, \theta)$ is calculated using (5.39) in Lemma 2. As can be seen in Figure 4, at relatively low $\beta$s, $E_{\mbox{ frac}}(\beta)$ is a constant and it strictly improves upon $E_{\mbox{ sec}}(\beta)$. In this range, the optimizer is $\alpha^{*} = 0$. At higher $\beta$ values, the optimizer is $\alpha^{*} = 1$, and $E_{\mbox{ frac}}(\beta)$ is actually related to Markov's inequality. In the range of relatively high $\beta$ values, $E_{\mbox{ sec}}(\beta)$ outperforms $E_{\mbox{ frac}}(\beta)$, which is not very surprising, since Chebyshev's inequality is usually tighter than Markov's inequality.

With respect to the bound in $E_{\mbox{ int}}(\beta)$, the situation is somewhat more complicated and depends on the model's parameters. For $E_{\mbox{ int}}(\beta)$ to be higher than $E_{\mbox{ sec}}(\beta)$, we have two contradictory conditions. On the one hand, we need $n^{2}Q(d, \theta) \leq 1$, which holds for relatively high $\theta$ values, but, on the other hand, we require $nP(d, \rho, \theta)$ relatively large, which holds for relatively low $\theta$ values. Thus, $E_{\mbox{ int}}(\beta)$ improves on $E_{\mbox{ sec}}(\beta)$ only in some cases but not generally. To capture this fact, we present plots of the three bounds in Figure 5 for the parameters $n = 200$ and $d = 50$, but for two different pairs of $(\rho, \theta)$ for which $n^{2}Q(d, \theta) \leq 1$. Since the numbers $\mathsf{B}(k)$ in (5.17) grow quite rapidly with $k$, when calculating the bound in $E_{\mbox{ int}}(\beta)$, we switched the infimum over $\{3, 4, \ldots\}$ with a minimization over $\{3, 4, \ldots, 30\}$. For $\rho = 0.6$ and $\theta = 0.7$, it turns out that $nP(d, \rho, \theta) \approx 24.2$; in this case, $E_{\mbox{ sec}}(\beta)$ uniformly outperforms $E_{\mbox{ int}}(\beta)$ for all $\beta \in [0, 1]$. For $\rho = 0.7$ and $\theta = 0.6$, we find that $nP(d, \rho, \theta) \approx 179.3$. In this alternative case, $E_{\mbox{ int}}(\beta)$ is higher than $E_{\mbox{ sec}}(\beta)$ for relatively high $\beta$ values.

By comparing among $E_{\mbox{ frac}}(\beta)$, $E_{\mbox{ sec}}(\beta)$, and $E_{\mbox{ int}}(\beta)$ for specific parameter values, and showing that none of them uniformly dominates the others, we can safely conclude that, generally, all three bounds are needed in order to achieve the best guarantee for the type Ⅰ error probability.

6.   Bounding the moments of $N(\theta)$

As we explained before in Section 5.3, a feasible way to upper-bound the type Ⅰ probability of error is by using the generalized Chebyshev's inequality, which, in turn, requires to evaluate (or bound) the moments

where $\alpha > 0$. For $\alpha \in (0, 1]$ we relied on existing techniques from ^[41]. The case $\alpha > 1$ seems to be much more intricate; nonetheless, for $k$-th order integer moments, we were able to derive plausible bounds by using some graph-theoretic concepts. In what follows, we present a slightly more general result, which is the main theoretical contribution of this work.

Theorem 2. Let $n, d \in \mathbb{N}$. Let $\boldsymbol{X}_{1}, \ldots, \boldsymbol{X}_{n}$ and $\boldsymbol{Y}_{1}, \ldots, \boldsymbol{Y}_{n}$ be two sets of IID random variables taking values in $\mathbb{R}^{d}$. Let $J: \mathbb{R}^{d} \times \mathbb{R}^{d} \to \{0, 1\}$ and assume that

where $Q \in [0, 1]$ is independent of $\boldsymbol{x}$ and $\boldsymbol{y}$. Let $k \in \mathbb{N}$. Then,

A proof of Theorem 2 is given in Appendix C. Due to the three technical uniformity conditions in (6.2)–(6.4), we can better understand the motivation for the initial normalization of the feature vectors in (5.4) and (5.5). Thanks to these normalizations and the spherical symmetry of the Gaussian distribution, we have the following for any $\boldsymbol{x} \in \mathbb{R}^d$ and $\boldsymbol{y} \in \mathbb{R}^d$:

Thus, we can use Theorem 2 when deriving theoretical guarantees on the type Ⅰ error probability of the count test as defined with $N(\theta)$. On the other hand, referring to the statistic in (5.3), which does not involve data normalization, we see that the conditions in (6.2)–(6.4) are not satisfied. For example, the probability $\mathbb{P}\left\{ \boldsymbol{x}^{\mathsf{T}} \boldsymbol{Y} \geq \theta \right\}$ is given by a function of $\theta$ and $\| \boldsymbol{x}\|$.

We now move to explaining the main proof concepts of Theorem 2 by referring to a slightly different probabilistic problem. The main benefit of switching to a close problem is that its proof techniques are very close to those required in the proof of Theorem 2, but they are still easy to understand from simple diagrams.

Let $\boldsymbol{X}_{1}, \ldots, \boldsymbol{X}_{M}$ be a set of IID random variables taking values in $\mathbb{R}^{d}$ and let $J: \mathbb{R}^{d} \times \mathbb{R}^{d} \to \{0, 1\}$. Let us denote the indicator random variables ${\cal I}(m, m') = J(\boldsymbol{X}_m, \boldsymbol{X}_{m'})$ and the enumerator

where the set $[M]^2$ is an abbreviation for the set $\{(m, m'): m, m' \in \{1, 2, \ldots, M\}, m \neq m'\}$. The main objective is to derive an upper bound for $\mathbb{E}[N^k]$. In what follows, we provide and explain only the novel concepts in analyzing this $k$-th-order moment. We divide the analysis into three main steps: Graph counting, graph pruning, and graph reduction.

6.1.   Step Ⅰ: Graph counting

For any $k \in \mathbb{N}$, let $\mathsf{S}(k, d)$ be the number of ways to partition a set of $k$ labeled objects into $d \in \{1, 2, \dotsc, k\}$ nonempty unlabeled subsets, which is given by Stirling numbers of the second kind ^[45]:

We begin as follows:

where, in the inner summation in (6.11), we sum over all possible $k$ pairs of vector indices, which are divided in any possible way into exactly $d$ subsets, and all pairs in each subset are identical^Ⅳ. In (6.12), we use the Stirling numbers of the second kind and sum over exactly $d$ distinct pairs of vector indices, where all the identical pairs of indices in (6.11) have been merged together, using the trivial fact that multiplying any number of identical indicator random variables is equal to any one of them.

^ⅣTwo pairs $(m_{1}, m'_{1})$ and $(m_{2}, m'_{2})$ are called identical if and only if $m_{1} = m_{2}$ and $m'_{1} = m'_{2}$, otherwise, they said to be distinct.

Let us handle the inner sum in (6.12). The idea is as follows. Instead of summing over the set $\{(m_{i}, m'_{i}) \in [M]^{2}, \; 1 \leq i \leq d, \; (m_{i}, m'_{i}) \neq (m_{j}, m'_{j}) \; \forall i \neq j\}$ of $d$ distinct pairs of vector indices, we represent each possible configuration of the indices in this set as a graph $G$, and sum over all the different graphs with exactly $d$ distinct edges. In our graph representation, each vector index $m_{i} \in \{1, 2, \dotsc, M\}$ is denoted by a vertex, and each pair of indices $(m_{i}, m'_{i})$, $m_{i} \neq m'_{i}$, is connected by an edge^Ⅴ. Hence, the number of edges is fixed, but the numbers of vertices and subgraphs (i.e., disconnected parts of the graph) are variable.

^ⅤIndices that belong to distinct pairs may be joined together, e.g., if $(m_{1}, m'_{1})$ and $(m_{2}, m'_{2})$ are distinct, then it may be that $m_{1} = m_{2}$ or $m'_{1} = m'_{2}$, but not both.

Now, given $d \in \{1, 2, \dotsc, k\}$, we sum over the range of integers, which consists of all possible numbers of vertices needed to support a graph with $d$ different edges. At one extreme, if all of the $d$ edges are disconnected, then we must have $2d$ vertices. At the other extreme, let $\mathcal{V}(d)$ be the minimal number of vertices that can support a graph of $d$ edges.

Next, given $d \in \{1, 2, \dotsc, k\}$ and $v \in [\mathcal{V}(d), 2d]$, we sum over the range of possible number of subgraphs. Let $\mathcal{S}_{\mbox{ min}}(d, v)$ ($\mathcal{S}_{\mbox{ max}}(d, v)$) be the minimal (maximal) number of subgraphs that a graph with $d$ edges and $v$ vertices can have. For a given triplet $(d, v, s)$, where $s \in [\mathcal{S}_{\mbox{ min}}(d, v), \mathcal{S}_{\mbox{ max}}(d, v)]$ is the number of subgraphs within $G$, note that one can create many different graphs (see Figure 6), and we have to take all of them into account. Hence, let $\mathsf{T}(d, v, s)$ be the number of distinct ways (or topologies) to connect a graph with $d$ edges, $v$ vertices, and $s$ subgraphs. Finally, for any $1 \leq i \leq \mathsf{T}(d, v, s)$, let $\mathsf{G}_{i}(d, v, s)$ be the set of different graphs with $d$ edges, $v$ vertices, $s$ subgraphs, and the topology $i$, which can be defined on the set of $M$ vectors, as we explained before.

Let $\Theta(G)$ be an indicator random variable that equals one if and only if all the indicator random variables related to the pairs of vectors that are linked by the edges of $G$ equals one. With the definitions above, the inner sum in (6.12) can now be written as:

i.e., for any $d \in \{1, 2, \dotsc, k\}$, we first sum over the number of vertices, then over the number of subgraphs. Later, for a fixed triplet $(d, v, s)$, we sum over all possible $\mathsf{T}(d, v, s)$ topologies and finally over all specific graphs $G \in \mathsf{G}_{i}(d, v, s)$ with a given topology.

6.2.   Step Ⅱ: Graph pruning

It turns out that the expectation of $\Theta(G)$ can be easily evaluated if all subgraphs of $G$ are trees (also known as a forest in the terminology of graph theory). If at least one subgraph of $G$ contains loops, we apply a process of graph pruning, in which we cut out the minimal amount of edges^Ⅵ, while keeping all vertices intact, until we get a forest (for example, see Figure 7).

^ⅥIn fact, this procedure is equivalent to upper-bounding some of the indicator functions in (6.13) by one.

Denote by $\mathcal{P}(G)$ the pruned graph of $G$. Notice that the expectation of $\Theta(G)$ is upper-bounded^Ⅶ by the expectation of $\Theta(\mathcal{P}(G))$, and equality holds between them if $G$ is a tree. Before we proceed, let us calculate the quantity $\mathcal{E}(G)$, which is the number of edges in $\mathcal{P}(G)$. Of course, if $G$ is already a forest, then $\mathcal{E}(G) = d$. For any $G \in \mathsf{G}_{i}(d, v, s)$ which is not necessarily a forest, we find $\mathcal{E}(G)$ as follows. Assume that $v_{1}, v_{2}, \dotsc, v_{s}$ are the number of vertices in each of the $s$ subgraphs of $G$. Then, in the process of graph pruning, each of the $j \in \{1, 2, \dotsc, s\}$ subgraphs of $G$ will transform into a tree with exactly $v_{j} - 1$ edges. Hence,

^ⅦIt follows from the fact that $\Theta(G) \leq\Theta(\mathcal{P}(G))$ with probability one.

6.3.   Step Ⅲ: Graph reduction

The expectation of $\Theta(\mathcal{P}(G))$ can be upper-bounded in a simple iterative process of graph reduction. In the first step, we take the expectation with respect to all vectors that are labels of leaf vertices in $\mathcal{P}(G)$, while we condition on the realizations of all other vectors, namely those corresponding to inner vertices in $\mathcal{P}(G)$; afterwards, we erase the leaf vector vertices and the corresponding edges. The successive steps are identical to the first one on the remaining (unerased) graph, continuing until all vectors that are attributed to $G$ have been considered (for example, see Figure 8).

In each step of graph reduction, the expectation with respect to each of the leaf vectors is upper-bounded as $\mathbb{P} \left\{ J(\boldsymbol{x}, \boldsymbol{X}_{\mbox{ leaf}}) = 1 \right\} \leq Q$, regardless of $\boldsymbol{x}$, since we condition on the realizations of vectors that are attributed to the inner vertices. For any graph $G \in \mathsf{G}_{i}(d, v, s)$, we conclude that the expectation of $\Theta(\mathcal{P}(G))$ is upper-bounded by $Q^{\mathcal{E}(G)}$. Thus, for any $G \in \mathsf{G}_{i}(d, v, s)$, we prove the following upper bound on the expectation of $\Theta(G)$ as follows:

This bound involves, in fact, the main conceptual steps in the derivation of an upper bound on $\mathbb{E}[N^{k}]$; after upper-bounding (6.14) using (6.16), the remaining steps are much more technical and will not be presented here, as they resemble the second half of the proof of Theorem 2 (in Appendix C).

7.   Comparison with the sum test

We now show that for some parameter choices, the new proposed statistical test in (5.12) achieves lower type Ⅰ and type Ⅱ error probabilities than the sum test in (4.2), which was proposed in ^[13]. The fact that we could prove that the new test has lower error probabilities is not trivial, since the analysis in ^[13] is based on Chernoff's bound, which is known to be relatively tight^Ⅷ in many cases, while the analysis in the current manuscript follows other methods that are able to accommodate the statistical dependencies between the indicator random variables in (5.6).

^ⅧIn the sense that a lower bound with a matching exponent function can be derived.

For each specific $\rho$, the trade-off between the two error probabilities varies significantly with the choices of the thresholds $\beta$ and $\theta$; hence, these parameters should be tuned accordingly to achieve the desired trade-off. Let us denote the right-hand sides of (5.18) and (5.19) as $P_{\mbox{ FA}}(\beta, \theta)$ and $P_{\mbox{ MD}}(\beta, \theta)$, respectively, where the dependence on $(n, d, \rho)$ is made implicit. We define a unique performance curve for the count test by minimizing the type Ⅱ error probability while constraining the type Ⅰ error probability to a desired level. More specifically,

In Figure 9 below, we present a plot of the trade-off between $\tfrac{d}{2}G_{\mbox{ FA}}(\gamma)$ and $\tfrac{d}{2}G_{\mbox{ MD}}(\gamma)$ for $\gamma \in (0, 4\rho^{2})$ (solid line) together with a plot of $E_{\mbox{ MD}}^{\mbox{ Count}}(n, d, \rho, E_{\mbox{ FA}})$ as a function of $E_{\mbox{ FA}}$ (scattered points) for the parameters $n = 200$, $d = 50$, and for two values of $\rho$. The quantity $Q(d, \theta)$ is calculated numerically using (5.20) and $P(d, \rho, \theta)$ is calculated using (5.39) in Lemma 2. Since the numbers $\mathsf{B}(k)$ in (5.17) grow quite rapidly with $k$, when calculating the bound in (5.42), we switched the infimum over $\{3, 4, 5, \ldots\}$ with a minimization over $\{3, 4, \ldots, 30\}$. As can be seen in Figure 9, the new proposed statistical test achieves lower error probabilities for both $\rho = 0.7$ and $\rho = 0.4$.

In the comparison aboove, we see that the count test uniformly outperforms the sum test for specific choices of the parameter triplet $n, d, \rho$. We now show that the range of parameter choices for which the count test is better than the sum test is relatively wide. To compare between the two tests, let us define

We let $d$ vary while fixing the parameter values $n = 200$ and $E_{\mbox{ FA}} = 3$, such that the type Ⅰ error probabilities are upper-bounded by approximately $0.05$ for any value of $d$. In Figure 10 below, we present plots of $E_{\mbox{ MD}}^{\mbox{ Count}}(n, d, \rho, E_{\mbox{ FA}})$ and $E_{\mbox{ MD}}^{\mbox{ Sum}}(d, \rho, E_{\mbox{ FA}})$ as functions of $d$ for two values of $\rho$. As can be seen in Figure 10, the count test outperforms the sum test for relatively low $d$ values, while the sum test performs better otherwise. One should note that for lower values of $\rho$, the range of $d$ in which the count test outperforms the sum test increases.

It may be somewhat surprising to some readers that the sum test was found to perform worse than the count test in the Gaussian setup. Moreover, it is possible that the sum test may actually perform better in practice, but the (Chernoff-based) bounds for its error probabilities may not be tight enough to show this. In order to reject this hypothesis, we computed the type Ⅰ and type Ⅱ error probabilities of both tests via Monte–Carlo simulations. In Figure 11 below, we present points of the form $(-\log \hat{P}_{\mbox{ FA}}, -\log \hat{P}_{\mbox{ MD}})$ for some threshold values $t$ in the sum test and for some threshold pairs $(\theta, \beta)$ in the count test for the parameters $n = 200$, $d = 50$, and $\rho = 0.3$. In order to facilitate the simulations for the count test, we fixed the local threshold as $\theta = 0.4$ and picked a few values for $\beta$ in $(0, 1)$. The error probabilities of the sum test have been estimated on the basis of 20,000 samples at each point, while for the count test we increased the sample size to 200,000 at each point. As can be seen in Figure 11, the estimated error probabilities of the sum test are higher than those of the count test, thus the latter performs better also in practice, at least for the specific chosen parameter values.

8.   Summary and future research

In this manuscript, we propose the count test, which is a new statistical test that solves the correlation detection problem between two Gaussian databases. The proposed test has a reduced computational complexity in comparison with the GLR test, which makes it more desirable from a practical point of view. The count test relies on a statistic given by a sum of weakly dependent indicator random variables. Therefore, novel graph-theoretic techniques have been developed in order to derive theoretical guarantees on the type Ⅰ probability of error. We compared the count test with the sum test, which was recently proposed as a valid solution for the same statistical problem. By comparing the analytical bounds of the two error probabilities, it is realized that the count test outperforms the sum test for a relatively wide range of system parameters. In principle, the probability bounds may not reflect the true performance of the tests, and thus we also present a comparison between the estimated error probabilities that result from Monte–Carlo simulations of both tests. In this comparison as well, the count test outperforms the sum test. Further possible directions for future research are suggested as follows.

(1) A goal for future research is to analyze the GLR test for the correlation detection problem and compare its performance with those of the sum test and the count test. Bounding the type Ⅱ error probability of the GLR test should be relatively straightforward, but deriving a plausible bound for its type Ⅰ error probability seems to be more challenging and may require new probabilistic tools. In addition, one can also propose a generalization of the simplified form of the GLR test in (4.10), which trades-off between computational complexity and reliability; we suggest a statistical test with a running time of ${\cal O}(n^{\delta})$ for some $\delta \in (1, 3)$. Specifically, we suggest the following test. For two given databases $\boldsymbol{X}^{n}$ and $\boldsymbol{Y}^{n}$ and a predefined $\alpha \in [0, 1]$, we consider the first $n^{\alpha}$ rows in $\boldsymbol{X}^{n}$ and solve the partial assignment problem between $\{ \boldsymbol{X}_{1}, \ldots, \boldsymbol{X}_{n^{\alpha}}\}$ and $\boldsymbol{Y}^{n}$, i.e., we calculate the statistic

where $\boldsymbol{Y}^{ {\cal A}}$ is a database that contains only the rows from $\boldsymbol{Y}^{n}$, with indices as given by the set ${\cal A} \subseteq [n]$. The proposed test then compares $W(\alpha)$ to a threshold as follows:

where $\xi \in (\mathbb{E}_{0}[W(\alpha)], \mathbb{E}_{1}[W(\alpha)])$ is a global threshold.

Concerning the running time of the test $\phi_{{\mbox{ GLR}}}(\boldsymbol{X}^{n}, \boldsymbol{Y}^{n})$, it is directly connected to the computational complexity of the partial assignment problem between $J$ jobs and $W$ workers ($J \leq W$). Such an assignment problem can be solved sequentially; one can add the $j$-th job and update the total cost in time ${\cal O}(jW)$, yielding an overall time complexity of ${\cal O}(\sum_{j = 1}^{J}jW) = {\cal O}(J^{2}W)$. In our case, the time complexity is given by ${\cal O}(n^{1+2\alpha})$. It may be of special interest to compare this test at $\alpha = 0$ with the sum test (whose computational complexity scales like ${\cal O}(n)$) and, additionally, to compare this test at $\alpha = 1/2$ with the count test (whose computational complexity scales like ${\cal O}(n^2)$).

(2) In the current manuscript, we have considered a relatively simplified model, in which the components of every feature vector are IID and Gaussian. In practice, both of these assumptions may not be valid. In the first step towards more general settings, one should consists a model where each feature vector is still Gaussian but with a general covariance matrix. In a second step, a model with non-Gaussian feature vectors may be considered as well. It is of great interest to explore statistical tests for more general models, which are characterized by high reliability and low computational complexity.

Use of Generative-AI tools declaration

The author declares that he has not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The author gratefully acknowledges the timely and constructive reports of the anonymous referees, as well as editorial comments provided by the editor. Special thanks are extended to Edward Hall (EPFL) for his help in executing the Monte–Carlo simulations in Section 7. The author also thanks Argaman and Omri Tamir for sharing their artistic preferences when finalizing Figure 4.

Conflict of interest

The author declares no conflicts of interest.

Appendix A

Preliminaries

The main purpose of this appendix is to provide the general setting and the main result borrowed from ^[38].

Let $\{U_{ \boldsymbol{k}}\}_{ \boldsymbol{k} \in {\cal K}}$ be a family of Bernoulli random variables, where ${\cal K}$ is a set of multidimensional indexes. Let ${\cal G}$ be a dependency graph for $\{U_{ \boldsymbol{k}}\}_{ \boldsymbol{k} \in {\cal K}}$, i.e., a graph with a vertex set ${\cal K}$ such that if ${\cal A}$ and ${\cal B}$ are two disjoint subsets of ${\cal K}$, and ${\cal G}$ contains no edge between ${\cal A}$ and ${\cal B}$, then the families $\{U_{ \boldsymbol{k}}\}_{ \boldsymbol{k} \in {\cal A}}$ and $\{U_{ \boldsymbol{k}}\}_{ \boldsymbol{k} \in {\cal B}}$ are independent. Let $S = \sum_{ \boldsymbol{k} \in {\cal K}} U_{ \boldsymbol{k}}$ and $\Delta = \mathbb{E}[S]$. Moreover, we write $\boldsymbol{i} \sim \boldsymbol{j}$ if $(\boldsymbol{i}, \boldsymbol{j})$ is an edge in the dependency graph $G$. Let

and

The following result will be used in the proof of Theorem 1 in Appendix B:

Theorem 3. (^[38], Theorem 10) With the notation as given above, then for any $0\leq \beta \leq 1$,

Appendix B - Proof of Theorem 1

Analysis of false alarms

For $\alpha \geq 0$, consider the following:

where (B.4) is due to Markov's inequality. Since $\alpha \geq 0$ is arbitrary, it holds that

so the main tasks are to evaluate the fractional $\alpha$-th moment and the integer $k$-th moment of $N(\theta)$. We start with the fractional $\alpha$-th moment of $N(\theta)$ and proceed as follows. For a given $\alpha \in [0, 1]$, let $\xi \in [\alpha, 1]$. In this case,

where the first inequality is based on the fact that $(\sum_{i}a_{i})^{t} \leq \sum_{i}a_{i}^{t}$ whenever $\{a_{i}\}$ are non-negative and $t \in [0, 1]$, and the second inequality follows from Jensen's inequality and the concavity of the function $f(u) = u^{\alpha/\xi}$ when $u \geq 0$ and $0 < \alpha/\xi \leq 1$. In order to proceed, we use the following modification of [43, Appendix A, Lemma 1.1].

Lemma 3. Let $I_{1}, \ldots, I_{n}$ be IID Bernoulli random variables with success probability bounded as:

where $n \in \mathbb{N}$ and $Q \in [0, 1]$. Let $\xi \in (0, 1)$. In this case,

Proof. We distinguish between two cases. If $nQ \leq 1$, then we rely on the result in [43, Equation (149)] with $(\lceil\xi\rceil!)^2\lceil\xi\rceil = 1$ to conclude that

Conversely, if $nQ > 1$, Jensen's inequality and the concavity of the function $f(u) = u^{\xi}$ when $u \geq 0$ and $0 < \xi < 1$ yields

■

Note that, conditioned on $\boldsymbol{X}_{i} = \boldsymbol{x}$, the random variables $\left\{ \mathbb{1}\{\tilde{ \boldsymbol{x}}^{\mathsf{T}}\tilde{ \boldsymbol{Y}}_{j} \geq \theta \}\right\}_{j = 1}^{n}$ are IID Bernoulli, and thus

Since the right-hand side of (B.16) does not depend on $\boldsymbol{X}_{i}$, it also holds that

Upper-bounding (B.11) using (B.17) yields

Finally, minimizing over $\xi \in [\alpha, 1]$ yields

It then follows that the first term inside the minimum in (B.7) is upper-bounded by

Moving to upper-bounding the $k$-th integer moments of $N(\theta)$, let us start with the case of $k = 2$.

where (B.29) is due to

The resulting second-order bound is given by

For the general case of $k \geq 3$, we use the result of Theorem 2 (which appears in Section 6). It follows that the second term inside the minimum in (B.7) is upper-bounded by

Upper-bounding (B.7) with (B.26), (B.35), and (B.36) proves (5.18) in Theorem 1.

Analysis of missed detection

Consider the following:

Let us abbreviate the indicator random variables as ${\cal I}(i, j) = \mathbb{1}\left\{\tilde{ \boldsymbol{X}}_{i}^{\mathsf{T}}\tilde{ \boldsymbol{Y}}_{j} \geq \theta \right\}$. In order to upper-bound (B.38), we use the result of Theorem 3, which appears in Appendix A. In our case, we have $\Delta = \Delta_{n, d}$, and it only remains to assess the quantities $\Theta$ and $\Omega$. One can easily check that the indicator random variables ${\cal I}(i, j)$ and ${\cal I}(k, \ell)$ are independent as long as $i \neq k$ and $j \neq \ell$. Thus, we define our dependency graph so that each vertex $(i, j)$ is connected exactly to $2n - 2$ vertices of the form $(i, \ell)$, $\ell \neq j$ or $(k, j)$, $k \neq i$. If the vertices $(i, j)$ and $(k, \ell)$ are connected, we write $(i, j) \sim (k, \ell)$.

Let us denote the set $\Psi_{n} = \{(m, m'):\; m, m'\in \{1, 2, \ldots, n\}\}$. Concerning $\Theta$ and $\Omega$, we get

Regarding the summands in the left-hand term of (B.40), we derive them as follows:

Deriving the summands in the right-hand term of (B.40) in a similar way, we eventually arrive at

In addition

Then

and

Hence

which completes the proof of Theorem 1.

Appendix C - Proof of Theorem 2

For any $k \in \mathbb{N}$, let $\mathsf{S}(k, d)$ be the number of ways to partition a set of $k$ labeled objects into $d \in \{1, 2, \dotsc, k\}$ nonempty unlabeled subsets, which is given by Stirling numbers of the second kind ^[45], i.e.,

Obviously, $\mathsf{S}(k, 1) = \mathsf{S}(k, k) = 1$. As before, we denote $\Psi_{n} = \{(m, m'):\; m, m'\in \{1, 2, \ldots, n\}\}$. In this case,

where, in the inner summation in (C.4), we sum over all possible $k$ pairs of vectors indices, which are divided in any possible way into exactly $d$ subsets, and all pairs in each subset are identical. In (C.5), we use the Stirling numbers of the second kind and sum over exactly $d$ distinct pairs of vector indices, where all the identical pairs of indices in (C.4) have been merged together, using the trivial fact that multiplying any number of identical indicator random variables is equal to any one of them.

Let us handle the inner sum of (C.5). The idea is as follows. Instead of summing over the set $\{(m_{i}, m'_{i}) \in \Psi_{n}, \; 1 \leq i \leq d, \; (m_{i}, m'_{i}) \neq (m_{j}, m'_{j}) \; \forall i \neq j\}$ of $d$ distinct pairs of indices of vectors, we represent each possible configuration of indices in this set as a graph $G$ and sum over all different graphs with exactly $d$ distinct edges. In our graph representation, each vector index $m_{i} \in \{1, 2, \dotsc, n\}$ and $m'_{i} \in \{1, 2, \dotsc, n\}$ is denoted by a vertex, and each pair of indices $(m_{i}, m'_{i})$, $m_{i} \neq m'_{i}$, is connected by an edge. Hence, the number of edges is fixed, but the numbers of vertices and subgraphs (i.e., disconnected parts of the graph) are variable.

Given $d \in \{1, 2, \dotsc, k\}$, we sum over the set ${\cal V}(d) = \{(v_{x}, v_{y})\}$ of pairs of integers, which consists of all possible pairs of vertices needed in order to support a graph with $d$ different edges. Next, given $d \in \{1, 2, \dotsc, k\}$ and $(v_{x}, v_{y}) \in {\cal V}(d)$, we sum over the range of the possible number of subgraphs. Let $\mathcal{S}_{\mbox{ min}}(d, v_{x}, v_{y})$ ($\mathcal{S}_{\mbox{ max}}(d, v_{x}, v_{y})$) be the minimal (maximal) number of subgraphs that a graph with $d$ edges and $(v_{x}, v_{y})$ vertices can have. For a given quadruplet $(d, v_{x}, v_{y}, s)$, where $s \in [\mathcal{S}_{\mbox{ min}}(d, v_{x}, v_{y}), \mathcal{S}_{\mbox{ max}}(d, v_{x}, v_{y})]$ is the number of subgraphs within $G$, note that one can create many different graphs (see Figure 12), and we have to take all of them into account. Hence, let $\mathsf{T}(d, v_{x}, v_{y})$ ($\mathsf{T}(d, v_{x}, v_{y}, s)$) be the number of distinct ways to connect a graph with $d$ edges and $(v_{x}, v_{y})$ vertices (and $s$ subgraphs). Finally, for any $1 \leq i \leq \mathsf{T}(d, v_{x}, v_{y}, s)$, let $\mathsf{G}_{i}(d, v_{x}, v_{y}, s)$ be the set of different graphs with $d$ edges, $(v_{x}, v_{y})$ vertices, and $s$ subgraph, that can be defined on the set $\Psi_{n}$ of pairs of vectors, as we explained before.

We now prove that the cardinality of the set $\mathsf{G}_{i}(d, v_{x}, v_{y}, s)$ is upper-bounded by an expression that depends only on the numbers of vertices $(v_{x}, v_{y})$. First, let $N(v_{x})$ be the number of options to choose $v_{x}$ different vectors from a set of cardinality $n$. In this case,

Thus

Let $\Theta(G)$ be an indicator random variable that equals one if and only if all pairs of feature vectors that are linked by the edges of $G$ have $J(\boldsymbol{X}, \boldsymbol{Y}) = 1$. With the definitions above, the inner sum of (C.5) can now be written as

i.e., for any $d \in \{1, 2, \dotsc, k\}$, we first sum over the numbers of vertices, then over the number of subgraphs, then, for a fixed quadruplet $(d, v_{x}, v_{y}, s)$, over all possible $\mathsf{T}(d, v_{x}, v_{y}, s)$ topologies, and, finally, over all specific graphs $G \in \mathsf{G}_{i}(d, v_{x}, v_{y}, s)$ with a given topology. One should note that all limits of the three outer sums in (C.10) depend only on $k$, while $|\mathsf{G}_{i}(d, v_{x}, v_{y}, s)|$ is the only one that depends also on $n$. Similarly to the procedure described in Section 6.2, also here, the expectation of $\Theta(G)$ can be easily evaluated if all subgraphs of $G$ are trees (i.e., $G$ is a forest). If at least one subgraph of $G$ contains loops, we apply a process of graph pruning, in which we cut out the minimal amount of edges^Ⅸ, while keeping all vertices intact, until we get a forest (for example, see Figure 13).

^ⅨIn fact, this procedure is equivalent to upper-bounding some of the indicator functions in (C.9) by one.

We use $\mathcal{P}(G)$ to denote the pruned graph of $G$. Notice that the expectation of $\Theta(G)$ is upper-bounded^Ⅹ by the expectation of $\Theta(\mathcal{P}(G))$, which can be evaluated in a simple iterative process of graph reduction, similarly to the procedure described in Section 6.3. In the first step, we take the expectation with respect to all vectors that are the labels of leaf vertices in $\mathcal{P}(G)$, while we condition on the realizations of all other vectors, namely those corresponding to inner vertices in $\mathcal{P}(G)$; afterwards, we erase leaf vector vertices and corresponding edges. The successive steps are identical to the first one on the remaining (unerased) graph, continuing until all vectors that are attributed to $G$ have been considered (for example, see Figure 14).

^ⅩIt follows from the fact that $\Theta(G) \leq\Theta(\mathcal{P}(G))$ with probability one.

In each step of graph reduction, the expectation with respect to each of the leaf vectors is given by $\mathbb{P} \left\{J(\boldsymbol{x}, \boldsymbol{Y}_{\mbox{ leaf}}) = 1 \right\} \leq Q$, since we condition on the realizations of vectors that are attributed to the inner vertices. For any graph $G \in \mathsf{G}_{i}(d, v_{x}, v_{y}, s)$, we conclude that the expectation of $\Theta(\mathcal{P}(G))$ is upper-bounded by $Q^{ {\cal E}(G)}$, where ${\cal E}(G)$ is the number of edges in ${\cal P}(G)$. Of course, if $G$ is already a forest, then $\mathcal{E}(G) = d$. For any $G \in \mathsf{G}_{i}(d, v_{x}, v_{y}, s)$ which is not a forest, we find $\mathcal{E}(G)$ as follows. Assume that $v_{x}(1), v_{x}(2), \dotsc, v_{x}(s)$ and $v_{y}(1), v_{y}(2), \dotsc, v_{y}(s)$ are the number of vertices in each of the $s$ subgraphs of $G$. In the process of graph pruning, each of the $j \in \{1, 2, \dotsc, s\}$ subgraphs of $G$ will transform into a tree with exactly $v_{x}(j) + v_{y}(j) - 1$ edges. Hence

The innermost sum of (C.10) can be treated as follows:

where (C.14) follows from (C.11), and (C.16) is due to (C.8). Next, we substitute (C.16) back into (C.10) and get

where (C.18) is true since $Q \in [0, 1]$, such that replacing $s$ by its maximal value $\mathcal{S}_{\mbox{ max}}(d, v_{x}, v_{y})$ provides an upper bound. The passage (C.19) follows from the definitions of $\mathsf{T}(d, v_{x}, v_{y})$ and $\mathsf{T}(d, v_{x}, v_{y}, s)$. Before we substitute it back into (C.10) and then into (C.5), we summarize some minor results that will be needed in the sequel. Let us define $d^{*} = \max\{v_{x}, v_{y}\}$.

Lemma 4. We have the following:

1. For fixed $(v_{x}, v_{y})$, $\mathcal{S}_{\mathit{\mbox{max}}}(d, v_{x}, v_{y})$ is a non-increasing sequence of $d$.

2. For any $(v_{x}, v_{y})$, we have $\mathcal{S}_{\mathit{\mbox{max}}}(d^{*}, v_{x}, v_{y}) = \min\{v_{x}, v_{y}\}$.

Proof. We prove each of the two arguments separately.

1. For fixed $(v_{x}, v_{y})$, if we add to the graph an edge, we have only two options. On the one hand, we may connect vertices that belong to the same subgraph so the number of subgraphs remains the same. On the other hand, we can connect vertices that belong to different subgraphs, in which case, the number of subgraphs decreases.

2. Without loss of generality, assume that $v_{x} \leq v_{y}$. Then $d^{*} = v_{y}$, and hence it follows by definition that each column contains exactly one edge, such that the set of edges in each row provides a subgraph. Thus, the number of subgraphs equals exactly $v_{x}$.

■

Now we have

In (C.22) we changed the order of summation, and (C.23) is true since $Q \in [0, 1]$, and thus, according to the first point in Lemma 4, we reach an upper bound by substituting $d = d^{*}$. Moving forward, we use the trivial bound

and arrive at

where (C.25) follows from the second point in Lemma 4 and (C.28) follows from the definition in (5.17). Finally,

Now, if $n^{2}Q > 1$, then

otherwise, if $n^{2}Q \leq 1$, then

which completes the proof of Theorem 2.

Appendix D - Proof of Lemma 1

We upper-bound the expression in (5.20), which is given by

As for the numerator, we have

In order to bound the beta function, we use the following identity:

where $\Gamma(\cdot)$ is the gamma function:

In general

In order to bound the ratio of gamma functions, let us invoke Gautschi's inequality.

Lemma 5. Let x be a positive real number and let $s \in (0, 1)$. In this case,

For a lower bound

where (D.14) is due to the upper bound in Lemma 5. Now, combining (D.6) and (D.15) yields the upper bound

which completes the proof of Lemma 1.

Appendix E - Proof of Lemma 2

Observe that under the assumption of

it holds that $\boldsymbol{Y} = \rho \boldsymbol{X} + \sqrt{1-\rho^{2}} \boldsymbol{Z}$ with $\boldsymbol{Z} \sim {\cal N}(\boldsymbol{0}_{d}, {\bf{I}}_{d})$ and independent of $\boldsymbol{X}$. Consider the following for some $\theta \in (0, 1)$:

Since $\theta > 0$, the event in (E.4) can occur only if $\rho\| \boldsymbol{X}\|^{2} + \sqrt{1-\rho^{2}} \boldsymbol{X}^{\mathsf{T}} \boldsymbol{Z} \geq 0$. Let us denote the event

and the angle between $\boldsymbol{X}$ and $\boldsymbol{Z}$ as $\Phi_{ \mbox{xz}}$. In this case,

Rearranging, we get

Note that $\rho\| \boldsymbol{X}\|^{2} + \sqrt{1-\rho^{2}} \boldsymbol{X}^{\mathsf{T}} \boldsymbol{Z} \geq 0$ is equivalent to

and therefore

Now, the left-hand side event in (E.16) becomes trivial if and only if

while the right-hand side event in (E.16) becomes trivial if and only if

In addition, note that for any $\theta \in (0, 1)$, it holds that $\beta(\rho, \theta) \geq \alpha(\rho)$. Define the functions

such that

Note that both $\| \boldsymbol{X}\|^{2}$ and $\| \boldsymbol{Z}\|^{2}$ follow a $\chi^{2}$ distribution with $d$ degrees of freedom. Hence, the random variable defined by the ratio

follows the $F$-distribution with $(d, d)$ degrees of freedom. The probability density function of a general $F$-distributed random variable with $(d_{1}, d_{2})$ degrees of freedom is given by

and for $d_{1} = d_{2} = d$, we denote it as

We now have

where (E.28) follows from the following considerations. For the second integral, we use the fact that for any $u \geq \alpha(\rho)$, the second event is trivial, and for the last integral, we use the fact that for any $u \geq \beta(\rho, \theta)$, both events become trivial. In order to facilitate the first integral in (E.28), we prove that for any $u \in [0, \alpha(\rho)]$, it holds that $F_{1}(u) \leq F_{3}(u) \leq F_{2}(u)$ (as can be seen in Figure 15 for two specific choices of the pair $(\rho, \theta)$).

It immediately follows from the definitions of $F_{1}(u)$ and $F_{2}(u)$ in (E.19) and (E.20) that for any $u \in [0, \beta(\rho, \theta)]$, $F_{1}(u) \leq F_{2}(u)$. We start by proving that $F_{1}(u) \leq F_{3}(u)$. Note that $F_{3}(u)$ is monotonically decreasing and $F_{3}(0) = 0$. In addition, $F_{1}(0) = -\theta < F_{3}(0)$. Furthermore, note that $F_{1}(\alpha(\rho)) = F_{3}(\alpha(\rho)) = -1$, so it only remains to show that $F_{1}(u)$ is also monotonically decreasing for any $u \in [0, \alpha(\rho)]$. To this end, we show that $F'_{1}(u) = 0$ has a unique solution at $u = \alpha(\rho)$. The derivative $F'_{1}(u)$ is given by

$F'_{1}(u) = 0$ is then equivalent to

or, in turn, to the linear equation

whose unique solution is given by

Since $F_1(0) = -\theta > -1 = F_1(\alpha(\rho))$, this proves that $F_{1}(u)$ is monotonically decreasing for any $u \in [0, \alpha(\rho)]$. This completes the proof of $F_{1}(u) \leq F_{3}(u)$.

We next prove that $F_{3}(u) \leq F_{2}(u)$. The derivative of $F_{2}(u)$ is given by

which is negative for any $u \in [0, \beta(\rho, \theta)]$, and thus $F_{2}(u)$ is a monotonically decreasing function on the same interval. Note that $F_{2}(0) = \theta > 0 = F_{3}(0)$ and, in addition

Since $F_{2}(u)$ is monotonically decreasing and $\beta(\rho, \theta) \geq \alpha(\rho)$, we get

which completes the proof of $F_{3}(u) \leq F_{2}(u)$, since $F_{3}(u)$ is monotonically decreasing for any $u\geq 0$.

Using the double inequality $F_{1}(u) \leq F_{3}(u) \leq F_{2}(u)$, which holds for any $u \in [0, \alpha(\rho)]$, we arrive at

Regarding the probabilities inside the first two integrals in (E.38), consider the following result.

Lemma 6. Let $d \in \mathbb{N}$ and $\boldsymbol{X}, \boldsymbol{Y} \sim {\cal N}(\boldsymbol{0}_{d}, {\bf{I}}_{d})$ be two independent random vectors. Let $\tilde{ \boldsymbol{X}} = \tfrac{ \boldsymbol{X}}{\| \boldsymbol{X}\|}, \; \tilde{ \boldsymbol{Y}} = \tfrac{ \boldsymbol{Y}}{\| \boldsymbol{Y}\|}$, and define $S = \cos(\Phi) = \tilde{ \boldsymbol{X}}^{ \mathsf{T}}\tilde{ \boldsymbol{Y}}$. The probability density function of $S$ is then given by

where the complete beta function is

Finally,

which completes the proof of Lemma 2.