#  Selective inference for multiple pairs of clusters
after $K$-means clustering

Youngjoo Yun  Department of Statistics, University of Wisconsin-Madison
Yinqiu He  Department of Statistics, University of Wisconsin-Madison

###### Abstract

If the same data is used for both clustering and for testing a null hypothesis
that is formulated in terms of the estimated clusters, then the traditional
hypothesis testing framework often fails to control the Type I error. Gao et
al. (2022) and Chen and Witten (2023) provide selective inference frameworks
for testing if a pair of estimated clusters indeed stem from underlying
differences, for the case where hierarchical clustering and $K$-means
clustering, respectively, are used to define the clusters. In applications,
however, it is often of interest to test for multiple pairs of clusters. In
our work, we extend the pairwise test of Chen and Witten (2023) to a test for
multiple pairs of clusters, where the cluster assignments are produced by
$K$-means clustering. We further develop an analogous test for the setting
where the variance is unknown, building on the work of Yun and Barber (2023)
that extends Gao et al. (2022)’s pairwise test to the case of unknown
variance. For both known and unknown variance settings, we present methods
that address certain forms of data-dependence in the choice of pairs of
clusters to test for. We show that our proposed tests control the Type I
error, both theoretically and empirically, and provide a numerical study of
their empirical powers under various settings.

##  1 Introduction

Clustering is a widely used tool for studying unlabeled data that works by
dividing a given data into groups based on certain similarity measures. The
number of clusters to expect from a given data may not always be apparent, but
several popular clustering algorithms require that it be specified, including
$K$-means clustering. In such cases, researchers might try running the
algorithm with a relatively large number of clusters and then examine if there
exists any difference among several of the estimated clusters. It could then
be of interest to do a statistical test to investigate if there is indeed an
underlying group structure among these clusters. In this work, we propose
methods for testing the null hypothesis that states there is no difference in
the means of the cluster centers of an arbitrary number of clusters, where the
cluster assignments are produced by the $K$-means algorithm run on the same
data as the one used for inference; here, and in the rest of the paper, the
cluster center of a cluster denotes the sample mean of the observations in the
cluster.

Since our null hypothesis is formulated in terms of the clusters defined by
$K$-means clustering, it is inevitably data-dependent and breaches the
assumption of the traditional hypothesis testing framework that all aspects of
the inference procedure are determined independently of the data. As a result,
traditional inference procedures may no longer be valid for such a
setting—they could invalidate the p-value obtained, as well as undermine
replicability, as discussed in Benjamini (2020). While sample splitting is a
widely used method for addressing issues of data-dependence, it is not
applicable to statistical inferences involving clusters, as discussed in Gao
et al. (2022) and Neufeld et al. (2024). An alternative approach that is
relevant to such settings is a framework called selective inference, which,
first proposed in Fithian et al. (2014), allows for valid inference in the
presence of data-dependence in the inference procedure. It works by accounting
for the event that leads to this dependence—more specifically, Fithian et al.
(2014) account for this event by considering the selective Type I error, the
Type I error conditioned on the selection event.

To address the challenges of statistical inference for data-dependent
clusters, various selective inference procedures have been developed; examples
include Gao et al. (2022) for hierarchical clustering algorithms, Chen and
Witten (2023) for $K$-means clustering, Bachoc et al. (2023) for convex
clustering, and Watanabe and Suzuki (2021) for latent block models whose
structure is determined by a clustering algorithm.

In particular, Gao et al. (2022) and Chen and Witten (2023) provide selective
inference frameworks for testing for the difference in means between the
cluster centers of a pair of clusters, which are chosen independently of the
data from the $K$ estimated clusters. They consider the data generating
distribution where $n$ observations $X_{i}\in\mathbb{R}^{q}$ for
$i\in\\{1,\ldots,n\\}$ are generated independently as

$\displaystyle X_{i}\sim\mathcal{N}\left(\mu_{i},\sigma^{2}I_{q}\right)$ (1)

with unknown $\mu_{i}\in\mathbb{R}^{q}$ and known $\sigma>0$. Let
$\\{\mathcal{C}_{1},...,\mathcal{C}_{K}\\}$ be a partition of {1,…,n}, where
$\mathcal{C}_{k}\subset\\{1,...,n\\}$ denotes the set of indices of the
observations $X_{i}$s that are assigned to the $k$th cluster. Gao et al.
(2022) and Chen and Witten (2023) consider the null hypothesis that states

$\displaystyle H_{0,\,\\{k,k^{\prime}\\}}:\ \
\bar{\mu}_{\,\mathcal{C}_{k}}=\bar{\mu}_{\,\mathcal{C}_{k^{\prime}}},$ (2)

where $k\neq k^{\prime}\in\\{1,...,K\\},$ and
$\bar{\mu}_{\mathcal{C}_{k}}=\sum_{i\in\mathcal{C}_{k}}\mu_{i}/|\mathcal{C}_{k}|$
denotes the mean of the cluster center of the $k$th cluster.

Several works have extended these works to other related settings. Yun and
Barber (2023) study the case where the parameter $\sigma$ in (1) is unknown,
and González-Delgado et al. (2023) relax the assumption on the data generating
process in (1) by allowing for dependence across the observations.
Furthermore, Chen and Gao (2023) develop a method for testing the null
hypothesis analogous to (2) for a single feature, which is also studied in
Hivert et al. (2022) but under different assumptions on the data. Hivert et
al. (2022) additionally propose a method for testing for clusters that are in
a specific arrangement with respect to each other. In this setting, they
provide a method that combines the p-values produced by the test of Gao et al.
(2022) for the pairs of clusters involved. While this work also considers a
test for multiple clusters, it differs from our proposed tests in that the
latter can be applied to any collection of clusters.

In this work, we extend the work of both Chen and Witten (2023) and Yun and
Barber (2023) by developing tests for multiple pairs of clusters for both
known and unknown variances, where the clusters are produced by $K$-means
clustering.

###  1.1 Global null hypothesis for multiple pairs of clusters

Let $\mathcal{V}_{\mathrm{all}}=\\{(k,k^{\prime}):k<k^{\prime}\in[K]\\}$
denote the set of all possible index pairs out of integers 1 through $K,$ the
number of clusters outputted by $K$-means clustering. We consider the null
hypothesis that states

$\displaystyle
H_{0,\,\mathcal{V}}:\,\bar{\mu}_{\,\mathcal{C}_{k}}=\bar{\mu}_{\,\mathcal{C}_{k^{\prime}}}\
\text{ for all }\,(k,k^{\prime})\in\mathcal{V},$ (3)

where $\mathcal{V}\subseteq\mathcal{V}_{\mathrm{all}}$ is defined as the set
of index pairs corresponding to the pairs of clusters to test for. Note that
if $\mathcal{V}=\mathcal{V}_{\mathrm{all}},$ then the null hypothesis states
that the cluster centers of all $K$ clusters have equal means, i.e.,
$H_{0,\mathcal{V}}:\bar{\mu}_{\mathcal{C}_{1}}=\cdots=\bar{\mu}_{\mathcal{C}_{K}}.$

The set $\mathcal{V}$ can be any subset of $\mathcal{V}_{\mathrm{all}},$ and
the way in which it is chosen determines the corresponding inference
procedure.

  * •

If $\mathcal{V}$ is chosen from $\mathcal{V}_{\mathrm{all}}$ independently of
the data, then the data-dependence in the null hypothesis exists only through
the clustering procedure. In this setting, note that if $\mathcal{V}$ contains
a single index pair $(k,k^{\prime})$, then the null hypothesis in (3) reduces
to the null hypothesis in (2) that tests for the pair of clusters
$\mathcal{C}_{k}$ and $\mathcal{C}_{k^{\prime}}.$

  * •

If the choice of $\mathcal{V}$ is data-dependent, then it introduces an
additional selection event, which may lead to a lack of Type I error control
if not accounted for. An example of such a data-dependent choice includes the
selection of the pair of clusters that are the closest to each other among all
pairs.

Our contributions include the following:

  * •

when the noise level $\sigma$ in (1) is known, we provide a selective
inference procedure for testing the null hypothesis in (3) for pre-specified
$\mathcal{V},$ along with methods that address certain data-dependent choices
of $\mathcal{V}$, and

  * •

we develop analogous procedures for the case where $\sigma$ is unknown.

For each of the tests that we propose, we provide a p-value that can be
computed exactly.

An immediate test for the null hypothesis in (3) would be to combine the
pairwise test of Chen and Witten (2023) with a correction for multiple
comparisons. One such method for multiplicity adjustment is the Bonferroni
correction, which is applicable to many settings due to the lack of
distributional assumptions it makes, especially in this setting where the
selective p-values may have complicated dependence structures; further
discussion on the use of the Bonferroni correction in the context of testing
for the null hypothesis in (3) can be found in Section 3.1. Our method differs
from this testing procedure in that it is based on a single test statistic
that combines signals across all pairs of clusters of interest. With both
being valid tests that control the Type I error, it would be interesting to
compare how the two methods perform in terms of power—we provide a simulation
study in Section 6.1.1 that explores their empirical powers in different
settings.

The rest of the paper is organized as follows. In Section 2, we review the
pairwise test of Chen and Witten (2023). In Sections 3 and 4, we discuss the
proposed tests for the null hypothesis in (3), for the cases where the set
$\mathcal{V}$ is pre-specified and chosen in a data-dependent way,
respectively. In Section 5, we propose analogous tests for the case of unknown
$\sigma.$ Section 6 presents a simulation study on the Type I error control
and empirical powers of the proposed tests, followed by an application to a
real data in Section 7. All of the proofs can be found in the Appendix, and
the codes for reproducing the empirical results are available at
https://github.com/yjyun97/cluster_inf_multiple.

Throughout the paper, we let $\|A\|_{F}$ denote the Frobenius norm of a matrix
$A$, and let $\|\mathbf{a}\|_{2}$ denote the $\ell_{2}$-norm of a vector
$\mathbf{a}$. For $r>0,$ we let $\chi_{r}$ denote the distribution of a random
variable $\sqrt{Y}$ where $Y\sim\chi_{r}^{2},$ the chi-squared distribution
with $r$ degrees of freedom. For a null hypothesis $H_{0}$ and an event
$\mathcal{A},$ $\mathbb{P}_{H_{0}}(\mathcal{A})$ denotes the probability of
the event under $H_{0}$.  In the case where a null hypothesis $H_{0}(f(X))$
depends on $f(X)$ for some function $f$ and random variable $X,$
$\mathbb{P}_{H_{0}(f(X))}(\mathcal{A}\mid f(X))$ denotes the conditional
probability of an event $\mathcal{A}$ given $f(X)$ under $H_{0}(f(X))$—this
notation appears in the statements of the theorems throughout this paper,
which follow the style of those in Yun and Barber (2023). For a set
$\mathcal{A}\subset\\{1,...,m\\}$ for some $m\in\mathbbm{N},$ we let
$\mathbf{1}_{\mathcal{A}}\in\mathbb{R}^{m}$ denote a vector whose $i$th entry
is 1 if $i\in\mathcal{A}$ and $0$ otherwise; likewise, $I_{\mathcal{A}}$
denotes a diagonal matrix whose $i$th diagonal entry is 1 if $i\in\mathcal{A}$
and 0 otherwise. For any $m\in\mathbb{N},$ $I_{m}$ and $\mathbf{1}_{m}$ denote
an identity matrix in $\mathbb{R}^{m\times m}$ and a vector of 1s in
$\mathbb{R}^{m},$ respectively, and for $m,n\in\mathbb{N},$ $0_{m\times n}$
denotes a matrix of 0s and $0_{m}$ a vector of 0s. For a set $\mathcal{A},$
$|\mathcal{A}|$ denotes its cardinality, and for a matrix $A,$ $A_{i}$ denotes
its $i$th row and $A^{j}$ its jth column. Finally, given a positive integer
$m$, we define $[m]=\\{1,\ldots,m\\}$.

##  2 Pairwise test of Chen and Witten (2023)

We first review the method of Chen and Witten (2023) for testing the null
hypothesis in (2), where $K$-means clustering is used for generating the
cluster assignments. Let $X=[X_{1}\cdots X_{n}]^{\top}\in\mathbb{R}^{n\times
q}$ denote the matrix consisting of the $n$ observations and
$\bar{X}_{\mathcal{C}_{k}}\coloneqq\sum_{i\in\mathcal{C}_{k}}X_{i}/|\mathcal{C}_{k}|$
the cluster center of the $k$th cluster. Further define
$\mathbf{v}_{k,k^{\prime}}\coloneqq\frac{1}{|\mathcal{C}_{k}|}\mathbf{1}_{\mathcal{C}_{k}}-\frac{1}{|\mathcal{C}_{k^{\prime}}|}\mathbf{1}_{\mathcal{C}_{k^{\prime}}}$
and
$P_{\mathbf{v}_{k,k^{\prime}}}:=\frac{\mathbf{v}_{k,k^{\prime}}\mathbf{v}_{k,k^{\prime}}^{\top}}{\|\mathbf{v}_{k,k^{\prime}}\|_{2}^{2}},$
which denotes the projection matrix that projects onto the span of
$\mathbf{v}_{k,k^{\prime}}.$ Chen and Witten (2023) propose the test statistic

$\displaystyle
T_{\sigma,k,k^{\prime}}\coloneqq\left\|\bar{X}_{\mathcal{C}_{k}}-\bar{X}_{\mathcal{C}_{k^{\prime}}}\right\|_{2}/\|\mathbf{v}_{k,k^{\prime}}\|_{2}\sigma=\|P_{\mathbf{v}_{k,k^{\prime}}}X\|_{F}/\sigma,$
(4)

which is the scaled distance between the cluster centers of the $k$th and
$k^{\prime}$th clusters.

To account for the selection event, they condition on the clustering
outcome—henceforth, let $\mathcal{C}(A)$ denote the outcome of $K$-means
clustering run on the rows of a matrix $A\in\mathbb{R}^{n\times q},$ where the
outcome refers to the cluster assignments generated in every iteration of the
algorithm. They further condition on components of $X$ that are independent of
$T_{\sigma,k,k^{\prime}}$ in order to derive a p-value that can be computed.
They thus provide the selective p-value
$p_{\sigma,k,k^{\prime}}=1-Q_{\sigma,k,k^{\prime}}(T_{\sigma,k,k^{\prime}}),$
where $Q_{\sigma,k,k^{\prime}}$ is the conditional CDF (cumulative
distribution function) of $T_{\sigma,k,k^{\prime}}$ given

$\displaystyle\mathcal{C}(X)\hskip 10.00002pt\text{and}\hskip
10.00002ptZ_{k,k^{\prime}}\coloneqq\left(\frac{P_{\mathbf{v}_{k,k^{\prime}}}X}{\|P_{\mathbf{v}_{k,k^{\prime}}}X\|_{F}},\
\ P_{\mathbf{v}_{k,k^{\prime}}}^{\perp}X\right),$

where
$P_{\mathbf{v}_{k,k^{\prime}}}^{\perp}:=I_{n}-P_{\mathbf{v}_{k,k^{\prime}}}.$
They show that the p-value $p_{\sigma,k,k^{\prime}},$ conditioned on
$\mathcal{C}(X),$ is uniformly distributed under the null hypothesis in (2);
specifically, they derive that the distribution function
$Q_{\sigma,k,k^{\prime}}$ equals
$F_{\chi_{q}}(\cdot;\mathcal{S}_{\sigma,k,k^{\prime}}),$ which represents the
CDF of the $\chi_{q}$ distribution truncated to the set

$\displaystyle\mathcal{S}_{\sigma,k,k^{\prime}}\coloneqq\\{\psi\geq
0:\mathcal{C}(X)=\mathcal{C}(x_{\sigma,k,k^{\prime}}(\psi))\\},$

where $x_{\sigma,k,k^{\prime}}:[0,\infty)\rightarrow\mathbb{R}^{n\times q},$

$\displaystyle x_{\sigma,k,k^{\prime}}(\psi)=\psi\frac{\sigma
P_{\mathbf{v}_{k,k^{\prime}}}X}{\|P_{\mathbf{v}_{k,k^{\prime}}}X\|_{F}}+P^{\perp}_{\mathbf{v}_{k,k^{\prime}}}X.$
(5)

In words, $\mathcal{S}_{\sigma,k,k^{\prime}}$ is the set of realizations of
the test statistic for which the $K$-means algorithm yields identical outcomes
in every step of the algorithm to those of the algorithm run on $X.$

Chen and Witten (2023) derive an explicit characterization of the truncation
set $\mathcal{S}_{\sigma,k,k^{\prime}}$ for the clusters produced by the
$K$-means algorithm, specifically the standard Lloyd’s algorithm (Lloyd
(1982)). Details of the algorithm can be found in Chen and Witten (2023,
Section 2.1).

To present Chen and Witten (2023)’s characterization of
$\mathcal{S}_{\sigma,k,k^{\prime}},$ we first define relevant notations that
have been modified from those of Chen and Witten (2023). Suppose that
$K$-means clustering is applied to the rows of $A\in\mathbb{R}^{n\times q}$
for $J$ iterations. We let $m_{l}^{(0)}(A)$ denote the $l$th cluster center
determined at the initialization step of the $K$-means algorithm, and for each
$j\in\\{0\\}\cup[J]$, where $j=0$ represents the initialization step, we let
$c_{i}^{(j)}(A)\in[K]$ denote the cluster assignment of the $i$th row of $A$
at $j$th step of the algorithm. Further define

$\displaystyle\hskip
10.00002ptw_{l,s}^{(j-1)}=\frac{\mathbf{1}\left\\{c_{s}^{(j-1)}(X)=l\right\\}}{\sum_{i=1}^{n}\mathbf{1}\left\\{c_{i}^{(j-1)}(X)=l\right\\}}\hskip
10.00002pt\text{and}\hskip
10.00002ptM^{(j-1)}_{l}(A)=\sum_{s=1}^{n}w_{l,s}^{(j-1)}A_{s}$

for $l\in[K]$ and $j\in[J],$ where $M_{l}^{(j-1)}(A)$ represents the average
of the rows of $A$ in the $l$th cluster, where the clusters are defined by the
output of the $j-1$th iteration of $K$-means clustering run on $X.$ For each
$i\in[n],$ $l\in[K],$ and $j\in\\{0\\}\cup[J],$ define the function
$\mathcal{S}_{i,l,j}:\mathcal{F}([0,\infty),\mathbb{R}^{n\times
q})\rightarrow\mathcal{P}([0,\infty)),$ where
$\mathcal{F}([0,\infty),\mathbb{R}^{n\times q})$ and $\mathcal{P}([0,\infty))$
denote the set of functions from $[0,\infty)$ to $\mathbb{R}^{n\times q}$ and
the power set of $[0,\infty),$ respectively,

$\displaystyle\mathcal{S}_{i,l,j}(y)=\begin{cases}\\{\psi\geq
0:\,\|[y(\psi)]_{i}-m^{(0)}_{c_{i}^{(0)}(X)}(y(\psi))\|^{2}_{2}\leq\|[y(\psi)]_{i}-m^{(0)}_{l}(y(\psi))\|^{2}_{2}\\}&\text{
if }j=0\\\\[15.0pt] \\{\psi\geq
0:\,\|[y(\psi)]_{i}-M^{(j-1)}_{c_{i}^{(j)}(X)}(y(\psi))\|^{2}_{2}\leq\|[y(\psi)]_{i}-M^{(j-1)}_{l}(y(\psi))\|^{2}_{2}\\}&\text{
if }j\in[J].\end{cases}$

Here, and throughout the rest of the paper, $[A]_{i}$ for a matrix $A$ and
$i\in[n]$ is used interchangeably with $A_{i}$ for the clarity of notations.
Chen and Witten (2023) show that

$\displaystyle\mathcal{S}_{\sigma,k,k^{\prime}}=\bigcap_{j=0}^{J}\bigcap_{l=1}^{K}\bigcap_{i=1}^{n}\mathcal{S}_{i,l,j}(x_{\sigma,k,k^{\prime}}).$
(6)

The authors further show that each
$\mathcal{S}_{i,l,j}(x_{\sigma,k,k^{\prime}})$ is the set of solutions to a
quadratic inequality, and thus $\mathcal{S}_{\sigma,k,k^{\prime}}$ in (6) is
the set of solutions to a system of $nK(J+1)$ quadratic inequalities.

##  3 Proposed test for $H_{0,\mathcal{V}}$ with pre-specified $\mathcal{V}$

Building on the work of Chen and Witten (2023), we develop a test for the null
hypothesis in (3). Throughout this section, we consider the setting where
$\sigma$ is known and $\mathcal{V}$ is pre-specified.

###  3.1 Baseline testing procedure for $H_{0,\mathcal{V}}$

Before presenting the proposed method, we first discuss a baseline test for
the null hypothesis in (3) that combines the pairwise test of Chen and Witten
(2023) reviewed in Section 2 with the Bonferroni correction. We consider the
Bonferroni adjusted p-value given by
$p_{\sigma,\textnormal{Bon}}=\min_{(k,k^{\prime})\in\mathcal{V}}\\{|\mathcal{V}|\cdot
p_{\sigma,k,k^{\prime}},\ 1\\},$ which, conditioned on $\mathcal{C}(X),$
follows the super-uniform distribution. As an illustration of the test’s Type
I error control, Figure 1 presents a QQ plot of a sample of
$p_{\sigma,\mathrm{Bon}}$ generated under the null hypothesis in (3) with
$\mathcal{V}=\mathcal{V}_{\mathrm{all}},$ i.e.,
$H_{0,\mathcal{V}}:\bar{\mu}_{\mathcal{C}_{1}}=\cdots=\bar{\mu}_{\mathcal{C}_{K}},$
for $K\in\\{3,5,7\\}.$ The test, as expected, controls the Type I error, and
we see that it becomes more conservative as $K$ increases. More details on the
simulation settings of Figure 1 can be found in Section 6.1.1.

Figure 1: QQ plot of a sample of $p_{\sigma,\mathrm{Bon}}$ generated under the
null hypothesis in (3) with $\mathcal{V}=\mathcal{V}_{\mathrm{all}}.$

###  3.2 Proposed method

We now present the proposed test for the null hypothesis in (3). Define
$P_{\mathcal{E}}$ as the matrix of the orthogonal projection that projects
onto the space
$\mathcal{E}\coloneqq\mathrm{span}\\{\mathbf{v}_{k,k^{\prime}}:\
(k,k^{\prime})\in\mathcal{V}\\}.$ We propose the test statistic

$\displaystyle T_{\sigma}=\frac{\|P_{\mathcal{E}}X\|_{F}}{\sigma},$ (7)

which captures signals across all pairs of clusters of interest. Building on
the work of Gao et al. (2022) and Chen and Witten (2023), we consider the
decomposition of $X,$

$\displaystyle X=T_{\sigma}\cdot\frac{\sigma
P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}}+P_{\mathcal{E}}^{\perp}X,$

where $P_{\mathcal{E}}^{\perp}:=I_{n}-P_{\mathcal{E}}.$ With this
decomposition in mind, we define the p-value as
$p_{\sigma}=1-Q_{\sigma}(T_{\sigma}),$ where $Q_{\sigma}$ is the conditional
CDF of $T_{\sigma}$ given

$\displaystyle\mathcal{C}(X)\hskip 10.00002pt\text{and}\hskip
10.00002ptZ\coloneqq\left(\frac{P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}},\
\ P_{\mathcal{E}}^{\perp}X\right).$ (8)

Theorem 1 provides an explicit form of the distribution function $Q_{\sigma}.$

######  Theorem 1.

Under the null hypothesis $H_{0,\mathcal{V}}$ in (3),

$\displaystyle
Q_{\sigma}=F_{\chi_{d}}\\!\left(\cdot;\,\mathcal{S}_{\sigma}\right),$

where $d=q\cdot\mathrm{dim}(\mathcal{E})$, and
$F_{\chi_{d}}(\cdot;\,\mathcal{S}_{\sigma})$ represents the CDF of the
$\chi_{d}$ distribution truncated to the set

$\displaystyle\mathcal{S}_{\sigma}\coloneqq\\{\psi\geq
0:\mathcal{C}(X)=\mathcal{C}(x_{\sigma}(\psi))\\},$

where $x_{\sigma}:[0,\infty)\rightarrow\mathbb{R}^{n\times q},$

$\displaystyle x_{\sigma}(\psi)=\psi\,\cdot\,\frac{\sigma
P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}}+P_{\mathcal{E}}^{\perp}X.$

Furthermore,
$\mathbb{P}_{H_{0,\mathcal{V}}}(p_{\sigma}\leq\alpha\mid\mathcal{C}(X))=\alpha.$

It remains to characterize the selection event $\mathcal{S}_{\sigma}$ in
Theorem 1. It follows from the characterization of $S_{\sigma,k,k^{\prime}}$
of Chen and Witten (2023) discussed in Section 2 that

$\displaystyle\mathcal{S}_{\sigma}=\bigcap_{j=0}^{J}\bigcap_{l=1}^{K}\bigcap_{i=1}^{n}\mathcal{S}_{i,l,j}(x_{\sigma}).$
(9)

By the definitions of the functions $\mathcal{S}_{i,l,j}$ for
$i\in[n],l\in[K],$ and $j\in\\{0\\}\cup[J]$ given above (6), each
$\mathcal{S}_{i,l,j}(x_{\sigma})$ is characterized by inequalities of the form

$\displaystyle\|{[x_{\sigma}(\psi)]_{i}-[x_{\sigma}(\psi)]_{i^{\prime}}}\|^{2}_{2}\leq\|{[x_{\sigma}(\psi)]_{i}-[x_{\sigma}(\psi)]_{i^{{}^{\prime\prime}}}}\|^{2}_{2}$
(10)

if $j=0$ and those of the form

$\displaystyle\|[x_{\sigma}(\psi)]_{i}-M_{l}^{(j-1)}(x_{\sigma}(\psi))\|_{2}^{2}\leq\|[x_{\sigma}(\psi)]_{i}-M_{l^{\prime}}^{(j-1)}(x_{\sigma}(\psi))\|_{2}^{2}$
(11)

if $j\in[J],$ where $i^{\prime},i^{\prime\prime}\in[n]$ and
$l^{\prime}\in[K].$ Proposition 2 below, analogous to Gao et al. (2022, Lemma
2) and Chen and Witten (2023, Lemma 2), states that these inequalities can be
written as quadratic inequalities in $\psi.$

######  Proposition 2.

Let $D=\sigma{P_{\mathcal{E}}X}/{\|P_{\mathcal{E}}X\|_{F}}$ and
$E=P_{\mathcal{E}}^{\perp}X.$ For all $i,i^{\prime}\in[n],$ $l\in[K],$ and
$j\in[J],$

$\displaystyle\left\lVert[x_{\sigma}(\psi)]_{i}-[x_{\sigma}(\psi)]_{i^{\prime}}\right\rVert_{2}^{2}=$
$\displaystyle~{}\lambda_{ii^{\prime},1}\psi^{2}+\lambda_{ii^{\prime},2}\psi+\lambda_{ii^{\prime},3}\text{
and}$
$\displaystyle\left\lVert[x_{\sigma}(\psi)]_{i}-M_{l}^{(j-1)}(x_{\sigma}(\psi))\right\rVert_{2}^{2}=$
$\displaystyle~{}\lambda_{ilj,1}\psi^{2}+\lambda_{ilj,2}\psi+\lambda_{ilj,3},$

with coefficients

$\displaystyle\lambda_{ii^{\prime},1}$
$\displaystyle=\|\mathbf{d}_{ii^{\prime}}\|_{2}^{2},$
$\displaystyle\lambda_{ii^{\prime},2}$
$\displaystyle=2\langle{\mathbf{d}_{ii^{\prime}},\mathbf{e}_{ii^{\prime}}}\rangle,$
$\displaystyle\lambda_{ii^{\prime},3}$
$\displaystyle=\|\mathbf{e}_{ii^{\prime}}\|_{2}^{2},$
$\displaystyle\lambda_{ilj,1}$ $\displaystyle=\|\mathbf{d}_{ilj}\|_{2}^{2},$
$\displaystyle\lambda_{ilj,2}$
$\displaystyle=2\langle{\mathbf{d}_{ilj},\mathbf{e}_{ilj}}\rangle,$
$\displaystyle\lambda_{ilj,3}$ $\displaystyle=\|\mathbf{e}_{ilj}\|_{2}^{2},$

where $\mathbf{d}_{ii^{\prime}}=D_{i}-D_{i^{\prime}},$
$\mathbf{e}_{ii^{\prime}}=E_{i}-E_{i^{\prime}},$
$\mathbf{d}_{ilj}=D_{i}-M_{l}^{(j-1)}(D),$ and
$\mathbf{e}_{ilj}=E_{i}-M_{l}^{(j-1)}(E).$

It then follows from Theorem 1 and Proposition 2 that $p_{\sigma}$ can be
computed exactly.

######  Remark 1.

The null hypothesis $H_{0,\mathcal{V}}$ reduces to the null hypothesis
$H_{0,\\{k,k^{\prime}\\}}$ if $\mathcal{V}=\\{(k,k^{\prime})\\}.$ In this
setting, $p_{\sigma},$ $T_{\sigma},$ and $S_{\sigma}$ reduce to
$p_{\sigma,k,k^{\prime}},$ $T_{\sigma,k,k^{\prime}},$ and
$S_{\sigma,k,k^{\prime}},$ respectively, and thus the proposed test
generalizes the pairwise test of Chen and Witten (2023).

######  Remark 2.

Different choices of $\mathcal{V}$ can lead to equivalent statements of the
null hypothesis $H_{0,\mathcal{V}}.$ For example, two different choices
$\mathcal{V}_{1}$ and $\mathcal{V}_{2}$ lead to the same statement of
$H_{0,\mathcal{V}}$ if the spans of $\\{\mathbf{v}_{k,k^{\prime}}:\
(k,k^{\prime})\in\mathcal{V}_{1}\\}$ and $\\{\mathbf{v}_{k,k^{\prime}}:\
(k,k^{\prime})\in\mathcal{V}_{2}\\}$ are equal. Under this condition, the
proposed test remains the same since $T_{\sigma}$ is invariant to different
specifications of $\mathcal{V}$ that correspond to the same set $\mathcal{E}.$
The baseline testing procedure discussed in Section 3.1, however, differs
since different choices of $\mathcal{V}$ lead to different tests. The reason
is that $p_{\sigma,\textnormal{Bon}}$ depends on both the cardinality of
$\mathcal{V}$ and the specific pairs of clusters chosen for the pairwise test
of Chen and Witten (2023)—Section 6.1.1 presents a comparison of empirical
power of the baseline testing procedure for different specifications of
$\mathcal{V}$ associated with the same set $\mathcal{E}.$

##  4 Proposed test for $H_{0,\mathcal{V}}$ with data-dependent choice of
$\mathcal{V}$

In many applications, researchers may use the clustering outcomes to choose
the pairs of clusters to test for. For instance, one may choose the index pair
$(k,k^{\prime})$ that corresponds to the two clusters whose cluster centers
are the farthest (or the closest) from each other (or to each other) and then
test for the null hypothesis in (3) with $\mathcal{V}=\\{(k,k^{\prime})\\}$ to
decide if the clusters $\mathcal{C}_{k}$ and $\mathcal{C}_{k^{\prime}}$ indeed
stem from underlying differences. In such cases,
$\mathcal{V}\subset\mathcal{V}_{\mathrm{all}}$ is chosen in a data-dependent
way, and the way in which it is chosen defines the additional selection event.
Depending on how $\mathcal{V}$ is chosen, not accounting for the selection
event may lead to a lack of Type I error control. The left-hand plot of Figure
2 presents a QQ plot of a sample of $p_{\sigma}$ generated under the null
hypothesis in (3) with $\mathcal{V}=\\{(k,k^{\prime})\\}$ that corresponds to
the pair of clusters that are the farthest apart among the $K=20$ clusters. It
illustrates that the distribution of $p_{\sigma}$ deviates from the uniform
distribution, in such a way that the test based on $p_{\sigma}$ fails to
control the Type I error. However, not accounting for the data-dependence in
the selection of $\mathcal{V}$ may not always lead to a lack of Type I error
control, as we see in the right-hand plot of Figure 2, whose settings are
analogous to those of the left-hand plot except that the pair of clusters that
are the closest to each other is chosen. More discussion on this phenomenon
can be found in Remark 3, and additional details on the simulation settings of
Figure 2 can be found in Section 6.1.2.

Figure 2: QQ plots of samples of $p_{\sigma}$ generated under the null
hypothesis in (3) with two different data-dependent choices of $\mathcal{V}.$

In this section, we propose a test for the null hypothesis in (3) where
$\mathcal{V}$ is chosen in a data-dependent way, for specific forms of data
dependence. We adapt the test presented in Section 3.2 to additionally account
for the data-dependence in the choice of $\mathcal{V}.$ Henceforth, let
$\mathcal{V}(A)$ for a matrix $A\in\mathbb{R}^{n\times q}$ denote the outcome
of the procedure that selects the set $\mathcal{V}$ based on $A.$ We consider
the same test statistic $T_{\sigma}$ and define the p-value as
$p_{\sigma,J}=1-Q_{\sigma,J}(T_{\sigma})$, where $Q_{\sigma,J}$ is the
conditional CDF of $T_{\sigma}$ given

$\displaystyle\mathcal{C}(X),\hskip 10.00002pt\mathcal{V}(X),\hskip
10.00002pt\text{and}\hskip 10.00002ptZ,$

where $Z$ is as defined in (8). Theorem 3 below, analogous to Theorem 1,
provides an explicit form of the distribution function $Q_{\sigma,J}.$

######  Theorem 3.

Under the null hypothesis $H_{0,\mathcal{V}}$ in (3),

$\displaystyle
Q_{\sigma,J}=F_{\chi_{d}}\\!\left(\cdot;\,\mathcal{S}_{\sigma,J}\right),$

where $d$ is as defined in Section 3.2, and
$F_{\chi_{d}}(\cdot;\,\mathcal{S}_{\sigma,J})$ represents the CDF of the
$\chi_{d}$ distribution truncated to the set
$\mathcal{S}_{\sigma,J}=\mathcal{S}_{\sigma}\cap\mathcal{S}_{\sigma,\mathcal{V}},$
where

$\displaystyle\mathcal{S}_{\sigma,\mathcal{V}}\coloneqq\\{\psi\geq
0:\,\mathcal{V}(X)=\mathcal{V}(x_{\sigma}(\psi))\\}.$

Furthermore,
$\mathbb{P}_{H_{0,\mathcal{V}}}(p_{\sigma,J}\leq\alpha\mid\mathcal{C}(X),\mathcal{V}(X))=\alpha.$

The characterization of the set $\mathcal{S}_{\sigma,\mathcal{V}}$ depends on
the way in which $\mathcal{V}$ is chosen. We consider three settings where the
choice of $\mathcal{V}$ depends on the data $X$ only through the $\ell_{2}$
distances between cluster centers, after the data has been divided into $K$
clusters. We show that $\mathcal{S}_{\sigma,\mathcal{V}}$ in each of the
settings can be written as a set of solutions to a system of inequalities.

######  Setting 1.

Let $t_{g}$ denote the $g$-th largest among all between-cluster distances
$\|\bar{X}_{\mathcal{C}_{k}}-\bar{X}_{\mathcal{C}_{k^{\prime}}}\|=\|X^{\top}\mathbf{v}_{k,k^{\prime}}\|_{2}$
for $(k,k^{\prime})\in\mathcal{V}_{\mathrm{all}},$ where $g$ is pre-specified.
If we choose the pairs of clusters whose corresponding distances are among the
$g$-th largest, then
$\mathcal{V}=\\{(k,k^{\prime})\in\mathcal{V}_{\mathrm{all}}:\,\|X^{\top}\mathbf{v}_{k,k^{\prime}}\|_{2}\geqslant
t_{g}\\}.$ The corresponding truncation set takes the form

$\displaystyle\mathcal{S}_{\sigma,\mathcal{V}}=\bigcap_{\mathbf{v}\in\mathcal{V}}\bigcap_{\mathbf{v}^{\prime}\in\mathcal{V}_{\mathrm{all}}\backslash\mathcal{V}}\left\\{\psi\geqslant
0:\,\big{\|}[x_{\sigma}(\psi)]^{\top}\mathbf{v}\big{\|}_{2}^{2}>\big{\|}[x_{\sigma}(\psi)]^{\top}\mathbf{v}^{\prime}\big{\|}_{2}^{2}\right\\},$

where $\mathcal{V}_{\mathrm{all}}\backslash\mathcal{V}$ represents the
relative complement of $\mathcal{V}$ with respect to
$\mathcal{V}_{\mathrm{all}}$. If $g=1,$ $\mathcal{V}$ consists of a single
index pair corresponding to the pair of clusters whose cluster centers are the
farthest apart among all pairs of clusters, which coincides with the setting
of the left-hand plot of Figure 2.

######  Setting 2.

Let $t_{g}$ be the $g$-th smallest among all between-cluster distances
$\|X^{\top}\mathbf{v}_{k,k^{\prime}}\|_{2}$ for
$(k,k^{\prime})\in\mathcal{V}_{\mathrm{all}},$ where $g$ is pre-specified. If
we choose the pairs of clusters whose corresponding distances are among the
$g$-th smallest, then
$\mathcal{V}=\\{(k,k^{\prime})\in\mathcal{V}_{\mathrm{all}}:\,\|X^{\top}\mathbf{v}_{k,k^{\prime}}\|_{2}\leqslant
t_{g}\\}.$ The corresponding truncation set takes the form

$\displaystyle\mathcal{S}_{\sigma,\mathcal{V}}=\bigcap_{\mathbf{v}\in\mathcal{V}_{\mathrm{all}}}\bigcap_{\mathbf{v}^{\prime}\in\mathcal{V}_{\mathrm{all}}\backslash\mathcal{V}}\left\\{\psi\geqslant
0:\,\big{\|}[x_{\sigma}(\psi)]^{\top}\mathbf{v}\big{\|}_{2}^{2}<\big{\|}[x_{\sigma}(\psi)]^{\top}\mathbf{v}^{\prime}\big{\|}_{2}^{2}\right\\}.$

If $g=1$, $\mathcal{V}$ consists of a single index pair corresponding to the
pair of clusters whose cluster centers are the closest to each other among all
pairs of clusters, which coincides with the setting of the right-hand plot of
Figure 2.

######  Setting 3.

Suppose $t_{g}>0$ is a pre-specified threshold. If we choose the pairs of
clusters where the distances between the cluster centers are no larger than
$t_{g},$ then
$\mathcal{V}=\\{(k,k^{\prime})\in\mathcal{V}_{\mathrm{all}}:\,\|X^{\top}\mathbf{v}_{k,k^{\prime}}\|_{2}\leqslant
t_{g}\\}.$ The corresponding truncation set takes the form

$\displaystyle\mathcal{S}_{\sigma,\mathcal{V}}=\bigcap_{\mathbf{v}\in\mathcal{V}}\left\\{\psi\geqslant
0:\,\big{\|}[x_{\sigma}(\psi)]^{\top}\mathbf{v}\big{\|}_{2}^{2}\leqslant
t_{g}\right\\}~{}\bigcap~{}\bigcap_{\mathbf{v}^{\prime}\in\mathcal{V}_{\mathrm{all}}\backslash\mathcal{V}}\left\\{\psi\geqslant
0:\,\big{\|}[x_{\sigma}(\psi)]^{\top}\mathbf{v}^{\prime}\big{\|}_{2}^{2}>t_{g}\right\\}.$

Similarly, if
$\mathcal{V}=\\{(k,k^{\prime})\in\mathcal{V}:\,\|X^{\top}\mathbf{v}_{k,k^{\prime}}\|_{2}\geqslant
t_{g}\\},$ then $\mathcal{S}_{\sigma,\mathcal{V}}$ takes a similar form, but
with the direction of the inequalities reversed.

Note that the set $\mathcal{S}_{\sigma,\mathcal{V}}$ is defined by quantities
of the form $\|[x_{\sigma}(\psi)]^{\top}\mathbf{v}_{k,k^{\prime}}\|^{2}$ in
each of the settings above. Proposition 4 shows that
$\|[x_{\sigma}(\psi)]^{\top}\mathbf{v}\|^{2}_{2}$ for any vector
${\mathbf{v}\in\mathbb{R}^{n}}$ can be written as a quadratic expression in
$\psi.$

######  Proposition 4.

Let $D=\sigma{P_{\mathcal{E}}X}/{\|P_{\mathcal{E}}X\|_{F}}$ and
$E=P_{\mathcal{E}}^{\perp}X.$ For any vector $\mathbf{v}\in\mathbb{R}^{n}$,

$\|[x_{\sigma}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}=\lambda_{{\mathbf{v}},1}\psi^{2}+\lambda_{{\mathbf{v}},2}\psi+\lambda_{{\mathbf{v}},3},$

with coefficients

$\displaystyle\lambda_{{\mathbf{v}},1}$
$\displaystyle=\|\mathbf{d}_{\mathbf{v}}\|_{2}^{2},$
$\displaystyle\lambda_{{\mathbf{v}},2}$
$\displaystyle=2\langle\mathbf{d}_{\mathbf{v}},\mathbf{e}_{\mathbf{v}}\rangle,$
$\displaystyle\lambda_{{\mathbf{v}},3}$
$\displaystyle=\|\mathbf{e}_{\mathbf{v}}\|_{2}^{2},$

where $\mathbf{d}_{\mathbf{v}}=D^{\top}\mathbf{v}$ and
$\mathbf{e}_{\mathbf{v}}=E^{\top}\mathbf{v}.$

Thus, $\mathcal{S}_{\sigma,\mathcal{V}}$ in each of the three settings is a
set of solutions to a system of quadratic inequalities, as is the case for
$\mathcal{S}_{\sigma}$. It follows that $p_{\sigma,J}$ can be computed exactly
by Theorem 3 and Proposition 4.

######  Remark 3.

We see in the right-hand plot of Figure 2 that the test based on $p_{\sigma},$
which does not account for the data-dependence in the choice of $\mathcal{V},$
still controls the Type I error under Setting 2. Intuitively,
$H_{0,\mathcal{V}}$ is more likely to happen under the selection event of
Setting 2, so, in this setting, it may be natural to expect the test based on
$p_{\sigma}$ to be more conservative than the test based on $p_{\sigma,J}.$ It
could then be of interest to ask if the latter has any advantage over the
former—in Section 6.1.2, we compare the empirical powers of the two tests to
address this question, and we observe that the test based on $p_{\sigma,J}$
leads to a higher empirical power. Another example of such a phenomenon in a
different context is discussed in Saha et al. (2024).

##  5 Unknown variance

In practice, the noise level $\sigma$ in (1) is often unknown. In Section 5.1,
we give a review of existing methods that test for a pair of clusters under
this setting. Then, in Section 5.2, we present our proposed test that
considers multiple pairs of clusters.

###  5.1 Existing methods

We start by discussing two existing approaches for testing for a pair of
clusters $C_{k}$ and $C_{k^{\prime}},$ which are assumed to be chosen
independently of the data.

####  5.1.1 Variance estimators of Gao et al. (2022) and Chen and Witten
(2023)

Gao et al. (2022) and Chen and Witten (2023) provide tests for the null
hypothesis in (2) that are based on plug-in estimators for $\sigma.$ They show
that if the estimators satisfy certain properties, then the tests control the
Type I error asymptotically in one of the two dimensions. Gao et al. (2022)
provide the estimator

$\displaystyle\hat{\sigma}^{2}_{\textnormal{sample}}=\frac{1}{(n-1)q}\sum_{i=1}^{n}\left\lVert
X_{i}-\bar{X}\right\rVert^{2}_{2},\hskip 15.00002pt\text{where}\hskip
15.00002pt\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i},$ (12)

which, as they show, asymptotically over-estimates $\sigma$ under certain
conditions. Chen and Witten (2023) provide the median-based estimator

$\displaystyle\hat{\sigma}^{2}_{\textnormal{med}}=\frac{1}{\textnormal{Median}(\chi_{1}^{2})}\cdot\mathrm{Median}\left(\\{(X_{ij}-\textnormal{Median}(\\{X_{sj}\\}_{s\in[n]}))^{2}\\}_{i\in[n],j\in[q]}\right),$
(13)

where $\textnormal{Median}(\cdot)$ represents the median of a distribution or
the median of a set of values depending on the input, and show that a closely
related estimator to that of (13) is consistent in one of the two dimensions
under certain conditions. In terms of the performance of the two estimators,
Chen and Witten (2023) numerically illustrate that their proposed test
achieves a higher empirical power when applied with
$\hat{\sigma}_{\textnormal{med}}.$

In Section 6.2.1, we show empirically that the proposed test of Section 3.2
controls the Type I error when applied with each of the two estimators.

####  5.1.2 Pairwise test of Yun and Barber (2023)

Alternatively, Yun and Barber (2023) propose a selective inference procedure
that avoids the use of a plug-in estimator. They consider a stronger null
hypothesis that states

$\displaystyle H_{0,\\{k,k^{\prime}\\}}^{*}:\
\mu_{i}=\mu_{i^{\prime}}\quad\text{for all
}i,i^{\prime}\in\mathcal{C}_{k}\cup\mathcal{C}_{k^{\prime}},$ (14)

where $k\neq k^{\prime}\in[K]$ are pre-specified. The null hypothesis assumes
that the means of all of the observations in the clusters $\mathcal{C}_{k}$
and $\mathcal{C}_{k^{\prime}}$ are equal, thereby allowing for the derivation
of a test statistic whose distribution is known under the null hypothesis;
more discussion on the motivation behind the stronger null hypothesis can be
found in Yun and Barber (2023, Section 3). They propose the test statistic

$\displaystyle
T_{k,k^{\prime}}^{*}=\frac{\|P_{\mathbf{v}_{k,k^{\prime}}}X\|^{2}_{F}\,/\,q}{\|P_{1,k,k^{\prime}}X\|^{2}_{F}\,/\,d^{*}_{k,k^{\prime}}},$
(15)

where $P_{\mathbf{v}_{k,k^{\prime}}}$ is as defined in Section 3.2,
$d^{*}_{k,k^{\prime}}\coloneqq
q\cdot(|\mathcal{C}_{k}|+|\mathcal{C}_{k^{\prime}}|-2),$ and

$\displaystyle
P_{1,k,k^{\prime}}\coloneqq\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)+\left(I_{\mathcal{C}_{k^{\prime}}}-\frac{\mathbf{1}_{\mathcal{C}_{k^{\prime}}}\mathbf{1}_{\mathcal{C}_{k^{\prime}}}^{\top}}{|\mathcal{C}_{k^{\prime}}|}\right).$

They provide the selective p-value
$p^{*}_{k,k^{\prime}}=1-Q_{k,k^{\prime}}^{*}(T^{*}_{k,k^{\prime}}),$ where
$Q_{k,k^{\prime}}^{*}$ is the conditional CDF of $T_{k,k^{\prime}}^{*}$ given

$\displaystyle\mathcal{C}(X)\text{ and
}Z^{*}_{k,k^{\prime}}\coloneqq\left(\frac{P_{\mathbf{v}_{k,k^{\prime}}}X}{\|P_{\mathbf{v}_{k,k^{\prime}}}X\|_{F}},\;\frac{P_{1,k,k^{\prime}}X}{\|P_{1,k,k^{\prime}}X\|_{F}},\;\|P_{\mathbf{v}_{k,k^{\prime}}}X\|_{F}^{2}+\|P_{1,k,k^{\prime}}X\|_{F}^{2},\;P_{2,k,k^{\prime}}X\right),$

where $P_{2,k,k^{\prime}}\coloneqq
I_{n}-P_{\mathbf{v}_{k,k^{\prime}}}-P_{1,k,k^{\prime}}.$ They show that the
p-value $p_{k,k^{\prime}}^{*},$ conditioned on $\mathcal{C}(X),$ follows the
uniform distribution under $H_{0,\\{k,k^{\prime}\\}}^{*}.$ Specifically, they
derive that the distribution function $Q^{*}_{k,k^{\prime}}$ equals
$F_{F_{q,d_{k,k^{\prime}}^{*}}}(\cdot;\mathcal{S}_{k,k^{\prime}}^{*}),$ which
represents the CDF of the $F_{q,d_{k,k^{\prime}}^{*}}$ distribution truncated
to the set

$\displaystyle\mathcal{S}^{*}_{k,k^{\prime}}\coloneqq\\{\psi\geq
0:\mathcal{C}(X)=\mathcal{C}(x_{k,k^{\prime}}^{*}(\psi))\\},$

where $x^{*}_{k,k^{\prime}}:[0,\infty)\rightarrow\mathbb{R}^{n\times q},$

$x^{*}_{k,k^{\prime}}(\psi)=\sqrt{\|P_{\mathbf{v}_{k,k^{\prime}}}X\|_{F}^{2}+\|P_{1,k,k^{\prime}}X\|_{F}^{2}}\bigg{(}\sqrt{\frac{\psi}{\psi+r^{*}_{k,k^{\prime}}}}\frac{P_{\mathbf{v}_{k,k^{\prime}}}X}{\|P_{\mathbf{v}_{k,k^{\prime}}}X\|_{F}}+\\\
\sqrt{\frac{r^{*}_{k,k^{\prime}}}{\psi+r^{*}_{k,k^{\prime}}}}\frac{P_{1,k,k^{\prime}}X}{\|P_{1,k,k^{\prime}}X\|_{F}}\bigg{)}+P_{2,k,k^{\prime}}X,$

where $r^{*}_{k,k^{\prime}}=d^{*}_{k,k^{\prime}}/q.$ Yun and Barber (2023)
derive an explicit characterization of the truncation set
$\mathcal{S}^{*}_{k,k^{\prime}}$ for the case where $K=2$ clusters are
produced by a clustering algorithm that is invariant to the scale and location
of the data, which includes $K$-means clustering, and provide an importance
sampling algorithm for the case where $K>2.$

###  5.2 Proposed test for $H_{0,\mathcal{V}}^{*}$

As discussed in Section 5.1, the pairwise tests of Gao et al. (2022) and Chen
and Witten (2023) for the null hypothesis in (2) that are based on plug-in
estimators for $\sigma^{2}$ control the Type I error asymptotically. While the
pairwise test of Yun and Barber (2023) controls the Type I error in finite
samples, the computation of the associated p-value relies on a sampling
algorithm in the presence of $K>2$ clusters. In this section, we provide a
test for multiple pairs of clusters that avoid the use of estimators and
produce exact p-values, building on the works of Chen and Witten (2023) and
Yun and Barber (2023).

Following the approach of Yun and Barber (2023), we consider the null
hypothesis that states

$\displaystyle H_{0,\mathcal{V}}^{*}:\ \mu_{i}=\mu_{i^{\prime}}\ \text{for all
}i,i^{\prime}\in\mathcal{C}_{k}\cup\mathcal{C}_{k^{\prime}}\ \text{and
}(k,k^{\prime})\in\mathcal{V}.$ (16)

Note (16) is stronger than (3) in that the former assumes all of the
observations in the clusters of interest have the same mean, and it reduces to
the null hypothesis in (14) if $\mathcal{V}=\\{(k,k^{\prime})\\}.$

Let $\mathcal{K}=\\{k\in[K]:\text{ there exists }k^{\prime}\in[K]\text{ such
that }(k,k^{\prime})\in\mathcal{V}\text{ or }(k^{\prime},k)\in\mathcal{V}\\}$
denote the set of indices of all clusters of interest. Analogous to the test
statistic in (15), we propose the test statistic

$\displaystyle
T^{*}=\frac{\|P_{\mathcal{E}}X\|^{2}_{F}\,/\,d}{\|P_{1}X\|^{2}_{F}\,/\,d^{*}},$

where $d$ and $P_{\mathcal{E}}$ are as defined in Section 3.2,
$d^{*}=q(\sum_{k\in\mathcal{K}}|\mathcal{C}_{k}|-|\mathcal{K}|)$, and

$\displaystyle
P_{1}=\sum_{k\in\mathcal{K}}\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right),$

which generalizes $P_{1,k,k^{\prime}}.$ Intuitively,
$\|P_{\mathcal{E}}X\|^{2}_{F}$ and $\|P_{1}X\|^{2}_{F}$ reflect the overall
between-cluster differences and within-cluster variations, respectively, for
the clusters whose indices are in $\mathcal{K}.$ Note that the test statistic
$T^{*}$ is undefined when each of the clusters with indices in $\mathcal{K}$
consists of a single observation, which aligns with the intuition that there
is not enough information to estimate the level of within-cluster variations
in such a case. Building on the work of Yun and Barber (2023), we consider the
decomposition

$\displaystyle X=$ $\displaystyle~{}P_{\mathcal{E}}X+P_{1}X+P_{2}X$
$\displaystyle=$
$\displaystyle~{}\sqrt{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\left(\sqrt{\frac{T^{*}}{T^{*}+r^{*}}}\frac{P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}}+\sqrt{\frac{r^{*}}{T^{*}+r^{*}}}\frac{P_{1}X}{\|P_{1}X\|_{F}}\right)+P_{2}X,$
(17)

where $r^{*}=d^{*}/d$ and $P_{2}=I_{n}-P_{\mathcal{E}}-P_{1}.$ With this
decomposition in mind, we derive the selective p-value, separately for the
cases where the set $\mathcal{V}$ is pre-specified and chosen in a data-
dependent way.

####  5.2.1 Pre-specified $\mathcal{V}$

We first consider the case where $\mathcal{V}$ is pre-specified. In this
setting, we define the selective p-value as $p^{*}=1-Q^{*}(T^{*}),$ where
$Q^{*}$ denotes the conditional CDF of $T^{*}$ given

$\displaystyle\mathcal{C}(X)\hskip 10.00002pt\text{and}\hskip
10.00002ptZ^{*}:=\left(\frac{P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}},\;\frac{{P_{1}}X}{\|P_{1}X\|_{F}},\;\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2},\;P_{2}X\right).$
(18)

Theorem 5 gives an explicit form of the distribution function $Q^{*}.$

######  Theorem 5.

Under the null hypothesis $H_{0,\mathcal{V}}^{*}$ in (16),

$\displaystyle Q^{*}=1-F_{F_{d,d^{*}}}(\cdot;\mathcal{S}^{*}),$

where $F_{F_{d,d^{*}}}(\cdot;\mathcal{S}^{*})$ represents the CDF of the
$F_{d,d^{*}}$ distribution truncated to the set

$\displaystyle\mathcal{S}^{*}\coloneqq\big{\\{}\psi\geq
0:\mathcal{C}(X)=\mathcal{C}(x^{*}(\psi))\big{\\}},$

where $x^{*}:[0,\infty)\rightarrow\mathbb{R}^{n\times q},$

$\displaystyle
x^{*}(\psi)=\sqrt{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\left(\sqrt{\frac{\psi}{\psi+r^{*}}}\frac{P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}}+\sqrt{\frac{r^{*}}{\psi+r^{*}}}\frac{P_{1}X}{\|P_{1}X\|_{F}}\right)+P_{2}X.$

Furthermore,
$\mathbb{P}_{H^{*}_{0,\mathcal{V}}}(p^{*}\leq\alpha\mid\mathcal{C}(X))=\alpha.$

We next characterize the set $\mathcal{S}^{*}.$ Analogous to (6) and (9), we
have

$\displaystyle\mathcal{S}^{*}=\bigcap_{j=0}^{J}\bigcap_{l=1}^{K}\bigcap_{i=1}^{n}\mathcal{S}_{i,l,j}(x^{*}),$
(19)

where, by the definitions of the functions $\mathcal{S}_{i,l,j}$ for
$i\in[n],l\in[K],$ and $j\in\\{0\\}\cup[J]$ given above (6), each
$\mathcal{S}_{i,l,j}(x^{*})$ is defined by inequalities of the form

$\displaystyle\|{[x^{*}(\psi)]_{i}-[x^{*}(\psi)]_{i^{\prime}}}\|^{2}_{2}\leq\|{[x^{*}(\psi)]_{i}-[x^{*}(\psi)]_{i^{{}^{\prime\prime}}}}\|^{2}_{2}$
(20)

if $j=0$ and those of the form

$\displaystyle\|[x^{*}(\psi)]_{i}-M_{l}^{(j-1)}(x^{*}(\psi))\|_{2}^{2}\leq\|[x^{*}(\psi)]_{i}-M_{l^{\prime}}^{(j-1)}(x^{*}(\psi))\|_{2}^{2}$
(21)

if $j\in[J],$ where $i^{\prime},i^{\prime\prime}\in[n]$ and
$l^{\prime}\in[K].$ Therefore, to characterize $\mathcal{S}^{*}$, it suffices
to find the sets of solutions to a system of inequalities of the forms above.
Proposition 6 expresses these inequalities explicitly with respect to $\psi.$

######  Proposition 6.

Let $A={P_{\mathcal{E}}X}/{\|P_{\mathcal{E}}X\|_{F}}$,
$B=P_{1}X/\|P_{1}X\|_{F}$, and
$C=P_{2}X/\sqrt{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}.$ For all
$i,i^{\prime},i^{{}^{\prime\prime}}\in[n],$ $l,l^{\prime}\in[K],$ and
$j\in[J],$ the inequalities in (20) and (21) are equivalent to

$\displaystyle f_{ii^{\prime}}(\psi)\leqslant
f_{ii^{{}^{\prime\prime}}}(\psi)\hskip 10.00002pt\text{ and }\hskip
10.00002pt{f}_{ijl}(\psi)\leqslant{f}_{ijl^{\prime}}(\psi),$ (22)

respectively, where $f_{ii^{\prime}},f_{ijl}:[0,\infty)\rightarrow\mathbb{R},$

$\displaystyle f_{ii^{\prime}}(\psi)=$
$\displaystyle~{}\lambda_{ii^{\prime},1}\psi+\lambda_{ii^{\prime},2}\sqrt{\psi}+\lambda_{ii^{\prime},3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{ii^{\prime},4}\sqrt{\psi+r^{*}}+\lambda_{ii^{\prime},5},$
$\displaystyle f_{ijl}(\psi)=$
$\displaystyle~{}\lambda_{ijl,1}\psi+\lambda_{ijl,2}\sqrt{\psi}+\lambda_{ijl,3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{ijl,4}\sqrt{\psi+r^{*}}+\lambda_{ijl,5},$

with coefficients

$\displaystyle\lambda_{ii^{\prime},1}=$
$\displaystyle~{}\|\mathbf{a}_{ii^{\prime}}\|_{2}^{2}+\|\mathbf{c}_{ii^{\prime}}\|_{2}^{2},$
$\displaystyle\lambda_{ii^{\prime},2}=$
$\displaystyle~{}2\langle\mathbf{a}_{ii^{\prime}},\mathbf{b}_{ii^{\prime}}\rangle\sqrt{r^{*}},$
$\displaystyle\lambda_{ii^{\prime},3}=$
$\displaystyle~{}2\langle\mathbf{a}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle,$
$\displaystyle\lambda_{ii^{\prime},4}=$
$\displaystyle~{}2\langle\mathbf{b}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle\sqrt{r^{*}},$
$\displaystyle\lambda_{ii^{\prime},5}=$
$\displaystyle~{}(\|\mathbf{b}_{ii^{\prime}}\|_{2}^{2}+\|\mathbf{c}_{ii^{\prime}}\|_{2}^{2})r^{*},$
$\displaystyle{\lambda}_{ijl,1}=$
$\displaystyle~{}\|\mathbf{a}_{ijl}\|_{2}^{2}+\|\mathbf{c}_{ijl}\|_{2}^{2},$
$\displaystyle{\lambda}_{ijl,2}=$
$\displaystyle~{}2\langle\mathbf{a}_{ijl},\mathbf{b}_{ijl}\rangle\sqrt{r^{*}},$
$\displaystyle{\lambda}_{ijl,3}=$
$\displaystyle~{}2\langle\mathbf{a}_{ijl},\mathbf{c}_{ijl}\rangle,$
$\displaystyle{\lambda}_{ijl,4}=$
$\displaystyle~{}2\langle\mathbf{b}_{ijl},\mathbf{c}_{ijl}\rangle\sqrt{r^{*}},$
$\displaystyle{\lambda}_{ijl,5}=$
$\displaystyle~{}(\|\mathbf{b}_{ijl}\|_{2}^{2}+\|\mathbf{c}_{ijl}\|_{2}^{2})r^{*},$

where $\mathbf{a}_{ii^{\prime}}=A_{i}-A_{i^{\prime}}$,
$\mathbf{b}_{ii^{\prime}}=B_{i}-B_{i^{\prime}}$,
$\mathbf{c}_{ii^{\prime}}=C_{i}-C_{i^{\prime}}$,
$\mathbf{a}_{ijl}=A_{i}-M_{l}^{(j-1)}(A)$,
$\mathbf{b}_{ijl}=B_{i}-M_{l}^{(j-1)}(B)$, and
$\mathbf{c}_{ijl}=C_{i}-M_{l}^{(j-1)}(C)$.

It follows by Theorem 5 and Proposition 6 that $p^{*}$ can be computed
exactly.

######  Remark 4.

Note that for any $i,i^{\prime},i^{{}^{\prime\prime}}\in[n],$
$l,l^{\prime}\in[K],$ and $j\in[J],$
$f_{ii^{\prime}},f_{ii^{\prime\prime}},f_{ijl},$ and $f_{ijl^{\prime}}$ are
continuous functions, so $f_{ii^{\prime}}-f_{ii^{\prime\prime}}$ and
$f_{ijl}-f_{ijl^{\prime}}$ are also continuous. Thus, Proposition 6 shows that
the set of solutions to each of (20) and (21) is equivalent to the sub-level
set of a continuous function at 0, which can be found by solving for the roots
of the function and checking the signs of its values on each interval
partitioned by the roots; further details on the implementation can be found
in Appendix A.2.2.

####  5.2.2 Data-dependent choice of $\mathcal{V}$

We next consider the setting where $\mathcal{V}$ is chosen in a data-dependent
way and develop a test that is analogous to that of Section 4. In this
setting, we define the selective p-value as
$p_{J}^{*}=Q_{\mathcal{G}_{J}^{*}}^{*}(T^{*})$, where
$Q^{*}_{\mathcal{G}_{J}^{*}}$ is the conditional CDF of $T^{*}$ given

$\displaystyle\mathcal{C}(X),\hskip 10.00002pt\mathcal{V}(X),\hskip
10.00002pt\text{and}\hskip 10.00002ptZ^{*},$

where $Z^{*}$ is as defined in (18). Theorem 7 gives an explicit form of the
distribution function $Q_{J}^{*}.$

######  Theorem 7.

Under the null hypothesis $H_{0,\mathcal{V}}^{*}$ in (16),

$\displaystyle Q_{J}^{*}=F_{F_{d,d^{*}}}(\cdot;\mathcal{S}^{*}_{J}),$

where $F_{F_{d,d^{*}}}(\cdot;\mathcal{S}^{*}_{J})$ represents the CDF of the
$F_{d,d^{*}}$ distribution truncated to the set

$\mathcal{S}^{*}_{J}\coloneqq\mathcal{S}^{*}\cap\mathcal{S}_{\mathcal{V}}^{*},$

where

$\mathcal{S}_{\mathcal{V}}^{*}:=\\{\psi\geq
0:\mathcal{C}(X)=\mathcal{C}(x^{*}(\psi))\\}.$

Furthermore,
$\mathbb{P}_{H^{*}_{0,\mathcal{V}}}(p^{*}_{J}\leq\alpha\mid\mathcal{C}(X),\mathcal{V}(X))=\alpha.$

The characterization of the set $\mathcal{S}_{\mathcal{V}}^{*}$ depends on the
specific way in which $\mathcal{V}$ is chosen. We again consider Settings 1
through 3 of Section 4, with $x_{\sigma}$ replaced by $x^{*}.$ Then, the set
$\mathcal{S}_{\mathcal{V}}^{*}$ in Settings 1 and 2 is defined by inequalities
of the form

$\displaystyle\|[x^{*}(\psi)]^{\top}\mathbf{v}\|^{2}_{2}<\|[x^{*}(\psi)]^{\top}\mathbf{v}^{\prime}\|^{2}_{2},$
(23)

where $\mathbf{v},\mathbf{v}^{\prime}\in\mathbb{R}^{n},$ and
$\mathcal{S}_{\mathcal{V}}^{*}$ in Setting 3 is defined by inequalities of the
form

$\displaystyle\|[x^{*}(\psi)]^{\top}\mathbf{v}\|^{2}_{2}<t,$ (24)

where $\mathbf{v}\in\mathbb{R}^{n}$ and $t>0.$ Proposition 8 expresses these
inequalities explicitly with respect to $\psi.$

######  Proposition 8.

Let $A,$ $B,$ and $C$ be defined as in Proposition 6. For any two vectors
$\mathbf{v},\mathbf{v}^{\prime}\in\mathbb{R}^{n}$ and for any $t>0,$ the
inequalities in (23) and (24) are equivalent to

$\displaystyle h_{\mathbf{v}}(\psi)\leqslant
h_{\mathbf{v}^{\prime}}(\psi)\hskip 10.00002pt\text{ and }\hskip
10.00002pth_{\mathbf{v}}(\psi)\leqslant h(\psi),$ (25)

respectively, where $h_{\mathbf{v}},h:[0,\infty)\rightarrow\mathbb{R},$

$\displaystyle h_{\mathbf{v}}(\psi)$
$\displaystyle=\lambda_{\mathbf{v},1}\psi+\lambda_{\mathbf{v},2}\sqrt{\psi}+\lambda_{\mathbf{v},3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{\mathbf{v},4}\sqrt{\psi+r^{*}}+\lambda_{\mathbf{v},5},$
$\displaystyle h(\psi)$ $\displaystyle=\gamma_{1}\psi+\gamma_{2},$

with coefficients

$\displaystyle\lambda_{\mathbf{v},1}=$
$\displaystyle~{}\|\mathbf{a}_{\mathbf{v}}\|_{2}^{2}+\|\mathbf{c}_{\mathbf{v}}\|_{2}^{2},$
$\displaystyle\lambda_{\mathbf{v},2}=$
$\displaystyle~{}2\langle\mathbf{a}_{\mathbf{v}},\mathbf{b}_{\mathbf{v}}\rangle\sqrt{r^{*}},$
$\displaystyle\lambda_{\mathbf{v},3}=$
$\displaystyle~{}2\langle\mathbf{a}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle,$
$\displaystyle\lambda_{\mathbf{v},4}=$
$\displaystyle~{}2\langle\mathbf{b}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle\sqrt{r^{*}},$
$\displaystyle\lambda_{\mathbf{v},5}=$
$\displaystyle~{}(\|\mathbf{b}_{\mathbf{v}}\|_{2}^{2}+\|\mathbf{c}_{\mathbf{v}}\|_{2}^{2})r^{*},$
$\displaystyle{\gamma}_{1}=$
$\displaystyle~{}t/(\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}),$
$\displaystyle{\gamma}_{2}=$
$\displaystyle~{}r^{*}t/(\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}),$

where $\mathbf{a}_{\mathbf{v}}=A^{\top}\mathbf{v}$,
$\mathbf{b}_{\mathbf{v}}=B^{\top}\mathbf{v}$, and
$\mathbf{c}_{\mathbf{v}}=C^{\top}\mathbf{v}.$

The solution sets to the inequalities in (25) can be computed by a method
analogous to that discussed in Remark 4. It then follows by Theorem 7 and
Proposition 8 that $p_{J}^{*}$ can be computed exactly.

##  6 Simulations

We now present a simulation study of the proposed tests, exploring their Type
I error control and empirical powers. Sections 6.1 and 6.2 provide empirical
results for the settings where the noise level $\sigma$ is known and unknown,
respectively. Sections 6.1.1 and 6.2.1 consider the case where $\mathcal{V}$
is pre-specified, and Sections 6.1.2 and 6.2.2 address the case where the
choice of $\mathcal{V}$ is data-dependent. Specifically, Sections 6.1.1,
6.2.1, 6.1.2, and 6.2.2 demonstrate the numerical performance of the proposed
tests based on the p-values $p_{\sigma},$ $p_{\sigma,J},$ $p^{*},$ and
$p^{*}_{J},$ respectively. In relevant contexts, we make comparisons with the
baseline testing procedure of Section 3.1 as well as the tests based on the
plug-in estimators $\hat{\sigma}_{\textrm{sample}}$ and
$\hat{\sigma}_{\textrm{med}}.$ For the simplicity of writing, we henceforth
denote the tests based on $p_{\hat{\sigma}},$ $p_{\hat{\sigma},J},$ $p^{*},$
$p^{*}_{J},$ and $p_{\hat{\sigma},\mathrm{Bon}}$ as $\phi_{\hat{\sigma}},$
$\phi_{\hat{\sigma},J},$ $\phi^{*},$ $\phi^{*}_{J},$ and
$\phi_{\hat{\sigma},\mathrm{Bon}},$ respectively, where
$\hat{\sigma}\in\\{\sigma,\hat{\sigma}_{\mathrm{sample}},\hat{\sigma}_{\mathrm{med}}\\}.$

Before presenting the empirical results, we first discuss the simulation
settings that are common to all experiments in this section. For each test, we
sample the associated p-value as follows. We draw each data from the
distribution in (1) with $n=120$ and $\sigma=1,$ and run $K$-means clustering
to divide the observations into $K$ clusters, where the values for $\mu,$ $q,$
and $K$ are specified in the respective sections. We then compute the
selective p-value. We discuss below the ways in which the Type I error control
and the empirical power of a test are illustrated in each section.

##### Type I error

For experiments under the null hypothesis, we set $\mu$ in (1) as $0_{n\times
q}.$ To explore the Type I error control of a test, we sample the associated
p-value 1500 times. We then present a QQ plot that compares the empirical
quantiles of the 1500 p-values against the theoretical quantiles of the
uniform distribution supported on $[0,1].$

##### Empirical power

For experiments under the alternative hypothesis, we consider the setting
where there are $K_{0}\in\mathbb{N}$ different values of $\mu_{i}$s, and we
henceforth refer to the sets of indices of the observations partitioned by
their means as true clusters. Additionally, we set $K=K_{0},$ i.e., the number
of clusters produced by $K$-means clustering is equal to the number of true
clusters. We consider two different specifications of $\mu$ in (1) for
studying the empirical power of a test. For any $\delta\geq 0$ and each
$k\in\\{0\\}\cup[K-1],$ define

  * •

(Horizontal) $\mu_{H}^{(k)}=(k\cdot\delta,\underbrace{0,...,0}_{q-1})^{\top}$
and

  * •

($K$-gon) $\mu_{K}^{(k)}=(\delta\cdot\mathrm{cos}(2\pi
k/K),\delta\cdot\mathrm{sin}(2\pi k/K),\underbrace{0,...,0}_{q-2})^{\top}.$

Note that if $q=2,$ $\mu_{H}^{(k)}$ for $k\in\\{0\\}\cup[K-1]$ are arranged
horizontally, and $\mu_{K}^{(k)}$ for $k\in\\{0\\}\cup[K-1]$ form the $K$
vertices of a polygon, hence the labels. We set each of the $K$ clusters to
contain an equal number of observations; specifically, there are $n/K$
$\mu_{i}$s that are set to $\mu_{H}^{(k)}$ for each $k\in\\{0\\}\cup[K-1]$ for
the Horizontal case, and similarly for the $K$-gon case—we only consider
values of $K$ that divide $n.$ Visualizations of data generated from the two
specifications of $\mu$ along with the clustering outcomes for the case where
$\delta=6,$ $q=2,$ and $K=3$ are shown in Figure 3—in visualizations of
clustering outcomes in this figure and in the rest of this paper, true
clusters are differentiated by shape and (estimated) clusters by color.

Figure 3: Visualizations of simulated data consistent with the alternative
hypothesis for $\delta=6.$

For each signal strength $\delta\in\\{0,0.5,1,...,5.5,6\\}$ and $\mu$ set
according to either of the two specifications above, we sample 1500 p-values
of the test of interest. Then, for each value of $\delta,$ we compute the
empirical power of the test as the proportion of null hypotheses that are
rejected (at the significance level of 0.05) among those that are false, and
present a plot of empirical powers against $\delta.$

###  6.1 Testing for $H_{0,\mathcal{V}}$ for known $\sigma$

We start by presenting the Type I error control and empirical powers of the
proposed tests for the null hypothesis in (3), where $\sigma$ is assumed to be
known. The performance of the tests $\phi_{\sigma}$ and $\phi_{\sigma,J}$ are
illustrated in Sections 6.1.1 and 6.1.2, respectively. Unless specified
otherwise, we set $q=2$ throughout the experiments in this section.

####  6.1.1 Pre-specified $\mathcal{V}$

For the setting where $\mathcal{V}$ is pre-specified, we test for the global
null hypothesis $H_{0,\mathcal{V}}:\bar{\mu}_{1}=\cdots\bar{\mu}_{K},$ where
we consider three different choices of $\mathcal{V}$:

  * •

$\mathcal{V}_{1}=\\{(k,k^{\prime}):k<k^{\prime}\in[K]\\},$

  * •

$\mathcal{V}_{2}=\\{(k,k+1):k\in[K-1]\\},$ and

  * •

$\mathcal{V}_{3}=\\{(1,k):k\in[K]\backslash\\{1\\}\\}.$

As the corresponding spaces
$\mathrm{span}\\{\mathbf{v}_{k,k^{\prime}}:(k,k^{\prime})\in\mathcal{V}_{m}\\}$
for $m\in[3]$ are identical, the proposed test $\phi_{\sigma}$ remains
invariant to the different choices of $\mathcal{V}$, while the baseline
testing procedure $\phi_{\sigma,\mathrm{Bon}}$ does not; see Remark 2 for
further discussion.

##### Type I error

Figure 4 presents QQ plots of samples of $p_{\sigma}$ generated under the null
hypothesis. The plots show that $p_{\sigma}$ is uniformly distributed, which
is consistent with Theorem 1. Analogous plots for $p_{\sigma,\mathrm{Bon}}$
for the setting where $q=2$ and $\mathcal{V}=\mathcal{V}_{1}$ was presented in
Figure 1.

Figure 4: QQ plots of samples of $p_{\sigma}$ generated under the null
hypothesis in (3) with a pre-specified $\mathcal{V}.$

##### Empirical power

Figure 5 presents the empirical powers of $\phi_{\sigma}$ and
$\phi_{\sigma,\mathrm{Bon}},$ where the performance of the latter is compared
for the three different choices of $\mathcal{V}.$ The figure illustrates that
the relative performances of the tests vary depending on the signal strength:
the proposed test $\phi_{\sigma}$ achieves a higher empirical power than
$\phi_{\sigma,\mathrm{Bon}}$ in the presence of weak signals, while the
opposite is true in the presence of strong signals.

We speculate that the intuition for the higher empirical power of
$\phi_{\sigma}$ in the presence of weak signals lies in the construction of
the test statistic that combines the signals across all pairs of clusters of
interest by considering the span of all of the vectors $v_{k,k^{\prime}}$s for
$(k,k^{\prime})$ in $\mathcal{V}.$ On the other hand, the presence of at least
one strong signal is conducive to $\phi_{\sigma,\mathrm{Bon}},$ whose test
statistic is associated with only the strongest signal, potentially accounting
for its superior performance for large values of $\delta.$

Figure 5: Plots of empirical powers of the proposed test based on $p_{\sigma}$
and the baseline testing procedure based on $p_{\sigma,\mathrm{Bon}}$ for the
null hypothesis in (3) with pre-specified $\mathcal{V}$s.

####  6.1.2 Data-dependent choice of $\mathcal{V}$

We next consider the setting where $\mathcal{V}$ is chosen in a data-dependent
way.

##### Type I error

The first and second columns of Figure 6 present QQ plots of empirical
p-values obtained from the tests $\phi_{\sigma,J}$ and $\phi_{\sigma},$
respectively, under the null hypothesis when $K=20$ clusters are produced by
$K$-means clustering. Consistent with Theorem 3, the figure shows that
$p_{\sigma,J}$ is uniformly distributed under both Settings 1 and 2. On the
other hand, $\phi_{\sigma}$ fails to control the Type I error under Setting 1,
where the test becomes more confident as $g,$ the number of pairs of clusters
chosen, decreases. The test controls the Type I error under Setting 2 but
becomes more conservative as $g$ decreases. As discussed in Remark 3, this
observation aligns with the intuition that the null hypothesis is less likely
to happen under Setting 1 and more likely to happen under Setting 2. Note that
the QQ plot of a sample of $p_{\sigma}$ for the case where $g=1$ was also
presented in Figure 2.

Figure 6: QQ plots of a sample of $p_{\sigma,J}$ (left) and a sample of
$p_{\sigma}$ (right) generated under the null hypothesis in (3) with data-
dependent choices of $\mathcal{V},$ for $K=20.$

Figure 7 presents analogous results for different values of $K$ when $g=3$
pairs of clusters are chosen to be tested. The figure shows that as $K$
increases, $p_{\sigma}$ becomes more confident under Setting 1 and more
conservative under Setting 2. Both Figures 6 and 7 illustrate that the effects
of not accounting for the data-dependence in the choice of $\mathcal{V}$ are
not significant, especially when $K$ is small or $g$ is large.

Figure 7: QQ plots of a sample of $p_{\sigma,J}$ (left) and a sample of
$p_{\sigma}$ (right) generated under the null hypothesis in (3) with data-
dependent choices of $\mathcal{V},$ for $g=3.$

##### Empirical power

Figure 8 presents empirical powers of $\phi_{\sigma,J}$ and $\phi_{\sigma}$
under Settings 1 and 2 with $K=20$ and $g=3.$ As suggested by the Type I error
control of $\phi_{\sigma},$ the empirical power of $\phi_{\sigma,J}$ tends to
be lower than that of $\phi_{\sigma}$ under Setting 1, and the opposite is
true under Setting 2.

Figure 8: Plots of empirical powers of the tests based on $p_{\sigma,J}$ and
$p_{\sigma}$ for the null hypothesis in (3) with data-dependent choices of
$\mathcal{V},$ for $K=20$ and $g=3.$

###  6.2 Testing for $H_{0,\mathcal{V}}^{*}$ for unknown $\sigma$

We next consider the setting where $\sigma$ is unknown and test for the null
hypothesis in (16). Unless specified otherwise, we set $q=20$ throughout the
experiments in this section. The choice of $q=20$ that is relatively large is
due to a computational limitation of $\phi^{*},$ which we discuss below.

##### Computational limitation of $\phi^{*}$

Since the selective p-value $p^{*}$ is the right-tail probability of a
truncated $F$ distribution, its computation involves taking ratios of
probabilities associated with the $F$ distribution, which may be very small in
some cases. As a result, computing the probabilities using a built-in function
in `R` and then taking ratios can lead to numerical inaccuracies. To address
this computational issue, we take an alternative approach for computing the
p-value. Specifically, following the approach of Yun and Barber (2023,
Appendix A.3), we first use the procedure of Li and Martin (2002) to
approximate the truncation set $\mathcal{S}^{*},$ which is associated with the
$F_{n_{1},n_{2}}$ distribution (where $n_{1},n_{2}>0$) with a set associated
with the $\chi^{2}_{n_{1}}$ distribution, which we denote as
$\mathcal{S}^{*}_{\chi^{2}_{n_{1}}},$ so that $p_{J}^{*}\approx
1-F_{\chi_{n_{1}}^{2}}(T^{*};\mathcal{S}^{*}_{\chi^{2}_{n_{1}}}),$ where
$F_{\chi_{n_{1}}^{2}}(\cdot;\mathcal{S}^{*}_{\chi^{2}_{n_{1}}})$ represents
the CDF of the $\chi_{n_{1}}^{2}$ distribution truncated to the set
$\mathcal{S}^{*}_{\chi^{2}_{n_{1}}}.$ We then compute the approximation of
$p_{J}^{*}$ using the function `TChisqRatioApprox` of the package
`KmeansInference` of Chen and Witten (2023).

We speculate that the approximation of the $F$ distribution with the
$\chi^{2}$ distribution is less accurate for values that are far in the right
tail of the $F$ distribution. We have observed that the realizations of the
set $\mathcal{S}^{*}$ tend to decrease with $q$ and increase with $n$ and the
signal strength $\delta.$ Accordingly, we have noticed that the accuracy of
the approximation, as measured by the empirical Type I error control of
$\phi^{*},$ tends to increase with $q$ and decrease with $n$ and $\delta,$
where the realizations of $p^{*}$ tend to be underestimated for small values
of $q.$ Thus, to ensure that the results presented in this section are
accurate both under the null hypothesis and the alternative hypothesis, we set
$q=20$ unless specified otherwise.

####  6.2.1 Pre-specified $\mathcal{V}$

We test for the global null hypothesis
$H_{\mathcal{V}}^{*}:\mu_{i}=\mu_{i^{\prime}}$ for all $i,i^{\prime}\in[n],$
where we set $\mathcal{V}=\mathcal{V}_{1}.$

##### Type I error

Figure 9 presents QQ plots of samples of p-values obtained from the test
$\phi^{*}$ under the null hypothesis, which are consistent with Theorem 5.
Figure 10 presents analogous plots for $\phi_{\hat{\sigma}}$ for
$\hat{\sigma}\in\\{\hat{\sigma}_{\textrm{sample}},\hat{\sigma}_{\textrm{med}}\\},$
illustrating that each test controls the Type I error empirically.

Figure 9: QQ plots of samples of $p^{*}$ generated under the null hypothesis
in (16) with a pre-specified $\mathcal{V}.$ Figure 10: QQ plots of a sample of
$p_{\hat{\sigma}}$ from each of
$\hat{\sigma}\in\\{\hat{\sigma}_{\mathrm{sample}},\hat{\sigma}_{\mathrm{med}}\\}$
generated under the null hypothesis in (16) with a pre-specified
$\mathcal{V}.$

##### Empirical power

Figure 11 presents empirical powers of the tests $\phi^{*},$
$\phi_{\hat{\sigma}},$ and $\phi_{\hat{\sigma},\mathrm{Bon}}$ for
$\hat{\sigma}\in\\{\hat{\sigma}_{\mathrm{sample}},\hat{\sigma}_{\mathrm{Bon}}\\}.$
The figure illustrates that the relative performances of $\phi^{*}$ and
$\phi_{\hat{\sigma},\mathrm{Bon}}$ for either choice of
$\hat{\sigma}\in\\{\hat{\sigma}_{\mathrm{sample}},\hat{\sigma}_{\mathrm{Bon}}\\}$
is analogous to that illustrated in Figure 5, where $\phi^{*}$ achieves a
higher empirical power in the presence of weak signals. The figure shows that
the empirical powers of $\phi^{*}$ and $\phi_{\hat{\sigma}}$ for either choice
of $\hat{\sigma}$ do not differ much in the presence of weak signals. For
strong signal strengths, $\phi^{*}$ tends to perform marginally better than
$\phi_{\hat{\sigma}_{\mathrm{sample}}},$ but is outperformed by
$\phi_{\hat{\sigma}_{\mathrm{med}}}$ in most cases.

In this figure, as well as in Figures 11 and 13, the empirical power of
$\phi^{*}$ may not be trusted for large values of $\delta$ for the Horizontal
case as we have observed that the realizations of $S^{*}$ tend to be large
even when $q=20.$

Figure 11: Plots of empirical powers of various tests for the null hypothesis
in (16) with a pre-specified $\mathcal{V}.$

Figure 12 presents the empirical powers of $\phi^{*}$ and $\phi_{\sigma},$
where the latter assumes $\sigma$ is known, illustrating the loss of power due
to not knowing $\sigma.$

Figure 12: Plots of empirical powers of the proposed tests based on $p^{*}$
and $p_{\sigma}$ for the null hypothesis in (16) with a pre-specified
$\mathcal{V}.$

####  6.2.2 Data-dependent choice of $\mathcal{V}$

We next let $\mathcal{V}$ be chosen in a data-dependent way. We specifically
consider the case where it is chosen as in Setting 1 with $K=20$ and $g=3.$
The leftmost plot of Figure 13 illustrates that $\phi^{*}_{J}$ controls the
Type I error, as implied by Theorem 3. The middle and the rightmost plots
compare the empirical powers of $\phi^{*}_{J}$ and $\phi_{\sigma},$ the latter
of which assumes $\sigma$ is known, to illustrate the loss of power due to not
knowing $\sigma.$

Figure 13: QQ plot of a sample of $p^{*}_{J}$ generated under the null
hypothesis in (16) with $\mathcal{V}$ chosen according to Setting 2, and plots
of empirical powers of the proposed tests based on $p_{J}^{*}$ and
$p_{\sigma,J}$ for the same null hypothesis.

##  7 Real data application

We next apply the proposed methods to the penguins data of Horst et al.
(2020), which is also studied in Gao et al. (2022), Chen and Witten (2023),
and Yun and Barber (2023). The data consists of measurements of different body
parts of three species of penguins (Adelie, Gentoo, and Chinstrap) of the male
and female sexes. For our purposes, we specifically consider the variables
bill depth (mm) and bill length (mm) of female penguins. We test for the null
hypothesis in (16): Sections 7.1 and 7.2 present the cases where $\mathcal{V}$
is pre-specified and chosen in a data-dependent way, respectively.

###  7.1 Testing for $H_{0,\mathcal{V}}$ with pre-specified $\mathcal{V}$

For the case where $\mathcal{V}$ is pre-specified, we test for the equality of
means of all observations, i.e., we consider the global null hypothesis
$H^{*}_{\mathcal{V}}:\mu_{i}=\mu_{i^{\prime}}$ for all $i,i^{\prime}\in[n],$
where we set $\mathcal{V}=\mathcal{V}_{1}.$ We apply the tests
$\phi_{\hat{\sigma}}$ and $\phi_{\hat{\sigma},\mathrm{Bon}}$ for
$\hat{\sigma}\in\\{\hat{\sigma}_{\mathrm{sample}},\hat{\sigma}_{\mathrm{Bon}}\\}$
for two different subsets of the penguins data, a subset consisting of
observations from the Adelie species only and a subset consisting of
observations from both the Adelie and Gentoo species, which we assume to be
consistent with the null and the alternative hypotheses, respectively. We run
$K$-means clustering on the standardized data with $K=4$ and present an
average of 100 realizations for each p-value to account for the randomness in
the initialization step of the algorithm. Note that we omit the test
$\phi^{*}$ due to the relatively small number of features that could cause the
associated p-value to be underestimated, as discussed in Section 6.2.

Figure 14 presents visualizations of the outcomes of an instance of $K$-means
clustering run on the two subsets of the data, and Table 1 presents an average
of 100 p-values associated with each of the tests considered. The table
illustrates that the p-values of the proposed tests tend to be lower than
those of the baseline testing procedure, both under the null and alternative
hypotheses.

Figure 14: Visualizations of subsets of the standardized penguins data that are consistent with the null hypothesis (left) and the alternative hypothesis (right), along with outcomes of an instance of $K$-means clustering run with $K=4.$ | $p_{\hat{\sigma}_{\mathrm{sample}}}$ | $p_{\hat{\sigma}_{\mathrm{med}}}$ | $p_{\hat{\sigma}_{\mathrm{sample},\mathrm{Bon}}}$ | $p_{\hat{\sigma}_{\mathrm{med},\mathrm{Bon}}}$
---|---|---|---|---
Null | 0.52 | 0.51 | 0.65 | 0.63
Alternative | 0.26 | 0.33 | 0.47 | 0.56
Table 1: Average of 100 p-values associated with various tests for the null
hypothesis in (16) with a pre-specified $\mathcal{V}.$

###  7.2 Testing for $H_{0,\mathcal{V}}$ with data-dependent choice of
$\mathcal{V}$

We next choose $\mathcal{V}$ in a data-dependent way after running $K$-means
clustering on the subset of the data that consists of observations from the
Adelie and Gentoo species, which coincides with the subset visualized in the
right-hand plot of Figure 14. We apply the tests $\phi_{\hat{\sigma}}$ and
$\phi_{\hat{\sigma},J}$ for
$\hat{\sigma}\in\\{\hat{\sigma}_{\mathrm{sample}},\hat{\sigma}_{\mathrm{Bon}}\\}$—again,
we omit the test $\phi^{*}_{J}.$ We run $K$-means clustering on the
standardized data with $K=10$ and choose $g=2$ pairs of clusters according to
each of Setting 1 and Setting 2. The two pairs that are chosen according to
Setting 1 are $(2,3)$ and $(3,8),$ and those chosen according to Setting 2 are
$(1,7)$ and $(6,7)$—note that such choices align with the visualizations of
the clustering outcomes illustrated in Figure 15. Table 2 presents the
p-values of the tests and shows that the tests that do not account for the
data-dependence in the choice of $\mathcal{V}$ results in the same p-values as
those that do. This observation is consistent with the simulation results of
Section 6.1.2, where we have observed that the effect of not accounting for
this additional selection event is noticeable only for relatively large values
of $K.$

Figure 15: Visualizations of a subset of the standardized penguins data with $K$-means clustering run with $K=10.$ | $p_{\hat{\sigma}_{\mathrm{sample}}}$ | $p_{\hat{\sigma}_{\mathrm{med}}}$ | $p_{\hat{\sigma}_{\mathrm{sample}},J}$ | $p_{\hat{\sigma}_{\mathrm{med}},J}$
---|---|---|---|---
Setting 1 | 0.17 | 0.2 | 0.17 | 0.2
Setting 2 | 0.17 | 0.17 | 0.17 | 0.17
Table 2: P-values associated with various tests for the null hypothesis in
(16) with data-dependent choices of $\mathcal{V}.$

##  8 Discussion

In this work, we have developed tests for multiple pairs of clusters for both
known and unknown variance settings, extending the work of Chen and Witten
(2023) and Yun and Barber (2023). We have shown that the proposed tests
control the Type I error, and we have derived expressions for the associated
p-values that can be computed exactly. We have also presented numerical
illustrations of the empirical powers of the proposed tests, which we have
compared with that of the baseline testing procedure that combines Chen and
Witten (2023)’s test with the Bonferroni correction—empirical results
illustrate that the proposed tests tend to have a higher empirical power in
the presence of weak signals. We have also briefly discussed a computational
limitation of $\phi^{*},$ which we speculate lies in the computation of
probabilities associated with a truncated distribution.

As a possible direction for future work, it would be of practical importance
to develop tests for the null hypothesis $H_{0,\mathcal{V}}$ for data
generated from a more flexible model that captures the complexity of real
data. Another direction of computational importance would be to explore ways
of computing more accurate selective p-values associated with a truncated $F$
distribution, especially for truncation sets that lie far in the tail of the
distribution with non-negligible probability. In this work, we have
approximated the $F$ distribution with the $\chi^{2}$ distribution, which is
then approximated using the normal distribution. It could be of interest to
study ways of approximating the $F$ distribution directly with the normal
distribution. Improvements in the accuracy of such computations would not only
address the computational limitation of the proposed test based on $p^{*}$ but
also provide a valuable tool in the literature of selective inference.

##  9 Acknowledgements

Yinqiu He was partially supported by Wisconsin Alumni Research Foundation. We
thank the Center for High Throughput Computing (Center for High Throughput
Computing (2006)) for the computational resources that were used for producing
the empirical results presented in Section 6.

## References

  * Bachoc et al. [2023] François Bachoc, Cathy Maugis-Rabusseau, and Pierre Neuvial.  Selective inference after convex clustering with $\backslash\ell\\_1$ penalization.  _arXiv preprint arXiv:2309.01492_ , 2023.
  * Benjamini [2020] Yoav Benjamini.  Selective inference: The silent killer of replicability.  _Harvard Data Science Review_ , 2020.
  * Center for High Throughput Computing [2006] Center for High Throughput Computing.  Center for high throughput computing, 2006.  URL https://chtc.cs.wisc.edu/.
  * Chen and Gao [2023] Yiqun T Chen and Lucy L Gao.  Testing for a difference in means of a single feature after clustering.  _arXiv preprint arXiv:2311.16375_ , 2023.
  * Chen and Witten [2023] Yiqun T Chen and Daniela M Witten.  Selective inference for k-means clustering.  _J. Mach. Learn. Res._ , 24:152–1, 2023.
  * Fithian et al. [2014] William Fithian, Dennis Sun, and Jonathan Taylor.  Optimal inference after model selection.  _arXiv preprint arXiv:1410.2597_ , 2014.
  * Gao et al. [2022] Lucy L Gao, Jacob Bien, and Daniela Witten.  Selective inference for hierarchical clustering.  _Journal of the American Statistical Association_ , pages 1–11, 2022.
  * González-Delgado et al. [2023] Javier González-Delgado, Juan Cortés, and Pierre Neuvial.  Post-clustering inference under dependency.  _arXiv preprint arXiv:2310.11822_ , 2023.
  * Hivert et al. [2022] Benjamin Hivert, Denis Agniel, Rodolphe Thiébaut, and Boris P Hejblum.  Post-clustering difference testing: valid inference and practical considerations.  _arXiv preprint arXiv:2210.13172_ , 2022.
  * Horst et al. [2020] Allison Marie Horst, Alison Presmanes Hill, and Kristen B Gorman.  palmerpenguins: Palmer archipelago (antarctica) penguin data.  _R package version 0.1. 0_ , 2020.
  * Li and Martin [2002] Baibing Li and Elaine B Martin.  An approximation to the f distribution using the chi-square distribution.  _Computational statistics & data analysis_, 40(1):21–26, 2002.
  * Lloyd [1982] Stuart Lloyd.  Least squares quantization in PCM.  _IEEE transactions on information theory_ , 28(2):129–137, 1982.
  * Neufeld et al. [2024] Anna Neufeld, Lucy L Gao, Joshua Popp, Alexis Battle, and Daniela Witten.  Inference after latent variable estimation for single-cell rna sequencing data.  _Biostatistics_ , 25(1):270–287, 2024.
  * Saha et al. [2024] Arkajyoti Saha, Daniela Witten, and Jacob Bien.  Inferring independent sets of gaussian variables after thresholding correlations.  _Journal of the American Statistical Association_ , (just-accepted):1–20, 2024.
  * Watanabe and Suzuki [2021] Chihiro Watanabe and Taiji Suzuki.  Selective inference for latent block models.  _Electronic Journal of Statistics_ , 15(1):3137–3183, 2021.
  * Yun and Barber [2023] Young-Joo Yun and Rina Foygel Barber.  Selective inference for clustering with unknown variance.  _Electronic Journal of Statistics_ , 17(2):1923–1946, 2023.

##  Appendix A Appendix

Appendix A.1 contains proofs of the theorems and propositions presented in
this paper. Appendix A.2 provides details on the implementations of the
proposed tests, which align with the codes available at
https://github.com/yjyun97/cluster_inf_multiple.

###  A.1 Proofs

The proofs of Theorems 1 and 3 can be found in Appendix A.1.1, and those of
Theorems 5 and 7 can be found in Appendix A.1.2. Additionally, the proofs of
Propositions 2, 4, 6, and 8 can be found in Appendices A.1.3, A.1.4, A.1.5,
and A.1.6, respectively.

We first introduce additional notations that are used throughout the proofs.
We write $Y_{i}\overset{\perp\\!\\!\\!\perp}{\sim}F$ for $i\in[m]$ and
$m\in\mathbb{N}$ to denote that $Y_{i}$s follow the distribution $F$
independently, and we write $Y\overset{H_{0}}{\sim}F$ to denote that $Y$
follows the distribution $F$ under the null hypothesis $H_{0}.$ Likewise,
$\overset{H_{0}}{=}$ and $\overset{H_{0}}{\propto}$ denote that the equality
and the proportionality, respectively, hold under the null hypothesis $H_{0}.$

Before presenting the proofs, we state and prove Lemmas 9 and 10, which are
used in the proofs of Theorems 1, 3, 5, and 7.

######  Lemma 9.

For any vector $\mathbf{e}\in\mathcal{E},$
$\mu^{\top}\mathbf{e}=\mathbf{0}_{q}$ under $H_{0,\mathcal{V}}.$

###### Proof.

Since $\mathbf{e}\in\mathcal{E},$
$\mathbf{e}=\sum_{(k,k^{\prime})\in\mathcal{V}}\lambda_{k,k^{\prime}}\mathbf{v}_{k,k^{\prime}}$
for some
$\\{\lambda_{k,k^{\prime}}\\}_{(k,k^{\prime})\in\mathcal{V}}\subset\mathbb{R}.$
Then,
$\mu^{\top}\mathbf{e}=\sum_{(k,k^{\prime})\in\mathcal{V}}\lambda_{k,k^{\prime}}\mu^{\top}\mathbf{v}_{k,k^{\prime}}\overset{\mathcal{H}_{0,\mathcal{V}}}{=}0_{q}$
since $\mu^{\top}\mathbf{v}_{k,k^{\prime}}=0_{q}$ for all
$(k,k^{\prime})\subset\mathcal{V}$ under $H_{0,\mathcal{V}}.$ ∎

######  Lemma 10.

Let $X\in\mathbb{R}^{n\times q}$ be a matrix whose rows are distributed
independently as in (1). Let
$\Pi=\sum_{i=1}^{r}\mathbf{e}_{i}\mathbf{e}_{i}^{\top}$ for some $r\leq n,$
where $\mathbf{e}_{i}\in\mathbb{R}^{n}$ for $i\in[r]$ are orthonormal. Suppose
$\mu$ in (1) satisfies the condition that for each $i\in[r],$
$\mu^{\top}\mathbf{e}_{i}=0_{q}.$ Then,

$\|\Pi X\|_{F}\perp\\!\\!\\!\perp\frac{\Pi X}{\|\Pi X\|_{F}}.$

###### Proof.

Define
$\mathbf{w}=[\mathbf{e}_{1}^{\top}X\cdots\mathbf{e}_{r}^{\top}X]^{\top},$ and
define $\tilde{I}_{i}\in\mathbb{R}^{rq\times q}$ for $i\in[r]$ to be matrices
where $\tilde{I}_{i:i+q-1,:}=I_{q},$ and the remaining entries are 0; here,
$A_{i:i^{\prime},:}$ for $i\leq i^{\prime}\in\mathbb{N}$ denotes the entries
of the matrix $A$ corresponding to the rows $i$ through $i^{\prime}$ and all
columns. Next, let $f:\mathbb{R}^{rq}\rightarrow\mathbb{R}^{n\times
q},f(u)=\sum_{i=1}^{r}\mathbf{e}_{i}u^{\top}\tilde{I}_{i}.$ Note that

$\displaystyle
f(\mathbf{w})=\sum_{i=1}^{r}\mathbf{e}_{i}\mathbf{e}_{i}^{\top}X=\Pi X$ (26)

and

$\displaystyle\|f(\mathbf{w})\|_{F}=\sqrt{\|\sum_{i=1}^{r}\mathbf{e}_{i}\mathbf{e}_{i}^{\top}X\|_{F}^{2}}=\sqrt{\sum_{i=1}^{r}\|\mathbf{e}_{i}\mathbf{e}_{i}^{\top}X\|^{2}_{F}}=\sqrt{\sum_{i=1}^{r}\|\mathbf{e}_{i}^{\top}X\|^{2}_{2}}=\|\mathbf{w}\|_{2}.$
(27)

By the assumption that $\mu^{\top}\mathbf{e}_{i}=\mathbf{0}_{q}$ for all
$i\in[r]$ and the distributional assumptions on $X,$ we have
$\mathbf{w}\sim\mathcal{N}\left(0,\sigma^{2}I_{rq}\right).$ Thus, it follows
that

$\displaystyle\|\mathbf{w}\|_{2}\perp\\!\\!\\!\perp\frac{\mathbf{w}}{\|\mathbf{w}\|_{2}}.$

Then,

$\|\mathbf{w}\|_{2}\perp\\!\\!\\!\perp
f\left(\frac{\mathbf{w}}{\|\mathbf{w}\|_{2}}\right)=\frac{1}{\|\mathbf{w}\|_{2}}f\left(\mathbf{w}\right),$

where the equality follows by linearity of $f.$ It then follows from (27) that

$\|f(\mathbf{w})\|_{F}\perp\\!\\!\\!\perp\frac{1}{\|f(\mathbf{w})\|_{F}}f\left(\mathbf{w}\right).$

Finally, by (26), we have

$\left\lVert\Pi X\right\rVert_{F}\perp\\!\\!\\!\perp\frac{\Pi
X}{\left\lVert\Pi X\right\rVert_{F}}.$

∎

We now present the proofs of Theorem 1, Theorem 3, Theorem 5, and Theorem 7.

####  A.1.1 Proofs of Theorems 1 and 3

The proofs closely follow Yun and Barber [2023, Appendix A.1] and parts of Gao
et al. [2022, Appendix A.1].

We start by presenting the proof of Theorem 3. We first note that
$p_{\sigma,J},$ conditioned on $Z,$ $\mathcal{C}(X),$ and $\mathcal{V}(X),$ is
uniformly distributed under $H_{0,\mathcal{V}}$ by the property that $F(Y)$ is
uniformly distributed for a random variable $Y$ with CDF $F.$ Then, for any
$\alpha\in(0,1),$

$\displaystyle\mathbb{P}_{H_{0,\mathcal{V}}}\left(p_{\sigma,J}\leq\alpha\mid\mathcal{C}(X),\mathcal{V}(X)\right)$
$\displaystyle=\mathbb{E}\left[\mathbb{P}_{H_{0,\mathcal{V}}}\left(p_{\sigma,J}\leq\alpha\mid\mathcal{C}(X),\mathcal{V}(X),Z\right)\right]=\mathbb{E}[\alpha]=\alpha,$

as desired.

We next characterize the distribution function $Q_{\sigma,J}.$ For any
realization $\left(Z^{0},\mathcal{C}^{0},\mathcal{V}^{0}\right)$ of
$\left(Z,\mathcal{C}(X),\mathcal{V}(X)\right),$ define

$\displaystyle h(t,Z^{0},\mathcal{C}^{0},\mathcal{V}^{0})=f_{T_{\sigma}\mid
Z=Z^{0},\;\mathcal{C}(X)=\mathcal{C}^{0},\;\mathcal{V}(X)=\mathcal{V}^{0}}(t)$

for any $t>0.$ Then, $h(\cdot,Z,\mathcal{C}(X),\mathcal{V}(X))$ is the
conditional PDF (probability density function) of $T_{\sigma}$ given $Z,$
$\mathrm{C}(X),$ and $\mathcal{V}(X).$ We aim to show

$\displaystyle
h(t,Z,\mathcal{C}(X),\mathcal{V}(X))\overset{H_{0,\mathcal{V}}}{\propto}f_{\chi_{d}}(t)\mathbbm{1}_{t\in
S_{\sigma,J}},$ (28)

where $f_{\chi_{d}}$ is the PDF of the $\chi_{d}$ distribution. To show (28),
we first state and prove Lemmas 11 and 12.

######  Lemma 11.

Suppose the cluster assignments and the set $\mathcal{V}$ are pre-specified,
i.e., $\mathcal{C}_{k}$ for $k\in[K]$ and the set $\mathcal{V}$ are determined
independently of the data. Then,

$T_{\sigma}^{2}\overset{H_{0,\mathcal{V}}}{\sim}\chi^{2}_{d}.$

###### Proof.

Let $\\{\mathbf{e}_{l}:l\in[\mathrm{dim}(\mathcal{E})]\\}$ be an orthonormal
basis of $\mathcal{E}.$ Then,
$P_{\mathcal{E}}=\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}\mathbf{e}_{l}\mathbf{e}_{l}^{\top},$
so we have

$\displaystyle T_{\sigma}^{2}=\frac{1}{\sigma^{2}}\left\lVert
P_{\mathcal{E}}X\right\rVert^{2}_{F}=\frac{1}{\sigma^{2}}\overset{\mathrm{dim}(\mathcal{E})}{\underset{l=1}{\sum}}\|\mathbf{e}_{l}^{\top}X\|_{2}^{2}=\frac{1}{\sigma^{2}}\overset{\mathrm{dim}(\mathcal{E})}{\underset{l=1}{\sum}}\overset{q}{\underset{j=1}{\sum}}(\mathbf{e}_{l}^{\top}X^{j})^{2},$

where the second equality follows from the orthogonality of the vectors
$\mathbf{e}_{l}$ for $l\in[\mathrm{dim}(\mathcal{E})].$ Note that for each
$l\in[\mathrm{dim}(\mathcal{E})]$ and $j\in[q],$
$\mathbb{E}[\mathbf{e}_{l}^{\top}X^{j}]=\mathbf{e}_{l}^{\top}\mu^{j}\overset{H_{0,\mathcal{V}}}{=}0$
by Lemma 9, and $\mathrm{Var}[\mathbf{e}_{l}^{\top}X^{j}]=\sigma^{2}.$ By the
orthogonality across $\mathbf{e}_{l}$ for $l\in[\mathrm{dim}(\mathcal{E})]$
and the distributional assumptions on $X^{j},$ we have
$\frac{1}{\sigma^{2}}\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}(\mathbf{e}_{l}^{\top}X^{j})^{2}\overset{H_{0,\mathcal{V}}}{\sim}\chi^{2}_{\mathrm{dim}(\mathcal{E})}.$
Finally, independence across $X^{j}$ for $j\in[q]$ gives
$\frac{1}{\sigma^{2}}\overset{q}{\underset{j=1}{\sum}}\overset{\mathrm{dim}(\mathcal{E})}{\underset{l=1}{\sum}}(\mathbf{e}_{l}^{\top}X^{j})^{2}\overset{H_{0,\mathcal{V}}}{\sim}\chi^{2}_{d}.$
∎

######  Lemma 12.

Suppose the cluster assignments and the set $\mathcal{V}$ are pre-specified.
Then,

$T_{\sigma}^{2}\perp\\!\\!\\!\perp Z$

under $H_{0,\mathcal{V}}.$

###### Proof.

Recall $T_{\sigma}^{2}\overset{H_{0,\mathcal{V}}}{\sim}\chi^{2}_{d}$ by Lemma
11. We prove $T_{\sigma}^{2}$ and $Z$ are independent under
$H_{0,\mathcal{V}}$ by showing that

$\displaystyle T^{2}_{\sigma}\mid
Z\overset{H_{0,\mathcal{V}}}{\sim}\chi^{2}_{d}.$ (29)

Note that for each $j\in[q],$ $X^{j}\sim\mathcal{N}(\mu^{j},\sigma^{2}I_{n}),$
so $P_{\mathcal{E}}X^{j}$ and $P_{\mathcal{E}}^{\perp}X^{j}$ are independent.
By independence across $X^{j}$ for $j\in[q],$ we further have independence
across $\left(P_{\mathcal{E}}X^{j},\ \ P_{\mathcal{E}}^{\perp}X^{j}\right)$
for $j\in[q].$ As a result, $P_{\mathcal{E}}X$ and $P_{\mathcal{E}}^{\perp}X$
are independent, which allows (29) to be equivalently written as

$\displaystyle
T_{\sigma}^{2}\mid\frac{P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}}\overset{H_{0,\mathcal{V}}}{\sim}\chi^{2}_{d}$
(30)

since for random quantities $Y_{1},Y_{2},$ and $Y_{3},$ we have that
$Y_{3}\perp\\!\\!\\!\perp(Y_{1},Y_{2})$ implies $Y_{3}\perp\\!\\!\\!\perp
Y_{1}\mid Y_{2}.$ We next show
$T_{\sigma}^{2}\perp\\!\\!\\!\perp\frac{P_{\mathcal{E}}X}{\left\lVert
P_{\mathcal{E}}X\right\rVert_{F}}.$ Let
$\\{\mathbf{e}_{l}:l\in[\mathrm{dim}(\mathcal{E})]\\}$ be an orthonormal basis
of $\mathcal{E}$ and write
$P_{\mathcal{E}}=\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}\mathbf{e}_{l}\mathbf{e}_{l}^{\top},$
where $\mu^{\top}\mathbf{e}_{l}\overset{H_{0,\mathcal{V}}}{=}0_{q}$ for all
$i\in[\mathrm{dim}(\mathcal{E})]$ by Lemma 9. Then, Lemma 10 gives the desired
result. It follows that (30) can be equivalently written as
$T^{2}_{\sigma}\overset{H_{0,\mathcal{V}}}{\sim}\chi^{2}_{d},$ which holds by
Lemma 11. ∎

We now show (28). In the remainder of this section, we write
$H_{0,\mathcal{V}(X)}(\mathcal{C}(X))$ to make explicit the dependence of
$H_{0,\mathcal{V}}$ on $\mathcal{C}(X)$ and $\mathcal{V}(X).$ Fix any
realization $\left(Z^{0},\mathcal{C}^{0},\mathcal{V}^{0}\right)$ of
$\left(Z,\mathcal{C}(X),\mathcal{V}(X)\right),$ and define
$\tilde{\mathcal{S}}_{\sigma,J}(\mathcal{C}^{0},\mathcal{V}^{0})=\tilde{\mathcal{S}_{\sigma}}(\mathcal{C}^{0})\cap\tilde{S}_{\sigma,\mathcal{V}}(\mathcal{V}^{0}),$
where

$\displaystyle\tilde{\mathcal{S}}_{\sigma}(\mathcal{C}^{0})=\\{(\psi,z)\in[0,\infty)\times(\mathbb{R}^{n\times
q}\times\mathbb{R}^{n\times
q}):\mathcal{C}(\tilde{x}_{\sigma}(\psi,z))=\mathcal{C}^{0}\\}$

and

$\displaystyle\tilde{\mathcal{S}}_{\sigma,\mathcal{V}}(\mathcal{V}^{0})=\\{(\psi,z)\in[0,\infty)\times(\mathbb{R}^{n\times
q}\times\mathbb{R}^{n\times
q}):\mathcal{V}(\tilde{x}_{\sigma}(\psi,z))=\mathcal{V}^{0}\\},$

where $\tilde{x}_{\sigma}:[0,\infty)\times(\mathbb{R}^{n\times
q}\times\mathbb{R}^{n\times q})\rightarrow\mathbb{R}^{n\times q},$

$\displaystyle\tilde{x}_{\sigma}(\psi,(z_{1},z_{2}))=\psi\cdot\sigma
z_{1}+z_{2}.$

Let $f_{T_{\sigma}}$ be the PDF of $T_{\sigma}$ in the setting where the
cluster assignments and the set $\mathcal{V}$ are pre-specified; similarly
define $f_{T_{\sigma},Z}$ as the joint PDF of $T_{\sigma}$ and $Z,$ and
$f_{Z}$ as the PDF of $Z.$ Note that

$\displaystyle\mathcal{C}(X)=\mathcal{C}^{0}\text{ and
}\mathcal{V}(X)=\mathcal{V}^{0}\iff(T_{\sigma},Z)\in\tilde{\mathcal{S}}_{\sigma,J}(\mathcal{C}^{0},\mathcal{V}^{0}).$
(31)

Then,

$\displaystyle h(t,Z^{0},\mathcal{C}^{0},\mathcal{V}^{0})$
$\displaystyle=f_{T_{\sigma}\mid
Z=Z^{0},\;\mathcal{C}(X)=\mathcal{C}^{0},\;\mathcal{V}(X)=\mathcal{V}^{0}}(t)$
(32) $\displaystyle=f_{T_{\sigma}\mid
Z=Z^{0},\;(T_{\sigma},Z)\in\tilde{\mathcal{S}}_{\sigma,J}(\mathcal{C}^{0},\mathcal{V}^{0})}(t)$
(33) $\displaystyle\propto
f_{T_{\sigma},Z\mid(T_{\sigma},Z)\in\tilde{\mathcal{S}}_{\sigma,J}(\mathcal{C}^{0},\mathcal{V}^{0})}(t,Z^{0})$
$\displaystyle\overset{H_{0,\mathcal{V}^{0}}(\mathcal{C}^{0})}{=}f_{T_{\sigma}}(t)f_{Z}(Z^{0})\mathbbm{1}_{(t,Z^{0})\in\tilde{\mathcal{S}}_{\sigma,J}(\mathcal{C}^{0},\mathcal{V}^{0})}$
(34) $\displaystyle\propto
f_{T_{\sigma}}(t)\mathbbm{1}_{(t,Z^{0})\in\tilde{\mathcal{S}}_{\sigma,J}(\mathcal{C}^{0},\mathcal{V}^{0})}$
(35)

where (32) follows from the definition of the function $h,$ (33) follows from
the observation in (31), and (34) holds by Lemma 12. Thus, we have

$\displaystyle
h(t,Z,\mathcal{C}(X),\mathcal{V}(X))\overset{H_{0,\mathcal{V}(X)}(\mathcal{C}(X))}{\propto}f_{T_{\sigma}}(t)\mathbbm{1}_{(t,Z)\in\mathcal{\tilde{S}}_{\sigma,J}(\mathcal{C}(X),\mathcal{V}(X))}=f_{T_{\sigma}}(t)\mathbbm{1}_{t\in\mathcal{S}_{\sigma,J}},$

where the equality follows from the observation that

$\displaystyle(t,Z)\in\mathcal{\tilde{S}}_{\sigma,J}(\mathcal{C}(X),\mathcal{V}(X))\iff
t\in\mathcal{S}_{\sigma,J}.$

By Lemma 11, $f_{T_{\sigma}}$ is the PDF of the $\chi_{d}$ distribution, and
thus we have shown (28).

To prove Theorem 1, recall that $\mathcal{V}$ is pre-specified in the setting
of Theorem 1. Then, $Q_{\sigma,J}=Q_{\sigma},$ and Theorem 1 immediately
follows from Theorem 3.

####  A.1.2 Proofs of Theorems 5 and 7

The proofs closely follow Yun and Barber [2023, Appendix A.1] and parts of Gao
et al. [2022, Appendix A.1].

We first present the proof of Theorem 7. We first note that $p^{*}_{J},$
conditioned on $Z^{*},$ $\mathcal{C}(X),$ and $\mathcal{V}(X),$ is uniformly
distributed under $H_{0,\mathcal{V}}^{*}$ by the property that $F(Y)$ is
uniformly distributed for a random variable $Y$ with CDF $F.$ Then, for any
$\alpha\in(0,1),$

$\displaystyle\mathbb{P}_{H_{0,\mathcal{V}}^{*}}(p^{*}_{J}\leq\alpha\mid\mathcal{C}(X),\mathcal{V}(X))=\mathbb{E}\left[\mathbb{P}_{H_{0,\mathcal{V}}^{*}}(p_{J}^{*}\leq\alpha\mid\mathcal{C}(X),\mathcal{V}(X),Z^{*})\right]=\mathbb{E}[\alpha]=\alpha,$

as desired.

We next characterize the distribution function $Q_{J}^{*}.$ For any
realization $\left(Z^{0},\mathcal{C}^{0},\mathcal{V}^{0}\right)$ of
$\left(Z^{*},\mathcal{C}(X),\mathcal{V}(X)\right),$ define

$\displaystyle h^{*}(t,Z^{0},\mathcal{C}^{0},\mathcal{V}^{0})=f_{T^{*}\mid
Z^{*}=Z^{0},\;\mathcal{C}(X)=\mathcal{C}^{0},\;\mathcal{V}(X)=\mathcal{V}^{0}}(t)$

for any $t>0.$ Then, $h^{*}(\cdot,Z^{*},\mathcal{C}(X),\mathcal{V}(X))$ is the
conditional PDF of $T^{*}$ given $Z^{*},$ $\mathrm{C}(X),$ and
$\mathcal{V}(X).$ We aim to show

$\displaystyle
h^{*}(t,Z^{*},\mathcal{C}(X),\mathcal{V}(X))\overset{H^{*}_{0,\mathcal{V}}}{\propto}f_{F_{d,d^{*}}}(t)\mathbbm{1}_{t\in
S^{*}_{J}},$ (36)

where $f_{F_{d,d^{*}}}$ is the PDF of the $F_{d,d^{*}}$ distribution. To show
(36), we first state and prove Lemmas 13 and 14, which are used in the proofs
of Lemmas 15 and 16.

######  Lemma 13.

Let $P_{\mathcal{E}}$ and $P_{1}$ be as defined in Section 5.2. Then,
$P_{\mathcal{E}}$ and $P_{1}$ are orthogonal.

###### Proof.

We show that $\mathrm{Col}\left(P_{\mathcal{E}}\right)$ and
$\mathrm{Col}\left(P_{1}\right)$ are orthogonal, where $\mathrm{Col}(A)$ for a
matrix $A$ denotes its column space. Note

$\mathrm{Col}\left(P_{\mathcal{E}}\right)=\mathrm{span}\\{\mathbf{v}_{k,k^{\prime}}:(k,k^{\prime})\in\mathcal{V}\\}$

and recall that for any $k,k^{\prime}\in[K],$
$\mathbf{v}_{k,k^{\prime}}=\frac{1}{|\mathcal{C}_{k}|}\mathbf{1}_{\mathcal{C}_{k}}-\frac{1}{|\mathcal{C}_{k^{\prime}}|}\mathbf{1}_{\mathcal{C}_{k^{\prime}}}.$
Therefore, we have

$\mathrm{Col}(P_{\mathcal{E}})\subset\mathrm{span}\\{\mathbf{1}_{\mathcal{C}_{k}}:k\in\mathcal{K}\\},$

where $\mathcal{K}$ is as defined in Section 5.2. Thus, to show
$\mathrm{Col}\left(P_{\mathcal{E}}\right)\perp\mathrm{Col}\left(P_{1}\right),$
it is enough to show

$\mathrm{span}\\{\mathbf{1}_{\mathcal{C}_{k}}:k\in\mathcal{K}\\}\perp\mathrm{Col}\left(P_{1}\right),$

which immediately follows from the orthogonality between

$\displaystyle\sum_{k\in\mathcal{K}}\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\hskip
10.00002pt\text{and}\hskip
10.00002pt\sum_{k\in\mathcal{K}}I_{\mathcal{C}_{k}}-\sum_{k\in\mathcal{K}}\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}.$

∎

######  Lemma 14.

For each $k\in\mathcal{K},$
$\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)\mu=0_{n\times
q}$ under $H_{0,\mathcal{V}}^{*}.$

###### Proof.

Fix any $k\in\mathcal{K}.$ Under $H_{0,\mathcal{V}}^{*},$ $\mu_{i}=\mu_{0}$
for some $\mu_{0}\in\mathbb{R}^{q}$ for all $i\in\mathcal{C}_{k}.$ We thus
have
$I_{\mathcal{C}_{k}}\mu\overset{H_{0,\mathcal{V}}^{*}}{=}\mathbf{1}_{\mathcal{C}_{k}}\mu_{0}^{\top}.$
Likewise,
$\mathbf{1}_{\mathcal{C}_{k}}^{\top}\mu\overset{H_{0,\mathcal{V}}^{*}}{=}|\mathcal{C}_{k}|\mu_{0}^{\top},$
giving
$\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\mu\overset{H_{0,\mathcal{V}}^{*}}{=}\mathbf{1}_{\mathcal{C}_{k}}\mu_{0}^{\top}.$
Therefore,

$\displaystyle\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)\mu=I_{\mathcal{C}_{k}}\mu-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\mu\overset{H_{0,\mathcal{V}}^{*}}{=}\mathbf{1}_{\mathcal{C}_{k}}\mu_{0}^{\top}-\mathbf{1}_{\mathcal{C}_{k}}\mu_{0}^{\top}=0_{n\times
q}.$

∎

######  Lemma 15.

Suppose the cluster assignments and the set $\mathcal{V}$ are pre-specified.
Then,

$T^{*}\overset{H_{0,\mathcal{V}}^{*}}{\sim}F_{d,d^{*}}.$

###### Proof.

We first show
$\frac{1}{\sigma^{2}}\|P_{\mathcal{E}}X\|^{2}_{F}\overset{H_{0,\mathcal{V}}^{*}}{\sim}\chi^{2}_{d}.$
Let $\\{\mathbf{e}_{l}:l\in\mathrm{dim}(\mathcal{E})\\}$ be an orthonormal
basis of $\mathcal{E}$ and write
$P_{\mathcal{E}}=\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}\mathbf{e}_{l}\mathbf{e}_{l}^{\top}.$
Then,

$\displaystyle\|P_{\mathcal{E}}X\|^{2}_{F}=\|\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}\mathbf{e}_{l}\mathbf{e}_{l}^{\top}X\|^{2}_{F}=\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}\|\mathbf{e}_{l}^{\top}X\|^{2}_{2}=\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}\sum_{j=1}^{q}(\mathbf{e}_{l}^{\top}X^{j})^{2}.$

Fix any $l\in\mathrm{dim}(\mathcal{E})$ and $j\in[q].$ We have
$\mathbb{E}[\mathbf{e}_{l}^{\top}X^{j}]\overset{H_{0,\mathcal{V}}^{*}}{=}0$
and $\mathrm{Var}[\mathbf{e}_{l}^{\top}X^{j}]=\sigma^{2},$ where the former
follows by Lemma 9 since $H_{0,\mathcal{V}}^{*}$ implies $H_{0,\mathcal{V}}.$
Then, independence across $\mathbf{e}_{l}$ for
$l\in[\mathrm{dim}(\mathcal{E})]$ and the distributional assumptions on
$X^{j}$ imply
$\frac{1}{\sigma^{2}}\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}(\mathbf{e}_{l}^{\top}X^{j})^{2}\overset{H_{0,\mathcal{V}}^{*}}{\sim}\chi^{2}_{\mathrm{dim}(\mathcal{E})}.$
Finally, independence across $X^{j}$ for $j\in[q]$ gives
$\frac{1}{\sigma^{2}}\sum_{j=1}^{q}\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}(\mathbf{e}_{l}^{\top}X^{j})^{2}\overset{H_{0,\mathcal{V}}^{*}}{\sim}\chi^{2}_{d}.$

We next show
$\frac{1}{\sigma^{2}}\|P_{1}X\|^{2}_{F}\overset{H_{0,\mathcal{V}}^{*}}{\sim}\chi^{2}_{d^{*}}.$

$\displaystyle\|P_{1}X\|^{2}_{F}=\sum_{k\in\mathcal{K}}\|\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)X\|^{2}_{F}=\sum_{k\in\mathcal{K}}\sum_{j=1}^{q}\|\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)X^{j}\|^{2}_{2},$

where the first equality holds by the orthogonality across
$I_{\mathcal{C}_{k}}$ for $k\in\mathcal{K}$ and the fact that
$\mathrm{Col}\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)\subset\mathrm{Col}\left(I_{\mathcal{C}_{k}}\right)$
for each $k\in\mathcal{K}.$ Fix any $k\in\mathcal{K}$ and $j\in[q],$ and note
that

$\displaystyle\frac{1}{\sigma^{2}}\|\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)X^{j}\|^{2}_{2}=\frac{X^{j}}{\sigma}^{\top}\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)\frac{X^{j}}{\sigma},$

where $\frac{X^{j}}{\sigma}\sim\mathcal{N}(\mu^{j},I_{n}),$ and
$I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}$
is idempotent and has rank $|\mathcal{C}_{k}|-1.$ It follows that

$\displaystyle\frac{1}{\sigma^{2}}\|\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)X^{j}\|^{2}_{2}\sim\chi_{|\mathcal{C}_{k}|-1}^{2}\left(\frac{1}{\sigma^{2}}{\mu^{j}}^{\top}\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)\mu^{j}\right)\overset{H_{0,\mathcal{V}}^{*}}{=}\chi_{|\mathcal{C}_{k}|-1}^{2}$

since
$\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)\mu^{j}\overset{H_{0,\mathcal{V}}^{*}}{=}0_{n}$
by Lemma 14. Note that
$\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)X^{j}$
for $k\in\mathcal{K}$ are independent by orthogonality across
$\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)$
for $k\in\mathcal{K}$ and the distributional assumptions on $X^{j}.$ It
follows that

$\displaystyle\frac{1}{\sigma^{2}}\sum_{k=1}^{K}\|\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)X^{j}\|^{2}_{2}\overset{H_{0,\mathcal{V}}^{*}}{\sim}\chi^{2}_{\sum_{k\in\mathcal{K}}(|\mathcal{C}_{k}|-1)}.$

Then, independence across $X^{j}$ for $j\in[q]$ gives

$\displaystyle\frac{1}{\sigma^{2}}\sum_{j=1}^{q}\sum_{k=1}^{K}\|\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)X^{j}\|^{2}_{2}\overset{H_{0,\mathcal{V}}^{*}}{\sim}\chi^{2}_{d^{*}}.$

Finally, we show that $\|P_{\mathcal{E}}X\|^{2}_{F}$ and $\|P_{1}X\|^{2}_{F}$
are independent. Note that $P_{\mathcal{E}}$ and $P_{1}$ are orthogonal by
Lemma 13, so for each $j\in[q],$ the distributional assumptions on $X^{j}$
imply independence between $P_{\mathcal{E}}X^{j}$ and $P_{1}X^{j}.$ Then,
independence across $X^{j}$ for $j\in[q]$ implies independence across
$\left(P_{\mathcal{E}}X^{j},P_{1}X^{j}\right)$ for $j\in[q],$ which then
implies that $\|P_{\mathcal{E}}X\|^{2}_{F}$ and $\|P_{1}X\|^{2}_{F}$ are
independent. Thus, by definition of the $F$ distribution, we have

$\displaystyle\frac{\frac{1}{\sigma^{2}}\|P_{\mathcal{E}}X\|^{2}_{F}/d}{\frac{1}{\sigma^{2}}\|P_{1}X\|^{2}_{F}/d^{*}}\overset{H_{0,\mathcal{V}}^{*}}{\sim}F_{d,d^{*}}.$

∎

######  Lemma 16.

Suppose the cluster assignments and the set $\mathcal{V}$ are pre-specified.
Then,

$T^{*}\perp\\!\\!\\!\perp Z^{*}$

under $H_{0,\mathcal{V}}^{*}.$

###### Proof.

By Lemma 15, we have

$T^{*}\overset{H_{0,\mathcal{V}}^{*}}{\sim}F_{d,d^{*}}.$

We prove $T^{*}$ and $Z^{*}$ are independent under $H_{0,\mathcal{V}}^{*}$ by
showing that

$\displaystyle T^{*}\mid
Z^{*}\overset{H_{0,\mathcal{V}}^{*}}{\sim}F_{d,d^{*}}.$ (37)

To show (37), we repeatedly use the fact that for random quantities
$Y_{1},Y_{2},$ and $Y_{3},$

$\displaystyle Y_{3}\perp\\!\\!\\!\perp(Y_{1},Y_{2})\implies
Y_{3}\perp\\!\\!\\!\perp Y_{1}\>|\>Y_{2}.$ (38)

For each $j\in[q],$ the distributional assumptions on $X^{j}$ and the
orthogonality across $P_{\mathcal{E}},$ $P_{1},$ and $P_{2}$ give independence
across $P_{\mathcal{E}}X^{j},$ $P_{1}X^{j},$ and $P_{2}X^{j}.$ Furthermore,
the independence across $X^{j}$ for $j\in[q]$ implies independence across
$(P_{\mathcal{E}}X^{j},P_{1}X^{j},P_{2}X^{j})$ for $j\in[q].$ As a result,
$P_{\mathcal{E}}X,$ $P_{1}X,$ and $P_{2}X$ are independent, so (37) can be
equivalently written as

$\displaystyle T^{*}\ \ |\ \
\left(\frac{P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}},\ \
\frac{P_{1}X}{\|P_{1}X\|_{F}},\ \
\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}\right)\overset{H_{0,\mathcal{V}}^{*}}{\sim}F_{d,d^{*}},$
(39)

where we use the fact in (38). Next, note that independence between
$P_{\mathcal{E}}X$ and $P_{1}X$ gives

$\displaystyle\left(\|P_{\mathcal{E}}X\|_{F}^{2},\ \
\frac{P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}}\right)\perp\\!\\!\\!\perp\left(\|P_{1}X\|_{F}^{2},\
\ \frac{P_{1}X}{\|P_{1}X\|_{F}}\right).$ (40)

Further note that there exist orthonormal bases
$\\{\mathbf{e}_{l}\\}_{l=1}^{\mathrm{dim}(\mathcal{E})}$ and
$\\{\mathbf{e}^{\prime}_{l}\\}_{l=1}^{\sum_{k\in\mathcal{K}}|\mathcal{C}_{k}|-|\mathcal{K}|}$
of the column spaces of $P_{\mathcal{E}}$ and $P_{1},$ respectively, so we can
write
$P_{\mathcal{E}}=\sum_{l=1}^{\mathrm{dim}(\mathcal{E})}\mathbf{e}_{l}\mathbf{e}_{l}^{\top}$
and
$P_{1}=\sum_{l=1}^{\sum_{k\in\mathcal{K}}|\mathcal{C}_{k}|-|\mathcal{K}|}\mathbf{e}^{\prime}_{l}{\mathbf{e}^{\prime}_{l}}^{\top}.$
For each $l\in[\mathrm{dim}(\mathcal{E})],$
$\mu^{\top}\mathbf{e}_{l}\overset{H_{0,\mathcal{V}}^{*}}{=}\mathbf{0}_{q}$ by
Lemma 9 since $H_{0,\mathcal{V}}^{*}$ implies $H_{0,\mathcal{V}}.$
Furthermore,
$\mu^{\top}{\mathbf{e}^{\prime}_{l}}\overset{H_{0,\mathcal{V}}^{*}}{=}\mathbf{0}_{q}$
for each $l\in[m-K]$ by Lemma 14 since
$\mathbf{e}^{\prime}_{l}=\sum_{k\in\mathcal{K}}\left(I_{\mathcal{C}_{k}}-\frac{\mathbf{1}_{\mathcal{C}_{k}}\mathbf{1}_{\mathcal{C}_{k}}^{\top}}{|\mathcal{C}_{k}|}\right)a$
for some $a\in\mathbb{R}^{n}.$ Thus, by Lemma 10, we have

$\displaystyle\|P_{\mathcal{E}}X\|_{F}^{2}\perp\\!\\!\\!\perp\frac{P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}}\hskip
10.00002pt\text{and}\hskip
10.00002pt\|P_{1}X\|_{F}^{2}\perp\\!\\!\\!\perp\frac{P_{1}X}{\|P_{1}X\|_{F}}$
(41)

under $H_{0,\mathcal{V}}^{*}.$ Then, (40) and (41) imply

$\displaystyle\left(\|P_{\mathcal{E}}X\|_{F}^{2},\ \
\|P_{1}X\|_{F}^{2}\right)\perp\\!\\!\\!\perp\left(\frac{P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}},\
\ \frac{P_{1}X}{\|P_{1}X\|_{F}}\right),$

allowing (39) to be equivalently written as

$\displaystyle T^{*}\ \ |\ \
\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}\overset{H_{0,\mathcal{V}}^{*}}{\sim}F_{d,d^{*}}.$
(42)

Finally,
$T^{*}\perp\\!\\!\\!\perp\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}$
under $H_{0,\mathcal{V}}^{*}$ since
$T^{*}=\frac{\frac{1}{\sigma^{2}}\|P_{\mathcal{E}}X\|^{2}_{F}/d}{\frac{1}{\sigma^{2}}\|P_{1}X\|^{2}_{F}/d^{*}},$
where
$\frac{1}{\sigma^{2}}\|P_{\mathcal{E}}X\|^{2}_{F}\overset{H_{0,\mathcal{V}}^{*}}{\sim}\chi^{2}_{d},$
$\frac{1}{\sigma^{2}}\|P_{1}X\|^{2}_{F}\overset{H_{0,\mathcal{V}}^{*}}{\sim}\chi^{2}_{d^{*}},$
and
$\|P_{\mathcal{E}}X\|^{2}_{F}\perp\\!\\!\\!\perp\frac{1}{\sigma^{2}}\|P_{1}X\|^{2}_{F}$
under $H_{0,\mathcal{V}}^{*}.$ Therefore, (42) is equivalent to

$\displaystyle T^{*}\overset{H_{0,\mathcal{V}}^{*}}{\sim}F_{d,d^{*}},$ (43)

which holds by Lemma 15. ∎

We now show (36). In the remainder of this section, we write
$H^{*}_{0,\mathcal{V}(X)}(\mathcal{C}(X))$ to make explicit the dependence of
$H^{*}_{0,\mathcal{V}}$ on $\mathcal{C}(X)$ and $\mathcal{V}(X).$ Fix any
realization $\left(Z^{0},\mathcal{C}^{0},\mathcal{V}^{0}\right)$ of
$\left(Z^{*},\mathcal{C}(X),\mathcal{V}(X)\right),$ and define
$\tilde{\mathcal{S}}^{*}_{J}(\mathcal{C}^{0},\mathcal{V}^{0})=\tilde{\mathcal{S}^{*}}(\mathcal{C}^{0})\cap\tilde{S}_{\mathcal{V}}^{*}(\mathcal{V}^{0}),$
where

$\displaystyle\tilde{\mathcal{S}}^{*}(\mathcal{C}^{0})=\\{(\psi,z)\in[0,\infty)\times(\mathbb{R}^{n\times
q}\times\mathbb{R}^{n\times q}\times(0,\infty)\times\mathbb{R}^{n\times
q}):\mathcal{C}(\tilde{x}^{*}(\psi,z))=\mathcal{C}^{0}\\}$

and

$\displaystyle\tilde{\mathcal{S}}^{*}_{\mathcal{V}}(\mathcal{V}^{0})=\\{(\psi,z)\in[0,\infty)\times(\mathbb{R}^{n\times
q}\times\mathbb{R}^{n\times q}\times(0,\infty)\times\mathbb{R}^{n\times
q}):\mathcal{V}(\tilde{x}^{*}(\psi,z))=\mathcal{V}^{0}\\},$

where $\tilde{x}^{*}:[0,\infty)\times(\mathbb{R}^{n\times
q}\times\mathbb{R}^{n\times q}\times(0,\infty)\times\mathbb{R}^{n\times
q})\rightarrow\mathbb{R}^{n\times q},$

$\tilde{x}^{*}(\psi,(z_{1},z_{2},z_{3},z_{4}))=\sqrt{z_{3}}\left(\sqrt{\frac{\psi}{\psi+r^{*}}}z_{1}+\sqrt{\frac{r^{*}}{\psi+r^{*}}}z_{2}\right)+z_{4}.$

Let $f_{T^{*}}$ be the PDF of $T^{*}$ in the setting where the cluster
assignments and the set $\mathcal{V}$ are pre-specified; similarly define
$f^{*}_{T^{*},Z^{*}}$ as the joint PDF of $T^{*}$ and $Z^{*},$ and $f_{Z^{*}}$
as the PDF of $Z^{*}.$ Note that

$\displaystyle\mathcal{C}(X)=\mathcal{C}^{0}\text{ and
}\mathcal{V}(X)=\mathcal{V}^{0}\iff(T^{*},Z^{*})\in\tilde{\mathcal{S}}^{*}_{J}(\mathcal{C}^{0},\mathcal{V}^{0}).$
(44)

Then,

$\displaystyle h^{*}(t,Z^{0},\mathcal{C}^{0},\mathcal{V}^{0})$
$\displaystyle=f_{T^{*}\mid
Z^{*}=Z^{0},\;\mathcal{C}(X)=\mathcal{C}^{0},\;\mathcal{V}(X)=\mathcal{V}^{0}}(t)$
(45) $\displaystyle=f_{T^{*}\mid
Z^{*}=Z^{0},\;(T^{*},Z^{*})\in\tilde{\mathcal{S}}^{*}_{J}(\mathcal{C}^{0},\mathcal{V}^{0})}(t)$
(46) $\displaystyle\propto
f_{T^{*},Z^{*}\mid(T^{*},Z^{*})\in\tilde{\mathcal{S}}^{*}_{J}(\mathcal{C}^{0},\mathcal{V}^{0})}(t,Z^{0})$
$\displaystyle\overset{H^{*}_{0,\mathcal{V}^{0}}(\mathcal{C}^{0})}{=}f_{T^{*}}(t)f_{Z^{*}}(Z^{0})\mathbbm{1}_{(t,Z^{0})\in\tilde{\mathcal{S}}^{*}_{J}(\mathcal{C}^{0},\mathcal{V}^{0})}$
(47) $\displaystyle\propto
f_{T^{*}}(t)\mathbbm{1}_{(t,Z^{0})\in\tilde{\mathcal{S}}^{*}_{J}(\mathcal{C}^{0},\mathcal{V}^{0})}$
(48)

where (45) follows from the definition of the function $h^{*},$ (46) follows
from the observation in (44), and (47) holds by Lemma 16. Thus, we have

$\displaystyle
h^{*}(t,Z^{*},\mathcal{C}(X),\mathcal{V}(X))\overset{H^{*}_{0,\mathcal{V}(X)}(\mathcal{C}(X))}{\propto}f_{T^{*}}(t)\mathbbm{1}_{(t,Z^{*})\in\mathcal{\tilde{S}}^{*}_{J}(\mathcal{C}(X),\mathcal{V}(X))}=f_{T^{*}}(t)\mathbbm{1}_{t\in\mathcal{S}^{*}_{J}},$

where the equality follows from the observation that

$\displaystyle(t,Z^{*})\in\mathcal{\tilde{S}}^{*}_{J}(\mathcal{C}(X),\mathcal{V}(X))\iff
t\in\mathcal{S}^{*}_{J}.$

By Lemma 15, we have that $f_{T^{*}}$ is the PDF of the $F_{d,d^{*}}$
distribution, and thus (36) holds.

To prove Theorem 5, recall that $\mathcal{V}$ is pre-specified in the setting
of Theorem 5. Then, $Q_{J}^{*}=Q^{*},$ and Theorem 5 immediately follows from
Theorem 7.

####  A.1.3 Proof of Proposition 2

Recall $x_{\sigma}(\psi)=\psi\cdot\frac{\sigma
P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}}+P_{\mathcal{E}}^{\perp}X=\psi
D+E,$ and fix any $i,i^{\prime}\in[n].$

$\displaystyle\left\lVert[x_{\sigma}(\psi)]_{i}-[x_{\sigma}(\psi)]_{i^{\prime}}\right\rVert_{2}^{2}$
$\displaystyle=\|\psi D_{i}+E_{i}-(\psi
D_{i^{\prime}}+E_{i^{\prime}})\|^{2}_{2}$
$\displaystyle=\|(D_{i}-D_{i^{\prime}})\psi+E_{i}-E_{i^{\prime}}\|_{2}^{2}$
$\displaystyle=\|\mathbf{d}_{ii^{\prime}}\psi+\mathbf{e}_{ii^{\prime}}\|_{2}^{2}$
$\displaystyle=\|\mathbf{d}_{ii^{\prime}}\|_{2}^{2}\psi^{2}+2\langle\mathbf{d}_{ii^{\prime}},\mathbf{e}_{ii^{\prime}}\rangle\psi+\|\mathbf{e}_{ii^{\prime}}\|^{2}_{2}$
$\displaystyle=\lambda_{ii^{\prime},1}\psi^{2}+\lambda_{ii^{\prime},2}\psi+\lambda_{ii^{\prime},3}.$

Fix any $i\in[n],l\in[K],$ and $j\in[J].$

$\displaystyle\|[x_{\sigma}(\psi)]_{i}-M_{l}^{(j-1)}(x_{\sigma}(\psi))\|_{2}^{2}$
$\displaystyle=\|{\psi D_{i}+E_{i}-\sum_{s=1}^{n}w_{l,s}^{(j-1)}\left(\psi
D_{s}+E_{s}\right)}\|_{2}^{2}$
$\displaystyle=\|(D_{i}-\sum_{s=1}^{n}w_{l,s}^{(j-1)}D_{s})\psi+E_{i}-\sum_{s=1}^{n}w_{l,s}^{(j-1)}E_{s}\|_{2}^{2}$
$\displaystyle=\|(D_{i}-M_{l}^{(j-1)}(D))\psi+E_{i}-M_{l}^{(j-1)}(E)\|_{2}^{2}$
$\displaystyle=\|\mathbf{d}_{ilj}\psi+\mathbf{e}_{ilj}\|_{2}^{2}$
$\displaystyle=\|\mathbf{d}_{ilj}\|_{2}^{2}\psi^{2}+2\langle\mathbf{d}_{ilj},\mathbf{e}_{ilj}\rangle\psi+\|\mathbf{e}_{ilj}\|^{2}_{2}$
$\displaystyle=\lambda_{ilj,1}\psi^{2}+\lambda_{ilj,2}\psi+\lambda_{ilj,3}.$

####  A.1.4 Proof of Proposition 4

Recall $x_{\sigma}(\psi)=\psi\frac{\sigma
P_{\mathcal{E}}X}{\|P_{\mathcal{E}}X\|_{F}}+P_{\mathcal{E}}^{\perp}X=\psi
D+E,$ and fix any $\mathbf{v}\in\mathcal{V}.$

$\displaystyle\|[x_{\sigma}(\psi)]^{\top}\mathbf{v}\|^{2}$
$\displaystyle=\|(\psi D+E)^{\top}\mathbf{v}\|^{2}_{2}$ $\displaystyle=\|\psi
D^{\top}\mathbf{v}+E^{\top}\mathbf{v}\|^{2}_{2}$
$\displaystyle=\|\psi\mathbf{d}_{\mathbf{v}}+\mathbf{e}_{\mathbf{v}}\|^{2}_{2}$
$\displaystyle=\|\mathbf{d}_{\mathbf{v}}\|_{2}^{2}\psi^{2}+2\langle\mathbf{d}_{\mathbf{v}},\mathbf{e}_{\mathbf{v}}\rangle\psi+\|\mathbf{e}_{\mathbf{v}}\|^{2}_{2}$
$\displaystyle=\lambda_{{\mathbf{v}},1}\psi^{2}+\lambda_{{\mathbf{v}},2}\psi+\lambda_{{\mathbf{v}},3}.$

####  A.1.5 Proof of Proposition 6

For the simplicity of notations, let
$u_{\psi}=\sqrt{\frac{\psi}{\psi+r^{*}}}.$ Fix any
$i,i^{\prime},i^{\prime\prime}\in\mathbb{N}.$ We first show

$\displaystyle\|[x^{*}(\psi)]_{i}-[x^{*}(\psi)]_{i^{\prime}}\|^{2}_{2}\leq\|[x^{*}(\psi)]_{i}-[x^{*}(\psi)]_{i^{\prime\prime}}\|^{2}_{2}\iff
f_{ii^{\prime}}(\psi)\leq f_{ii^{\prime\prime}}(\psi).$

Since $\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}>0,$ we have

$\displaystyle\frac{1}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]_{i}-[x^{*}(\psi)]_{i^{\prime}}\|^{2}_{2}$
$\displaystyle=\|(u_{\psi}A_{i}+\sqrt{1-u_{\psi}^{2}}B_{i}+\mathcal{C}_{i})-(u_{\psi}A_{i^{\prime}}+\sqrt{1-u_{\psi}^{2}}B_{i^{\prime}}+\mathcal{C}_{i^{\prime}})\|_{2}^{2}$
$\displaystyle=\|(A_{i}-A_{i^{\prime}})u_{\psi}+(B_{i}-B_{i^{\prime}})\sqrt{1-u^{2}_{\psi}}+\mathcal{C}_{i}-\mathcal{C}_{i^{\prime}}\|^{2}_{2}$
$\displaystyle=\|\mathbf{a}_{ii^{\prime}}u_{\psi}+\mathbf{b}_{ii^{\prime}}\sqrt{1-u^{2}_{\psi}}+\mathbf{c}_{ii^{\prime}}\|^{2}_{2}$
$\displaystyle=\|\mathbf{a}_{ii^{\prime}}\|_{2}^{2}u_{\psi}^{2}+\|\mathbf{b}_{ii^{\prime}}\|_{2}^{2}(1-u^{2}_{\psi})+\|\mathbf{c}_{ii^{\prime}}\|^{2}_{2}+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{b}_{ii^{\prime}}\rangle
u_{\psi}\sqrt{1-u^{2}_{\psi}}+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle
u_{\psi}$
$\displaystyle\qquad+2\langle\mathbf{b}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle\sqrt{1-u_{\psi}^{2}}$
$\displaystyle=(\|\mathbf{a}_{ii^{\prime}}\|_{2}^{2}-\|\mathbf{b}_{ii^{\prime}}\|_{2}^{2})u_{\psi}^{2}+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{b}_{ii^{\prime}}\rangle
u_{\psi}\sqrt{1-u^{2}_{\psi}}+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle
u_{\psi}+2\langle\mathbf{b}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle\sqrt{1-u_{\psi}^{2}}$
$\displaystyle\qquad+\|\mathbf{b}_{ii^{\prime}}\|^{2}_{2}+\|\mathbf{c}_{ii^{\prime}}\|^{2}_{2}.$

Substituting $u_{\psi}=\sqrt{\frac{\psi}{\psi+r^{*}}},$ we have

$\displaystyle\frac{1}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]_{i}-[x^{*}(\psi)]_{i^{\prime}}\|^{2}_{2}$
$\displaystyle=(\|\mathbf{a}_{ii^{\prime}}\|_{2}^{2}-\|\mathbf{b}_{ii^{\prime}}\|_{2}^{2})\frac{\psi}{\psi+r^{*}}+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{b}_{ii^{\prime}}\rangle\sqrt{\frac{\psi}{\psi+r^{*}}}\sqrt{\frac{r^{*}}{\psi+r^{*}}}+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle\sqrt{\frac{\psi}{\psi+r^{*}}}$
$\displaystyle\qquad+2\langle\mathbf{b}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle\sqrt{\frac{r^{*}}{\psi+r^{*}}}+\|\mathbf{b}_{ii^{\prime}}\|^{2}_{2}+\|\mathbf{c}_{ii^{\prime}}\|^{2}_{2}.$

Thus,

$\displaystyle\frac{\psi+r^{*}}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{\prime}(\psi)]_{i}-[x^{\prime}(\psi)]_{i^{\prime}}\|^{2}_{2}$
$\displaystyle=(\|\mathbf{a}_{ii^{\prime}}\|_{2}^{2}-\|\mathbf{b}_{ii^{\prime}}\|_{2}^{2})\psi+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{b}_{ii^{\prime}}\rangle\sqrt{r^{*}}\sqrt{\psi}+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle\sqrt{\psi}\sqrt{\psi+r^{*}}$
$\displaystyle\qquad+2\langle\mathbf{b}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle\sqrt{r^{*}}\sqrt{\psi+r^{*}}+(\|\mathbf{b}_{ii^{\prime}}\|^{2}_{2}+\|\mathbf{c}_{ii^{\prime}}\|^{2}_{2})(\psi+r^{*})$
$\displaystyle=(\|\mathbf{a}_{ii^{\prime}}\|_{2}^{2}+\|\mathbf{c}_{ii^{\prime}}\|_{2}^{2})\psi+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{b}_{ii^{\prime}}\rangle\sqrt{r^{*}}\sqrt{\psi}+2\langle\mathbf{a}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle\sqrt{\psi}\sqrt{\psi+r^{*}}$
$\displaystyle\qquad+2\langle\mathbf{b}_{ii^{\prime}},\mathbf{c}_{ii^{\prime}}\rangle\sqrt{r^{*}}\sqrt{\psi+r^{*}}+(\|\mathbf{b}_{ii^{\prime}}\|^{2}_{2}+\|\mathbf{c}_{ii^{\prime}}\|^{2}_{2})r^{*}$
$\displaystyle=\lambda_{ii^{\prime},1}\psi+\lambda_{ii^{\prime},2}\sqrt{\psi}+\lambda_{ii^{\prime},3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{ii^{\prime},4}\sqrt{\psi+r^{*}}+\lambda_{ii^{\prime},5}.$

Similarly, we have

$\frac{\psi+r^{*}}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]_{i}-[x^{*}(\psi)]_{i^{\prime\prime}}\|^{2}_{2}=\\\
\lambda_{ii^{\prime\prime},1}\psi+\lambda_{ii^{\prime\prime},2}\sqrt{\psi}+\lambda_{ii^{\prime\prime},3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{ii^{\prime\prime},4}\sqrt{\psi+r^{*}}+\lambda_{ii^{\prime\prime},5}.$

Then, since $\psi+r^{*}>0,$ it follows that

$\displaystyle\|[x^{*}(\psi)]_{i}-[x^{*}(\psi)]_{i^{\prime}}\|^{2}_{2}\leq\|[x^{*}(\psi)]_{i}-[x^{*}(\psi)]_{i^{\prime\prime}}\|^{2}_{2}\iff
f_{ii^{\prime}}(\psi)\leq f_{ii^{\prime\prime}}(\psi).$

Fix any $l,l^{\prime}\in[K].$ We next show

$\displaystyle\|[x^{*}(\psi)]_{i}-M_{l}^{(j-1)}(x^{*}(\psi))\|^{2}_{2}\leq\|[x^{*}(\psi)]_{i}-M_{l^{\prime}}^{(j-1)}(x^{*}(\psi))\|^{2}_{2}\iff
f_{ijl}(\psi)\leq f_{ijl^{\prime}}(\psi).$

Again, by $\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}>0,$ we have

$\displaystyle\frac{1}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]_{i}-M_{l}^{(j-1)}(x^{*}(\psi))\|^{2}_{2}$
$\displaystyle=\frac{1}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|{[x^{*}(\psi)]_{i}-\sum_{s=1}^{n}w_{l,s}^{(j-1)}[x^{*}(\psi)]_{s}}\|^{2}_{2}$
$\displaystyle=\|(u_{\psi}A_{i}+\sqrt{1-u_{\psi}^{2}}B_{i}+\mathcal{C}_{i})-\sum_{s=1}^{n}w_{l,s}^{(j-1)}(u_{\psi}A_{s}+\sqrt{1-u_{\psi}^{2}}B_{s}+\mathcal{C}_{s})\|^{2}_{2}$
$\displaystyle=\|(A_{i}-\sum_{s=1}^{n}w_{l,s}^{(j-1)}A_{s})u_{\psi}+(B_{i}-\sum_{s=1}^{n}w_{l,s}^{(j-1)}B_{s})\sqrt{1-u_{\psi}^{2}}$
$\displaystyle\qquad+\mathcal{C}_{i}-\sum_{s=1}^{n}w_{l,s}^{(j-1)}\mathcal{C}_{s}\|^{2}_{2}$
$\displaystyle=\|(A_{i}-M_{l}^{(j-1)}(A))u_{\psi}+(B_{i}-M_{l}^{(j-1)}(B))\sqrt{1-u_{\psi}^{2}}+\mathcal{C}_{i}-M_{l}^{(j-1)}(C)\|_{2}^{2}$
$\displaystyle=\|\mathbf{a}_{ijl}u_{\psi}+\mathbf{b}_{ijl}\sqrt{1-u_{\psi}^{2}}+\mathbf{c}_{ijl}\|^{2}_{2}$
$\displaystyle=\|\mathbf{a}_{ijl}\|_{2}^{2}u_{\psi}^{2}+\|\mathbf{b}_{ijl}\|_{2}^{2}(1-u^{2}_{\psi})+\|\mathbf{c}_{ijl}\|^{2}_{2}+2\langle\mathbf{a}_{ijl},\mathbf{b}_{ijl}\rangle
u_{\psi}\sqrt{1-u^{2}_{\psi}}+2\langle\mathbf{a}_{ijl},\mathbf{c}_{ijl}\rangle
u_{\psi}$
$\displaystyle\qquad+2\langle\mathbf{b}_{ijl},\mathbf{c}_{ijl}\rangle\sqrt{1-u_{\psi}^{2}}$
$\displaystyle=(\|\mathbf{a}_{ijl}\|_{2}^{2}-\|\mathbf{b}_{ijl}\|_{2}^{2})u_{\psi}^{2}+2\langle\mathbf{a}_{ijl},\mathbf{b}_{ijl}\rangle
u_{\psi}\sqrt{1-u^{2}_{\psi}}+2\langle\mathbf{a}_{ijl},\mathbf{c}_{ijl}\rangle
u_{\psi}+2\langle\mathbf{b}_{ijl},\mathbf{c}_{ijl}\rangle\sqrt{1-u_{\psi}^{2}}$
$\displaystyle\qquad+\|\mathbf{b}_{ijl}\|^{2}_{2}+\|\mathbf{c}_{ijl}\|^{2}_{2}.$

Substituting $u_{\psi}=\sqrt{\frac{\psi}{\psi+r^{*}}},$ we have

$\displaystyle\frac{1}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]_{i}-M_{l}^{(j-1)}(x^{*}(\psi))\|^{2}_{2}$
$\displaystyle=(\|\mathbf{a}_{ijl}\|_{2}^{2}-\|\mathbf{b}_{ijl}\|_{2}^{2})\frac{\psi}{\psi+r^{*}}+2\langle\mathbf{a}_{ijl},\mathbf{b}_{ijl}\rangle\sqrt{\frac{\psi}{\psi+r^{*}}}\sqrt{\frac{r^{*}}{\psi+r^{*}}}+2\langle\mathbf{a}_{ijl},\mathbf{c}_{ijl}\rangle\sqrt{\frac{\psi}{\psi+r^{*}}}$
$\displaystyle\qquad+2\langle\mathbf{b}_{ijl},\mathbf{c}_{ijl}\rangle\sqrt{\frac{r^{*}}{\psi+r^{*}}}+\|\mathbf{b}_{ijl}\|^{2}_{2}+\|\mathbf{c}_{ijl}\|^{2}_{2}.$

Thus,

$\displaystyle\frac{\psi+r^{*}}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]_{i}-M_{l}^{(j-1)}(x^{*}(\psi))\|^{2}_{2}$
$\displaystyle=(\|\mathbf{a}_{ijl}\|_{2}^{2}-\|\mathbf{b}_{ijl}\|_{2}^{2})\psi+2\langle\mathbf{a}_{ijl},\mathbf{b}_{ijl}\rangle\sqrt{r^{*}}\sqrt{\psi}+2\langle\mathbf{a}_{ijl},\mathbf{c}_{ijl}\rangle\sqrt{\psi}\sqrt{\psi+r^{*}}$
$\displaystyle\qquad+2\langle\mathbf{b}_{ijl},\mathbf{c}_{ijl}\rangle\sqrt{r^{*}}\sqrt{\psi+r^{*}}+(\|\mathbf{b}_{ijl}\|^{2}_{2}+\|\mathbf{c}_{ijl}\|^{2}_{2})(\psi+r^{*})$
$\displaystyle=(\|\mathbf{a}_{ijl}\|_{2}^{2}+\|\mathbf{c}_{ijl}\|_{2}^{2})\psi+2\langle\mathbf{a}_{ijl},\mathbf{b}_{ijl}\rangle\sqrt{r^{*}}\sqrt{\psi}+2\langle\mathbf{a}_{ijl},\mathbf{c}_{ijl}\rangle\sqrt{\psi}\sqrt{\psi+r^{*}}$
$\displaystyle\qquad+2\langle\mathbf{b}_{ijl},\mathbf{c}_{ijl}\rangle\sqrt{r^{*}}\sqrt{\psi+r^{*}}+(\|\mathbf{b}_{ijl}\|^{2}_{2}+\|\mathbf{c}_{ijl}\|^{2}_{2})r^{*}$
$\displaystyle=\lambda_{ijl,1}\psi+\lambda_{ijl,2}\sqrt{\psi}+\lambda_{ijl,3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{ijl,4}\sqrt{\psi+r^{*}}+\lambda_{ijl,5}.$

Similarly, we have

$\frac{\psi+r^{*}}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]_{i}-M_{l^{\prime}}^{(j-1)}(x^{*}(\psi))\|^{2}_{2}=\\\
\lambda_{ijl^{\prime},1}\psi+\lambda_{ijl^{\prime},2}\sqrt{\psi}+\lambda_{ijl^{\prime},3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{ijl^{\prime},4}\sqrt{\psi+r^{*}}+\lambda_{ijl^{\prime},5}.$

Then, since $\psi+r^{*}>0,$ it follows that

$\displaystyle\|[x^{*}(\psi)]_{i}-M_{l}^{(j-1)}(x^{*}(\psi))\|^{2}_{2}\leq\|[x^{*}(\psi)]_{i}-M_{l^{\prime}}^{(j-1)}(x^{*}(\psi))\|^{2}_{2}\iff
f_{ijl}(\psi)\leq f_{ijl^{\prime}}(\psi).$

####  A.1.6 Proof of Proposition 8

For the simplicity of notations, let
$u_{\psi}=\sqrt{\frac{\psi}{\psi+r^{*}}}.$ Fix any
$\mathbf{v},\mathbf{v}^{\prime}\in\mathbb{R}^{n}.$ We first show

$\displaystyle\|[x^{*}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}\leq\|[x^{*}(\psi)]^{\top}\mathbf{v}^{\prime}\|_{2}^{2}\iff
h_{\mathbf{v}}(\psi)\leq h_{\mathbf{v}^{\prime}}(\psi).$

Since $\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}>0,$ we have

$\displaystyle\frac{1}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}$
$\displaystyle=\|(u_{\psi}A+\sqrt{1-u_{\psi}^{2}}B+C)^{\top}\mathbf{v}\|^{2}_{2}$
$\displaystyle=\|A^{\top}\mathbf{v}u_{\psi}+B^{\top}\mathbf{v}\sqrt{1-u_{\psi}^{2}}+C^{\top}\mathbf{v}\|^{2}_{2}$
$\displaystyle=\|\mathbf{a}_{\mathbf{v}}u_{\psi}+\mathbf{b}_{\mathbf{v}}\sqrt{1-u_{\psi}^{2}}+\mathbf{c}_{\mathbf{v}}\|^{2}_{2}$
$\displaystyle=\|\mathbf{a}_{\mathbf{v}}\|_{2}^{2}u_{\psi}^{2}+\|\mathbf{b}_{\mathbf{v}}\|_{2}^{2}(1-u_{\psi}^{2})+\|\mathbf{c}_{\mathbf{v}}\|_{2}^{2}+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{b}_{\mathbf{v}}\rangle
u_{\psi}\sqrt{1-u_{\psi}^{2}}+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle
u_{\psi}+2\langle\mathbf{b}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle\sqrt{1-u_{\psi}^{2}}$
$\displaystyle=(\|\mathbf{a}_{\mathbf{v}}\|_{2}^{2}-\|\mathbf{b}_{\mathbf{v}}\|_{2}^{2})u_{\psi}^{2}+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{b}_{\mathbf{v}}\rangle
u_{\psi}\sqrt{1-u_{\psi}^{2}}+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle
u_{\psi}+2\langle\mathbf{b}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle\sqrt{1-u_{\psi}^{2}}+\|\mathbf{b}_{\mathbf{v}}\|_{2}^{2}+\|\mathbf{c}_{\mathbf{v}}\|^{2}_{2}$

Substituting $u_{\psi}=\sqrt{\frac{\psi}{\psi+r^{*}}},$ we have

$\displaystyle\frac{1}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}$
$\displaystyle=(\|\mathbf{a}_{\mathbf{v}}\|_{2}^{2}-\|\mathbf{b}_{\mathbf{v}}\|_{2}^{2})\frac{\psi}{\psi+r^{*}}+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{b}_{\mathbf{v}}\rangle\sqrt{\frac{\psi}{\psi+r^{*}}}\sqrt{\frac{r^{*}}{\psi+r^{*}}}+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle\sqrt{\frac{\psi}{\psi+r^{*}}}$
$\displaystyle\qquad+2\langle\mathbf{b}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle\sqrt{\frac{r^{*}}{\psi+r^{*}}}+\|\mathbf{b}_{\mathbf{v}}\|_{2}^{2}+\|\mathbf{c}_{\mathbf{v}}\|^{2}_{2}.$

Thus,

$\displaystyle\frac{\psi+r^{*}}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}$
$\displaystyle=(\|\mathbf{a}_{\mathbf{v}}\|_{2}^{2}-\|\mathbf{b}_{\mathbf{v}}\|_{2}^{2})\psi+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{b}_{\mathbf{v}}\rangle\sqrt{r^{*}}\sqrt{\psi}+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle\sqrt{\psi}\sqrt{\psi+r^{*}}$
$\displaystyle\qquad+2\langle\mathbf{b}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle\sqrt{r^{*}}\sqrt{\psi+r^{*}}+(\|\mathbf{b}_{\mathbf{v}}\|_{2}^{2}+\|\mathbf{c}_{\mathbf{v}}\|^{2}_{2})(\psi+r^{*})$
$\displaystyle=(\|\mathbf{a}_{\mathbf{v}}\|_{2}^{2}+\|\mathbf{c}_{\mathbf{v}}\|_{2}^{2})\psi+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{b}_{\mathbf{v}}\rangle\sqrt{r^{*}}\sqrt{\psi}+2\langle\mathbf{a}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle\sqrt{\psi}\sqrt{\psi+r^{*}}$
$\displaystyle\qquad+2\langle\mathbf{b}_{\mathbf{v}},\mathbf{c}_{\mathbf{v}}\rangle\sqrt{r^{*}}\sqrt{\psi+r^{*}}+(\|\mathbf{b}_{\mathbf{v}}\|_{2}^{2}+\|\mathbf{c}_{\mathbf{v}}\|_{2}^{2})r^{*}.$
$\displaystyle=\lambda_{v,1}\psi+\lambda_{v,2}\sqrt{\psi}+\lambda_{v,3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{v,4}\sqrt{\psi+r^{*}}+\lambda_{v,5}.$
(49)

Similarly, we have

$\frac{\psi+r^{*}}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]^{\top}\mathbf{v}^{\prime}\|_{2}^{2}=\lambda_{\mathbf{v}^{\prime},1}\psi+\lambda_{\mathbf{v}^{\prime},2}\sqrt{\psi}+\lambda_{\mathbf{v}^{\prime},3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{\mathbf{v}^{\prime},4}\sqrt{\psi+r^{*}}+\lambda_{\mathbf{v}^{\prime},5}.$

Then, since $\psi+r^{*}>0,$ it follows that

$\displaystyle\|[x^{*}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}\leq\|[x^{*}(\psi)]^{\top}\mathbf{v}^{\prime}\|_{2}^{2}\iff
h_{\mathbf{v}}(\psi)\leq h_{\mathbf{v}^{\prime}}(\psi).$

Fix any $\mathbf{v}\in\mathbb{R}^{n}$ and $t>0.$ We next show

$\displaystyle\|[x^{*}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}\leq t\iff
h_{\mathbf{v}}(\psi)\leq h(\psi).$

By (A.1.6), we have

$\frac{\psi+r^{*}}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}=h_{\mathbf{v}}(\psi).$

Then,

$\displaystyle\|[x^{*}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}\leq t$
$\displaystyle\iff\frac{\psi+r^{*}}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\|[x^{*}(\psi)]^{\top}\mathbf{v}\|_{2}^{2}\leq\frac{t}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}\psi+\frac{r^{*}t}{\|P_{\mathcal{E}}X\|_{F}^{2}+\|P_{1}X\|_{F}^{2}}$
$\displaystyle\iff h_{\mathbf{v}}(\psi)\leq h(\psi).$

###  A.2 Notes on implementation

All of the implementation is done in `R`. Parts of the implementation of the
proposed methods have been adapted from the source code of the package
`KmeansInference` of Chen and Witten [2023] or call its functions—more details
can be found in the codes. In the rest of this section, we elaborate on
various aspects of the implementation of the proposed tests.

####  A.2.1 The proposed test of Section 3.2

##### Computation of $\mathrm{dim}(\mathcal{E})$

A challenge in computing $\mathrm{dim}(\mathcal{E})$ given a set of vectors
$\\{\mathbf{v}_{k,k^{\prime}}:(k,k^{\prime})\in\mathcal{V}\\}$ lies in finite
precision. For instance, it may be the case that two linearly dependent
vectors are numerically linearly independent due to finite precision. To
address this phenomenon, we compute $\mathrm{dim}(\mathcal{E})$ differently
depending on the value of $|\mathcal{V}|.$

  * •

If $|\mathcal{V}|=\binom{K}{2},$ then we know that
$\mathrm{dim}(\mathcal{E})=K-1$ since the set
$\\{\mathbf{v}_{k,k+1}:k\in[K-1]\\}$ forms a basis for
$\mathrm{dim}(\mathcal{E})$ by Lemma 17 below.

  * •

If $|\mathcal{V}|<\binom{K}{2},$ we resort to numerical methods for computing
$\mathrm{dim}(\mathcal{E}).$ We use the function `fast.svd` from the package
`corpcor` for computing the condensed singular value decomposition (SVD) that
gives the condensed SVD $U\Sigma W^{\top}$ of $V,$ where $V$ is the matrix
whose columns consist of the vectors in
$\\{\mathbf{v}_{k,k^{\prime}}:(k,k^{\prime})\in\mathcal{V}\\}.$ In the case
where $V$ does not have full rank, it is likely to be the case that $V$ still
has full numerical rank due to finite precision. To account for finite
precision, we set the rank of $V,$ i.e., $\mathrm{dim}(\mathcal{E}),$ to be
the number of diagonal entries of $\Sigma,$ which corresponds to the number of
“nonzero” singular values of $V,$ where the default threshold value of the
function `fast.svd` is used for determining if a singular value is to be
treated as zero.

##### Computation of $P_{\mathcal{E}}$

To be consistent with the computation of $\mathrm{dim}(\mathcal{E})$ discussed
above, we compute $P_{\mathcal{E}}$ differently depending on the value of
$|\mathcal{V}|.$

  * •

If $|\mathcal{V}|=\binom{K}{2},$ we compute the projection matrix
$P_{\mathcal{E}}$ by setting
$P_{\mathcal{E}}=\widetilde{U}\widetilde{U}^{\top},$ where $\widetilde{U}$ is
an orthogonal matrix whose columns are generated by the Gram-Schmidt
orthogonalization procedure applied to the columns of
$\begin{bmatrix}v_{1,2}&\cdots&v_{K-1,K}\end{bmatrix},$ using the function
`gramSchmidt` from the package `pracma`.

  * •

If $|\mathcal{V}|<\binom{K}{2},$ we compute $P_{\mathcal{E}}$ by setting
$P_{\mathcal{E}}=UU^{\top},$ where $U$ is as defined above.

Here, we state and prove Lemma 17, which is referred to in the discussion
above.

######  Lemma 17.

Suppose $|\mathcal{V}|=\binom{K}{2}.$ Then, the set
$\left\\{v_{k,k+1}:k\in[K-1]\right\\}$ forms a basis of $\mathcal{E}.$

###### Proof.

Note that if $|\mathcal{V}|=\binom{K}{2},$ then
$\mathcal{E}=\mathrm{span}\\{v_{k,k^{\prime}}:k<k^{\prime}\in[K]\\}.$ For any
$k,k^{\prime}\in[K]$ such that $k<k^{\prime},$ note that

$\displaystyle\mathbf{v}_{k,k^{\prime}}$