[]{}

# Space Complexity of Euclidean Clustering

Xiaoyi Zhu<EMAIL_ADDRESS>School of Data Science, Fudan University,
China. Yuxiang Tian<EMAIL_ADDRESS>School of Data Science, Fudan
University, China. Lingxiao Huang 55footnotemark: 5<EMAIL_ADDRESS>State Key Laboratory of Novel Software Technology, Nanjing University, China.
Zengfeng Huang<EMAIL_ADDRESS>School of Data Science, Fudan University,
China.Corresponding Author.

###### Abstract

The $(k,z)$-Clustering problem in Euclidean space $\mathbb{R}^{d}$ has been
extensively studied. Given the scale of data involved, compression methods for
the Euclidean $(k,z)$-Clustering problem, such as data compression and
dimension reduction, have received significant attention in the literature.
However, the space complexity of the clustering problem, specifically, the
number of bits required to compress the cost function within a multiplicative
error $\varepsilon$, remains unclear in existing literature.

This paper initiates the study of space complexity for Euclidean
$(k,z)$-Clustering and offers both upper and lower bounds. Our space bounds
are nearly tight when $k$ is constant, indicating that storing a coreset, a
well-known data compression approach, serves as the optimal compression
scheme. Furthermore, our lower bound result for $(k,z)$-Clustering establishes
a tight space bound of $\Theta(nd)$ for terminal embedding, where $n$
represents the dataset size. Our technical approach leverages new geometric
insights for principal angles and discrepancy methods, which may hold
independent interest.

###### Contents

  1. 1 Introduction
    1. 1.1 Problem Definition and Our Results
    2. 1.2 Technical Overview
    3. 1.3 Other Related Work
  2. 2 Proof of Theorem 1.2: Space Upper Bounds
  3. 3 Proof of Theorem 1.3: Space Lower Bounds
    1. 3.1 Proof of Theorem 1.3
    2. 3.2 Proof of Lemma 3.4: Principal Angles to Cost Difference
    3. 3.3 Proof of Lemma 3.5: Construction of A Large Family $\mathcal{P}$
    4. 3.4 Extension to General $z\geq 1$
    5. 3.5 Extension to General $k\geq 2$
  4. 4 Application to Space Lower Bound for Terminal Embedding
  5. 5 Conclusions and Future Work

##  1 Introduction

Clustering problems are fundamental in theoretical computer science and
machine learning with various applications [3, 13, 38]. An important class of
clustering is called Euclidean $(k,z)$-Clustering where, given a dataset
$P\subset\mathbb{R}^{d}$ of $n$ points and a $k\geq 1$, the goal is to find a
center set $C\subset\mathbb{R}^{d}$ of $k$ points that minimizes the cost
$\operatorname{cost}_{z}(P,C):=\sum_{p\in P}d(p,C)^{z}$. Here,
$d^{z}(p,C)=\min_{c\in C}d^{z}(p,c)$ is the $z$-th power Euclidean distance of
$p$ to $C$. Well-known examples of $(k,z)$-Clustering include $k$-Median (when
$z=1$) and $k$-Means (when $z=2$).

In many real-world scenarios, the dataset $P$ is large and the dimension $d$
is high, and it is desirable to compress $P$ to reduce storage and
computational requirements in order to solve the underlying clustering problem
efficiently. Previous studies have proposed two approaches: data compression
and dimension reduction. On one hand, coresets have been proposed as a
solution to data compression [25] – a coreset is a small representative subset
$S$ that approximately preserves the clustering cost for all possible center
sets. Recent research has focused on developing efficient coresets [44, 14,
15, 16, 29], showing that the coreset size remains independent of both the
size $n$ of dataset and the dimension $d$. On the other hand, dimension
reduction methods have also proven to be effective for $(k,z)$-Clustering,
including techniques like Johnson-Lindenstrauss (JL) [39, 10] and terminal
embedding [42, 28]. Specifically, terminal embedding (Definition 1.4), which
projects a dataset $P$ to a low-dimensional space while approximately
preserving all pairwise distances between $P$ and $\mathbb{R}^{d}$, is the key
for removing the size dependence on $d$ for coreset [28, 14].

While the importance of compression for clustering has been widely
acknowledged, the literature currently lacks clarity regarding the space
complexity of the clustering problem itself. Specifically, one may want to
know how many bits are required to compress the cost function. Space
complexity, a fundamental factor in theoretical computer science, serves as a
measure of the complexity of the cost function. Previous research has
investigated the space complexity for various other problems, including
approximate nearest neighbor [31], inner products [2], Euclidean metric
compression [32], and graph cuts [9].

To investigate the space complexity of the $(k,z)$-Clustering problem, one
initial approach is to utilize a coreset $S$, which yields a space requirement
of $\tilde{O}(|S|\cdot d)$ using standard quantization methods (see Theorem
1.2 in the paper). Here the $d$ factor arises from preserving all coordinates
of each point in the coreset $S$. One might wonder if it is possible t combine
the benefits of coreset construction and dimension reduction to eliminate the
dependence on the dimension $d$ in terms of space requirements. This leads to
a natural question: “Is it possible to obtain an $|S|\cdot o(d)$ bound?
Additionally, is coreset the most efficient compression scheme for the
$(k,z)$-Clustering problem?” Perhaps surprisingly, we show that
$\tilde{\Omega}(|S|\cdot d)$ is necessary for interesting parameter regimes
(see Theorem 1.3 in the paper). This means a quantized coreset is optimal and
dimensionality reduction does not help for space complexity. The proof of the
lower bound for space complexity is our main contribution, which encounters
more technical challenges. Unlike upper bounds, existing lower bounds for
coresets do not directly translate into lower bounds for space complexity
since compression approaches can go beyond simply storing a subset of points
as a coreset. Overall, the study of space complexity is intricately connected
to the optimality of coresets and poses technical difficulties.

###  1.1 Problem Definition and Our Results

In this paper, we initiate the study of the space complexity for the Euclidean
$(k,z)$-Clustering problem. We first formally define the notion of space
complexity. Assume that $P\subseteq[\Delta]^{d}$ for some integer $\Delta\geq
1$, i.e., every $p\in P$ is a grid point in
$[\Delta]^{d}=\left\\{1,2,\ldots,\Delta\right\\}^{d}$. This assumption is
standard in the literature, e.g., for clustering [7, 27], facility location
[18], minimum spanning tree [24], and the max-cut problem [11], and necessary
for analyzing the space complexity. 111We need such an assumption to ensure
that the precision of every coordinate of $p\in P$ is bounded. Otherwise, when
$P$ contains a unique point $p\in\mathbb{R}^{d}$, we need to maintain all
coordinates of $p$ such that the information of
$\mathrm{cost}_{z}(P,\\{p\\})=0$ is preserved. Then if the precision of $p$
can be arbitrarily large, the space complexity is unlimited.  Let
$\mathcal{C}$ denote the collection of all $k$-center sets in
$\mathbb{R}^{d}$, i.e.,
$\mathcal{C}:=\left\\{C\subset\mathbb{R}^{d}:|C|=k\right\\}$. An
$\varepsilon$-sketch for $P$ is a data structure $\mathcal{O}$ that given any
center set $C\in\mathcal{C}$, returns a value
$\mathcal{O}(C)\in(1\pm\varepsilon)\cdot\mathrm{cost}_{z}(P,C)$ which recovers
the value $\mathrm{cost}_{z}(P,C)$ up to a multiplicative error of
$\varepsilon$. We give the following notion.

######  Definition 1.1 (Space complexity for Euclidean $(k,z)$-Clustering).

We are given a dataset $P\subseteq[\Delta]^{d}$, integers $n,k\geq 1$,
constant $z\geq 1$ and an error parameter $\varepsilon\in(0,1)$. We define
$sc(P,\Delta,k,z,d,\varepsilon)$ to be the minimum possible number of bits of
an $\varepsilon$-sketch for $P$. Moreover, we define
$sc(n,\Delta,k,z,d,\varepsilon):=\sup_{P\subseteq[\Delta]^{d}:|P|=n}sc(P,\Delta,k,z,d,\varepsilon)$
to be the space complexity function, i.e., the maximum cardinality
$sc(P,\Delta,k,z,d,\varepsilon)$ over all possible datasets
$P\subseteq[\Delta]^{d}$ of size at most $n$.

Space upper bounds. Our first contribution is to provide upper bounds for the
space complexity $sc(n,\Delta,k,z,d,\varepsilon)$. We apply the idea of
storing an $\varepsilon$-coreset and have the following theorem. Here, an
$\varepsilon$-coreset for $(k,z)$-Clustering is a weighted subset $S\subseteq
P$ together with a weight function $w:S\rightarrow\mathbb{R}_{\geq 0}$ such
that for every $C\in\mathcal{C}$, $\sum_{p\in S}w(p)\cdot
d^{z}(p,C)\in(1\pm\varepsilon)\cdot\operatorname{cost}_{z}(P,C)$.

######  Theorem 1.2 (Space upper bounds).

Suppose for any dataset $P\subseteq[\Delta]^{d}$ of size $n$, there exists an
$\varepsilon$-coreset of $P$ for $(k,z)$-Clustering of size at most
$\Gamma(n)\geq 1$. We have the following space upper bounds:

  * •

When $n\leq k$, $sc(n,\Delta,k,z,d,\varepsilon)\leq
O\left(nd\log\Delta\right)$;

  * •

When $n>k$, $sc(n,\Delta,k,z,d,\varepsilon)\leq O(kd\log\Delta+\Gamma(n)(d\log
1/\varepsilon+d\log\log\Delta+\log\log n))$.

The proof of this theorem can be found in Section 2, which relies on novel
geometric findings; see Section 1.2 for discussion. Fully storing a coreset
$S$ requires $\Gamma(n)\cdot d\log\Delta$ bits for points and
$\Gamma(n)\cdot\log n$ for its weight function $w$. To further reduce the
storage space, we provide a quantification scheme for the weight function $w$
and points in $S$ (Algorithm 1). When ignoring the logarithmic term, we have
$sc(n,\Delta,k,z,d,\varepsilon)\leq\tilde{O}(\Gamma(n)\cdot d)$. 222In this
paper, $\tilde{O}(\cdot)$ may hide a factor of $2^{O(z)}$ and the logarithmic
term of the input parameters $n,\Delta,k,d,1/\varepsilon$. Combining with the
recent breakthroughs that shows that
$\Gamma(n)=\tilde{O}(\min\left\\{k^{\frac{2z+2}{z+2}}\varepsilon^{-2},k\varepsilon^{-z-2}\right\\})$
[14, 15, 16, 29], we conclude that when $n>k$,

$\displaystyle
sc(n,\Delta,k,z,d,\varepsilon)\leq\tilde{O}(d\cdot\min\left\\{\frac{k^{\frac{2z+2}{z+2}}}{\varepsilon^{2}},\frac{k}{\varepsilon^{z+2}}\right\\}).$
(1)

Space lower bounds. Our main contribution is to provide the following lower
bounds for the space complexity $sc(n,\Delta,k,z,d,\varepsilon)$.

######  Theorem 1.3 (Space lower bounds).

We have the following space lower bounds:

  * •

When $n\leq k$, $sc(n,\Delta,k,z,d,\varepsilon)\geq\Omega(nd\log\Delta)$;

  * •

When $n>k\geq 2$ and
$\Delta=\Omega\left(\frac{k^{\frac{1}{d}}\sqrt{d}}{\varepsilon}\right)$,
$sc(n,\Delta,k,z,d,\varepsilon)\geq\Omega\left(kd\log\Delta+kd\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},\frac{n}{k}\right\\}+k\log\log\frac{n}{k}\right)$.

The proof of this theorem can be found in Section 3. Compared to Theorem 1.2,
our lower bound for space complexity is tight when $n\leq k$. For the case
when $n>k$, the key term in our lower bound is
$\Omega(kd\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},\frac{n}{k}\right\\})$. Comparing this with Inequality (1), we can conclude
that the optimal space complexity
$sc(n,\Delta,k,z,d,\varepsilon)\approx\frac{d}{\varepsilon^{2}}$ when
$k=O(1)$, $n\geq\Omega(\frac{1}{\varepsilon^{2}})$ and
$d\geq\Omega(\frac{1}{\varepsilon^{2}\log 1/\varepsilon})$. As a corollary, we
can affirm that the coreset method is indeed the optimal compression method
when the size and dimension of the dataset $P$ are large and the number of
centers $k$ is constant. It would be interesting to further investigate
whether the coreset method remains optimal for large $k$. Another corollary of
Theorem 1.2 is a lower bound $\Omega(\frac{k}{\varepsilon^{2}})$ for the
coreset size $\Gamma(n)$. This bound matches the previous result in [15], and
it has been recently improved to $\Omega(\frac{k}{\varepsilon^{-z-2}})$ when
$\varepsilon=\Omega(k^{\frac{1}{z+2}})$ [29]. Since the technical approach is
different, our methods for space lower bounds may also be useful to further
improve the coreset lower bounds.

It is worth noting that $d$ still appears in our lower bound results, which
implies that exploiting dimension reduction techniques does not necessarily
lead to a reduction in storage space. Although this may seem counter-
intuitive, it is reasonable since we still need to maintain the mapping from
the original space to the embedded space (which is also the space consumed by
the dimensionality reduction itself), and the storage of this mapping could
also be relatively large. Moreover, we can utilize this fact to lower bound
the space cost of these dimension reduction methods from our results; see the
following applications.

Application: Tight space lower bound for terminal embedding. Our Theorem 1.3
also yields an interesting by-product: a nearly tight lower bound for the
space complexity of terminal embedding, which is a well-known dimension
reduction method recently introduced by [21, 42]. It is a pre-processing step
to map input data to a low-dimensional space. The definition of it is given as
follows.

######  Definition 1.4 (Terminal embedding).

Let $\varepsilon\in(0,1)$ and $X\subseteq\mathbb{R}^{d}$ be a collection of
$n$ points. A mapping $f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$ is called an
$\varepsilon$-terminal embedding of $X$ if for any $p\in X$ and
$q\in\mathbb{R}^{d}$, $d(p,q)\leq d(f(p),f(q))\leq(1+\varepsilon)\cdot
d(p,q).$

As a consequence of Theorem 1.3, the preservation of the terminal embedding
function $f$ must incur a large space cost; summarized by the following
theorem. The result is obtained by another natural idea for sketch
construction: maintaining a terminal embedding function $f$ for a coreset $S$
and the projection $f(S)$ of a coreset $S$, in which the storage space for
$f(S)$ can be independent on the dimension $d$.

######  Theorem 1.5 (Informal; see Theorem 4.2).

Let $\varepsilon\in(0,1)$ and assume $d=\Omega\left(\frac{\log
n\log(n/\varepsilon)}{\varepsilon^{2}}\right)$. An $\varepsilon$-terminal
embedding, that projects a given dataset $P\subset\mathbb{R}^{d}$ of size $n$
to a target dimension $O(\frac{\log n}{\varepsilon^{2}})$, requires space at
least $\Omega(nd)$.

The bound $\Omega(nd)$ is not surprising since terminal embedding can be used
to approximately recover the original dataset. In the case when
$d\geq\Omega(\frac{\log n\log(n/\varepsilon)}{\varepsilon^{2}})$, our result
improves upon the previous lower bound of $\Omega(\frac{n\log
n}{\varepsilon^{2}})$ from [2]. 333Although the paper does not directly study
terminal embedding, their bound for preserving inner products (Theorem 1.1 in
[2]) implies a lower bound of $\Omega(\frac{n\log n}{\varepsilon^{2}})$ for
terminal embedding. We replace their factor of $\frac{\log
n}{\varepsilon^{2}}$ with $d$. Furthermore, our lower bound of $\Omega(nd)$
matches the prior upper bound of $\tilde{O}(nd)$ for terminal embedding [12],
making it nearly tight.

###  1.2 Technical Overview

We mainly focus on analyzing the technical idea behind our main contribution
Theorem 1.3. In general, our approach involves using a clever counting
argument to establish lower bounds on space. We do this by creating a large
family of datasets $\mathcal{P}$ where, for any pair $P$ and $Q$ from this
family, there exists a center set $C$ that separates their cost function by a
significant margin, denoted as
$\mathrm{cost}_{z}\left(P,C\right)\notin\left(1\pm
O(\varepsilon)\right)\mathrm{cost}_{z}\left(Q,C\right)$. This difference in
cost implies that $P$ and $Q$ can not share the same sketch, which leads to a
lower bound on space of $\log\left(\left|\mathcal{P}\right|\right)$ (Lemma
3.1). Hence, we focus on how to construct such a family $\mathcal{P}$.

We discuss the most technical bound, which is
$\Omega\left(kd\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},\frac{n}{k}\right\\}\right)$, when $n>k\geq 2$ and
$\Delta=\Omega\left(\frac{k^{\frac{1}{d}}\sqrt{d}}{\varepsilon}\right)$. The
proofs for other bounds are pretty standard. For brevity, we will explain the
technical idea for the case of $z=k=2$ (2-Means). The extension to general $z$
and $k$ is straightforward, by analyzing Taylor expansions for $(1+x)^{z}$
(Section 3.4) and make $\Omega(k)$ copies of datasets in $\mathcal{P}$
(Section 3.5). Our construction of $\mathcal{P}$ relies on a fundamental
geometric concept known as _principal angles_ (Definition 3.2). The Cosine of
these angles, when given the orthonormal bases
$P=\left\\{p_{i}:i\in[n]\right\\}$ and $Q=\left\\{q_{i}:i\in[n]\right\\}$ of
two distinct subspaces in $\mathbb{R}^{d}$, uniquely correspond to the
singular values of $P^{\top}Q$ (Lemma 3.3). This correspondence essentially
measures how orthogonal the two subspaces are to each other. With principal
angles in mind, we outline the two main components of our proof. Assuming that
$d>n$, the first component (Lemma 3.4) demonstrates that if the largest $O(n)$
principal angles between two orthonormal bases $P$ and $Q$ are sufficiently
large, there exists a center set $C=\left\\{c,-c\right\\}\in\mathcal{C}$ with
$\|c\|_{2}=1$ such that
$\operatorname{cost}_{2}(P,\\{c,-c\\})-\operatorname{cost}_{2}(Q,\\{c,-c\\})\geq\Omega\left(\sqrt{n}\right)$.
This induced error of $\Omega\left(\sqrt{n}\right)$ from $C$ achieves the
desired scale of $\varepsilon\cdot\mathrm{cost}_{z}(P,C)=O(\varepsilon n)$
when $n=O\left(\frac{1}{\varepsilon^{2}}\right)$. The second component (Lemma
3.5) states that when $n=O\left(\frac{d}{\log d}\right)$, there exists a large
family $\mathcal{P}$ of orthonormal bases (for different $n$-dimensional
subspaces) with size $\exp\left(nd\right)$ such that most principal angles of
any two different orthonormal bases in the family are sufficiently large. The
space lower bound
$\Omega\left(d\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},n\right\\}\right)$ directly follows from these two lemmas.

Next, we delve into the technical insights behind Lemmas 3.4 and 3.5.

Lemma 3.4: Reduction from principal angles to cost difference. Recall that we
aim to show the existence of a center set $C=\left\\{c,-c\right\\}$ that
incurs a large cost difference between two orthonormal bases
$P=\left\\{p_{i}:i\in[n]\right\\}$ and $Q=\left\\{q_{i}:i\in[n]\right\\}$. By
the formulation of $C$, we note that
$\mathrm{cost}_{2}(P,C)-\mathrm{cost}_{2}(Q,C)=2\left(\sum_{i=1}^{n}\left|\langle
q_{i},c\rangle\right|-\left|\langle p_{i},c\rangle\right|\right)$. Hence, we
focus on showing the existence of a unit vector $c\in\mathbb{R}^{d}$ such that

$\displaystyle\sum_{i=1}^{n}\left|\langle q_{i},c\rangle\right|-\left|\langle
p_{i},c\rangle\right|\geq\Omega(\sqrt{n}).$ (2)

Intuitively, our goal is to increase the magnitude of the first term
$\sum_{i=1}^{n}\left|\langle q_{i},c\rangle\right|$ while decreasing the
magnitude of the second term $\sum_{i=1}^{n}\left|\langle
p_{i},c\rangle\right|$. One initial approach is to choose
$c=\frac{1}{\sqrt{n}}Q\lambda=\frac{1}{\sqrt{n}}\sum_{i\in[n]}\lambda_{i}q_{i}$,
where $\lambda\in\left\\{-1,+1\right\\}^{n}$ is a full coloring on $[n]$. By
this selection, center $c$ lies on the subspace spanned by $Q$ and maximizes
the first term $\sum_{i=1}^{n}\left|\langle q_{i},c\rangle\right|$ to be
$\sqrt{n}$. Moreover, the second term becomes $\sum_{i=1}^{n}\left|\langle
p_{i},c\rangle\right|=\frac{1}{\sqrt{n}}\|P^{\top}Q\lambda\|_{1}\leq\sqrt{n}\|P^{\top}Q\lambda\|_{\infty}$.
Ideally, if we can find a coloring $\lambda\in\left\\{-1,+1\right\\}^{n}$ such
that $\|P^{\top}Q\lambda\|_{\infty}\leq 0.5$, we can achieve the desired cost
difference in Inequality (2). However, the existence of such $\lambda$ appears
to be non-trivial. For instance, if we randomly select a coloring $\lambda$
from $\left\\{-1,+1\right\\}^{n}$, the expected value of
$\|P^{\top}Q\lambda\|_{\infty}$ can be as large as $O(\log n)$ [45].

Motivated by the discrepancy literature (e.g., [45, 19]), we enhance the
previous idea by allowing $\lambda\in\left\\{-1,0,+1\right\\}^{n}$ to be a
partial coloring with $\|\lambda\|_{1}=0.75n$. With this modification, we
still have $\sum_{i=1}^{n}\left|\langle q_{i},c\rangle\right|=0.75\sqrt{n}$,
and it suffices to bound $\|P^{\top}Q\lambda\|_{\infty}\leq 0.5$ to achieve
Inequality (2). Spencer et al. [45] have shown the existence of such a partial
coloring $\lambda$ with $\|P^{\top}Q\lambda\|_{\infty}\leq\alpha$ for some
constant $\alpha\geq 1$, considering that both $P$ and $Q$ are orthonormal
bases. However, we require a stricter bound of $\alpha\leq 0.5$, which calls
for new ideas. Fortunately, we discover that large principal angles indicate
the existence of a partial coloring $\lambda$ such that
$\|P^{\top}Q\lambda\|_{\infty}\leq 0.5$ (see Lemmas 3.6 and 3.7).
Geometrically, large principal angles imply that the two subspaces spanned by
$P$ and $Q$ are nearly orthogonal to each other in many directions. As a
consequence, most inner products $\langle p_{i},q_{j}\rangle$ are close to 0,
indicating that the majority of the row norms $\|(P^{\top}Q)_{i}\|_{2}$ are
smaller than 0.1 (Lemma 3.6). These small row sums enable us to find a partial
coloring $\lambda$ that further reduces the bound for
$\|P^{\top}Q\lambda\|_{\infty}$ to 0.5 (Lemma 3.7), employing similar
approaches as in [45]. In summary, we have completed the proof of Lemma 3.4.

Lemma 3.5: Construction of $\mathcal{P}$. Our construction is inspired by a
geometric observation made in Absil et al. [1], which states that the largest
principal angle between the orthonormal bases $P$ and $Q$ of two
$n$-dimensional subspaces, independently drawn from the uniform distribution
on the Grassmann manifold of $n$-planes in $\mathbb{R}^{d}$, is at least
$\Omega(1)$ with high probability. We extend this result and prove that even
the largest $O(n)$ principal angles between $P$ and $Q$ are at least
$\Omega(1)$ (Lemma 3.9). This extension relies on a more careful integral
calculation for the density function of principal angles. Moreover, this
extension leads to an enhanced geometric observation: on average, these two
orthonormal bases $P$ and $Q$ are distinct with respect to principal angles,
which could be of independent research interest. Then using standard
probabilistic arguments, we can randomly select a family $\mathcal{P}$ of
$\exp(\Omega(nd))$ orthonormal bases, ensuring that the largest $O(n)$
principal angles between any pair $P$ and $Q$ from $\mathcal{P}$ are
consistently large.

###  1.3 Other Related Work

Coreset construction for clustering. There are a series of works towards
closing the upper and lower bounds of coreset size for $(k,z)$-Clustering in
high dimensional Euclidean spaces [22, 6, 14, 15, 16, 29]. The current best
upper bound is
$\tilde{O}(\min\\{\frac{k^{\frac{2z+2}{z+2}}}{\varepsilon^{2}},\frac{k}{\varepsilon^{z+2}}\\})$
by [14, 15, 16, 29]. On the other hand, Huang and Vishnoi [28] proved a size
lower bound $\Omega(k\min\\{2^{z/20},d\\})$ and Cohen-addad et al. [15] showed
bound $\Omega(k\varepsilon^{-2})$. Very recently, Huang and Li [29] gave a
size lower bound of $\Omega(k\varepsilon^{-z-2})$ for
$\varepsilon=\Omega(k^{-1/(z+2)})$, which matches the size upper bound and is
nearly tight. There have also been studies for the coreset size when the
dimension is small, see e.g. [25, 30]. In addition to offline settings,
coresets have also been studied in the stream setting [25, 8, 17], distributed
setting [4] and dynamic setting [26].

Dimension reduction. Dimension reduction is an important technique for data
compression, including techniques like Johnson-Lindenstrauss (JL) [39, 10] and
terminal embedding [42, 28]. The target dimension of any embedding satisfying
the JL lemma is shown to be $\Theta(\varepsilon^{-2}\log n)$ [33, 2, 37],
where $n$ is the size of the data set. The space complexity of JL is shown to
be $O(\log d+\log(1/\delta)(\log\log(1/\delta)+\log(1/\varepsilon)))$ random
bits [35], where $\varepsilon$ and $\delta$ are error and fail probability
respectively. In the context of clustering, Makarychev et al. [39] gives a
nearly optimal target dimension $O(\log(k/\varepsilon)/\varepsilon^{2})$ for
$(k,z)$-Clustering by applying JL. Their reduction ensures that the cost of
the optimal clustering is preserved within a factor of $(1+\varepsilon)$
instead of preserving the clustering cost for all center sets. For terminal
embedding, Narayanan and Nelson [42] provided an optimal terminal embedding
with target dimension $O(\varepsilon^{-2}\log n)$. For the space complexity,
the best-known construction of terminal embedding costs $\tilde{O}(nd)$ bits
[12].

##  2 Proof of Theorem 1.2: Space Upper Bounds

The proof for the first part when $n\leq k$ is to simply store all data
points. Since $P\subseteq[\Delta]^{d}$, the storage space for each coordinate
is at most $\log\Delta$, which results in the space upper bound
$O(nd\log\Delta)$. Next, we focus on the second part when $n>k$. The main idea
is to construct a sketch to store a coreset using space as small as possible.
For preparation, we need the following lemma.

######  Lemma 2.1 (Relaxed triangle inequality (Lemma 10 of [15])).

Let $a,b,c$ be an arbitrary set of points in a metric space with distance
function $d$, and let $z$ be a positive integer. Then for any $\varepsilon>0,$

$\displaystyle
d(a,b)^{z}\leq(1+\varepsilon)^{z-1}d(a,c)^{z}+\left(\frac{1+\varepsilon}{\varepsilon}\right)^{z-1}d(b,c)^{z},$
$\displaystyle\left|d(a,b)^{z}-d(a,c)^{z}\right|\leq\varepsilon\cdot
d(a,c)^{z}+\left(\frac{z+\varepsilon}{\varepsilon}\right)^{z-1}d(b,c)^{z}.$

Let $P\subseteq[\Delta]^{d}$ be a dataset of size $n>k$. Let $(S,w)$ be an
$\frac{\varepsilon}{5}$-coreset of $P$ for $(k,z)$-Clustering. Let $C^{\star}$
be an $O(1)$-approximation of optimal center set, that is, a center set
satisfying $\operatorname{cost}_{z}(P,C^{\star})\leq
O(1)\cdot\min_{C\in\mathcal{C}}\operatorname{cost}_{z}(P,C).$ We argue that by
rounding each $c_{l}^{\star}\in C^{\star}$ to the nearest point in $P$, i.e.
$p_{c^{\star}}:=\operatorname{argmin}_{p\in P}d(c^{\star},p)$, it remains the
property of $O(1)$-approximation. To this end, by Lemma 2.1, for any $p\in P,$
$|d(p,c^{\star})^{z}-d(p,p_{c^{\star}})^{z}|\leq
d(p,c^{\star})^{z}+(1+z)^{z-1}d(p_{c^{\star}},c^{\star})^{z}\leq(1+(1+z)^{z-1})d(p,c^{\star})^{z}.$
As $z$ is constant, the claim is proved. Without of loss of generality, we
assume $C^{\star}\subseteq P$ and $\operatorname{cost}_{z}(P,C^{\star})\leq
2\min_{C\in\mathcal{C}}\operatorname{cost}_{z}(P,C).$

The compression scheme is summarized in Algorithm 1. Intuitively, we need to
compress the weight $w(p)$ and each coordinate $i\in[d]$ of points $p\in P$.
For $w(p)$, we either safely ignore too small weight, i.e.,
$w(p)\leq\frac{\varepsilon}{4|S|}$, or remains its highest position by
$\gamma_{p}$ and the first $\lceil\log 4/\varepsilon\rceil$ digits by
$w_{p,\varepsilon}$. For each $p$, we denote $c^{\star}_{p}$ to be the closest
center of $p$ in $C^{\star}$ and $c^{\star}_{p,i}$ to be the $i$’th coordinate
of $c^{\star}$ Then compress each coordinate $p_{i}-c^{\star}_{p,i}$ by a
similar idea as for weight. In Algorithm 1 we abuse the notation
$c^{\star}_{l}$ to denote the $l$’th point in $C^{\star},$ and
$c^{\star}_{l,i}$ similarly.

1

2

Input : Error parameter $\varepsilon\in(0,1)$, an
$\frac{\varepsilon}{4}$-coreset $S\subseteq P$ of size $|S|\leq\Gamma(n)$
together with a weight function $w:S\rightarrow\mathbb{R}_{\geq 0}$, an
$1$-approximate center set $C^{\star}\subseteq P$ of $P$ for
$(k,z)$-Clustering

Output : A sketch $T$ of $P$ for $(k,z)$-Clustering

3 Partition $S$ into $S_{l}:=\left\\{p\in
S|c_{l}=\operatorname{argmin}_{c_{l}^{\star}\in
C^{\star}}d(p,c_{l}^{\star})\right\\},l=1,\cdots,k$;

4 for  _$c^{\star}_{l}\in C^{\star}$_ do

5 for  _$p\in S_{l}$_ do

6 if  _ $w(p)\leq\frac{\varepsilon}{4|S|}$_ then
$(w_{p,\varepsilon},\gamma_{p})\leftarrow(0,0)$ ;

7 else

8 $w_{p,\varepsilon}\leftarrow\frac{w(p)}{2^{\lfloor\log w(p)\rfloor}}$,
rounds to $\lceil\log 4/\varepsilon\rceil$ decimal places;

9 $\gamma_{p}\leftarrow\lfloor\log w(p)\rfloor$

10 $w_{p}\leftarrow(w_{p,\varepsilon},\gamma_{p})$;

11 foreach  _coordinate $i\in[d]$_ do

12 if  _ $p_{i}-c^{\star}_{l,i}=0$_ then
$(\tau_{i,\varepsilon},\gamma_{p,i})\leftarrow(0,0)$ ;

13 else

14
$\tau_{p,i}\leftarrow\frac{p_{i}-c^{\star}_{l,i}}{2^{\lfloor\log(p_{i}-c^{\star}_{l,i})\rfloor}}$,
rounds to $\lceil\log 4z/\varepsilon\rceil$ decimal places;

15 $\gamma_{p,i}\leftarrow\lfloor\log(p_{i}-c^{\star}_{l,i})\rfloor$;

16

17 $\tau_{p,i}\leftarrow(\tau_{p,i},\gamma_{p,i})$;

18

19 $T_{l}\leftarrow\cup_{p\in S_{l}}(\\{\tau_{p,i}\\}_{i=1}^{d},w_{p})$;

20

21

return _$T\leftarrow\cup_{l\in[k]}(c^{\star}_{l},T_{l})$_

Algorithm 1 A compression scheme based on coreset

Since $S$ is a coreset, we will make use of the following lemma.

######  Lemma 2.2 (Sum of weights).

We have that $\sum_{p\in S}w(p)\in(1\pm\varepsilon)n$.

###### Proof.

Consider a center set $C\in\mathcal{C}$ far away from $P$, e.g.,
$C=+\infty^{d}$. then $\frac{\sum_{p\in P}d(p,C)^{z}}{\sum_{p\in
S}w(p)d(p,C)^{z}}\approx\frac{n}{\sum_{p\in S}w(p)}$. By the coreset
definition, we have $\frac{\operatorname{cost}_{z}(P,C)}{\sum_{p\in
S}w(p)d(p,C)^{z}}=\frac{\sum_{p\in P}d(p,C)^{z}}{\sum_{p\in
S}w(p)d(p,C)^{z}}\in 1\pm\varepsilon$, which proves the lemma. ∎

Now we are ready to prove the second part of Theorem 1.2.

###### Proof of Theorem 1.2 (second part).

Correctness analysis. We first show Algorithm 1 indeed outputs an
$\varepsilon$-sketch of $P$ for $(k,z)$-Clustering function. We use $T$ to
obtain $\widehat{w}_{p}=w_{p,\varepsilon}\cdot 2^{\gamma_{p}}$ and
$\widehat{p}=(\hat{\tau_{1}},\cdots,\hat{\tau_{d}})+c^{\star}_{p}$ with
$\hat{\tau_{i}}=\tau_{p,i}\cdot 2^{\gamma_{p,i}}$ for $i\in[d]$. Given a
center set $C\in\mathcal{C},$ we approximate $(k,z)$-Clustering function by
the following value:

$\sum_{p\in S}\widehat{w}_{p}\cdot d(\widehat{p},C)^{z}.$

We claim that for each $p\in S$,
$\widehat{w}_{p}\in(1\pm\frac{\varepsilon}{4})w(p)$ when
$w(p)>\frac{\varepsilon}{4|S|}.$ This is because $\frac{w(p)}{2}\leq
2^{\gamma_{p}}\leq w(p)$ and
$|w_{p,\varepsilon}-\frac{w(p)}{2^{\gamma_{p}}}|\leq\frac{\varepsilon}{4}$,
which implies that
$w_{p,\varepsilon}\in(1\pm\frac{\varepsilon}{4})\frac{w(p)}{2^{\gamma_{p}}}$
and $\widehat{w}_{p}\in(1\pm\frac{\varepsilon}{4})w(p)$. When
$w(p)\leq\frac{\varepsilon}{4|S|},$ we have
$w(p)d(p,C)^{z}\leq\frac{\varepsilon}{4|S|}d(p,C)^{z}\leq\frac{\varepsilon}{4|S|}\sum_{p\in
P}d(p,C)^{z}$, which means this quantity is too small to affect the
$(k,z)$-Clustering function and we could set all such $w(p)$ to zero.

We nextly analysis $\widehat{p}$. By Lemma 2.1, for any $c\in C,$
$|d(p,c)^{z}-d(\widehat{p},c)^{z}|\leq\frac{\varepsilon}{4}d(p,c)^{z}+(1+\frac{4z}{\varepsilon})^{z-1}d(p,\widehat{p})^{z}.$
By our construction,
$d(p,\widehat{p})=d(p-c^{\star}_{p},\hat{\tau})=\sqrt{\sum_{i=1}^{d}(p_{i}-c^{\star}_{p,i}-\hat{\tau}_{i})^{2}},$
and as the same argument for weight,
$p_{i}-c^{\star}_{p,i}-\hat{\tau}_{i}\leq\frac{\varepsilon}{4z}(p_{i}-c^{\star}_{p,i}),$
thus $d(p,\widehat{p})\leq\frac{\varepsilon}{4z}d(p,c^{\star}_{p}).$

Putting the above results together,

$\displaystyle\sum_{p\in S}\widehat{w}_{p}\cdot d(\widehat{p},C)^{z}\in$
$\displaystyle\sum_{p\in
S}w(p)\left(1\pm\frac{\varepsilon}{4}\right)\left[d(p,c_{p})^{z}\pm\left(\frac{\varepsilon}{4}d(p,c_{p})^{z}+\left(1+\frac{4z}{\varepsilon}\right)^{z-1}d(p,\widehat{p})^{z}\right)\right]$
$\displaystyle\in$
$\displaystyle\left(1\pm\frac{\varepsilon}{4}\right)\sum_{p\in
S}w(p)\left[\left(1\pm\frac{\varepsilon}{4}\right)d(p,c_{p})^{z}\pm\frac{\varepsilon}{4z}\left(1+\frac{\varepsilon}{4z}\right)^{z-1}d(p,c^{\star}_{p})^{z}\right]$
$\displaystyle\in$
$\displaystyle\left(1\pm\frac{\varepsilon}{4}\right)\sum_{p\in
S}w(p)\left[\left(1\pm\frac{\varepsilon}{4}\right)d(p,c_{p})^{z}\pm\frac{\varepsilon}{8}d(p,c^{\star}_{p})^{z}\right]$
$\displaystyle\in$
$\displaystyle\left(1\pm\frac{\varepsilon}{4}\right)\sum_{p\in
S}w(p)\left(1\pm\frac{\varepsilon}{2}\right)d(p,c_{p})^{z}$ $\displaystyle\in$
$\displaystyle\left(1\pm\frac{\varepsilon}{4}\right)\left(1\pm\frac{\varepsilon}{2}\right)\left(1\pm\frac{\varepsilon}{5}\right)\sum_{p\in
P}d(p,c_{p})^{z}$ $\displaystyle\in$ $\displaystyle(1\pm\varepsilon)\sum_{p\in
P}d(p,c_{p})^{z},$

where the third line follows from
$\ln(1+\frac{\varepsilon}{4z})\leq\frac{\varepsilon}{4z}$, the fourth line
follows from $C^{\star}$ is a $1$-approximation of an optimal center set, and
the penultimate line follows from the construction of coreset. Therefore we
construct an $\varepsilon$-sketch for $P$.

Space complexity analysis. We analyze its space complexity from now on. The
storage for $k$ grid points $C^{\star}$ is $O(kd\log\Delta).$ We store each
weight by a set $(w_{p,\varepsilon},\gamma_{p})$, where the first number is up
to $O(\lceil\log 4/\varepsilon\rceil)$ decimal places, and representing the
integer number $\gamma_{p}=\lfloor\log w(p)\rfloor$ requires
$O(\log\max\\{\log\frac{4|S|}{\varepsilon},\log n\\})$ bits by Lemma 2.2.
Similarly, the storage for each $\tau_{p}$ is $O(d\log
4z/\varepsilon+d\log\log\Delta)$ bits. Combining them and notice that $|S|\leq
n,$ we obtain the final bound

$\displaystyle sc(P,\Delta,k,z,d,\varepsilon)\leq$ $\displaystyle
O\left(kd\log\Delta+|S|\left(\log\frac{4}{\varepsilon}+\log\max\left\\{\log\frac{4|S|}{\varepsilon},\log
n\right\\}\right.\right.+\left.\left.d\log\frac{4z}{\varepsilon}+d\log\log\Delta\right)\right)$
$\displaystyle=$ $\displaystyle O\left(kd\log\Delta+\Gamma(n)(d\log
1/\varepsilon+d\log\log\Delta+\log\log n)\right),$

where we ignore the dependence on $z.$ ∎

##  3 Proof of Theorem 1.3: Space Lower Bounds

In this section, we prove the space lower bounds. The high-level idea is to
construct a large family of datasets such that any two of them can not use the
same sketch; summarized by the following lemma.

######  Lemma 3.1 (A family of datasets leads to space lower bounds).

Suppose there exists a family $\mathcal{P}$ of datasets of size $n\geq 1$ such
that for any two datasets $P,Q\in\mathcal{P}$, there exists a center set
$C\in\mathcal{C}$ with $\operatorname{cost}_{z}(P,C)\notin\left(1\pm
3\varepsilon\right)\operatorname{cost}_{z}(Q,C)$. Then we have
$sc(n,\Delta,k,z,d,\varepsilon)\geq\Omega(\log\left|\mathcal{P}\right|)$.

###### Proof.

We prove this by contradiction. Assume that
$sc(n,\Delta,k,z,d,\varepsilon)=o(\log\left|\mathcal{P}\right|)$, we must be
able to find two datasets $P$ and $Q$ such that they correspond to the same
$\varepsilon$-sketch $\mathcal{O}$. Since $\mathcal{O}$ is an
$\varepsilon$-sketch for both $P$ and $Q$, we have for every center set
$C\in\mathcal{C}$,

$\displaystyle\mathcal{O}(C)\in(1\pm\varepsilon)\cdot\operatorname{cost}_{z}(P,C),~{}\mathcal{O}(C)\in(1\pm\varepsilon)\cdot\operatorname{cost}_{z}(Q,C),$
$\displaystyle\operatorname{cost}_{z}(P,C)\leq\frac{1}{1-\varepsilon}\mathcal{O}(C)\leq\frac{1+\varepsilon}{1-\varepsilon}\operatorname{cost}_{z}(Q,C)\leq(1+3\varepsilon)\operatorname{cost}_{z}(Q,C),$
$\displaystyle\operatorname{cost}_{z}(P,C)\geq\frac{1}{1+\varepsilon}\mathcal{O}(C)\geq\frac{1-\varepsilon}{1+\varepsilon}\operatorname{cost}_{z}(Q,C)\geq(1-3\varepsilon)\operatorname{cost}_{z}(Q,C).$

This contradicts with our assumption that
$\operatorname{cost}_{z}(P,C)\notin\left(1\pm
3\varepsilon\right)\operatorname{cost}_{z}(Q,C)$. ∎

###  3.1 Proof of Theorem 1.3

We first prove the lower bound $\Omega\left(nd\log\Delta\right)$ when $n\leq
k$.

###### Proof of Theorem 1.3 (first part).

We construct a family $\mathcal{P}$ as follows: for each dataset
$P\in\mathcal{P}$, we choose $n$ different grid points in $[\Delta]^{d}$. Note
that for each single grid point, there are $\Delta^{d}$ choices. Therefore,
the size $|\mathcal{P}|$ is $\binom{\Delta^{d}}{n}$, which implies that
$\log|\mathcal{P}|=\Omega(nd\log\Delta)$.

For any two datasets $P,Q\in\mathcal{P}$, there must be a single grid point
$p$ such that $p\in Q\setminus P$. Let
$C=P\cup\\{\underbrace{c,\cdots,c}_{k-n\text{ points}}\\}$ , where
$c\in\mathbb{R}^{d}$ is an arbitrary point with $c\neq p$. We have

$\operatorname{cost}_{z}\left(Q,C\right)\geq
d\left(p,C\right)^{z}>0,~{}\operatorname{cost}_{z}\left(P,C\right)=0\notin\left(1\pm
3\varepsilon\right)\operatorname{cost}_{z}\left(Q,C\right).$

Using Lemma 3.1, we obtain the space lower bound
$\Omega\left(nd\log\Delta\right)$. ∎

We then consider the second part of Theorem 1.3 when $n>k$. We first prove the
lower bound $\Omega\left(kd\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},\frac{n}{k}\right\\}\right)$. Recall that we have $n>2$ and
$\Delta=\Omega(\frac{k^{\frac{1}{d}}\sqrt{d}}{\varepsilon})$. For preparation,
we introduce the notion of principal angles.

######  Definition 3.2 (Principal angles).

Suppose $n\leq d$. Given two $n$-dimensional subspaces $\mathcal{X}$ and
$\mathcal{Y}$ of $\mathbb{R}^{d}$, the principal angles (or canonical angles)
$\theta_{1}(\mathcal{X},\mathcal{Y}),\cdots,\theta_{n}(\mathcal{X},\mathcal{Y})\in\left[0,\frac{\pi}{2}\right]$
between them are defined recursively by the following equations:

$\forall
i\in[n],~{}\cos\left(\theta_{i}(\mathcal{X},\mathcal{Y})\right)=\sup_{x\in\mathcal{X},y\in\mathcal{Y}}|x^{T}y|=|x_{l}^{T}y_{l}|,$

subject to $x\perp x_{1},\cdots,x_{i-1},\left\|x\right\|_{2}=1,y\perp
y_{1},\cdots,y_{i-1},\left\|y\right\|_{2}=1$.

The notion of principal angles between subspaces was first introduced by
Jordan [34] and has many important applications in statistics and numerical
analysis [20, 46]. Intuitively, small principal angles indicate that the two
subspaces are nearly parallel in many directions, while large principal angles
imply that the two subspaces are more distinct and span many directions that
are nearly orthogonal to each other. For example, when
$\mathcal{X}\perp\mathcal{Y}$, all principal angles
$\theta_{i}(\mathcal{X},\mathcal{Y})=\frac{\pi}{2}$. The following lemma shows
a relation between principal angles and singular value decomposition.

######  Lemma 3.3 (Property of principal angles (Theorem 1 in [5])).

Given two $n$-dimensional subspaces $\mathcal{X}$ and $\mathcal{Y}$ of
$\mathbb{R}^{d}$, let the columns of matrices $X\in\mathbb{R}^{d\times n}$ and
$Y\in\mathbb{R}^{d\times n}$ form orthonormal bases for the subspaces
$\mathcal{X}$ and $\mathcal{Y}$ respectively. Denote
$1\geq\sigma_{1}\geq\cdots\geq\sigma_{n}$ to be the singular values of the
inner product matrix $X^{T}Y$. We have
$\sigma_{i}=\cos\left(\theta_{i}(\mathcal{X},\mathcal{Y})\right),\forall
i\in[n].$

Lemma 3.3 implies that the principal angles are symmetric, i.e.
$\theta(\mathcal{X},\mathcal{Y})=\theta(\mathcal{Y},\mathcal{X})$. It also
implies that the principal angles are orthogonally invariant, i.e.
$\theta(\mathcal{X}A,\mathcal{Y}B)=\theta(\mathcal{X},\mathcal{Y})$ for any
orthogonal matrix $A,B\in\mathbb{R}^{n\times n}$, since
$\sigma\left(A^{T}X^{T}YB\right)=\sigma\left(X^{T}Y\right)$. Hence, Lemma 3.3
holds for any choice of orthonormal bases $X$ and $Y$ of corresponding
subspaces.

The idea is still to construct a large family $\mathcal{P}$ of datasets to
apply Lemma 3.1. For ease of analysis, we first do not require the
construction of datasets $P\subseteq[\Delta]^{d}$ and actually ensure that
every $P$ consists of orthonormal bases of some subspaces. At the end of the
proof, we will show how to round and scale these datasets $P$ into
$[\Delta]^{d}$.

For any two datasets $P,Q\in\mathcal{P}$, let their inner product matrix be

$U:=P^{T}Q=\left[U_{1},\cdots,U_{n}\right]^{T}=\begin{bmatrix}p_{1}^{T}q_{1}&\cdots&p_{1}^{T}q_{n}\\\
\vdots&\ddots&\vdots\\\
p_{n}^{T}q_{1}&\cdots&p_{n}^{T}q_{n}\end{bmatrix}=\left(U_{ij}\right)_{i,j\in[n]}.$

Slightly abuse of notation, we use $\theta_{i}\left(P,Q\right)$ to represent
the $i$-th least principal angles of the two subspaces spanned by $P$ and $Q$.
The following lemma shows that large principal angles between $P$ and $Q$
imply a large cost difference on some center set $\left\\{c,-c\right\\}$.

######  Lemma 3.4 (Principal angles to cost difference).

Let $P$, $Q$ be datasets of $n$ orthonormal bases (with $100\leq
n\leq\frac{d}{2}$) satisfying that $\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(P,Q\right)\geq\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right).$ There
exists a unit vector $c\in\mathbb{R}^{d}$ such that
$\operatorname{cost}_{2}(P,\\{c,-c\\})-\operatorname{cost}_{2}(Q,\\{c,-c\\})\geq\frac{1}{2}\sqrt{n}.$

###### Proof.

Proof of Lemma 3.4 can be found in section 3.2. ∎

Applying $n=O\left(\frac{1}{\varepsilon^{2}}\right)$ to the above lemma leads
to our desired cost difference $\Omega\left(\varepsilon
n\right)=\Omega\left(\varepsilon\mathrm{cost}_{2}(P,\left\\{c,-c\right\\})\right)$.
We then show it is possible to construct a large family $\mathcal{P}$ such
that the principal angles between any two datasets in $\mathcal{P}$ are
sufficiently large.

######  Lemma 3.5 (Construction of a large family of datasets).

When $n=O\left(\frac{d}{\log d}\right)$, there is a family $\mathcal{P}$ of
size
$\exp\left(\frac{1}{256}10^{-6}\log\left(\frac{1}{1-\frac{1}{32}10^{-6}}\right)\cdot
nd\right)$ such that for any two dataset $P,Q\in\mathcal{P}$, we have
$\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(P,Q\right)\geq\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right).$

###### Proof.

Proof of Lemma 3.5 can be found in section 3.3. ∎

Combining Lemma 3.4 and 3.5, we are ready to prove the second part of Theorem
1.3.

###### Proof of Theorem 1.3 (second part).

The lower bound of $\Omega(kd\log\Delta)$ is trivial since
$sc(n,\Delta,k,z,d,\varepsilon)$ is non-decreasing with $n$. Then by the first
part of Theorem 1.3, we have $sc(n,\Delta,k,z,d,\varepsilon)\geq
sc(k,\Delta,k,z,d,\varepsilon)\geq\Omega(kd\log\Delta)$.

Next, we prove the lower bound of
$\Omega\left(kd\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},\frac{n}{k}\right\\}\right)$. For ease of analysis, we prove the case of
$k=z=2$. The extensions to general $k$ and $z$ can be found in Section 3.4 and
3.5. Denote

$\tilde{n}=\min\left\\{\Theta\left(\frac{1}{484\varepsilon^{2}}\right),\Theta\left(\frac{d}{\log
d}\right),n\right\\}\geq 100,$

where the first term $\Theta\left(\frac{1}{484\varepsilon^{2}}\right)$ is for
achieving a large cost difference by Lemma 3.4 and the second term
$\Theta\left(\frac{d}{\log d}\right)$ is to satisfy the condition of Lemma
3.5. Since $sc(n,\Delta,2,2,d,\varepsilon)$ is non-decreasing with $n$, it
suffices to prove a lower bound for $sc(\tilde{n},\Delta,2,2,d,\varepsilon)$.

Lemma 3.5 shows that we can find a family $\mathcal{P}$ of size
$\exp\left(\frac{1}{256}10^{-6}\log\left(\frac{1}{1-\frac{1}{32}10^{-6}}\right)\cdot\tilde{n}d\right)$
such that for any two dataset in this set $P$ and $Q$, we have
$\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(P,Q\right)\geq\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right).$ Lemma
3.4 shows that such a condition allows us to find a unit-norm vector $c$ such
that
$\operatorname{cost}_{2}(P,\\{c,-c\\})-\operatorname{cost}_{2}(Q,\\{c,-c\\})\geq\frac{1}{2}\sqrt{\tilde{n}}.$
By our choice of $\tilde{n}$, we have $\frac{1}{2}\sqrt{\tilde{n}}\geq
11\varepsilon\tilde{n}\geq 5\varepsilon\cdot\mathrm{cost}_{2}(P,\\{c,-c\\})$
and $\tilde{n}=O(\frac{d}{\log d})$. Hence, there exists a family
$\mathcal{P}$ of size
$\exp\left(\Theta(\tilde{n}d)\right)=\exp\left(\Theta\left(d\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},n\right\\}\right)\right)$ such that for any two datasets
$P,Q\in\mathcal{P}$, there exists a unit vector $c\in\mathbb{R}^{d}$ with
$\operatorname{cost}_{2}(P,\\{c,-c\\})-\operatorname{cost}_{2}(Q,\\{c,-c\\})\geq
11\varepsilon\tilde{n}.$

We then round and scale every dataset $P\in\mathcal{P}$ to $[\gamma]^{d}$,
where $\gamma=\lceil\frac{10\sqrt{d}}{\varepsilon}\rceil$. The extra term
$k^{\frac{1}{d}}$ in $\Delta$ will show up when we extend the result to
general $k\geq 2$ (Section 3.5). Without loss of generality, we may assume
that $\gamma$ is an odd integer. Otherwise, we just let
$\gamma=\lceil\frac{10\sqrt{d}}{\varepsilon}\rceil+1$.

Denote $\mathbf{1}=(1,\cdots,1).$ For a dataset
$P=\left(p_{1},\cdots,p_{\tilde{n}}\right)\in\mathcal{P}$, we will construct
$\tilde{\mathcal{P}}$ to be our final family as follows: For each of dataset
$P\in\mathcal{P}$, we shift the origin to
$\lceil\frac{\gamma}{2}\rceil\cdot\mathbf{1}$, scale it by a factor of
$\frac{\gamma}{2}$ and finally perform an upward rounding on each dimension to
put every point on the grid:
$\tilde{P}=\left(\lceil\frac{\gamma}{2}p_{1}\rceil,\cdots,\lceil\frac{\gamma}{2}p_{\tilde{n}}\rceil\rceil\right)+\lceil\frac{\gamma}{2}\rceil\cdot\mathbf{1}=\left(\tilde{p}_{1},\cdots,\tilde{p}_{\tilde{n}}\right).$
We will then show that this set fulfills the requirement of Lemma 3.1. For
ease of explanation, we also define $\hat{P}$ to be the dataset without
rounding:
$\hat{P}=\left(\frac{\gamma}{2}p_{1},\cdots,\frac{\gamma}{2}p_{\tilde{n}}\right)+\lceil\frac{\gamma}{2}\rceil\cdot\mathbf{1}=\left(\hat{p}_{1},\cdots,\hat{p}_{\tilde{n}}\right).$
Moreover, let
$\bar{c}=\frac{\gamma}{2}c+\lceil\frac{\gamma}{2}\rceil\cdot\mathbf{1}$. We
must have that for the scaling dataset,

$\displaystyle\operatorname{cost}_{2}\left(\hat{P},\left\\{\bar{c},-\bar{c}\right\\}\right)=\frac{\gamma^{2}}{4}\operatorname{cost}_{2}\left(P,\\{c,-c\\}\right)\leq\frac{\gamma^{2}\tilde{n}}{2},$
$\displaystyle\operatorname{cost}_{2}\left(\hat{P},\left\\{\bar{c},-\bar{c}\right\\}\right)-\operatorname{cost}_{2}\left(\hat{Q},\left\\{\bar{c},-\bar{c}\right\\}\right)=\frac{\gamma^{2}}{4}\left(\operatorname{cost}_{2}(P,\\{c,-c\\})-\operatorname{cost}_{2}(Q,\\{c,-c\\})\right)\geq\frac{11\gamma^{2}\varepsilon\tilde{n}}{4}.$

On the other hand, for the rounding dataset, we have

$\displaystyle\left|\left\|\hat{p}_{i}-\bar{c}\right\|_{2}^{2}-\left\|\tilde{p}_{i}-\bar{c}\right\|_{2}^{2}\right|$
$\displaystyle\leq
2\left\|\hat{p}_{i}-\tilde{p}_{i}\right\|_{2}\left\|\hat{p}_{i}-\bar{c}\right\|_{2}+\left\|\hat{p}_{i}-\tilde{p}_{i}\right\|_{2}^{2}\leq
2\gamma\sqrt{d}+d\leq\frac{\gamma^{2}\varepsilon}{4}.$

The case for $-\bar{c}$ and other datasets is similar. Therefore, we have that
for any dataset

$\displaystyle\left|\operatorname{cost}_{2}(\hat{P},\\{\bar{c},-\bar{c}\\})-\operatorname{cost}_{2}(\tilde{P},\\{\bar{c},-\bar{c}\\})\right|\leq\frac{\gamma^{2}\varepsilon\tilde{n}}{4},$
$\displaystyle\operatorname{cost}_{2}\left(\tilde{P},\left\\{\bar{c},-\bar{c}\right\\}\right)\leq\operatorname{cost}_{2}\left(\hat{P},\left\\{\bar{c},-\bar{c}\right\\}\right)+\frac{\gamma^{2}\varepsilon\tilde{n}}{4}\leq\frac{\gamma^{2}\tilde{n}}{2}+\frac{\gamma^{2}\varepsilon\tilde{n}}{4}\leq\frac{3\gamma^{2}\tilde{n}}{4}.$

We now have a rounded family $\tilde{\mathcal{P}}$ such that all points are on
the grid and we can find $\bar{c}$ that

$\displaystyle\operatorname{cost}_{2}\left(\tilde{P},\left\\{\bar{c},-\bar{c}\right\\}\right)-\operatorname{cost}_{2}\left(\tilde{Q},\left\\{\bar{c},-\bar{c}\right\\}\right)\geq\operatorname{cost}_{2}\left(\hat{P},\left\\{\bar{c},-\bar{c}\right\\}\right)-\operatorname{cost}_{2}\left(\hat{Q},\left\\{\bar{c},-\bar{c}\right\\}\right)-\frac{\gamma^{2}\varepsilon\tilde{n}}{2}\geq\frac{9\gamma^{2}\varepsilon\tilde{n}}{4}.$

Since the cost function value is upper bounded by
$\frac{3\gamma^{2}\tilde{n}}{4}$, we must have that
$\operatorname{cost}_{2}(\tilde{P},\\{c,-c\\})\notin\left(1\pm
3\varepsilon\right)\operatorname{cost}_{2}(\tilde{Q},\\{c,-c\\}).$ Moreover,
we can find origin being $\lceil\frac{\gamma}{2}\rceil\cdot\mathbf{1}$ such
that all the center points and data points have distance to it less than
$\frac{\gamma}{2}+\sqrt{d}\leq\gamma$. By Lemma 3.1, we have

$sc(n,\gamma,2,2,d,\varepsilon)\geq\Omega\left(\log\left|\tilde{\mathcal{P}}\right|\right)=\Omega\left(\log\left|\mathcal{P}\right|\right)\geq\Omega\left(d\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},n\right\\}\right).$

The extension to any constant $z\geq 1$ can be found in Section 3.4, which
relies on the analysis of the Taylor expansion of function
$f_{z}(x)=(1+x)^{z}$. The extension to general $k\geq 2$ can be found in
Section 3.5, whose main idea is to let every dataset consist of $\Theta(k)$
datasets from $\mathcal{P}$ and set the positions of their center points in
$[\Delta]^{d}$ “remote” from each other.

Finally, we prove the lower bound $\Omega\left(k\log\log\frac{n}{k}\right)$.
We again construct a large family $\mathcal{P}$ of datasets. For preparation,
we find arbitrary $\frac{k}{2}$ points, denoted as
$p_{1},\cdots,p_{\frac{k}{2}}$, such that the distance between every two
points is at least 10. This is available since $\Delta^{d}=\Omega(k)$. Every
dataset $P\in\mathcal{P}$ is constructed as follow: for each
$i\in\left[\frac{k}{2}\right]$, we select $m_{i}\in[\log\frac{n}{k}]$ and put
$2^{m_{i}}$ points at $p_{i}+e_{1}$ and $\frac{2n}{k}-2^{m_{i}}$ points at
$p_{i}$. Therefore, the total number of possible datasets is
$|\mathcal{P}|=\prod_{i=1}^{k}m_{i}=O\left(\left(\log\frac{n}{k}\right)^{\frac{k}{2}}\right)$.
We then consider for any two different datasets $P,Q\in\mathcal{P}$, there
must exist $l$ such that $P$ and $Q$ have different assignments for $p_{l}$
and $p_{l}+e_{1}$. Without loss of generality,assume that $P$ put $2^{i}$ at
$p_{l}+e_{1}$ while $Q$ put $2^{j}$ for $i<j$. Choosing center set
$C=\left\\{p_{1},p_{1}+e_{1},\cdots,p_{l},p_{l}+2e_{1},\cdots,p_{\frac{k}{2}},p_{\frac{k}{2}}+e_{1}\right\\},$
we must have that
$\operatorname{cost}_{z}(P,C)=2^{i}\leq\frac{1}{2}2^{j}\notin\left(1\pm\frac{1}{2}\right)\operatorname{cost}_{z}(Q,C),$
which satisfies our requirement of $\mathcal{P}$. Lemma 3.1 provides us with a
lower bound of
$\Omega\left(\log\left|\mathcal{P}\right|\right)\geq\Omega\left(k\log\log\frac{n}{k}\right).$

∎

###  3.2 Proof of Lemma 3.4: Principal Angles to Cost Difference

Let $P=\left\\{p_{i}\in\mathbb{R}^{d}\right\\}_{i\in[n]}$ and
$Q=~{}\left\\{q_{i}\in\mathbb{R}^{d}\right\\}_{i\in[n]}$ be two orthonormal
bases. We have the following equation for any unit vector
$c\in\mathbb{R}^{d}$:

$\displaystyle\operatorname{cost}_{2}(P,\\{c,-c\\})=\sum_{i=1}^{n}\left(\left\|p_{i}\right\|_{2}^{2}+\left\|c\right\|_{2}^{2}-2\left|\langle
p_{i},c\rangle\right|\right)=2n-2\sum_{i=1}^{n}\left|\langle
p_{i},c\rangle\right|\leq 2n.$

The difference between the cost of the two datasets $P$ and $Q$ is

$\operatorname{cost}_{2}(P,\\{c,-c\\})-\operatorname{cost}_{2}(Q,\\{c,-c\\})=2\left(\sum_{i=1}^{n}\left|\langle
q_{i},c\rangle\right|-\left|\langle p_{i},c\rangle\right|\right).$

Then it suffices to show the existence of a unit vector $c$ such that
$\sum_{i=1}^{n}|\langle q_{i},c\rangle|-\sum_{i=1}^{n}|\langle
p_{i},c\rangle|\geq\frac{1}{4}\sqrt{n}$. To this end, we first show that large
principal angles imply that most rows of the inner product matrix $U$ have a
small $\ell_{2}^{2}$-norm.

######  Lemma 3.6 (Principal angles to row norms).

Let $P$, $Q$ be datasets of $n$ orthonormal bases following the condition that
$\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(P,Q\right)\geq\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right).$ There
exists a set $K$ of size larger than $\left(1-\frac{10^{-4}}{16}\right)n$ and
having property that
$\|U_{i}\|_{2}^{2}:=\sum_{j=1}^{n}\left(U_{ij}\right)^{2}=\left\\{\begin{array}[]{l}\leq
10^{-2},i\in K\\\ \leq 1,i\notin K\end{array}\right..$

###### Proof.

Since both of the datasets are composed of only orthonormal bases, we must
have $\forall
i\in[n],\sum_{j=1}^{n}\left(U_{ij}\right)^{2}=\sum_{j=1}^{n}\left(p_{i}^{T}q_{j}\right)^{2}\leq\left\|p_{i}\right\|_{2}^{2}=1.$
Therefore, we focus on the existence of set $K$. By the property of principal
angles show in Lemma 3.3, we have that
$\sigma_{i}=\cos\theta_{i},i=1,\cdots,n.$ Moreover, we have the relation
between singular values and Frobenius norm of the matrix being
$\sum_{i=1}^{n}\sigma_{i}^{2}=\left\|U\right\|_{F}^{2}=\sum_{i=1}^{n}\sum_{j=1}^{n}\left(U_{ij}\right)^{2}.$
On the other hand, the condition shows that

$\displaystyle\theta_{n}\left(P,Q\right)\geq\cdots\geq\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(P,Q\right)\geq\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right),$
$\displaystyle\sigma_{n}\leq\cdots\leq\sigma_{\frac{1}{32}10^{-6}\cdot
n}\leq\cos\left(\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right)\right)=\frac{10^{-3}}{4\sqrt{2}}.$

With the general upper bound that
$\sigma_{i}=\cos\left(\theta_{i}\left(P,Q\right)\right)\leq 1$, we have

$\sum_{i=1}^{n}\sigma_{i}^{2}\leq\frac{1}{32}10^{-6}n+\left(1-\frac{1}{32}10^{-6}\right)n\cdot\left(\frac{10^{-3}}{4\sqrt{2}}\right)^{2}\leq\frac{1}{16}10^{-6}n.$

We would then have that the number of rows with sum of square larger than
$10^{-2}$ is less than $\frac{1}{16}10^{-6}n/10^{-2}=\frac{1}{16}10^{-4}n$,
which completes the proof. ∎

Next, we show that a partial coloring can be found for the rows of $U$ using
similar techniques as that of [45].

######  Lemma 3.7 (Row norms to partial coloring).

Considering that we have a matrix $U_{n\times n}$ (with $n\geq 100$) such that
we can find a set $K$ of size larger than $\left(1-\frac{10^{-4}}{16}\right)n$
and having the property that
$\sum_{j=1}^{n}U_{ij}^{2}=\left\\{\begin{array}[]{l}\leq 10^{-2},i\in K\\\
\leq 1,i\notin K\end{array}\right..$ we can find a partial coloring
$\\{\lambda_{j}\\}_{[n]}\in\\{-1,0,1\\}_{[n]}$ such that
$\left|j:\lambda_{j}=0\right|\leq\frac{1}{4}n$ and
$\left|\sum_{j=1}^{n}\lambda_{j}U_{ij}\right|\leq\frac{1}{2},\forall j\in[n]$.

###### Proof.

Define
$L_{i}(\lambda_{1},\cdots,\lambda_{n}):=\sum_{j=1}^{n}\lambda_{j}U_{ij}$ for
all $i\in[n]$. Define a map: $T:\\{-1,+1\\}^{n}\rightarrow\mathbb{Z}^{n}$ by
$T(\lambda_{1},\cdots,\lambda_{n})=(b_{1},\cdots,b_{n}),$ where $b_{i}$ is the
nearest integer to $L_{i}(\lambda_{1},\cdots,\lambda_{n})$. That is, $b_{i}=0$
if and only if $\left|L_{i}\right|\leq\frac{1}{2},b_{i}=1$ if and only if
$\frac{1}{2}<\left|L_{i}\right|\leq\frac{3}{2},b_{i}=-1$ if and only if
$-\frac{3}{2}\leq\left|L_{i}\right|<-\frac{1}{2},$ etc.. We then define a
subset $B\subset\mathbb{Z}^{n}$ of the range that
$B=\\{(b_{1},\cdots,b_{n})\in\mathbb{Z}^{n}:|\\{i:|b_{i}|\geq
s\\}|<\alpha_{s}n\\},$ where

$\alpha_{s}=\left[2\left(1-\frac{10^{-4}}{16}\right)\exp\left(-\frac{(2s-1)^{2}}{8\cdot
10^{-2}}\right)+2\cdot\frac{10^{-4}}{16}\exp\left(-\frac{(2s-1)^{2}}{8}\right)\right]2^{s+1}.$

We firstly prove that $\left|T^{-1}(B)\right|\geq\frac{1}{2}2^{n}.$ To see
this, let $\lambda_{1},\cdots,\lambda_{n}\in\\{-1,+1\\}$ be independent and
uniform and let $L_{1},\cdots,L_{n},b_{1},\cdots,b_{n}$ be the values
generated. We shall note that the standard deviation of $L_{i}$ is the square
root of sum of squares of row $i$. Thus, classic Chernoff bound provides

$\operatorname{Pr}\left[\left|b_{i}\right|\geq
s\right]=\operatorname{Pr}\left[\left|L_{i}\right|\geq\frac{2s-1}{2}\right]<\left\\{\begin{matrix}2\exp\left(-\frac{(2s-1)^{2}}{8\cdot
10^{-2}}\right),i\in K\\\ 2\exp\left(-\frac{(2s-1)^{2}}{8}\right),i\notin
K\end{matrix}\right..$

As expectation is linear, we would have

$\displaystyle\mathbb{E}\left[\left|\left\\{i:\left|b_{i}\right|\geq
s\right\\}\right|\right]<n\left[2\left(1-\frac{10^{-4}}{16}\right)\exp\left(-\frac{(2s-1)^{2}}{8\cdot
10^{-2}}\right)+2\cdot\frac{10^{-4}}{16}\exp\left(-\frac{(2s-1)^{2}}{8}\right)\right],$
$\displaystyle\operatorname{Pr}\left[\left|\left\\{i:\left|b_{i}\right|\geq
s\right\\}\right|\geq\alpha_{s}n\right]\leq\frac{1}{2^{s+1}},$
$\displaystyle\operatorname{Pr}\left[\left(b_{1},\cdots,b_{n}\right)\notin
B\right]\leq\sum_{s=1}^{\infty}\frac{1}{2^{s+1}}=\frac{1}{2}.$

That is, at least half of all
$\left(\lambda_{1},\cdots,\lambda_{n}\right)\in\\{-1,+1\\}^{n}$ are in
$T^{-1}(B)$, yielding $\left|T^{-1}(B)\right|\geq\frac{1}{2}2^{n}$.

We then consider the size of $B$ by crude counting arguments. In general,
suppose $B=\\{(b_{1},\cdots,b_{n})\in Z^{n}:|\\{i:|b_{i}|\geq
s\\}|\leq\alpha_{s}n,s=1,2,\cdots\\}.$ Then
$|B|\leq\prod_{s=1}^{\infty}[[\sum_{l=0}^{\alpha_{s}n}{\binom{n}{l}}]2^{\alpha_{s}n}].$
To this end, note that $\left\\{i:\left|b_{i}\right|=s\right\\}$ can be chosen
in at most $\sum_{i=0}^{\alpha_{s}n}{\binom{n}{i}}$ ways and, having been
selected, can be split into $\left\\{i:b_{i}=s\right\\}$ and
$\left\\{i:b_{i}=-s\right\\}$ in at most $2^{\alpha_{s}n}$ ways. We bound this
value with $\sum_{i=0}^{\alpha n}{\binom{n}{l}}\leq 2^{nH(\alpha)},$ where
$H(\alpha)=-\alpha\log_{2}\alpha-(1-\alpha)\log_{2}(1-\alpha)$ is the entropy
function. Therefore, $|B|\leq 2^{hn},$ where
$h=\sum_{s=1}^{\infty}[H(\alpha_{s})+\alpha_{s}].$ In our case, we shall have
that

$\displaystyle
h=\sum_{s=1}^{\infty}\left[H\left(\alpha_{s}\right)+\alpha_{s}\right]\leq\sum_{s=1}^{\infty}\left[e\alpha_{s}^{\frac{1}{\ln
4}}+\alpha_{s}\right]\leq(e+1)\sum_{s=1}^{\infty}\alpha_{s}^{\frac{1}{\ln
4}},$
$\displaystyle\frac{\alpha_{s}}{\alpha_{s+1}}\geq\frac{1}{2}\exp\left(\frac{(2s+1)^{2}-(2s-1)^{2}}{8}\right)=\frac{\exp(s)}{2}\geq\frac{e}{2},$
$\displaystyle\alpha_{1}=\left[2\left(1-\frac{10^{-4}}{16}\right)\exp\left(-\frac{1}{8\cdot
10^{-2}}\right)+2\cdot\frac{10^{-4}}{16}\exp\left(-\frac{1}{8}\right)\right]4\leq
10^{-4}.$

Combining together, we have

$h\leq(e+1)\sum_{s=1}^{\infty}\alpha_{s}^{\frac{1}{\ln
4}}\leq(e+1)\frac{\alpha_{1}^{\frac{1}{\ln
4}}}{1-\left(\frac{2}{e}\right)^{\frac{1}{\ln
4}}}\leq(e+1)\frac{\left(10^{-4}\right)^{\frac{1}{\ln
4}}}{1-\left(\frac{2}{e}\right)^{\frac{1}{\ln 4}}}\leq 0.03.$

Applying the pigeonhole principle, there exists specific
$(\tilde{b}_{1},\cdots,\tilde{b}_{n})\in B$ such that
$\mathcal{A}=\\{(\lambda_{1},\cdots,\lambda_{n})\in\\{-1,+1\\}^{n}:T(\lambda_{1},\cdots,\lambda_{n})=(\tilde{b}_{1},\cdots,\tilde{b}_{n})\\},|\mathcal{A}|\geq|T^{-1}(B)|/|B|\geq
2^{n(1-h)-1}.$ We use the following result.

######  Lemma 3.8 ([36]).

If $\mathcal{A}\subset\\{-1,+1\\}^{r}$ and $|\mathcal{A}|\geq 2^{rH(1/2-p)}$
with $p>0$, then $\operatorname{diam}(\mathcal{A})\geq(1-2p)r$.

In our case, we have for $n\geq 100$ and hence $2^{n(1-h)-1}\geq
2^{n\left(1-0.03-0.01\right)}\geq 2^{nH\left(\frac{1}{2}-\frac{1}{8}\right)}.$
Thus,
$\operatorname{diam}(\mathcal{A})\geq\left(1-\frac{2}{8}\right)n=\left(1-\frac{1}{4}\right)n$.
That is, there exist two vectors in $\mathcal{A}$ which differ in at least
$\left(1-\frac{1}{4}\right)n$ coordinates. Let
$\lambda^{\prime}=\left(\lambda_{1}^{\prime},\cdots,\lambda_{n}^{\prime}\right),\lambda^{\prime\prime}=\left(\lambda_{1}^{\prime\prime},\cdots,\lambda_{n}^{\prime\prime}\right)\in\mathcal{A}$
with
$\left\|\lambda^{\prime}-\lambda^{\prime\prime}\right\|_{1}=\operatorname{diam}(\mathcal{A})$.
Set
$\lambda=\left(\lambda_{1},\cdots,\lambda_{n}\right)=\frac{\lambda^{\prime}-\lambda^{\prime\prime}}{2}.$
All $\lambda_{j}\in\\{-1,0,+1\\}$ and $\lambda_{j}=0$ if and only if
$\lambda_{j}^{\prime}=\lambda_{j}^{\prime\prime}$. Therefore,
$\left|\left\\{j:\lambda_{j}=0\right\\}\right|=n-\left\|\lambda^{\prime}-\lambda^{\prime\prime}\right\|_{1}=n-\operatorname{diam}(\mathcal{A})\leq\frac{1}{4}n.$
Moreover, for all $i$, we have
$L_{i}(\lambda_{1},\cdots,\lambda_{n})=\frac{L_{i}(\lambda_{1}^{\prime},\cdots,\lambda_{n}^{\prime})-L_{i}(\lambda_{1}^{\prime\prime},\cdots,\lambda_{n}^{\prime\prime})}{2}.$
Since $T$ is identical on $\lambda^{\prime}$ and
$\lambda^{\prime\prime},L_{i}\left(\lambda^{\prime}\right)$ and
$L_{l}\left(\lambda^{\prime\prime}\right)$ lie on a common interval of length
$1$. Thus $\left|L_{i}(\lambda_{1},\cdots,\lambda_{n})\right|\leq\frac{1}{2}$.

∎

By Lemmas 3.6 and 3.7, we are ready to prove Lemma 3.4.

###### Proof of Lemma 3.4.

By Lemmas 3.6 and 3.7, there exists a partial coloring
$\\{\lambda_{j}\\}_{[n]}\in\\{-1,0,1\\}_{[n]}$ such that
$\left|j:\lambda_{j}=0\right|\leq\frac{1}{4}n$ and
$\left|\sum_{j=1}^{n}\lambda_{j}U_{ij}\right|\leq\frac{1}{2},\forall i\in[n]$.
Let $\tilde{c}=\sum_{j=1}^{n}\frac{\lambda_{j}}{\sqrt{n}}q_{j}$. The cost
difference w.r.t. $\\{\tilde{c},-\tilde{c}\\}$ is

$\displaystyle\operatorname{cost}_{2}(P,\\{\tilde{c},-\tilde{c}\\})-\operatorname{cost}_{2}(Q,\\{\tilde{c},-\tilde{c}\\})$
$\displaystyle=2\sum_{i=1}^{n}\left|\langle
q_{i},\tilde{c}\rangle\right|-\sum_{i=1}^{n}\left|\langle
p_{i},\tilde{c}\rangle\right|=2\sum_{j=1}^{n}\left|\frac{\lambda_{j}}{\sqrt{n}}\right|-\sum_{i=1}^{n}\left|\langle
p_{i},\sum_{j=1}^{n}\frac{\lambda_{j}}{\sqrt{n}}q_{j}\rangle\right|$
$\displaystyle=2\sum_{j=1}^{n}\left|\frac{\lambda_{j}}{\sqrt{n}}\right|-\sum_{i=1}^{n}\left|\sum_{j=1}^{n}\frac{\lambda_{j}}{\sqrt{n}}U_{ij}\right|.$

Due to our choice of $\\{\lambda_{j}\\}_{[n]}$, we would have that

$\displaystyle\sum_{j=1}^{n}\left|\frac{\lambda_{j}}{\sqrt{n}}\right|=\left(1-\frac{\left|j:\lambda_{j}=0\right|}{n}\right)\sqrt{n}\geq\frac{3}{4}\sqrt{n},$
$\displaystyle\sum_{i=1}^{n}\left|\sum_{j=1}^{n}\frac{\gamma_{j}}{\sqrt{n}}U_{ij}\right|=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left|\sum_{j=1}^{n}\lambda_{j}U_{ij}\right|\leq\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\frac{1}{2}=\frac{1}{2}\sqrt{n}.$

Combining together, we would have that
$\operatorname{cost}_{2}(P,\\{\tilde{c},-\tilde{c}\\})-\operatorname{cost}_{2}(Q,\\{\tilde{c},-\tilde{c}\\})\geq
2(\frac{3}{4}\sqrt{n}-\frac{1}{2}\sqrt{n})=\frac{1}{2}\sqrt{n}.$ To complete
proof, note that
$\left\|\tilde{c}\right\|_{2}=\sqrt{\sum_{k=1}^{n}\frac{\lambda_{j}^{2}}{n}}\leq\sqrt{\sum_{j=1}^{n}\frac{1}{n}}=1.$
Since $d>2n$, we can always find a vector $\hat{c}$ such that $\hat{c}\perp
P,Q$ and
$\left\|\hat{c}\right\|_{2}^{2}=1-\left\|\tilde{c}\right\|_{2}^{2}\geq 0$. Let
$c=\tilde{c}+\hat{c}$, we should have that $c$ is of unit norm and

$\operatorname{cost}_{2}(P,\\{c,-c\\})-\operatorname{cost}_{2}(Q,\\{c,-c\\})=\operatorname{cost}_{2}(P,\\{\tilde{c},-\tilde{c}\\})-\operatorname{cost}_{2}(Q,\\{\tilde{c},-\tilde{c}\\})\geq\frac{1}{2}\sqrt{n}.$

∎

###  3.3 Proof of Lemma 3.5: Construction of A Large Family $\mathcal{P}$

We first present the following lemma showing that the principal angles are
likely to be large between random subspaces.

######  Lemma 3.9 (Large principal angles between random subspaces).

Let $\mathcal{X},\mathcal{Y}$ be two sub-spaces chosen from the uniform
distribution on the Grassmann manifold of $n$-planes in $\mathbb{R}^{d}$
$\left(n=O\left(\frac{d}{\log d}\right)\right)$ endowed with its canonical
metric. We have

$\operatorname{Pr}\left(\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(\mathcal{X},\mathcal{Y}\right)<\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right)\right)<\exp\left(-\frac{1}{128}10^{-6}\log\left(\frac{1}{1-\frac{1}{32}10^{-6}}\right)\cdot
nd\right).$

With Lemma 3.9, we are ready to show the existence of a large enough family
$\mathcal{P}$.

###### Proof of Lemma 3.5.

We will generate
$\exp\left(\frac{1}{256}10^{-6}\log\left(\frac{1}{1-\frac{1}{32}10^{-6}}\right)\cdot
nd\right)$ sub-spaces, each of which is chosen from uniform distribution on
the Grassmann manifold of $n$-planes in $\mathbb{R}^{d}$. We then let our
dataset be arbitrary orthonormal bases of the subspace. Notice that by Lemma
3.3, the choice of the orthonormal bases will not affect the value of the
principal angles. With the result of lemma 3.9, we have that for any two
datasets $P$ and $Q$,

$\displaystyle\operatorname{Pr}\left(\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(P,Q\right)<\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right)\right)<\exp\left(-\frac{1}{128}10^{-6}\log\left(\frac{1}{1-\frac{1}{32}10^{-6}}\right)\cdot
nd\right).$

We then consider that

$\displaystyle\operatorname{Pr}\left(\forall P\neq
Q\in\mathcal{P},\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(P,Q\right)\geq\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right)\right)$
$\displaystyle=1-\operatorname{Pr}\left(\exists P\neq
Q\in\mathcal{P},\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(P,Q\right)<\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right)\right)$
$\displaystyle\geq 1-\sum_{i\neq
j}\operatorname{Pr}\left(\theta_{\frac{1}{32}10^{-6}\cdot
n}\left(P,Q\right)<\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right)\right)$
$\displaystyle>1-\left(\exp\left(\frac{1}{256}10^{-6}\log\left(\frac{1}{1-\frac{1}{32}10^{-6}}\right)\cdot
nd\right)\right)^{2}\cdot\exp\left(-\frac{1}{128}10^{-6}\log\left(\frac{1}{1-\frac{1}{32}10^{-6}}\right)\cdot
nd\right)=0.$

Therefore, there is a positive probability for us to find enough datasets that
fulfill our requirement, which shows the existence of the family. ∎

It remains to prove Lemma 3.9. The first idea is to apply Random Matrix
Theory, e.g. [40], which shows that with high probability the Hilbert-Schmidt
norm of a random matrix is small. However, the theory only considers the
squared matrices and their results may not be strong enough to have a bound of
$\exp\left(-O(nd)\right)$. Instead, we take advantage of the techniques in
[1], which calculates the distribution of the largest canonical angle
$\theta_{1}$. Using algebraic calculations, we extend their ideas to bound
$\theta_{O(n)}$.

For preparation, we first introduce several useful notions and facts for
calculation.

######  Definition 3.10 (Definition 2.1.10 in [41]).

The multivariate gamma function, denoted by $\Gamma_{m}(a)$, is defined to be

$\Gamma_{m}(a)=\int_{A>0}\operatorname{etr}(-A)(\operatorname{det}A)^{a-(m+1)/2}(dA),$

$\left[\operatorname{Re}(a)>\frac{1}{2}(m-1)\right]$, where
$\operatorname{etr}(.)\equiv\exp\operatorname{tr}(.)$ and the integral is over
the space of positive definite (and hence symmetric) $m\times m$ matrices.
(Here, and subsequently, the notation $A>0$ means that $A$ is positive
definite.)

Multivariate gamma functions can also be expressed as a product of ordinary
gamma functions, and satisfy the following property.

######  Lemma 3.11 (Theorem 2.1.12 in [41]).

$\Gamma_{m}(a)=\pi^{m(m-1)/4}\prod_{i=1}^{m}\Gamma\left[a-\frac{1}{2}(i-1)\right],\quad\left[\operatorname{Re}(a)>\frac{1}{2}(m-1)\right].$

We also need the Gaussian hypergeometric function of matrix argument.

######  Definition 3.12 (Definition 7.3.1 in [41]).

The Gaussian hypergeometric function of matrix argument is given by

${}_{2}F_{1}\left(e,f;g;X\right)=\sum_{k=0}^{\infty}\sum_{\kappa}\frac{\left(e\right)_{\kappa}\left(f\right)_{\kappa}}{\left(g\right)_{\kappa}}\frac{C_{\kappa}(X)}{k!},$

where $\sum_{\kappa}$ denotes summation over all partitions
$\kappa=\left(k_{1},\ldots,k_{m}\right),k_{1}\geq\cdots\geq$ $k_{m}\geq 0$, of
$k,C_{\kappa}(X)$ is the zonal polynomial of $X$ corresponding to $\kappa$ and
the generalized hypergeometric coefficient $(a)_{\kappa}$ is given by

$(a)_{\kappa}=\prod_{i=1}^{m}\left(a-\frac{1}{2}(i-1)\right)_{k_{i}},$

where $(a)_{k}=a(a+1)\ldots(a+k-1),(a)_{0}=1$. Here $X$, the argument of the
function, is a complex symmetric $q\times q$ matrix, and the parameters
$e,f,g$ are arbitrary complex numbers. Denominator parameter $g$ is not
allowed to be zero or an integer or half-integer $\leqslant\frac{1}{2}(m-1)$.

Moreover, we have the following properties of this function.

######  Lemma 3.13 (Theorem 7.4.2. in [41]).

The ${}_{2}F_{1}$ function has the integral representation

$\begin{gathered}{}_{2}F_{1}(e,f;g;X)=\frac{\Gamma_{q}(g)}{\Gamma_{q}(e)\Gamma_{q}(g-e)}\int_{0<Y<I_{q}}\operatorname{det}(I_{q}-XY)^{-f}(\operatorname{det}Y)^{e-(q+1)/2}\\\
\cdot\operatorname{det}(I_{q}-Y)^{g-e-(q+1)/2}(dY),\end{gathered}$

where $q$ is the size of $X$, valid for
$\operatorname{Re}(X)<I_{q},\operatorname{Re}(e)>\frac{1}{2}(q-1),\operatorname{Re}(g-e)>\frac{1}{2}(q-1)$.

######  Lemma 3.14 (Theorem 7.4.3. in [41]).

The ${}_{2}F_{1}$ function satisfies that

$\displaystyle{}_{2}F_{1}(e,f;g;X)$
$\displaystyle=\operatorname{det}(I_{q}-X)^{-f}{}_{2}F_{1}\left(g-e,f;g;-X(I_{q}-X)^{-1}\right).$

Combining Lemma 3.13 and Lemma 3.14, it is easy to verify that

######  Lemma 3.15.

The ${}_{2}F_{1}$ function satisfies that

$\displaystyle\int_{0<Y<I_{q}}\operatorname{det}(I_{q}-XY)^{-f}(\operatorname{det}Y)^{e-(q+1)/2}\operatorname{det}(I_{q}-Y)^{g-e-(q+1)/2}dY$
$\displaystyle=\frac{\Gamma_{q}(e)\Gamma_{q}(g-e)}{\Gamma_{q}(g)}\operatorname{det}(I_{q}-X)^{-f}{}_{2}F_{1}\left(g-e,f;g;-X(I_{q}-X)^{-1}\right)$

where $q$ is the size of $X$, valid for
$\operatorname{Re}(X)<I_{q},\operatorname{Re}(e)>\frac{1}{2}(q-1),\operatorname{Re}(g-e)>\frac{1}{2}(q-1).$

We also have the function value of the identity matrix being.

######  Lemma 3.16 (Equation (3.2) in [43]).

The value of ${}_{2}F_{1}$ function for matrix identity matrix $I_{q}$ is

${}_{2}F_{1}\left(e,f;g;I_{q}\right)=\frac{\Gamma_{q}(g)\Gamma_{q}(g-e-f)}{\Gamma_{q}(g-e)\Gamma_{q}(g-f)}.$

With the help of the above notations, we have the joint distribution of the
square of the cosine of the canonical angles given in [1]

######  Lemma 3.17 (Section 2 in [1]).

Let $\mathcal{X},\mathcal{Y}$ be two sub-spaces chosen from the uniform
distribution on the Grassmann manifold of $n$-planes in $\mathbb{R}^{d}$, with
$n\geq 2n$. Let $\theta_{1}\leq\cdots\leq\theta_{n}$ be the canonical angles
between $\mathcal{X}$ and $\mathcal{Y}$, and have
$\mu_{1}\geq\cdots\geq\mu_{n}$ such that $\mu_{i}=\cos^{2}\theta_{i}$. The
joint p.d.f. of the $\mu$’s is thus given by

$\operatorname{dens}\left(\mu_{1},\cdots,\mu_{n}\right)=c_{n,n,d-n}\prod_{i<j}\left|\mu_{i}-\mu_{j}\right|\prod_{i=1}^{p}\mu_{i}^{-\frac{1}{2}}\left(1-\mu_{i}\right)^{\frac{1}{2}\left(d-2n-1\right)}.$

where
$c_{n,n,d-n}=\frac{\pi^{\frac{n^{2}}{2}}}{\Gamma_{n}\left(\frac{n}{2}\right)}\cdot\frac{\Gamma_{n}\left(\frac{d}{2}\right)}{\Gamma_{n}\left(\frac{n}{2}\right)\Gamma_{n}\left(\frac{d-n}{2}\right)}$.

We now get back to the proof of Lemma 3.9.

###### Proof of Lemma 3.9.

For simplicity of expression, we denote $\frac{1}{32}10^{-6}\cdot
n=an$,$\theta_{i}=\theta_{i}\left(\mathcal{X},\mathcal{Y}\right)$ and
$\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right)=\theta$. Let
$1\geq\mu_{1}\geq\cdots\geq\mu_{n}\geq 0$ such that
$\mu_{i}=\cos^{2}\theta_{i}$ and $\mu=\cos^{2}\theta$. By Lemma 3.17, we have

$\operatorname{dens}\left(\mu_{1},\cdots,\mu_{n}\right)=c_{n,n,d-n}\prod_{i<j}\left|\mu_{i}-\mu_{j}\right|\prod_{i=1}^{p}\mu_{i}^{-\frac{1}{2}}\left(1-\mu_{i}\right)^{\frac{1}{2}\left(d-2n-1\right)}.$

Observe that the determinant of the Jacobian of the change of variables
between $\mu_{i}$s and $\theta_{i}$s are
$\prod_{i=1}^{n}2\sin\theta_{i}\cos\theta_{i}$, to obtain

$\operatorname{dens}\left(\theta_{1},\cdots,\theta_{n}\right)=2c_{n,n,d-n}\prod_{i<j}\left|\cos^{2}\theta_{i}-\cos^{2}\theta_{j}\right|\prod_{i=1}^{n}\cos^{0}\theta_{i}\sin^{d-2n}\theta_{i}.$

The rest of the proof is to calculate the probability we are interested in

$\displaystyle\operatorname{Pr}\left(\theta_{an}<\theta\right)$
$\displaystyle=\int_{\Theta^{\star}}\operatorname{dens}\left(\theta_{1},\cdots,\theta_{n}\right)d\theta_{1}\cdots\theta_{n}$
$\displaystyle=\int_{\Theta^{\star}}2c_{n,n,d-n}\prod_{i<j}\left|\cos^{2}\theta_{i}-\cos^{2}\theta_{j}\right|\prod_{i=1}^{n}\sin^{d-2n}\theta_{i}d\theta_{1}\cdots\theta_{n}$
$\displaystyle\leq\int_{\Theta^{\star}}2c_{n,n,d-n}\prod_{i<j\leq
an}\left|\cos^{2}\theta_{i}-\cos^{2}\theta_{j}\right|\prod_{i=1}^{an}\sin^{d-2n}\theta_{i}d\theta_{1}\cdots\theta_{n}$
$\displaystyle\leq\left(\frac{\pi}{2}\right)^{(1-a)n}\int_{\Theta^{\star}}2c_{n,n,d-n}\prod_{i<j\leq
an}\left|\cos^{2}\theta_{i}-\cos^{2}\theta_{j}\right|\prod_{i=1}^{an}\sin^{d-2n}\theta_{i}d\theta_{1}\cdots\theta_{an}$
$\displaystyle=\left(\frac{\pi}{2}\right)^{(1-a)n}\int_{\mu^{\star}}c_{n,n,d-n}\prod_{i<j\leq
an}\left|\mu_{i}-\mu_{j}\right|\prod_{i=1}^{an}\mu_{i}^{-\frac{1}{2}}(1-\mu_{i})^{\frac{d-2n-1}{2}}d\mu_{1}\cdots\mu_{an},$

where
$\Theta^{\star}=\left\\{0\leq\theta_{1}\leq\cdots\leq\theta_{an}<\theta\right\\}$
and $\mu^{\star}=\left\\{1\geq\mu_{1}\geq\cdots\geq\mu_{an}>\mu\right\\}.$
Denote $I_{n}$ be the $n\times n$ identity matrix. The change of variables
$\mu_{i}=(1-\mu)t_{i}+\mu$ gives

$\displaystyle\operatorname{Pr}\left(\theta_{an}<\theta\right)$
$\displaystyle\leq\left(\frac{\pi}{2}\right)^{(1-a)n}c_{n,n,d-n}(1-\mu)^{\frac{an(an-1)}{2}}\mu^{-\frac{an}{2}}(1-\mu)^{\frac{an(d-2n-1)}{2}}(1-\mu)^{an}$
$\displaystyle\quad\int_{1\geq t_{1}\geq\cdots\geq t_{an}\geq 0}\prod_{i<j\leq
an}\left|t_{i}-t_{j}\right|\times\prod_{i=1}^{an}\left(1+\frac{1-\mu}{\mu}t_{i}\right)^{-\frac{1}{2}}(1-t_{i})^{\frac{d-2n-1}{2}}dt_{1}\cdots
t_{an}$
$\displaystyle=\left(\frac{\pi}{2}\right)^{(1-a)n}c_{n,n,d-n}(1-\mu)^{\frac{an(an-1)}{2}}\mu^{-\frac{an}{2}}(1-\mu)^{\frac{an(d-2n+1)}{2}}$
$\displaystyle\quad\frac{2^{an}}{V\left(O_{an}\right)}\int_{0<Y<I_{an}}\left(\operatorname{det}\left(I_{an}+\frac{1-\mu}{\mu}I_{an}Y\right)\right)^{-\frac{1}{2}}\times\left(\operatorname{det}(I_{an}-Y)\right)^{\frac{d-2n-1}{2}}dY,$

where
$V\left(O_{q}\right)=\int_{O_{q}}Q^{T}\mathrm{d}Q=\frac{2^{q}\pi^{q^{2}/2}}{\Gamma_{q}\left(\frac{q}{2}\right)}$
is the volume of the orthogonal group $O_{q}$ [Page 71 in [41]] and the last
equation comes from the fact that
$dY=\prod\left|t_{i}-t_{j}\right|dT\left(Q^{T}dQ\right)$, where
$Y=QTQ^{\mathrm{T}}$ is an eigen-decomposition with eigenvalues sorted in non-
increasing order, and $Q$ cancels out everywhere in the integrated. The
inequality signs in the integral means PSD ordering and factor $2^{an}$
appears because the eigen-decomposition is defined up to the choice of the
direction of the eigenvectors. This procedure is similar to that in Section 3
of [1].

On the other hand, we have the property of Lemma 3.15 to have

$\displaystyle\int_{0<Y<I_{q}}$
$\displaystyle\operatorname{det}(I_{q}-XY)^{-f}(\operatorname{det}Y)^{e-(q+1)/2}\operatorname{det}(I_{q}-Y)^{g-e-(q+1)/2}dY$
$\displaystyle\quad=\frac{\Gamma_{q}(e)\Gamma_{q}(g-e)}{\Gamma_{q}(g)}\operatorname{det}(I_{q}-X)^{-f}{}_{2}F_{1}\left(g-e,f;g;-X(I_{q}-X)^{-1}\right),$

We make the following appointment

$\left\\{\begin{array}[]{l}q=an\\\ -f=-\frac{1}{2}\\\ e-(q+1)/2=0\\\
g-e-(q+1)/2=\frac{d-2n-1}{2}\\\
X=-\frac{1-\mu}{\mu}I_{an}\end{array}\right.\Rightarrow\left\\{\begin{array}[]{l}q=an\\\
f=\frac{1}{2}\\\ e=\frac{an+1}{2}\\\ g=\frac{d-2(1-a)n+1}{2}\\\
X=-\frac{1-\mu}{\mu}I_{an}\end{array}\right.,$

and we get

$\displaystyle\operatorname{Pr}\left(\theta_{an}<\theta\right)\leq$
$\displaystyle\left(\frac{\pi}{2}\right)^{(1-a)n}\cdot\frac{\pi^{\frac{n^{2}}{2}}}{\Gamma_{n}\left(\frac{n}{2}\right)}\cdot\frac{\Gamma_{n}\left(\frac{d}{2}\right)}{\Gamma_{n}\left(\frac{n}{2}\right)\Gamma_{n}\left(\frac{d-n}{2}\right)}\cdot\frac{\Gamma_{an}\left(\frac{an}{2}\right)}{\pi^{(an)^{2}/2}}$
$\displaystyle\frac{\Gamma_{an}\left(\frac{an+1}{2}\right)\Gamma_{an}\left(\frac{d-(2-a)n}{2}\right)}{\Gamma_{an}\left(\frac{d-2(1-a)n+1}{2}\right)}\mu^{-\frac{an}{2}}(1-\mu)^{\frac{an(d-(2-a)n)}{2}}\operatorname{det}\left(\frac{1}{\mu}I_{an}\right)^{-\frac{1}{2}}$
$\displaystyle{}_{2}F_{1}\left(\frac{d-(2-a)n}{2},\frac{1}{2};\frac{d-2(1-a)n+1}{2};(1-\mu)I_{an}\right).$

We now consider the value of Gaussian hypergeometric function of matrix
argument. By Lemma 3.13,

for positive definite $q\times q$ matrix $Y$, $0<1-\mu<1$ and $b>0$ ,

$\displaystyle\operatorname{det}(I_{q}-(1-\mu)Y)^{-f}=\left(\prod_{i=1}^{q}(1-(1-\mu)y_{i})\right)^{-f}<\left(\prod_{i=1}^{q}(1-y_{i})\right)^{-f}=\operatorname{det}(I_{q}-Y)^{-f}.$
$\displaystyle{}_{2}F_{1}\left(e,f;g;(1-\mu)I_{q}\right)$
$\displaystyle=\frac{\Gamma_{m}(g)}{\Gamma_{m}(e)\Gamma_{m}(g-e)}\int_{0<Y<I_{q}}\operatorname{det}(I_{q}-(1-\mu)Y)^{-f}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(\operatorname{det}Y)^{e-\frac{q+1}{2}}\operatorname{det}(I_{q}-Y)^{g-e-\frac{q+1}{2}}(dY)$
$\displaystyle\leq\frac{\Gamma_{q}(g)}{\Gamma_{q}(e)\Gamma_{q}(g-e)}\int_{0<Y<I_{q}}\operatorname{det}(I_{q}-Y)^{-f}(\operatorname{det}Y)^{e-\frac{q+1}{2}}\operatorname{det}(I_{q}-Y)^{g-e-\frac{q+1}{2}}(dY)$
$\displaystyle={}_{2}F_{1}\left(e,f;g;I_{q}\right).$

Combining with the value of the identity matrix given by Lemma 3.16, we have

$\displaystyle{}_{2}F_{1}\left(\frac{d-(2-a)n}{2},\frac{1}{2};\frac{d-2(1-a)n+1}{2};(1-\mu)I_{an}\right)$
$\displaystyle\leq{}_{2}F_{1}\left(\frac{d-(2-a)n}{2},\frac{1}{2};\frac{d-2(1-a)n+1}{2};I_{an}\right)=\frac{\Gamma_{an}\left(\frac{d-2(1-a)n+1}{2}\right)\Gamma_{an}\left(\frac{an}{2}\right)}{\Gamma_{an}\left(\frac{an+1}{2}\right)\Gamma_{an}\left(\frac{d-2(1-a)n}{2}\right)}.$

Bringing it back, we have that

$\displaystyle\operatorname{Pr}\left(\theta_{an}<\theta\right)\leq$
$\displaystyle\left(\frac{\pi}{2}\right)^{(1-a)n}\cdot\frac{\pi^{\frac{n^{2}}{2}}}{\Gamma_{n}\left(\frac{n}{2}\right)}\cdot\frac{\Gamma_{n}\left(\frac{d}{2}\right)}{\Gamma_{n}\left(\frac{n}{2}\right)\Gamma_{n}\left(\frac{d-n}{2}\right)}\cdot\frac{\Gamma_{an}\left(\frac{an}{2}\right)}{\pi^{(an)^{2}/2}}$
$\displaystyle\frac{\Gamma_{an}\left(\frac{an}{2}\right)\Gamma_{an}\left(\frac{d-(2-a)n}{2}\right)}{\Gamma_{an}\left(\frac{d-2(1-a)n}{2}\right)}(1-\mu)^{\frac{an(d-(2-a)n)}{2}}$
$\displaystyle\leq\left(\frac{\pi}{2}\right)^{(1-a)n}\cdot\pi^{\frac{(1-a^{2})n^{2}}{2}}\cdot\frac{\Gamma_{n}\left(\frac{d}{2}\right)}{\Gamma_{n}\left(\frac{d-n}{2}\right)}\left(\Gamma_{an}\left(\frac{an}{2}\right)\right)^{2}\cdot(1-\mu)^{\frac{an(d-(2-a)n)}{2}}.$

Using Lemma 3.11 and identities $\Gamma\left(\frac{1}{2}\right)=\sqrt{\pi}$
and $\Gamma\left(m+1\right)=m\Gamma\left(m\right)$, we would have that

$\displaystyle\frac{\Gamma_{n}\left(\frac{d}{2}\right)}{\Gamma_{n}\left(\frac{d-n}{2}\right)}$
$\displaystyle=\frac{\prod_{i=1}^{n}\Gamma\left(\frac{d-n}{2}+\frac{i}{2}\right)}{\prod_{i=1}^{n}\Gamma\left(\frac{d-2n}{2}+\frac{i}{2}\right)}=\prod_{i=1}^{n}\left(\frac{d-n-1}{2}+\frac{i}{2}\right)\cdots\left(\frac{d-2n}{2}+\frac{i}{2}\right)$
$\displaystyle\leq\left(\frac{d-1}{2}\right)^{n^{2}}=\exp\left(O(n^{2}\log
d)\right).$
$\displaystyle\left(\Gamma_{an}\left(\frac{an}{2}\right)\right)^{2}$
$\displaystyle=\pi^{\frac{an(an-1)}{2}}\left(\prod_{i=1}^{an}\Gamma\left(\frac{i}{2}\right)\right)^{2}\leq\pi^{\frac{an(an-1)}{2}}\left(\Gamma\left(\frac{an}{2}\right)\right)^{2an}$
$\displaystyle\leq\pi^{\frac{an(an-1)}{2}}\left(\sqrt{\pi}\right)^{2an}\left(\frac{an-1}{2}\right)^{a^{2}n^{2}}=\exp\left(O(n^{2}\log
n)\right).$

Combining together, we would have that

$\displaystyle\operatorname{Pr}\left(\theta_{an}<\theta\right)$
$\displaystyle\leq\exp\left(O(n^{2}\log n)\right)\cdot\exp\left(O(n^{2}\log
d)\right)\cdot(1-\mu)^{\frac{and}{2}}$
$\displaystyle\leq\exp\left(-\frac{a}{2}\log\left(\frac{1}{1-\mu}\right)\cdot
nd+O(n^{2}\log n)+O(n^{2}\log d)\right).$

In our case, $a=\frac{1}{32}10^{-6}$ and
$\mu=\cos^{2}\theta=\frac{1}{32}10^{-6}$ this should be

$\displaystyle\operatorname{Pr}\left(\theta_{\frac{1}{32}10^{-6}\cdot
n}<\arccos\left(\frac{10^{-3}}{4\sqrt{2}}\right)\right)$
$\displaystyle\leq\exp\left(-\frac{1}{64}10^{-6}\log\left(\frac{1}{1-\frac{1}{32}10^{-6}}\right)\cdot
nd+O(n^{2}\log n)+O(n^{2}\log d)\right)$
$\displaystyle<\exp\left(-\frac{1}{128}10^{-6}\log\left(\frac{1}{1-\frac{1}{32}10^{-6}}\right)\cdot
nd\right).$

where the last equation holds for $d=\Omega(n\log d)$ with sufficiently large
constant. ∎

###  3.4 Extension to General $z\geq 1$

In this section, we generalize the lower bound to arbitrary powers $z\geq 1$.
We again focus on the cases where $k=2$ as we can generalize the result to
higher $k$ in Section 3.5. For ease of analysis, we again do not require the
construction of datasets $P\subseteq[\gamma]^{d}$ and actually ensure that
every $P$ consists of orthonormal bases of some subspaces. At the end of the
proof, we will show how to round and scale these datasets $P$ into
$[\gamma]^{d}$.

The cost function we have now without scaling is

$\displaystyle\operatorname{cost}_{z}(P,\\{c,-c\\})$
$\displaystyle=\sum_{i=1}^{n}\min\left\\{d(p_{i},c)^{z},d(p_{i},-c)^{z}\right\\}$
$\displaystyle=\sum_{i=1}^{n}\left(\left\|p_{i}\right\|_{2}^{2}+\left\|c\right\|_{2}^{2}-2\left|\langle
p_{i},c\rangle\right|\right)^{\frac{z}{2}}=\sum_{i=1}^{n}\left(2-2\left|\langle
p_{i},c\rangle\right|\right)^{\frac{z}{2}}.$

The value is upper bounded by $2^{\frac{z}{2}}n$ and the difference between
the cost of two datasets is

$\left|\operatorname{cost}_{z}(P,\\{c,-c\\})-\operatorname{cost}_{z}(Q,\\{c,-c\\})\right|=\left|\sum_{i=1}^{n}\left(2-2\left|\langle
p_{i},c\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(2-2\left|\langle
q_{i},c\rangle\right|\right)^{\frac{z}{2}}\right|.$

Similarly, to prove a lower bound on $sc(n,\Delta,2,z,d,\varepsilon)$, we just
need to find a large enough set $\mathcal{P}$ such that the cost function of
any two elements is separated. The key tool is the following inequation.

######  Lemma 3.18 (Inequality of Taylor expansion).

For any $0<z\leq 2$ and any $x\in\left[0,\frac{1}{2}\right]$, we have

$1-{\frac{z}{2}}x-z\left(1-{\frac{z}{2}}\right)x^{2}\leq(1-x)^{\frac{z}{2}}\leq
1-{\frac{z}{2}}x.$

For any $z\geq 2$ and any $x\in\left[0,\frac{1}{2}\right]$, we have

$1-{\frac{z}{2}}x\leq(1-x)^{\frac{z}{2}}\leq
1-{\frac{z}{2}}x+{\frac{z}{2}}\left({\frac{z}{2}}-1\right)x^{2}.$

###### Proof.

We first deal with the case when $0<z\leq 2$. Note that the right hand of the
inequation can actually be found in [15]. For any $0<z\leq 2$ and any
$x\in\left[0,\frac{1}{2}\right]$, we have
$(1-x)^{\frac{z}{2}}=\exp\left(-{\frac{z}{2}}\sum_{n=1}^{\infty}(x)^{n}/n\right)$.
Since $z\leq 2$, this is at most
$\exp\left(-\sum_{n=1}^{\infty}\left({\frac{z}{2}}x\right)^{n}/n\right)=1-{\frac{z}{2}}x$.

For the other side, it is equal for us to prove

$h(x)=z\left(1-{\frac{z}{2}}\right)x^{2}+{\frac{z}{2}}x-1+(1-x)^{\frac{z}{2}}\geq
0,\forall x\in\left[0,\frac{1}{2}\right].$

Note that the first and second derivative of $h(x)$ is

$\displaystyle
h^{\prime}(x)=2z\left(1-{\frac{z}{2}}\right)x+{\frac{z}{2}}-{\frac{z}{2}}(1-x)^{{\frac{z}{2}}-1},$
$\displaystyle
h^{\prime\prime}(x)=2z\left(1-{\frac{z}{2}}\right)-{\frac{z}{2}}\left(1-{\frac{z}{2}}\right)(1-x)^{{\frac{z}{2}}-2}.$

since $x\in\left[0,\frac{1}{2}\right]$, we must have
$(1-x)^{{\frac{z}{2}}-2}\leq 2^{2-{\frac{z}{2}}}\leq 4$. We have
$h^{\prime\prime}(x)\geq 0,\forall x\in\left[0,\frac{1}{2}\right]$ and
consequently

$h^{\prime}(x)\geq h^{\prime}(0)=0,\forall
x\in\left[0,\frac{1}{2}\right],h(x)\geq h(0)=0,\forall
x\in\left[0,\frac{1}{2}\right].$

The case when $z\geq 2$ is rather similar. The left hand of the inequation can
again be found in [15]. For any $z\geq 2$ and any
$x\in\left[0,\frac{1}{2}\right]$, we have
$(1-x)^{\frac{z}{2}}=\exp\left(-{\frac{z}{2}}\sum_{n=1}^{\infty}(x)^{n}/n\right)$.
Since $z\geq 2$, this is at least
$\exp\left(-\sum_{n=1}^{\infty}\left({\frac{z}{2}}x\right)^{n}/n\right)=1-{\frac{z}{2}}x$.

For the other side, it is equal for us to prove

$h(x)=-{\frac{z}{2}}\left({\frac{z}{2}}-1\right)x^{2}+{\frac{z}{2}}x-1+(1-x)^{\frac{z}{2}}\leq
0,\forall x\in\left[0,\frac{1}{2}\right].$

Note that the first and second derivative of $h(x)$ is

$\displaystyle
h^{\prime}(x)=-{\frac{z}{2}}\left({\frac{z}{2}}-1\right)x+{\frac{z}{2}}-{\frac{z}{2}}(1-x)^{{\frac{z}{2}}-1},$
$\displaystyle
h^{\prime\prime}(x)=-{\frac{z}{2}}\left({\frac{z}{2}}-1\right)+{\frac{z}{2}}\left({\frac{z}{2}}-1\right)(1-x)^{{\frac{z}{2}}-2}.$

since $x\in\left[0,\frac{1}{2}\right]$, we must have
$(1-x)^{{\frac{z}{2}}-2}\leq\max\\{1,2^{2-{\frac{z}{2}}}\\}\leq 2$. We have
$h^{\prime\prime}(x)\leq 0,\forall x\in\left[0,\frac{1}{2}\right]$ and
consequently

$h^{\prime}(x)\leq h^{\prime}(0)=0,\forall
x\in\left[0,\frac{1}{2}\right],h(x)\leq h(0)=0,\forall
x\in\left[0,\frac{1}{2}\right].$

∎

With the inequation in Lemma 3.18, we have

######  Lemma 3.19.

Assume $P$ and $Q$ being two set of $n$ orthonormal bases in $\mathbb{R}^{d}$
(with $2n<d$). If we can find $\hat{c}$ to satisfy

$\left|\sum_{i=1}^{n}\left|\langle
p_{i},\hat{c}\rangle\right|-\sum_{i=1}^{n}\left|\langle
q_{i},\hat{c}\rangle\right|\right|>\frac{1}{2}\sqrt{n},$

where $\left\|\hat{c}\right\|=1$. We would then be able to find unit-norm
vector $c$ such that

$\left|\sum_{i=1}^{n}\left(2-2\left|\langle
p_{i},c\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(2-2\left|\langle
q_{i},c\rangle\right|\right)^{\frac{z}{2}}\right|\geq\left\\{\begin{matrix}\frac{2^{\frac{z}{2}}{z}}{8}\sqrt{n}-\frac{2^{\frac{z}{2}}{z}\left(1-{\frac{z}{2}}\right)}{4},0<z\leq
2\\\
\frac{2^{\frac{z}{2}}{z}}{8}\sqrt{n}-\frac{2^{\frac{z}{2}}{z}\left({\frac{z}{2}}-1\right)}{8},z\geq
2\end{matrix}\right.$

###### Proof.

Without loss of generality, we can assume that

$\sum_{i=1}^{n}\left|\langle
p_{i},\hat{c}\rangle\right|-\sum_{i=1}^{n}\left|\langle
q_{i},\hat{c}\rangle\right|>\frac{1}{2}\sqrt{n}.$

We can choose $\tilde{c}=\frac{1}{2}\hat{c}$ such that

$\left|\langle
p_{i},\tilde{c}\rangle\right|\leq\left\|p_{i}\right\|\left\|\tilde{c}\right\|\leq\frac{1}{2},\left|\langle
q_{i},\tilde{c}\rangle\right|\leq\left\|q_{i}\right\|\left\|\tilde{c}\right\|\leq\frac{1}{2},\forall
i\in[n],$

which fulfills the requirement of Lemma 3.18. For $0<z\leq 2$, we have that

$\displaystyle\sum_{i=1}^{n}\left(1-\left|\langle
q_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(1-\left|\langle
p_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}$
$\displaystyle\geq\sum_{i=1}^{n}\left(1-{\frac{z}{2}}\left|\langle
q_{i},\tilde{c}\rangle\right|-z\left(1-{\frac{z}{2}}\right)\langle
q_{i},\tilde{c}\rangle^{2}\right)-\sum_{i=1}^{n}\left(1-{\frac{z}{2}}\left|\langle
p_{i},\tilde{c}\rangle\right|\right)$
$\displaystyle={\frac{z}{2}}\left(\sum_{i=1}^{n}\left|\langle
p_{i},\tilde{c}\rangle\right|-\sum_{i=1}^{n}\left|\langle
q_{i},\tilde{c}\rangle\right|\right)-z\left(1-{\frac{z}{2}}\right)\sum_{i=1}^{n}\langle
q_{i},\tilde{c}\rangle^{2}.$

Based on our choice and the fact that $q_{i}$ is a set of $n$ orthonormal
bases, we have

$\displaystyle\sum_{i=1}^{n}\left|\langle
p_{i},\tilde{c}\rangle\right|-\sum_{i=1}^{n}\left|\langle
q_{i},\tilde{c}\rangle\right|=\frac{1}{2}\left(\sum_{i=1}^{n}\left|\langle
p_{i},\hat{c}\rangle\right|-\sum_{i=1}^{n}\left|\langle
q_{i},\hat{c}\rangle\right|\right)>\frac{1}{4}\sqrt{n},$
$\displaystyle\sum_{i=1}^{n}\langle
q_{i},\tilde{c}\rangle^{2}\leq\left\|\tilde{c}\right\|_{2}^{2}=\frac{1}{4}.$

We finally achieve

$\sum_{i=1}^{n}\left(1-\left|\langle
q_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(1-\left|\langle
p_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}\geq\frac{z}{8}\sqrt{n}-\frac{z\left(1-{\frac{z}{2}}\right)}{4}.$

Since $d>2n$, we can always find a vector $\bar{c}$ such that $\bar{c}\perp
p_{i},q_{i},i\in[n]$ and
$\left\|\bar{c}\right\|_{2}^{2}=1-\left\|\tilde{c}\right\|_{2}^{2}\geq 0$. Let
$c=\tilde{c}+\bar{c}$, we should have that $c$ is of unit norm and

$\displaystyle\sum_{i=1}^{n}\left(1-\left|\langle
q_{i},c\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(1-\left|\langle
p_{i},c\rangle\right|\right)^{\frac{z}{2}}$
$\displaystyle=\sum_{i=1}^{n}\left(1-\left|\langle
q_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(1-\left|\langle
p_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}$
$\displaystyle\geq\frac{z}{4}\varepsilon
n-\frac{z\left(1-{\frac{z}{2}}\right)}{4},$
$\displaystyle\left|\sum_{i=1}^{n}\left(2-2\left|\langle
p_{i},c\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(2-2\left|\langle
q_{i},c\rangle\right|\right)^{\frac{z}{2}}\right|$
$\displaystyle\geq\frac{2^{\frac{z}{2}}z}{8}\sqrt{n}-\frac{2^{\frac{z}{2}}z\left(1-{\frac{z}{2}}\right)}{4}.$

On the other hand, for $z\geq 2$, we have

$\displaystyle\sum_{i=1}^{n}\left(1-\left|\langle
q_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(1-\left|\langle
p_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}$
$\displaystyle\geq\sum_{i=1}^{n}\left(1-{\frac{z}{2}}\left|\langle
q_{i},\tilde{c}\rangle\right|\right)-\sum_{i=1}^{n}\left(1-{\frac{z}{2}}\left|\langle
p_{i},\tilde{c}\rangle\right|+{\frac{z}{2}}\left({\frac{z}{2}}-1\right)\langle
p_{i},\tilde{c}\rangle^{2}\right)$
$\displaystyle={\frac{z}{2}}\left(\sum_{i=1}^{n}\left|\langle
p_{i},\tilde{c}\rangle\right|-\sum_{i=1}^{n}\left|\langle
q_{i},\tilde{c}\rangle\right|\right)-{\frac{z}{2}}\left({\frac{z}{2}}-1\right)\sum_{i=1}^{n}\langle
p_{i},\tilde{c}\rangle^{2}\geq\frac{z}{8}\sqrt{n}-\frac{z\left({\frac{z}{2}}-1\right)}{8}.$

Since $d>2n$, we can always find a vector $\bar{c}$ such that $\bar{c}\perp
p_{i},q_{i},i\in[n]$ and
$\left\|\bar{c}\right\|_{2}^{2}=1-\left\|\tilde{c}\right\|_{2}^{2}\geq 0$. Let
$c=\tilde{c}+\bar{c}$, we should have that $c$ is of unit norm and

$\displaystyle\sum_{i=1}^{n}\left(1-\left|\langle
q_{i},c\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(1-\left|\langle
p_{i},c\rangle\right|\right)^{\frac{z}{2}}$
$\displaystyle=\sum_{i=1}^{n}\left(1-\left|\langle
q_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(1-\left|\langle
p_{i},\tilde{c}\rangle\right|\right)^{\frac{z}{2}}$
$\displaystyle\geq\frac{z}{8}\sqrt{n}-\frac{z\left({\frac{z}{2}}-1\right)}{8},$
$\displaystyle\left|\sum_{i=1}^{n}\left(2-2\left|\langle
p_{i},c\rangle\right|\right)^{\frac{z}{2}}-\sum_{i=1}^{n}\left(2-2\left|\langle
q_{i},c\rangle\right|\right)^{\frac{z}{2}}\right|$
$\displaystyle\geq\frac{2^{\frac{z}{2}}z}{8}\sqrt{n}-\frac{2^{\frac{z}{2}}z\left({\frac{z}{2}}-1\right)}{8}.$

∎

Combining the results from case $z=2$, we have

######  Lemma 3.20.

When $\gamma=\frac{3072\cdot
2^{\frac{z}{2}}\sqrt{d}}{z^{2}\cdot\varepsilon}=\Theta\left(\frac{\sqrt{d}}{\varepsilon}\right)$,
$d$ larger than a large enough constant and constant $z$, we have that
$sc(n,\gamma,2,z,d,\varepsilon)\geq\Omega\left(d\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},n\right\\}\right)$.

###### Proof.

Let $\varepsilon=\frac{z}{96}\tilde{\varepsilon}$. Denote

$\tilde{n}=\min\left\\{\Theta\left(\frac{1}{\tilde{\varepsilon}^{2}}\right),\Theta\left(\frac{d}{\log
d}\right),n\right\\}=\Omega\left(\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},n\right\\}\right)\geq 100.$

With the proof of second part of Theorem 1.3 and Lemma 3.19, for constant $z$,
we are able to find a set $\mathcal{P}$ with all points being orthonormal
bases and size being

$\exp\left(\Theta\left(\tilde{n}d\right)\right)=\exp\left(\Theta\left(d\min\left\\{\frac{1}{\tilde{\varepsilon}^{2}},\frac{d}{\log
d},n\right\\}\right)\right)=\exp\left(\Theta\left(d\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},n\right\\}\right)\right),$

such that for any two dataset in this set $P$ and $Q$, we would be able to
find a unit-norm vector $c$ satisfying

$\left|\sum_{i=1}^{n}\left(2-2\left|\langle
p_{i},c\rangle\right|\right)^{z}-\sum_{i=1}^{n}\left(2-2\left|\langle
q_{i},c\rangle\right|\right)^{z}\right|\geq\left\\{\begin{matrix}\frac{2^{\frac{z}{2}}{z}}{8}\sqrt{\tilde{n}}-\frac{2^{\frac{z}{2}}{z}\left(1-{\frac{z}{2}}\right)}{4},0<z\leq
2\\\
\frac{2^{\frac{z}{2}}{z}}{8}\sqrt{\tilde{n}}-\frac{2^{\frac{z}{2}}{z}\left({\frac{z}{2}}-1\right)}{8},z\geq
2\end{matrix}\right..$

We now show how to round and scale every dataset $P\in\mathcal{P}$ to
$[\gamma]^{d}$, where
$\gamma=\Theta\left(\frac{\sqrt{d}}{\varepsilon}\right)$. Without loss of
generality, we may assume that $\gamma$ is an odd integer. For a dataset
$P=\left(p_{1},\cdots,p_{\tilde{n}}\right)\in\mathcal{P}$, we will construct
$\tilde{\mathcal{P}}$ to be our final family as follows: For each of dataset
$P\in\mathcal{P}$, we shift the origin to
$\left(\lceil\frac{\gamma}{2}\rceil,\cdots,\lceil\frac{\gamma}{2}\rceil\right)$,
scale it by a factor of $\frac{\gamma}{2}$ and finally perform an upward
rounding on each dimension to put every point on the grid:

$\tilde{P}=\left(\lceil\frac{\gamma}{2}p_{1}\rceil+\lceil\frac{\gamma}{2}\rceil,\cdots,\lceil\frac{\gamma}{2}p_{\tilde{n}}\rceil+\lceil\frac{\gamma}{2}\rceil\right)=\left(\tilde{p}_{1},\cdots,\tilde{p}_{\tilde{n}}\right).$

We will then show that this set fulfills the requirement of Lemma 3.1. For
ease of explanation, we also define $\hat{P}$ to be the dataset without
rounding.

$\displaystyle\hat{P}=\left(\frac{\gamma}{2}p_{1}+\lceil\frac{\gamma}{2}\rceil,\cdots,\frac{\gamma}{2}p_{\tilde{n}}+\lceil\frac{\gamma}{2}\rceil\right)=\left(\hat{p}_{1},\cdots,\hat{p}_{\tilde{n}}\right).$

Moreover, let
$\bar{c}=\frac{\gamma}{2}c+\left(\lceil\frac{\gamma}{2}\rceil,\cdots,\lceil\frac{\gamma}{2}\rceil\right)$.
We must have that for the scaling dataset,

$\displaystyle\operatorname{cost}_{z}\left(\hat{P},\left\\{\bar{c},-\bar{c}\right\\}\right)=\frac{\gamma^{z}}{2^{z}}\operatorname{cost}_{z}\left(P,\\{c,-c\\}\right)\leq\frac{\gamma^{z}\tilde{n}}{2^{\frac{z}{2}}},$
$\displaystyle\operatorname{cost}_{z}\left(\hat{P},\left\\{\bar{c},-\bar{c}\right\\}\right)-\operatorname{cost}_{z}\left(\hat{Q},\left\\{\bar{c},-\bar{c}\right\\}\right)$
$\displaystyle=\frac{\gamma^{z}}{2^{z}}\left(\operatorname{cost}_{z}(P,\\{c,-c\\})-\operatorname{cost}_{z}(Q,\\{c,-c\\})\right)\geq\left\\{\begin{matrix}\frac{{z}\gamma^{z}}{8\cdot
2^{\frac{z}{2}}}\sqrt{\tilde{n}}-\frac{{z}\left(1-{\frac{z}{2}}\right)\gamma^{z}}{4\cdot
2^{\frac{z}{2}}},0<z\leq 2\\\ \frac{{z}\gamma^{z}}{8\cdot
2^{\frac{z}{2}}}\sqrt{\tilde{n}}-\frac{{z}\left({\frac{z}{2}}-1\right)\gamma^{z}}{8\cdot
2^{\frac{z}{2}}},z\geq 2\end{matrix}\right..$

On the other hand, for the rounding dataset, by our choice of $\gamma$, we
have

$\displaystyle\left|\left\|\hat{p}_{i}-\bar{c}\right\|_{2}^{z}-\left\|\tilde{p}_{i}-\bar{c}\right\|_{2}^{z}\right|$
$\displaystyle\leq\frac{\gamma^{z}}{2^{z}}2^{z}\frac{2\sqrt{d}}{\gamma}\leq\frac{\tilde{\varepsilon}\gamma^{z}}{64\cdot
2^{\frac{z}{2}}}.$

The case for $-\bar{c}$ and other datasets is similar. Therefore, we have that
for any dataset

$\displaystyle\left|\operatorname{cost}_{2}(\hat{P},\\{\bar{c},-\bar{c}\\})-\operatorname{cost}_{2}(\tilde{P},\\{\bar{c},-\bar{c}\\})\right|\leq\frac{\tilde{\varepsilon}\gamma^{z}\tilde{n}}{64\cdot
2^{\frac{z}{2}}},$
$\displaystyle\operatorname{cost}_{2}\left(\tilde{P},\left\\{\bar{c},-\bar{c}\right\\}\right)\leq\operatorname{cost}_{2}\left(\hat{P},\left\\{\bar{c},-\bar{c}\right\\}\right)+\frac{\tilde{\varepsilon}\gamma^{z}n}{64\cdot
2^{\frac{z}{2}}}\leq\frac{\gamma^{z}\tilde{n}}{2^{\frac{z}{2}}}+\frac{\tilde{\varepsilon}\gamma^{z}\tilde{n}}{64\cdot
2^{\frac{z}{2}}}\leq\frac{\gamma^{z}\cdot 2\tilde{n}}{2^{\frac{z}{2}}}.$

We can then have a rounded family $\tilde{\mathcal{P}}$ such that all points
are on the grid and we would be able to find $\bar{c}$,

$\displaystyle\operatorname{cost}_{2}\left(\tilde{P},\left\\{\bar{c},-\bar{c}\right\\}\right)-\operatorname{cost}_{2}\left(\tilde{Q},\left\\{\bar{c},-\bar{c}\right\\}\right)$
$\displaystyle\geq\operatorname{cost}_{2}\left(\hat{P},\left\\{\bar{c},-\bar{c}\right\\}\right)-\operatorname{cost}_{2}\left(\hat{Q},\left\\{\bar{c},-\bar{c}\right\\}\right)-\frac{\tilde{\varepsilon}\gamma^{z}\tilde{n}}{32\cdot
2^{\frac{z}{2}}}$
$\displaystyle\geq\left\\{\begin{matrix}\frac{{z}\gamma^{z}}{8\cdot
2^{\frac{z}{2}}}\sqrt{\tilde{n}}-\frac{{z}\left(1-{\frac{z}{2}}\right)\gamma^{z}}{4\cdot
2^{\frac{z}{2}}}-\frac{\tilde{\varepsilon}\gamma^{z}\tilde{n}}{32\cdot
2^{\frac{z}{2}}},0<z\leq 2\\\ \frac{{z}\gamma^{z}}{8\cdot
2^{\frac{z}{2}}}\sqrt{\tilde{n}}-\frac{{z}\left({\frac{z}{2}}-1\right)\gamma^{z}}{8\cdot
2^{\frac{z}{2}}}-\frac{\tilde{\varepsilon}\gamma^{z}\tilde{n}}{32\cdot
2^{\frac{z}{2}}},z\geq 2\end{matrix}\right.$

Note that for constant $z$ and our choice of $\tilde{n}$ that
$\sqrt{\tilde{n}}\geq\tilde{\varepsilon}\tilde{n}$ the right side is larger
than $\frac{{z}\gamma^{z}}{16\cdot
2^{\frac{z}{2}}}\tilde{\varepsilon}\tilde{n}$. On the other side, the cost
function is upper bounded by $\frac{\gamma^{z}\cdot
2\tilde{n}}{2^{\frac{z}{2}}}$. Therefore, as long as we make
$\varepsilon$-approximation, we must have

$\operatorname{cost}_{z}\left(P,\\{c,-c\\}\right)\notin(1\pm
3\varepsilon)\operatorname{cost}_{z}\left(Q,\\{c,-c\\}.\right)$

Moreover, we can find an origin being
$\left(\lceil\frac{\gamma}{2}\rceil,\cdots,\lceil\frac{\gamma}{2}\rceil\right)$
such that all the center points and data points have distance to it less than
$\frac{\gamma}{2}+\sqrt{d}\leq\gamma$. By Lemma 3.1, we have

$sc(n,\gamma,2,z,d,\varepsilon)\geq\Omega(\log\left|\mathcal{P}\right|)\geq\Omega\left(d\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},n\right\\}\right).$

∎

###  3.5 Extension to General $k\geq 2$

Recall that $\Delta\geq 4\lceil
k^{\frac{1}{d}}\rceil\gamma=\Omega\left(\frac{k^{\frac{1}{d}}\sqrt{d}}{\varepsilon}\right)$.
Without loss of generality, we may assume that $k$ is even. (If $k$ is odd, we
can use $k-1$ centers and put the rest center in a place not to affect the
value of the function but still have a similar asymptotic lower bound on the
size).

By proof of second part of Theorem 1.3 and Lemma 3.20, we can find a set
$\mathcal{P}$ with size being
$\exp\left(sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)$ with
property that

$\displaystyle\operatorname{cost}_{z}(P,\\{c,-c\\}),\operatorname{cost}_{z}(Q,\\{c,-c\\})\leq\frac{\gamma^{z}\cdot
2\cdot\frac{2n}{k}}{2^{\frac{z}{2}}},$
$\displaystyle\operatorname{cost}_{z}(P^{i},\\{c,-c\\})-\operatorname{cost}_{z}(P^{j},\\{c,-c\\})\geq\frac{3\varepsilon\gamma^{z}\cdot
2\cdot\frac{2n}{k}}{2^{\frac{z}{2}}}.$

Moreover, we can find an origin such that all the center points and data
points have the distance to it less than
$\frac{\gamma}{2}+\sqrt{d}\leq\gamma=\Theta\left(\frac{\sqrt{d}}{\varepsilon}\right)$.
The full instance is then made of $\frac{k}{2}$ distinct copies of the $k=2$
instance, denoted as $\mathcal{P}^{\frac{k}{2}}$. Note that each instance can
be wrapped by a hypercube with side length $4\gamma$ by putting its origin at
the center of the hypercube. In our model, The whole space is a hypercube with
side length $\Delta$. We can then put at most

$\left(\frac{\Delta}{4\gamma}\right)^{d}\geq\left(\lceil
k^{\frac{1}{d}}\rceil\right)^{d}\geq k.$

in the large hypercube, which fulfills our requirements. Moreover, the
distance between the origins of any two different instances is at least
$4\gamma$, which means that the points in the two instances will have a
distance of at least $2\gamma$ and will not interfere with the assignment of
clustering.

We then force that any two datasets $P,Q\in\mathcal{P}^{\frac{k}{2}}$ is
different on at least $\frac{k}{4}$ copies. It may be easier for us to think
of each dataset as a "vector" of dimension $\frac{k}{2}$, where each entry $i$
denotes the choice of the dataset on the $i$-th copy, and thus there are
$\exp\left(sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)$
choices. Our additional requirement is equal to the condition that
$\left\|P-Q\right\|_{0}\geq\frac{k}{4}.$ In $i$-th copy, we will place two
centers $\\{c_{i},-c_{i}\\}$. The total cost of dataset $P$ is thus

$\operatorname{cost}_{z}(P,\\{c_{i},-c_{i}\\}_{i\in\left[\frac{k}{2}\right]})=\sum_{i=1}^{\frac{k}{2}}\operatorname{cost}_{z}(P_{i},\\{c_{i},-c_{i}\\})\leq\frac{1}{2}k\cdot\frac{\gamma^{z}\cdot
2\cdot\frac{2n}{k}}{2^{\frac{z}{2}}},$

where $P_{i}$ is the dataset chosen at the $i$-th copy. On the other hand,
when it comes to the cost difference of two datasets, $P$ and $Q$ are
different on at least $\frac{k}{4}$ copies. Moreover, by the property of our
chosen dataset, we can find $\\{c_{i},-c_{i}\\}$ such that the cost on $i$-th
copy is at least $3\varepsilon\cdot\frac{\gamma^{z}\cdot
2\cdot\frac{2n}{k}}{2^{\frac{z}{2}}}$. We thus have the total cost difference
be

$\displaystyle\operatorname{cost}_{z}(P,\\{c_{i},-c_{i}\\}_{i\in\left[\frac{k}{2}\right]})-\operatorname{cost}_{z}(Q,\\{c_{i},-c_{i}\\}_{i\in\left[\frac{k}{2}\right]})$
$\displaystyle=\sum_{i=1}^{\frac{k}{2}}\left[\operatorname{cost}_{z}(P_{i},\\{c_{i},-c_{i}\\})-\operatorname{cost}_{z}(Q,\\{c_{i},-c_{i}\\}\right]$
$\displaystyle\geq\left\|P-Q\right\|_{0}\cdot
3\varepsilon\cdot\frac{\gamma^{z}\cdot
2\cdot\frac{2n}{k}}{2^{\frac{z}{2}}}\geq\frac{3}{4}\varepsilon
k\cdot\frac{\gamma^{z}\cdot 2\cdot\frac{2n}{k}}{2^{\frac{z}{2}}}.$

We then consider to compute the number of the dataset. Note that without the
additional requirement, the number of the dataset is

$\left(\exp\left(sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)\right)^{\frac{k}{2}}=\exp\left(\frac{k}{2}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right).$

On the other hand, we denote the neighbors of a dataset be those who have
differences on less than $\frac{k}{4}$ copies. For a dataset, the number of
neighbors is less than

$\sum_{i=1}^{\frac{k}{4}}\begin{pmatrix}\frac{k}{2}\\\
i\end{pmatrix}\left(\exp\left(sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)\right)^{i}=\sum_{i=1}^{\frac{k}{4}}\begin{pmatrix}\frac{k}{2}\\\
i\end{pmatrix}\exp\left(i\cdot
sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right),$

which means that we first choose $i$ copies to be the different ones (the rest
$\frac{k}{2}-i$ copies are then fixed to be the same as the original dataset),
and then choose the value on these positions arbitrarily. We can upper bound
this value with the Stirling inequation that

$e\left(\frac{n}{e}\right)^{n}\leq\sqrt{2\pi
n}\left(\frac{n}{e}\right)^{n}e^{1/(12n+1)}\leq n!\leq\sqrt{2\pi
n}\left(\frac{n}{e}\right)^{n}e^{1/12n}\leq en\left(\frac{n}{e}\right)^{n},$

which gives

$\displaystyle\sum_{i=1}^{\frac{k}{4}}\begin{pmatrix}\frac{k}{2}\\\
i\end{pmatrix}\exp\left(i\cdot
sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)\leq\frac{k}{4}\begin{pmatrix}\frac{k}{2}\\\
\frac{k}{4}\end{pmatrix}\exp\left(\frac{k}{4}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)$
$\displaystyle=\frac{k}{4}\frac{\left(\frac{k}{2}\right)!}{\left(\left(\frac{k}{4}\right)!\right)^{2}}\exp\left(\frac{k}{4}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)\leq\frac{k}{4}\frac{e\frac{k}{2}\left(\frac{k}{2e}\right)^{\frac{k}{2}}}{e^{2}\left(\frac{k}{4e}\right)^{\frac{k}{2}}}\exp\left(\frac{k}{4}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)$
$\displaystyle=\exp\left(\frac{k}{4}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)+\frac{k\ln
2}{2}+\ln\left(\frac{k^{2}}{8e}\right)\right).$

The size of the final dataset is at least the total number divided by the
number of neighbors and thus greater than

$\displaystyle\frac{\exp\left(\frac{k}{2}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)}{\exp\left(\frac{k}{4}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)+\frac{k\ln
2}{2}+\ln\left(\frac{k^{2}}{8e}\right)\right)}$
$\displaystyle=\exp\left(\frac{k}{4}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)-\frac{k\ln
2}{2}-\ln\left(\frac{k^{2}}{8e}\right)\right)\geq\exp\left(\frac{k}{8}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right),$

where the last equation holds for
$sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\geq 4\ln
2+\frac{8}{k}\ln\left(\frac{k^{2}}{8e}\right)$ larger than a large enough
constant.

Therefore, we can find a family $\mathcal{P}^{\frac{k}{2}}$ with size being at
least
$\exp\left(\frac{k}{8}sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)$
satisfying the requirement of Lemma 3.1. We thus have,

$\displaystyle sc\left(n,\Delta,k,z,d,\frac{1}{2}\varepsilon\right)$
$\displaystyle=\Omega\left(\log\left|\mathcal{P}^{\frac{k}{2}}\right|\right)=\Omega\left(k\cdot
sc\left(\frac{2n}{k},\gamma,2,z,d,\varepsilon\right)\right)$
$\displaystyle=\Omega\left(kd\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},\frac{n}{k}\right\\}\right).$

##  4 Application to Space Lower Bound for Terminal Embedding

We have already given the definition of Terminal Embedding in the
Introduction. In the case that $\mathcal{X}$ and $\mathcal{Y}$ are both
Euclidean metrics with $\mathcal{Y}$ being lower-dimensional, work of [42]
prove that the dimension of latter space can be as small as
$O\left(\varepsilon^{-2}\log n\right)$, which is optimal proven in [37].

In the following part, we will show that our lower bound on the minimum number
of bits of computing the cost function actually sheds light on the number of
bits of terminal embedding.

######  Definition 4.1 (Space complexity for terminal embedding).

Let $P\subset\mathbb{R}^{d}$ be a dataset, $n\geq 1$ and $\varepsilon>0$ be an
error parameter. We define $g(P,d,\varepsilon)$ to be the minimum possible
number of bits of a terminal embedding from $P$ into $\mathbb{R}^{m}$ with
$m=O\left(\varepsilon^{-2}\log n\right)$ and distortion $\varepsilon$.
Moreover, we define
$g(n,d,\varepsilon):=\sup_{P\subset\mathbb{R}^{d}:|P|=n}g(P,d,\varepsilon)$ to
be the space complexity function, i.e., the maximum cardinality
$g(P,d,\varepsilon)$ over all possible datasets $P\subset\mathbb{R}^{d}$ of
size $n$.

######  Theorem 4.2 (Space lower bound for terminal embedding).

Let $\varepsilon\in(0,1)$ and assume $d=\Omega\left(\frac{\log
n\log(n/\varepsilon)}{\varepsilon^{2}}\right)$. Function $g(n,d,\varepsilon)$
satisfy that $g(n,d,\varepsilon)=\Omega(nd)$.

###### Proof.

We will show that an $\varepsilon$-sketch can be constructed for the case of
our lower bound by using terminal embedding. We would consider the case where
$z=2$ and $k$ is large enough such that
$\frac{n}{k}\leq\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d}\right\\},k=O\left(n\right)$. Note that
$\Delta=\Theta\left(\frac{k^{\frac{1}{d}}\sqrt{d}}{\varepsilon}\right)=O\left(\frac{n^{\frac{1}{d}}\sqrt{d}}{\varepsilon}\right)$.
Moreover, in our proof of lower bound, since we are only considering the
scaled orthonormal bases, we would have that for any considered datasets $P$
and center $\\{c_{m}\\}_{m\in[2]}$.

$\operatorname{cost}_{2}\left(P,\\{c_{m}\\}_{m\in[2]}\right)\geq\frac{\Delta^{2}}{4}\left(2n-\sqrt{n}\right)\geq\Omega\left(\Delta^{2}n\right).$

To construct the $\varepsilon$-sketch, we first use the terminal embedding to
lower the dimension to $\frac{\log n}{\varepsilon^{2}}$. For a dataset
$P=\left(p_{1},\cdots,p_{n}\right)$, Let
$\hat{P}=\left(f\left(p_{1}\right),\cdots,f\left(p_{n}\right)\right)$ be the
embedded dataset. By the property of terminal embedding, we have for any
center point $c\in\mathbb{R}^{d},i\in[n]$,

$\displaystyle d(p_{i},c)\leq d(f(p_{i}),f(c))\leq(1+\varepsilon)\cdot
d(p_{i},c),d(p_{i},c)^{2}\leq d(f(p_{i}),f(c))^{2}\leq(1+3\varepsilon)\cdot
d(p_{i},c)^{2},$
$\displaystyle\operatorname{cost}_{2}\left(P,\\{c_{m}\\}_{m\in[2]}\right)\leq\operatorname{cost}_{2}\left(\hat{P},\\{f(c_{m})\\}_{m\in[2]}\right)\leq(1+3\varepsilon)\operatorname{cost}_{2}\left(P,\\{c_{m}\\}_{m\in[2]}\right).$

We then round the dataset to the grid points $\left[\Delta\right]^{\frac{\log
n}{\varepsilon^{2}}}$. Let the rounded dataset be $\tilde{P}=\left(\lceil
f\left(p_{1}\right)\rceil,\cdots,\lceil f\left(p_{n}\right)\rceil\right)$. We
would have that

$\displaystyle\left|\left\|\hat{p}_{i}-f(c)\right\|_{2}^{2}-\left\|\tilde{p}_{i}-f(c)\right\|_{2}^{2}\right|$
$\displaystyle\leq
2\left\|\hat{p}_{i}-\tilde{p}_{i}\right\|_{2}\left\|\tilde{p}_{i}-f(c)\right\|_{2}+\left\|\hat{p}_{i}-\tilde{p}_{i}\right\|_{2}^{2}$
$\displaystyle\leq\Delta\sqrt{\frac{\log n}{\varepsilon^{2}}}+\frac{\log
n}{\varepsilon^{2}}\leq O\left(\Delta^{2}\varepsilon\right),$

where the last inequation holds due to our choice of $\Delta$. Therefore, we
still have that

$\displaystyle\left|\operatorname{cost}_{2}\left(\hat{P},\\{f(c_{m})\\}_{m\in[2]}\right)-\operatorname{cost}_{2}\left(\tilde{P},\\{f(c_{m})\\}_{m\in[2]}\right)\right|\leq
O\left(\Delta^{2}\varepsilon
n\right)\leq\varepsilon\operatorname{cost}_{2}\left(P,\\{c_{m}\\}_{m\in[2]}\right),$
$\displaystyle(1-\varepsilon)\operatorname{cost}_{2}\left(P,\\{c_{m}\\}_{m\in[2]}\right)\leq\operatorname{cost}_{2}\left(\tilde{P},\\{f(c_{m})\\}_{m\in[2]}\right)\leq(1+4\varepsilon)\operatorname{cost}_{2}\left(P,\\{c_{m}\\}_{m\in[2]}\right).$

We then only need to construct an $\varepsilon$-sketch for
$\operatorname{cost}_{2}\left(\tilde{P},\\{f(c_{m})\\}_{m\in[2]}\right)$ in
the lower dimension of $\frac{\log n}{\varepsilon^{2}}$. With the result of
Corollary 1.2, the sketch only needs to use

$\displaystyle sc\left(n,\Delta,k,2,\frac{\log
n}{\varepsilon^{2}},\varepsilon\right)\leq$ $\displaystyle\frac{k\log
n\log\Delta}{\varepsilon^{2}}+\Gamma(n)\left(\frac{\log
n\left(\log\left(\log\Delta/\varepsilon\right)\right)}{\varepsilon^{2}}+\log\log
n\right)\leq 2n\frac{\log n\log\left(n/\varepsilon\right)}{\varepsilon^{2}},$

where we bring in
$\Delta=\Theta\left(\frac{k^{\frac{1}{d}}\sqrt{d}}{\varepsilon}\right),k,\Gamma(n)\leq
n$. Combining together, our sketch exploits bits of only

$sc\left(n,\Delta,k,2,d,\varepsilon\right)\leq g(n,d,\varepsilon)+2n\frac{\log
n\log\left(n/\varepsilon\right)}{\varepsilon^{2}}.$

On the other hand, with the result of the second part of Theorem 1.3, we have
that for $d={\Omega}\left(\frac{\log
n\log\left(n/\varepsilon\right)}{\varepsilon^{2}}\right)$ and our choice of
$n$, we can have that

$\displaystyle sc\left(n,\Delta,k,2,d,\varepsilon\right)$
$\displaystyle\geq\Omega\left(kd\min\left\\{\frac{1}{\varepsilon^{2}},\frac{d}{\log
d},\frac{n}{k}\right\\}\right)=\Omega\left(nd\right)\geq\Omega\left(n\frac{\log
n\log\left(n/\varepsilon\right)}{\varepsilon^{2}}\right).$

Therefore, we must have that

$\displaystyle g(n,d,\varepsilon)\geq\Omega\left(nd\right)-2n\frac{\log
n\log\left(n/\varepsilon\right)}{\varepsilon^{2}}\geq\Omega\left(nd\right).$

∎

The same technique can be applied to other dimensionality reduction methods.
For example, [23] initially applies dimensionality reduction to project the
given set of points into an $m$-dimensional subspace $L$, with
$m=O(k/\varepsilon^{2})$. Subsequently, they construct an approximate coreset
$S$ within this subspace $L$. Using a similar proof procedure, we can show
that the storage of the projection to the reduced-dimensional space is
$\Omega\left(md\right)=\Omega\left(kd/{\varepsilon^{2}}\right)$.

##  5 Conclusions and Future Work

In this study, we initiate the exploration of space complexity for the
Euclidean $(k,z)$-Clustering problem, presenting both upper and lower bounds.
Our findings suggest that a coreset serves as the optimal compression scheme
when $k$ is constant. Furthermore, the space lower bounds for
$(k,z)$-Clustering directly imply a tight space lower bound for terminal
embedding when $d\geq\Omega(\frac{\log
n\log(n/\varepsilon)}{\varepsilon^{2}})$. The techniques we employ for
establishing these lower bounds contribute to a deeper geometric understanding
of principal angles, which may be of independent research interest.

Our work opens up several interesting research directions. One immediate
challenge is to further narrow the gap between the upper and lower bounds of
the space complexity for Euclidean $(k,z)$-Clustering. Additionally, it would
be valuable to investigate whether a coreset remains optimal for compression
when $k$ is large.

## References

  * Absil et al. [2006] P-A Absil, Alan Edelman, and Plamen Koev.  On the largest principal angle between random subspaces.  _Linear Algebra and its applications_ , 414(1):288–294, 2006.
  * Alon and Klartag [2017] Noga Alon and Bo’az Klartag.  Optimal compression of approximate inner products and dimension reduction.  In _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 639–650. IEEE, 2017.
  * Arthur and Vassilvitskii [2007] David Arthur and Sergei Vassilvitskii.  $k$-means$++$: the advantages of careful seeding.  In _Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms_ , pages 1027–1035, 2007.
  * Balcan et al. [2013] Maria-Florina F Balcan, Steven Ehrlich, and Yingyu Liang.  Distributed $k$-means and $k$-median clustering on general topologies.  _Advances in neural information processing systems_ , 26, 2013.
  * Björck and Golub [1973] Ake Björck and Gene H Golub.  Numerical methods for computing angles between linear subspaces.  _Mathematics of computation_ , 27(123):579–594, 1973.
  * Braverman et al. [2016] Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou.  New frameworks for offline and streaming coreset constructions.  _arXiv preprint arXiv:1612.00889_ , 2016.
  * Braverman et al. [2017] Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F. Yang.  Clustering high dimensional dynamic data streams.  In _ICML_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 576–585. PMLR, 2017.
  * Braverman et al. [2019] Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus.  Streaming coreset constructions for $m$-estimators.  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * Carlson et al. [2019] Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan.  Optimal lower bounds for sketching graph cuts.  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 2565–2569. SIAM, 2019.
  * Charikar and Waingarten [2022] Moses Charikar and Erik Waingarten.  The Johnson-Lindenstrauss lemma for clustering and subspace approximation: From coresets to dimension reduction.  _arXiv preprint arXiv:2205.00371_ , 2022.
  * Chen et al. [2023] Xiaoyu Chen, Shaofeng H.-C. Jiang, and Robert Krauthgamer.  Streaming Euclidean max-cut: Dimension vs data reduction.  In _STOC_ , pages 170–182. ACM, 2023.
  * Cherapanamjeri and Nelson [2022] Yeshwanth Cherapanamjeri and Jelani Nelson.  Terminal embeddings in sublinear time.  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 1209–1216. IEEE, 2022.
  * Coates and Ng [2012] Adam Coates and Andrew Y Ng.  Learning feature representations with $k$-means.  In _Neural Networks: Tricks of the Trade: Second Edition_ , pages 561–580. Springer, 2012.
  * Cohen-Addad et al. [2021] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn.  A new coreset framework for clustering.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 169–182, 2021.
  * Cohen-Addad et al. [2022a] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn.  Towards optimal lower bounds for $k$-median and $k$-means coresets.  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1038–1051, 2022a.
  * Cohen-Addad et al. [2022b] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar.  Improved coresets for Euclidean $k$-Means.  In _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022_ , 2022b.
  * Cohen-Addad et al. [2023] Vincent Cohen-Addad, David P Woodruff, and Samson Zhou.  Streaming euclidean $k$-median and $k$-means with o (log n) space.  In _2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 883–908. IEEE, 2023.
  * Czumaj et al. [2013] Artur Czumaj, Christiane Lammersen, Morteza Monemizadeh, and Christian Sohler.  $(1+\varepsilon)$-approximation for facility location in data streams.  In _SODA_ , pages 1710–1728. SIAM, 2013.
  * Dadush et al. [2022] Daniel Dadush, Haotian Jiang, and Victor Reis.  A new framework for matrix discrepancy: partial coloring bounds via mirror descent.  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 649–658, 2022.
  * Dahlquist et al. [1968] G Dahlquist, B Sjöberg, and P Svensson.  Comparison of the method of averages with the method of least squares.  _Mathematics of Computation_ , 22(104):833–845, 1968.
  * Elkin et al. [2017] Michael Elkin, Arnold Filtser, and Ofer Neiman.  Terminal embeddings.  _Theoretical Computer Science_ , 697:1–36, 2017.
  * Feldman and Langberg [2011] Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In _Proceedings of the forty-third annual ACM symposium on Theory of computing_ , pages 569–578, 2011.
  * Feldman et al. [2020] Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for $k$-means, pca, and projective clustering.  _SIAM Journal on Computing_ , 49(3):601–657, 2020.
  * Frahling et al. [2008] Gereon Frahling, Piotr Indyk, and Christian Sohler.  Sampling in dynamic data streams and applications.  _Int. J. Comput. Geom. Appl._ , 18(1/2):3–28, 2008.
  * Har-Peled and Mazumdar [2004] Sariel Har-Peled and Soham Mazumdar.  On coresets for $k$-means and $k$-medians clustering.  In _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_ , pages 291–300, 2004.
  * Henzinger and Kale [2020] Monika Henzinger and Sagar Kale.  Fully-dynamic coresets.  _arXiv preprint arXiv:2004.14891_ , 2020.
  * Hu et al. [2018] Wei Hu, Zhao Song, Lin F. Yang, and Peilin Zhong.  Nearly optimal dynamic $k$-Means clustering for high-dimensional data.  _arXiv: Data Structures and Algorithms_ , 2018.  URL https://api.semanticscholar.org/CorpusID:127972547.
  * Huang and Vishnoi [2020] Lingxiao Huang and Nisheeth K Vishnoi.  Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1416–1429, 2020.
  * Huang et al. [2022] Lingxiao Huang, Jian Li, and Xuan Wu.  On optimal coreset construction for Euclidean $(k,z)$-clustering, 2022.
  * Huang et al. [2023] Lingxiao Huang, Ruiyuan Huang, Zengfeng Huang, and Xuan Wu.  On coresets for clustering in small dimensional Euclidean spaces.  In _ICML_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 13891–13915. PMLR, 2023.
  * Indyk and Wagner [2018] Piotr Indyk and Tal Wagner.  Approximate nearest neighbors in limited space.  In _Conference On Learning Theory_ , pages 2012–2036. PMLR, 2018.
  * Indyk and Wagner [2022] Piotr Indyk and Tal Wagner.  Optimal (Euclidean) metric compression.  _SIAM Journal on Computing_ , 51(3):467–491, 2022.
  * Johnson et al. [1986] William B Johnson, Joram Lindenstrauss, and Gideon Schechtman.  Extensions of lipschitz maps into Banach spaces.  _Israel Journal of Mathematics_ , 54(2):129–138, 1986.
  * Jordan [1875] Camille Jordan.  Essai sur la géométrie à $n$ dimensions.  _Bulletin de la Société mathématique de France_ , 3:103–174, 1875.
  * Kane et al. [2011] Daniel Kane, Raghu Meka, and Jelani Nelson.  Almost optimal explicit Johnson-Lindenstrauss families.  In _International Workshop on Approximation Algorithms for Combinatorial Optimization_ , pages 628–639. Springer, 2011.
  * Kleitman [1966] Daniel J Kleitman.  On a combinatorial conjecture of erdös.  _Journal of Combinatorial Theory_ , 1(2):209–214, 1966.
  * Larsen and Nelson [2017] Kasper Green Larsen and Jelani Nelson.  Optimality of the Johnson-Lindenstrauss lemma.  In _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 633–638. IEEE, 2017.
  * Lloyd [1982] Stuart Lloyd.  Least squares quantization in pcm.  _IEEE transactions on information theory_ , 28(2):129–137, 1982.
  * Makarychev et al. [2019] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn.  Performance of Johnson-Lindenstrauss transform for $k$-means and $k$-medians clustering.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1027–1038, 2019.
  * Meckes [2019] Elizabeth S. Meckes.  _The Random Matrix Theory of the Classical Compact Groups_.  Cambridge Tracts in Mathematics. Cambridge University Press, 2019.
  * Muirhead [1982] Robb J Muirhead.  _Aspects of multivariate statistical theory_.  John Wiley & Sons, 1982.
  * Narayanan and Nelson [2019] Shyam Narayanan and Jelani Nelson.  Optimal terminal dimensionality reduction in Euclidean space.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1064–1069, 2019.
  * Richards and Zheng [2020] Donald Richards and Qifu Zheng.  A reflection formula for the gaussian hypergeometric function of matrix argument.  _arXiv preprint arXiv:2002.05248_ , 2020.
  * Sohler and Woodruff [2018] Christian Sohler and David P. Woodruff.  Strong coresets for $k$-Median and subspace approximation: Goodbye dimension.  In _FOCS_ , pages 802–813. IEEE Computer Society, 2018.
  * Spencer [1985] Joel Spencer.  Six standard deviations suffice.  _Transactions of the American mathematical society_ , 289(2):679–706, 1985.
  * Varah [1970] James M Varah.  Computing invariant subspaces of a general matrix when the eigensystem is poorly conditioned.  _Mathematics of Computation_ , 24(109):137–149, 1970.