# The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation:
From Coresets to Dimension Reduction

Moses Charikar
Stanford University email<EMAIL_ADDRESS>Moses Charikar is supported
by a Simons Investigator Award. Erik Waingarten
University of Pennsylvania email<EMAIL_ADDRESS>Part of this work
was done while Erik Waingarten was a postdoc at Stanford University, supported
by an NSF postdoctoral fellowship and by Moses Charikar’s Simons Investigator
Award.

###### Abstract

We study the effect of Johnson-Lindenstrauss transforms in various projective
clustering problems, generalizing recent results which only applied to center-
based clustering [MMR19]. We ask the general question: for a Euclidean
optimization problem and an accuracy parameter $\varepsilon\in(0,1)$, what is
the smallest target dimension $t\in\mathbbm{N}$ such that a Johnson-
Lindenstrauss transform $\mathbf{\Pi}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$
preserves the cost of the optimal solution up to a $(1+\varepsilon)$-factor.
We give a new technique which uses coreset constructions to analyze the effect
of the Johnson-Lindenstrauss transform. Our technique, in addition applying to
center-based clustering, improves on (or is the first to address) other
Euclidean optimization problems, including:

  * •

For $(k,z)$-subspace approximation: we show that
$t=\tilde{O}(zk^{2}/\varepsilon^{3})$ suffices, whereas the prior best bound,
of $O(k/\varepsilon^{2})$, only applied to the case $z=2$ [CEM+15].

  * •

For $(k,z)$-flat approximation: we show $t=\tilde{O}(zk^{2}/\varepsilon^{3})$
suffices, completely removing the dependence on $n$ from the prior bound
$\tilde{O}(zk^{2}\log n/\varepsilon^{3})$ of [KR15].

  * •

For $(k,z)$-line approximation: we show $t=O((k\log\log
n+z+\log(1/\varepsilon))/\varepsilon^{3})$ suffices, and ours is the first to
give any dimension reduction result.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contribution
    2. 1.2 Related Work
    3. 1.3 Organization
  2. 2 Overview of Techniques
    1. 2.0.1 Sensitivity Sampling for Step 4
    2. 2.0.2 The Circularity and How to Break It
  3. 3 Preliminaries
  4. 4 Center-based $(k,z)$-clustering
    1. 4.1 Easy Direction: Optimum Cost Does Not Increase
    2. 4.2 Hard Direction: Optimum Cost Does Not Decrease
      1. 4.2.1 Preliminaries
    3. 4.3 The Important Events
      1. 4.3.1 A Bad Approximation Guarantee
      2. 4.3.2 Improving the Approximation
  5. 5 Subspace Approximation
    1. 5.1 Easy Direction: Optimum Cost Does Not Increase
    2. 5.2 Hard Direction: Optimum Cost Does Not Decrease
      1. 5.2.1 Preliminaries
    3. 5.3 The Important Events
      1. 5.3.1 A Bad Approximation Guarantee
      2. 5.3.2 Improving the Approximation
  6. 6 $k$-Flat Approximation
    1. 6.1 Easy Direction: Optimum Cost Does Not Increase
    2. 6.2 Hard Direction: Optimum Cost Does Not Decrease
      1. 6.2.1 Preliminaries
    3. 6.3 The Important Events
      1. 6.3.1 Improving the approximation
  7. 7 $k$-Line Approximation
    1. 7.1 Easy Direction: Optimum Cost Does Not Increase
    2. 7.2 Hard Direction: Optimum Cost Does Not Decrease
      1. 7.2.1 Preliminaries
      2. 7.2.2 The Important Events
    3. 7.3 A Sensitivity Function for $(k,z)$-Line Approximation
      1. 7.3.1 From Coresets for $(k,\infty)$-line approximation to Sensitivity Functions
      2. 7.3.2 A simple coreset for $(k,\infty)$-line approximation of one-dimensional instances
      3. 7.3.3 The coreset for points on $k$ lines and the effect of dimension reduction
    4. 7.4 Improving the approximation
  8. A On preserving “all solutions” and comparisons to prior work

##  1 Introduction

The Johnson-Lindenstrauss lemma [JL84] concerns dimensionality reduction for
high-dimensional Euclidean spaces. It states that, for any set of $n$ points
$x_{1},\dots,x_{n}$ in $\mathbbm{R}^{d}$ and any $\varepsilon\in(0,1)$, there
exists a map $\Pi\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$, with $t=O(\log
n/\varepsilon^{2})$ such that, for any $i,j\in[n]$,

$\displaystyle\dfrac{1}{1+\varepsilon}\cdot\|x_{i}-x_{j}\|_{2}\leq\|\Pi(x_{i})-\Pi(x_{j})\|_{2}\leq(1+\varepsilon)\cdot\|x_{i}-x_{j}\|_{2}.$
(1)

From a computational perspective, the lemma has been extremely influential in
designing algorithms for high-dimensional geometric problems, partly because
proofs show that a _random_ linear map, oblivious to the data, suffices.
Proofs specify a distribution $\mathcal{J}_{d,t}$ supported on linear maps
$\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ which is independent of
$x_{1},\dots,x_{n}$ (for example, given by a $t\times d$ matrix of i.i.d
$\mathcal{N}(0,1/t)$ entries [IM98, DG03]), and show that a draw
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ satisfies (1) with probability at least
$0.9$.

In this paper, we study the Johnson-Lindenstrauss transforms for _projective
clustering_ problems, generalizing a recent line-of-work which gave
(surprising) dimension reduction results for center-based clustering [BZD10,
CEM+15, BBCA+19, MMR19]. The goal is to reduce the dimensionality of the input
of a (more general) projective clustering problem (from $d$ to $t$ with $t\ll
d$) without affecting the cost of the optimal solution significantly. We map
$d$-dimensional points to $t$-dimensional points (via a random linear map
$\mathbf{\Pi}$) such that the optimal cost in $t$-dimensions is within a
$(1+\varepsilon)$-factor of the optimal cost in the original $d$-dimensional
space. We study this for a variety of problems, each of which is specified by
a set of candidate solutions $\mathcal{C}_{d}$ and a cost function. By varying
the family of candidate solutions $\mathcal{C}_{d}$ and the cost functions
considered, one obtains center-based clustering problems (like $k$-means and
$k$-median), as well as subspace approximation problems (like principal
components analysis), and beyond (like clustering with subspaces). The key
question we address here is:

> Main Question: For a projective clustering problem, how small can $t$ be as
> a function of $n$ (the dataset size) and $\varepsilon$ (the accuracy
> parameter), such that the cost of the optimization is preserved up to
> $(1\pm\varepsilon)$-factor with probability at least $0.9$ over
> $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$?

Our results fit into a line of prior work on the power of Johnson-
Lindenstrauss maps beyond the original discovery of [JL84]. These have been
investigated before for various problems and in various contexts, including
nearest neighbor search [IM98, HIM12, AIR18], numerical linear algebra [Sar06,
Mah11, Woo14], prioritized and terminal embeddings [EFN17, MMMR18, NN19,
CN21], and clustering and facility location problems [BZD10, CEM+15, KR15,
BBCA+19, MMR19, NSIZ21, ISZ21].

###  1.1 Our Contribution

In the $(k,j)$-projective clustering problem with $\ell_{z}$ cost ([HPV02,
AP03, EV05, DRVW06, VX12b, KR15, FSS20, TWZ+22]), the goal is to cluster a
dataset $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, where each cluster
is approximated by an affine $j$-dimensional subspace. Namely, we define an
objective function for $(k,j)$-projective clustering problems with $\ell_{z}$
cost on a dataset $X$, which aims to minimize

$\min_{c\in\mathcal{C}_{d}}\mathrm{cost}_{z}(X,c),$

where the “candidate solutions” $\mathcal{C}_{d}$ consist of all $k$-tuples of
$j$-dimensional affine subspaces. The cost function
$\mathrm{cost}_{z}(X,\cdot)$ maps each candidate solution
$c\in\mathcal{C}_{d}$ to a cost in $\mathbbm{R}_{\geq 0}$ given by the
$\ell_{z}$-norm of the vector of distances between each dataset point $x\in X$
to its nearest point on one of the $k$ subspaces. Intuitively, each point of
the dataset $x_{i}\in X$ “pays” for the Euclidean distance to the nearest
subspace in $c\in\mathcal{C}_{d}$, and the total cost is the $\ell_{z}$-norm
of the $n$ payments (one for each point).

There has been significant prior work which showed surprising results for the
special case of $(k,z)$-clustering (like $k$-means and $k$-median, which
corresponds to $(k,0)$-projective clustering with $\ell_{z}$-cost) as well as
for low-rank approximation (which corresponds to $(1,k)$-projective clustering
for non-affine subspaces with $\ell_{2}$-cost) [BZD10, CEM+15, BBCA+19,
MMR19]. It is important to note that the techniques in prior works are
_specifically tailored_ to the Euclidean optimization problem at hand. For
example, the results of [MMR19], which apply for $(k,0)$-clustering with
$\ell_{z}$-norm, rely on using center points as the approximation and do not
generalize to affine subspaces beyond dimension $0$. The other result of
[CEM+15] for low-rank approximation uses the specific algebraic properties of
the $\ell_{2}$-norm (which characterize the optimal low-rank approximation).
These prior works carry a strong conceptual message: for $(k,z)$-clustering
and low-rank approximation, even though many pairwise distances among dataset
points become highly distorted (since one projects to $t\ll\log n$
dimensions), the cost of the optimization (which aggregates distances) need
not be significantly distorted.

Our Results. We show that $(k,0)$-clustering with $\ell_{z}$-norm and low-rank
approximation are not isolated incidents, but rather, part of a more general
phenomenon. Our main conceptual contribution is the following: we use
algorithms for constructing _coresets_ (via the “sensitivity sampling”
framework of [FL11]) to obtain bounds on dimension reduction. Then, the
specific bounds that we obtain for the various problems depend on the sizes of
the coresets that the algorithms can produce. We can instantiate our framework
to new upper bounds for the following problems:

  * •

$(k,z)$-Subspace Approximation. This problem is a (restricted)
$(1,k)$-projective clustering problems with $\ell_{z}$-cost. We seek to
minimize over a $k$-dimensional subspace $S$ of $\mathbbm{R}^{d}$ the
$\ell_{z}$-norm of the $n$-dimensional vector where the coordinate $i\in[n]$
encodes the distance between $x_{i}$ and the closest point in $S$.111This is a
restricted version of projective clustering because subspaces are not affine
and required to go through the origin.

  * •

$(k,z)$-Flat Approximation. This problem is exactly the $(1.k)$-projective
clustering problem with $\ell_{z}$ cost. It is similar to $(k,z)$-subspace
approximation, except we optimize over all affine subspaces.

  * •

$(k,z)$-Line Approximation. This problem corresponds to $(k,1)$-projective
clustering with $\ell_{z}$-cost. The optimization minimizes, over an arbitrary
set $L$ of $k$ of $1$-dimensional affine subspaces $l_{1},\dots,l_{k}$ (i.e.,
$k$ lines in $\mathbbm{R}^{d}$), the $\ell_{z}$-norm of the $n$-dimensional
vector where the coordinate $i\in[n]$ encodes the distance between $x_{i}$ and
the closest point on any line in $L$.

Concretely, our quantitative results are summarized by the following theorem.

######  Theorem 1 (Main Result—Informal).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any dataset, and
$\mathcal{J}_{d,t}$ denote a $t\times d$ matrix of i.i.d entries from
$\mathcal{N}(0,1/t)$. Let $\mathcal{C}_{d}$ and $\mathcal{C}_{t}$ be candidate
solutions for a projective clustering problem in $\mathbbm{R}^{d}$ and
$\mathbbm{R}^{t}$, respectively. For any $\varepsilon\in(0,1)$, we have

$\displaystyle\mathop{{\bf
Pr}\/}_{\mathbf{\Pi}\sim\mathcal{J}_{d,t}}\left[\left|\dfrac{\min_{c^{\prime}\in\mathcal{C}_{t}}\mathrm{cost}(\mathbf{\Pi}(X),c^{\prime})}{\min_{c\in\mathcal{C}_{d}}\mathrm{cost}(X,c)}-1\right|\leq\varepsilon\right]\geq
0.9$ (2)

whenever:

  * •

_$(k,z)$ -subspace and $(k,z)$-flat approximation:_ $\mathcal{C}_{d}$ and
$\mathcal{C}_{t}$ are all $k$-dimensional subspaces of $\mathbbm{R}^{d}$ and
$\mathbbm{R}^{t}$, respectively; the cost measures the $\ell_{z}$-norm of
distances between points to the subspace; and,
$t=\tilde{O}(zk^{2}/\varepsilon^{3})$. Similarly, the same bound on $t$ holds
for $\mathcal{C}_{d}$ and $\mathcal{C}_{t}$ varying over all affine
$k$-dimensional subspaces.

  * •

_$(k,z)$ -line approximation:_ $\mathcal{C}_{d}$ and $\mathcal{C}_{t}$ are all
$k$-tuples of lines in $\mathbbm{R}^{d}$ and $\mathbbm{R}^{t}$, respectively;
the cost measures the $\ell_{z}$-norm of distances between points and the
nearest line; and, $t=O((k\log\log n+z+\log(1/\varepsilon))/\varepsilon^{3})$.

In all cases, the bound that we obtain is directly related to the size of the
best coresets from the sensitivity sampling framework, and all of our proofs
follow the same format.222The reason we did not generalize the results to
$(k,j)$-projective clustering with $\ell_{z}$-cost with $j>1$ is that these
problems do not admit small coresets [HP04]. Researchers have studied “integer
$(k,j)$-projective clustering” where one restricts the input points to have
bounded integer coordinates, where small coresets do exists [EV05]. However,
using this approach for dimension reduction would incur additional additive
errors, so we have chosen not to pursue this route. Our proofs are not
entirely black-box applications of coresets (since we use the specific
instantiations of the sensitivity sampling framework), but we believe that any
improvement on the size of the best coresets will likely lead to quantitative
improvements on the dimension reduction bounds. However, improving our current
bounds by either better coresets or via a different argument altogether (for
example, improving on the cubic dependence on $\varepsilon$) seems to require
significantly new ideas.

Target Dimension for Johnson-Lindenstrauss Transforms
---
Problem | New Result | Prior Best
$(k,z)$-subspace | $\tilde{O}(zk^{2}/\varepsilon^{3})$ |  $O(k/\varepsilon^{2})$ (when $z=2$) [CEM+15]
$(k,z)$-flat | $\tilde{O}(zk^{2}/\varepsilon^{3})$ |  $\tilde{O}(zk^{2}\log n/\varepsilon^{3})$ [KR15]
$(k,z)$-line | $O((k\log\log n+z+\log(1/\varepsilon))/\varepsilon^{3})$ | None
Figure 1: Comparison to Prior Bounds

A Subtlety in “For-All” versus “Optimal” Guarantees. So far, the main question
(and the results we obtain) focus on applying the Johnson-Lindenstrauss
transform and preserving the optimal cost, i.e., that the _minimizing
solution_ in the original and the dimension reduced space have approximately
the same cost. A stronger guarantee which one may hope for, a so-called “for-
all” guarantee, asks that after applying the Johnson-Lindenstrauss transform,
every solution has its cost approximately preserved before and after dimension
reduction. We do not achieve “for all” guarantees, like those appearing in
[MMR19]. However, we emphasize that various subtleties arise in what is meant
by “a solution,” as the prior work on dimension reduction and coresets refer
to _different notions_ (even though they agree at the optimum).

Consider, for example, the $1$-medoid problem, a constrained version of the
$1$-means problem. The $1$-medoid cost of a dataset $X$ is the minimum over
centers $c$ chosen from the dataset $X$, of the sum of squares of distances
from each dataset point $x$ to $c$. The subtlety is the following: one can
apply a Johnson-Lindenstrauss transform to
$t=O(\log(1/\varepsilon)/\varepsilon^{2})$ dimensions and preserve the
$1$-means cost, and one may hope that a “for-all” guarantee would also
preserve the $1$-medoid cost. Somewhat surprisingly, we show that it does not.

######  Theorem 2 (Johnson-Lindenstrauss for Medoid—Informal (see Theorem
12)).

For any $t=o(\log n)$, applying a Johnson-Lindenstrauss transform to dimension
$t$ decreases the cost of the $1$-medoid problem by a factor approaching $2$.

Not all “for-all” guarantees are the same. A “for-all” guarantee comes with
(an implicit) representation of a candidate “solution,” and different choices
of representations yield different guarantees. The above theorem does not
contradict the “for-all” guarantee of [MMR19] because there, a candidate
solution for $(k,z)$-clustering refers to a partition of $X$ into $k$ parts
and not a set of centers. Often in the coreset literature, a “solution” refers
to a set of centers and not arbitrary partitions. For $k=1$, there are many
possible centers but only one partition, and it is important (as per Theorem
2) that a potential “for all” guarantee considers partitions.

For $(k,z)$-subspace and -flat approximation, in a natural representation of
the solutions, the same issue arises. Consider the $1$-column subset selection
problem, a constrained version of the $(1,2)$-subspace approximation problem,
where subspaces must be in the span of the dataset points. The $1$-column
subset selection cost of a dataset is the minimum over $1$-dimensional
subspaces spanned by a dataset point of $X$, of the sum of squares of
distances from each dataset point $x$ to the projection onto the subspace.
Similarly to Theorem 2, a Johnson-Lindenstrauss transform does not preserve
the cost of $1$-column subset selection.

######  Theorem 3 (Johnson-Lindenstrauss for Column Subset Selection—Informal
(see Theorem 13)).

For any $t=o(\log n)$, applying a Johnson-Lindenstrauss transform to dimension
$t$ decreases the cost of the $1$-column subset selection problem by a factor
approaching $3/2$.

The above theorem does not contradict the “for-all” guarantee of [CEM+15] for
similar reasons (which, in addition, crucially rely on having $z=2$, and which
we elaborate on in Appendix A). For $(k,z)$-line approximation, however, there
is an interesting open problem: is it true that after applying a Johnson-
Lindenstrauss transform to $t=\mathrm{poly}(k\log\log n/\varepsilon)$, _for
all partitions_ of $X$ into $k$ parts, the cost of _optimally_ approximating
each part with a line has its cost preserved.

###  1.2 Related Work

##### Dimension Reduction.

Our paper continues a line of work initiated by Boutsidis, Zouzias, and
Drineas [BZD10], who first studied the effect of a Johnson-Lindenstrauss
transform for $k$-means clustering, and showed that $t=O(k/\varepsilon^{2})$
sufficed for a $2+\varepsilon$-approximation. The bound was improved to
$(1+\varepsilon)$-approximation with $t=O(k/\varepsilon^{2})$ by Cohen, Elder,
Musco, Musco, Persu [CEM+15], who also showed that $t=O(\log
k/\varepsilon^{2})$ gave a $9+\varepsilon$-approximation. Becchetti, Bury,
Cohen-Addad, Grandoni, Schwiegelshohn [BBCA+19] showed that $t=O((\log
k+\log\log n)\log(1/\varepsilon)/\varepsilon^{6})$ sufficed for preserving the
costs of all $k$-mean clusterings. Makarychev, Makarychev, and Razenshteyn
[MMR19] improved and generalized the above bounds for all $(k,z)$-clustering.
They showed that $t=O((\log k+z\log(1/\varepsilon)+z^{2})/\varepsilon^{2})$
preserved costs to $(1\pm\varepsilon)$-factor.

For subspace approximation problems, [CEM+15] showed that
$t=O(k/\varepsilon^{2})$ preserves the cost of $(k,2)$-subspace approximation
to $(1+\varepsilon)$-factor. In addition, [KR15] showed that $O(zk^{2}\log
n/\varepsilon^{3})$ preserved the cost of the $(k,z)$-flat approximation to
$(1+\varepsilon)$-factor.

##### Coresets.

Coresets are a well-studied technique for reducing the size of a dataset,
while approximately preserving a particular desired property. Since its
formalization in Agarwal, Har-Peled, and Varadarajan [AHPV05], coresets have
played a foundational role in computational geometry, and found widespread
application in clustering, numerical linear algebra, and machine learning (see
the recent survey [Fel20]). Indeed, even for clustering problems in Euclidean
spaces, there is a long line of work (which is still on-going) [BHPI02, HPM04,
AHPV05, Che09, LS10, FL11, VX12b, VX12a, FSS13, BFL16, SW18, HV20, BBH+20,
CASS21, CALSS22] exploring the best coreset constructions.

Most relevant to our work is the “sensitivity sampling” framework of Feldman
and Langberg [FL11], which gives algorithms for constructing coresets for the
projective clustering problems we study. In light of the results of [FL11], as
well as the classical formulation of the Johnson-Lindenstrauss lemma [JL84],
it may seem natural to apply coreset algorithms and dimensionality reduction
concurrently. However, this is not without a few technical challenges. As we
will see in the next subsection, it is not necessarily the case that coreset
algorithms and random projections “commute.” Put succinctly, the random
projection $\mathbf{\Pi}$ of a coreset of $X$ may not be a coreset of the
random projection $\mathbf{\Pi}(X)$. Indeed, proving such a statement
constitutes the bulk of the technical work.

###  1.3 Organization

The following section (Section 2) overviews the high-level plan, since all our
results follow the same technique. To highlight the technique, the first
technical section considers the case of $(k,z)$-clustering (Section 4), where
the technique of arguing via coresets shows to obtain
$t=O((\log(k)+z\log(1/\varepsilon))/\varepsilon^{2})$. The remaining sections
cover the technical material for $(k,z)$-subspace approximation (in Section
5), $(k,z)$-flat approximation (in Section 6), and finally $(k,z)$-line
approximation (in Section 7).

##  2 Overview of Techniques

In this subsection, we give a high-level overview of the techniques employed.
As it will turn out, all results in this paper follow from one general
technique, which we instantiate for the various problem instances.

We give an abstract instantiation of the approach. We will be concerned with
geometric optimization problems of the following sort:

  * •

For each $d\in\mathbbm{N}$, we specify a class of _candidate solutions_ given
by a set $\mathcal{C}_{d}$. For example, in center-based clustering,
$\mathcal{C}_{d}$ may be given by a tuple of $k$ points in $\mathbbm{R}^{d}$,
corresponding to $k$ centers for a center-based clustering. In subspace
approximation, the set $\mathcal{C}_{d}$ may denote the set of all
$k$-dimensional subspaces of $\mathbbm{R}^{d}$.

  * •

There will be a cost function
$f_{d}\colon\mathbbm{R}^{d}\times\mathcal{C}_{d}\to\mathbbm{R}_{\geq 0}$
which, takes a point $x\in\mathbbm{R}^{d}$ and a potential solution
$c\in\mathcal{C}_{d}$, and outputs the cost of $x$ on $c$. Continuing on the
example on center-based clustering, $f_{d}$ may denote the distance from a
dataset point $x\in\mathbbm{R}^{d}$ to its nearest point in $c$. In subspace
approximation, $f_{d}$ may denote the distance from a dataset point to the
orthogonal projection of that point onto the subspace $c$. For a parameter
$z\in\mathbbm{N}$, we will denote the cost of using $c$ for a dataset
$X\subset\mathbbm{R}^{d}$ by

$\mathrm{cost}_{d,z}(X,c)=\left(\sum_{x\in X}f_{d}(x,c)^{z}\right)^{1/z}.$

For simplicity in the notation, we will drop the subscripts from the functions
$f$ and $\mathrm{cost}$ when they are clear from context.

We let $\mathcal{J}_{d,t}$ denote a distribution over linear maps
$\mathbf{\Pi}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ which will satisfy some
“Johnson-Lindenstrauss” guarantees (we will specify in the preliminaries the
properties we will need). For concreteness, we will think of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ given by matrix multiplication by a
$t\times d$ matrix of i.i.d draws of $\mathcal{N}(0,1/t)$. We ask, for a
particular bound on the dataset size $n\in\mathbbm{N}$, a geometric
optimization problem (specified by $\\{\mathcal{C}_{d}\\}_{d\in\mathbbm{N}}$,
$f_{d}$ and $z$), and a parameter $\varepsilon\in(0,1)$, what is the smallest
$t\in\mathbbm{N}$ such that with probability at least $0.9$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\displaystyle\frac{1}{1+\varepsilon}\cdot\min_{c\in\mathcal{C}_{d}}\mathrm{cost}(X,c)\leq\min_{c\in\mathcal{C}_{t}}\mathrm{cost}(\mathbf{\Pi}(X),c)\leq(1+\varepsilon)\cdot\min_{c\in\mathcal{C}_{d}}\mathrm{cost}(X,c).$
(3)

The right-most inequality in (3) claims that the cost after applying
$\mathbf{\Pi}$ does not increase significantly, i.e.,
$\min_{c\in\mathcal{C}_{t}}\mathrm{cost}(\mathbf{\Pi}(X),c)\leq(1+\varepsilon)\min_{c\in\mathcal{C}_{d}}\mathrm{cost}(X,c)$.
This direction is easy to prove for the following reason. For a dataset
$X\subset\mathbbm{R}^{d}$, we consider the solution $c^{*}\in\mathcal{C}_{d}$
minimizing $\mathrm{cost}(X,c^{*})$. We sample
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ and we find a candidate solution
$c^{**}\in\mathcal{C}_{t}$ which exhibits an upper bound on
$\min_{c\in\mathcal{C}_{t}}\mathrm{cost}(\mathbf{\Pi}(X),c)\leq\mathrm{cost}(\mathbf{\Pi}(X),c^{**})$.
For example, in the center-based clustering, $c^{*}\in\mathcal{C}_{d}$ is a
set of $k$ centers in $\mathbbm{R}^{d}$, and we may consider
$c^{**}\in\mathcal{C}_{t}$ as the $k$ centers from $c^{*}$ after applying
$\mathbf{\Pi}$. The fact that
$\mathrm{cost}(\mathbf{\Pi}(x),c^{**})\leq(1+\varepsilon)\mathrm{cost}(X,c^{*})$
with high probability over $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ will follow
straight-forwardly from properties of $\mathcal{J}_{d,t}$. Importantly, the
optimal solution $c^{*}$ does not depend on
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$. In fact, while we expect
$\mathbf{\Pi}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ to distort some
distances substantially, we can pick $c^{**}\in\mathcal{C}_{t}$ so that too
many distortions on these points is unlikely.

However, the same reasoning _does not_ apply to the left-most inequality in
(3). This is because the solution $c^{**}\in\mathcal{C}_{t}$ which minimizes
$\min_{c\in\mathcal{C}_{t}}\mathrm{cost}(\mathbf{\Pi}(X),c)$ depends on
$\mathbf{\Pi}$. Indeed, we would expect $c^{**}\in\mathcal{C}_{t}$ to take
advantage of distortions in $\mathbf{\Pi}$ in order to decrease the cost of
the optimal solution. We proceed by the following high level plan. We identify
a sequence of important events defined over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ which occur with probability at least
$0.9$. The special property is that if $\mathbf{\Pi}$ satisfies these events,
we can identify, from $c^{**}\in\mathcal{C}_{t}$ minimizing
$\mathrm{cost}(\mathbf{\Pi}(X),c^{**})$, a candidate solution
$c^{*}\in\mathcal{C}_{d}$ which exhibits an upper bound
$\mathrm{cost}(X,c^{*})\leq(1+\varepsilon)\mathrm{cost}(\mathbf{\Pi}(X),c^{**})$.

We now specify how exactly we define, for an optimal
$c^{**}\in\mathcal{C}_{t}$ (depending on $\mathbf{\Pi}$), a candidate solution
$c^{*}\in\mathcal{C}_{t}$ whose cost is not much higher than
$\mathrm{cost}(\mathbf{\Pi}(X),c^{**})$. For that, we will use the notion of
coresets. Before the formal definition, we note there is a natural extension
of $\mathrm{cost}$ for weighted datasets. In particular, if
$S\subset\mathbbm{R}^{d}$ is a set of points and $w\colon
S\to\mathbbm{R}_{\geq 0}$ is a set of weights for $S$, then we will use
$\mathrm{cost}((S,w),c)$ as $1/z$-th power of the sum over all $x\in S$ of
$w(x)\cdot f_{d}(x,c)^{z}$.

######  Definition 2.1 ((Weak)333The word “weak” is used to distinguish these
from “strong” coresets. These are a weighted subset of points which
approximately preserve the cost of all candidate solutions. Coresets, see also
[Fel20]).

For $d\in\mathbbm{N}$, let $\mathcal{C}_{d}$ denote a class of candidate
solutions and $f\colon\mathbbm{R}^{d}\times\mathcal{C}_{d}\to\mathbbm{R}_{\geq
0}$ specify the cost of a point to a solution. For a dataset
$X\subset\mathbbm{R}^{d}$ and a parameter $\varepsilon\in(0,1)$, a (weak)
$\varepsilon$-coreset for $X$ is a weighted set of points
$S\subset\mathbbm{R}^{d}$ and $w\colon S\to\mathbbm{R}_{\geq 0}$ which satisfy

$\dfrac{1}{1+\varepsilon}\cdot\min_{c\in\mathcal{C}_{d}}\mathrm{cost}(X,c)\leq\min_{c\in\mathcal{C}_{d}}\mathrm{cost}((S,w),c)\leq(1+\varepsilon)\cdot\min_{c\in\mathcal{C}_{d}}\mathrm{cost}(X,c).$

It will be crucial for us that these problems admit small coresets. More
specifically, for the problems considered in this paper, there exists (known)
algorithms which can produce small-size coresets from a dataset. In what
follows, ALG is a randomized algorithm which receives as input a dataset
$X\subset\mathbbm{R}^{d}$ and outputs a weighted subset of points
$(\mathbf{S},\boldsymbol{w})$ which is a weak $\varepsilon$-coreset for $X$
with high probability. Computationally, the benefit of using coresets is that
the sets $\mathbf{S}$ tend to be much smaller than $X$, so that one may
compute on $(\mathbf{S},\boldsymbol{w})$ and obtain an approximately optimal
solution for $X$. For us, the benefit will come in defining the important
events. At a high level, since $\mathbf{S}$ is small, the important events
defined with respect to $\mathbf{\Pi}$ will only worry about distortions
within the subset (or subspace spanned by) $\mathbf{S}$.

In particular, it is natural to consider the following approach:

  1. 1.

We begin with the original dataset $X\subset\mathbbm{R}^{d}$, and we consider
the solution $c\in\mathcal{C}_{d}$ which minimizes $\mathrm{cost}(X,c)$. The
goal is to show that $\mathrm{cost}(X,c)$ cannot be much larger than
$\mathrm{cost}(\mathbf{\Pi}(X),c^{**})$, where $c^{**}\in\mathcal{C}_{t}$
minimizes $\mathrm{cost}(\mathbf{\Pi}(X),c^{**})$.

  2. 2.

Instead of considering the entire dataset $X$, we execute $\texttt{ALG}(X)$
and consider the weak $\varepsilon$-coreset $(\mathbf{S},\boldsymbol{w})$ that
we obtain. If we can identify a candidate solution $c^{*}\in\mathcal{C}_{d}$
whose cost
$\mathrm{cost}((\mathbf{S},\boldsymbol{w}),c^{*})\leq(1+\varepsilon)\mathrm{cost}(\mathbf{\Pi}(X),c^{**})$,
we would be done. Indeed,
$\min_{c\in\mathcal{C}_{d}}\mathrm{cost}((\mathbf{S},\boldsymbol{w}),c)\leq\mathrm{cost}((\mathbf{S},\boldsymbol{w}),c^{*})$,
and the fact $(\mathbf{S},\boldsymbol{w})$ is a weak $\varepsilon$-coreset
implies
$\min_{c\in\mathcal{C}_{d}}\mathrm{cost}(X,c)\leq(1+\varepsilon)\min_{c\in\mathcal{C}_{d}}\mathrm{cost}((\mathbf{S},\boldsymbol{w}),c)$.

  3. 3.

Moving to a coreset $(\mathbf{S},\boldsymbol{w})$ allows one to relate
$\mathrm{cost}((\mathbf{S},\boldsymbol{w}),c^{*})$ and
$\mathrm{cost}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),c^{**})$ by
considering the performance of $\mathbf{\Pi}$ on $\mathbf{S}$. The benefit is
that the important events, defined over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, set $t$ as a function of $|\mathbf{S}|$,
instead of $|X|$. A useful example to consider is requiring
$\mathbf{\Pi}^{-1}$ be $(1+\varepsilon)$-Lipschitz on the entire subspace
spanned by $\mathbf{S}$, which requires
$t=\Theta(|\mathbf{S}|/\varepsilon^{2})$. For the problems considered here, a
nearly optimal $c^{**}\in\mathcal{C}_{t}$ for $(\mathbf{S},\boldsymbol{w})$
will be in the subspace spanned by $\mathbf{S}$, so we may identify
$c^{*}\in\mathcal{C}_{d}$ whose cost on $(\mathbf{S},\boldsymbol{w})$ is not
much higher than the
$\mathrm{cost}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),c^{**})$ by
evaluating $\mathbf{\Pi}^{-1}(c^{**})$ since $c^{**}$ lies inside
$\mathrm{span}(\mathbf{S})$.444While the above results in bounds for $t$ which
are already meaningful, we will exploit other geometric aspects of the
problems considered to get bounds on $t$ which are logarithmic in the coreset
size. For center-based clustering, [MMR19] showed that one may apply
Kirzbraun’s theorem. For subspace approximation, we use the geometric lemmas
of [SV12].

  4. 4.

The remaining step is showing
$\mathrm{cost}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),c^{**})\leq(1+\varepsilon)\mathrm{cost}(\mathbf{\Pi}(X),c^{**})$.
In particular, one would like to claim
$(\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w})$ is a weak $\varepsilon$-coreset
for $\mathbf{\Pi}(X)$ and use the right-most inequality in Definition 2.1.
However, it is not clear this is so. The problem is that the algorithm ALG
depends on the $d$-dimensional representation of $X\subset\mathbbm{R}^{d}$,
and $(\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w})$ may not be a valid output for
$\texttt{ALG}(\mathbf{\Pi}(X))$. As we show, this does work for (some) coreset
algorithms built on the _sensitivity sampling_ framework (see, [FL11,
BFL16]).555We will not prove that with high probability over $\mathbf{\Pi}$
and $\texttt{ALG}(X)$, $(\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w})$ is a weak
$\varepsilon$-coreset for $\mathbf{\Pi}(X)$. Rather, all we need is that the
right-most inequality in Definition 2.1 holds for
$(\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w})$ and $\mathbf{\Pi}(X)$, which is
what we show.

####  2.0.1 Sensitivity Sampling for Step 4

In the remainder of this section, we briefly overview the sensitivity sampling
framework, and the components required to make Step 4 go through. At a high
level, coreset algorithms in the sensitivity sampling framework proceed in the
following way. Given a dataset $X\subset\mathbbm{R}^{d}$, the algorithm
computes a _sensitivity sampling distribution_ $\tilde{\sigma}$ supported on
$X$. The requirement is that, for each potential solution
$c\in\mathcal{C}_{d}$, sampling from $\tilde{\sigma}$ gives a low-variance
estimator for $\mathrm{cost}_{d,z}(X,c)^{z}$. In particular, we let
$\tilde{\sigma}(x)$ be the probability of sampling $x\in X$. Then, for any
distribution $\tilde{\sigma}$ and any $c\in\mathcal{C}_{d}$,

$\displaystyle\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\tilde{\sigma}}\left[\dfrac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\dfrac{f_{d}(\boldsymbol{x},c)^{z}}{\mathrm{cost}_{d,z}(X,c)^{z}}\right]=1.$
(4)

Equation 4 implies that, for any $m\in\mathbbm{N}$, if $\mathbf{S}$ is $m$
i.i.d samples from $\tilde{\sigma}$ and
$\boldsymbol{w}(x)=1/(m\tilde{\sigma}(x))$, the expectation of
$\mathrm{cost}_{d,z}((\mathbf{S},\boldsymbol{w}),c)^{z}$ is
$\mathrm{cost}_{d,z}(X,c)^{z}$. In addition, the algorithm designs
$\tilde{\sigma}$ so that, for a parameter $T>0$,

$\displaystyle\sup_{c\in\mathcal{C}_{d}}\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\tilde{\sigma}}\left[\left(\dfrac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\dfrac{f_{d}(\boldsymbol{x},c)^{z}}{\mathrm{cost}_{d,z}(X,c)^{z}}\right)^{2}\right]\leq
T.$ (5)

If we set $m\geq T/\varepsilon^{2}$, (5) and Chebyshev’s inequality implies
$\mathrm{cost}_{d,z}((\mathbf{S},\boldsymbol{w}),c)^{z}\approx_{1\pm\varepsilon}\mathrm{cost}_{d,z}(X,c)^{z}$
for each $c\in\mathcal{C}_{d}$ with a high constant probability, and the
remaining work is in increasing $m$ by a large enough factor to “union bound”
over all $c\in\mathcal{C}_{d}$. There is a canonical way of ensuring
$\tilde{\sigma}$ and $T$ satisfy (5): we first define $\sigma\colon
X\to\mathbbm{R}_{\geq 0}$, known as a “sensitivity function”, which sets for
each $x\in X$,

$\displaystyle\sigma(x)\geq\sup_{c\in\mathcal{C}_{d}}\dfrac{f_{d}(x,c)^{z}}{\mathrm{cost}_{d,z}(X,c)^{z}},\qquad\text{and}\qquad
T=\sum_{x\in X}\sigma(x),$ (6)

which is known as the “total sensitivity.” Then, the distribution is given by
letting $\tilde{\sigma}(x)=\sigma(x)/T$.

We now show how to incorporate the map $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, to
argue Step 4. Recall that we let $\mathbf{S}$ denote $m$ i.i.d draws from
$\tilde{\sigma}$ and the weights be
$\boldsymbol{w}(x)=1/(m\tilde{\sigma}(x))$. We want to argue that, with high
constant probability over the draw of $(\mathbf{S},\boldsymbol{w})$ and
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, we have

$\displaystyle\mathrm{cost}_{t,z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),c^{**})\leq(1+\varepsilon)\cdot\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c^{**}).$
(7)

First, note that the analogous version of (4) for
$\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c)$ continues to hold. In particular, for
any map $\mathbf{\Pi}$ in the support of $\mathcal{J}_{d,t}$ and
$c^{**}\in\mathcal{C}_{t}$ minimizing
$\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c)$,

$\displaystyle\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\tilde{\sigma}}\left[\dfrac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\dfrac{f_{t}(\mathbf{\Pi}(\boldsymbol{x}),c^{**})^{z}}{\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c^{**})^{z}}\right]=1.$
(8)

Hence, it remains to define $\tilde{\sigma}$ satisfying (6) which also
satisfies one additional requirement. With high probability over
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, we should have

$\displaystyle\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\tilde{\sigma}}\left[\left(\dfrac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\dfrac{f_{t}(\mathbf{\Pi}(\boldsymbol{x}),c^{**})^{z}}{\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c^{**})}\right)^{2}\right]\lesssim
T.$ (9)

The above translates to saying, for most $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$
the variance of
$\mathrm{cost}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),c^{**})$, when
$m=O(T/\varepsilon^{2})$, is small. Once that is established, we may apply
Chebyshev’s inequality and conclude (7) with high constant
probability.666Since Steps 1–4 only argued about the optimal
$c^{**}\in\mathcal{C}_{t}$, there is no need to “union bound” over all
$c\in\mathcal{C}_{t}$ in our arguments.

####  2.0.2 The Circularity and How to Break It

One final technical hurdle arises. While one may define the sensitivity
function $\sigma(x)$ to be exactly
$\sup_{c\in\mathcal{C}_{d}}f_{d}(x,c)^{z}/\mathrm{cost}_{d,z}(X,c)^{z}$ and
automatically satisfy (6), it becomes challenging to argue that (9) holds. In
the end, the complexity we seek to optimize is the total sensitivity $T$, so
there is flexibility in defining $\sigma$ while showing (9) holds. In fact,
sensitivity functions $\sigma$ which are computationally simple tend to be
known, since an algorithm using coresets must quickly compute $\sigma(x)$ for
every $x\in X$.

The sensitivity functions $\sigma$ used in the literature (for instance, in
[FL11, VX12b]) are defined with respect to an approximately optimal
$c\in\mathcal{C}_{d}$ (or bi-criteria approximation) for
$\mathrm{cost}_{d,z}(X,c)$. Furthermore, the arguments used to show these
function satisfy (6), which we will also employ for (9), crucially utilize the
approximation guarantee on $c\in\mathcal{C}_{d}$. The apparent circularity
appears in approximation algorithms and also shows up in the analysis here:

  * •

For $X\subset\mathbbm{R}^{d}$, we identify the optimal $c\in\mathcal{C}_{d}$
minimizing $\mathrm{cost}_{d,z}(X,c)$, and use $c$ to define $\sigma\colon
X\to\mathbbm{R}_{\geq 0}$. The fact that $c\in\mathcal{C}_{d}$ is optimal (and
therefore approximately optimal) allows us to use known arguments (in
particular, those in [VX12b, VX12a]) to establish (6) and give an upper bound
on $T$.

  * •

We use the proof of the “easy” direction to identify a solution
$c^{\prime}\in\mathcal{C}_{t}$ with
$\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c^{\prime})\leq(1+\varepsilon)\mathrm{cost}_{d,z}(X,c)$
(recall this was used to establish the right-most inequality in (3)). From the
analytical perspective, it is useful to think of
$\sigma^{\prime}\colon\mathbf{\Pi}(X)\to\mathbbm{R}_{\geq 0}$ as the function
one would get from defining a sensitivity function like in the previous step
with $c^{\prime}$ instead of $c$. If we could show
$c^{\prime}\in\mathcal{C}_{t}$ was approximately optimal for
$\mathbf{\Pi}(X)$, we could use [VX12b, VX12a] again to argue (9). The
circularity is the following. Showing $c^{\prime}\in\mathcal{C}_{t}$ is
approximately optimal means showing an upper bound on
$\min_{c\in\mathcal{C}_{t}}\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c)$ in terms of
$\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c^{\prime})$. Since, we picked
$\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c^{\prime})$ to be at most
$(1+\varepsilon)\min_{c\in\mathcal{C}_{d}}\mathrm{cost}_{d,z}(X,c)$, this is
exactly what we sought to prove.

If “approximately optimal” above required $c^{\prime}\in\mathcal{C}_{t}$ be a
$(1+\varepsilon)$-approximation to the optimal $\mathbf{\Pi}(X)$, we would
have a complete circularity and be unable to proceed. However, similarly to
the case of approximation algorithms, it suffices to have a poor
approximation. Suppose we showed $c^{\prime}\in\mathcal{C}_{t}$ was a
$C$-approximation, then, increasing $m$ by a factor depending on $C$ (which
would affect the resulting dimensionality $t$) would account for this increase
and drive the variance back down to $\varepsilon^{2}$. Moreover, showing
$c^{\prime}$ is a $O(1)$-approximation with probability at least $0.99$ over
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, given Steps 1–4 is straight-forward.
Instead of showing the stronger bound that
$\mathrm{cost}_{t,z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),c^{**})\leq(1+\varepsilon)\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c^{**})$,
we show that
$\mathrm{cost}_{t,z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),c^{**})\leq
O(1)\cdot\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c^{**})$. The latter (loose)
bound is a consequence of applying Markov’s inequality to (8).

In summary, we overcome the circularity by going through Steps 1–4 twice. In
the first time, we show a weaker $O(1)$-approximation. Specifically, we show
that $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ preserves the cost of
$\min_{c\in\mathcal{C}_{t}}\mathrm{cost}_{d,z}(\mathbf{\Pi}(X),c)$ up to
factor $O(1)$. The first time around, we won’t upper bound the variance in
(9), and we simply use Markov’s inequality to (8) in order to prove a (loose)
bound on Step 4. Once we’ve established the $O(1)$-factor approximation, we
are guaranteed that $c^{\prime}\in\mathcal{C}_{t}$ is a $O(1)$-approximation
to $\min_{c\in\mathcal{C}_{t}}\mathrm{cost}_{t,z}(\mathbf{\Pi}(X),c)$. This
means that, actually, the sensitivity sampling distribution $\tilde{\sigma}$
we had considered (when viewed as a sensitivity sampling distribution for
$\mathbf{\Pi}(X)$) gives estimators with bounded variance, as in (9). In
particular, going through Steps 1–4 once again implies that
$c^{\prime}\in\mathcal{C}_{t}$ was actually the desired
$1\pm\varepsilon$-approximation.

##  3 Preliminaries

We specify the properties we use from the distribution $\mathcal{J}_{d,t}$. We
will refer to these as “Johnson-Lindenstrauss” distributions. Throughout the
proof, we will often refer to $\mathcal{J}_{d,t}$ as given by a $t\times d$
matrix of i.i.d draws from $\mathcal{N}(0,1/t)$. The goal of specifying the
useful properties is to use other “Johnson-Lindenstrauss”-like distributions.
The first property we need is that
$\mathbf{\Pi}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ is a linear map, and
that any $x,y\in\mathbbm{R}^{d}$ satisfies

$\mathop{{\bf
E}\/}_{\mathbf{\Pi}\sim\mathcal{J}_{d,t}}\left[\dfrac{\|\mathbf{\Pi}(x)-\mathbf{\Pi}(y)\|_{2}^{2}}{\|x-y\|_{2}^{2}}\right]=1.$

We use the standard property of $\mathcal{J}_{d,t}$, that $\mathbf{\Pi}$
preserves distances with high probability, i.e., for any
$x,y\in\mathbbm{R}^{d}$,

$\mathop{{\bf
Pr}\/}_{\mathbf{\Pi}\sim\mathcal{J}_{d,t}}\left[\left|\dfrac{\|\mathbf{\Pi}(x)-\mathbf{\Pi}(y)\|_{2}^{2}}{\|x-y\|_{2}^{2}}-1\right|\geq\varepsilon\right]\leq
e^{-\Omega(\varepsilon^{2}t)}.$

More generally, we use the conclusion of the following lemma. We give a proof
when $\mathcal{J}_{d,t}$ is a $t\times d$ i.i.d entries of
$\mathcal{N}(0,1/t)$.

######  Lemma 3.1.

Let $\mathcal{J}_{d,t}$ denote a Johnson-Lindenstrauss distribution over maps
$\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ given by a matrix multiplication on the
left by a $t\times d$ matrix of i.i.d draws of $\mathcal{N}(0,1/t)$. If
$t\gtrsim z/\varepsilon^{2}$, then for any $x,y\in\mathbbm{R}^{d}$,

$\displaystyle\mathop{{\bf
E}\/}_{\mathbf{\Pi}\sim\mathcal{J}_{d.t}}\left[\left(\dfrac{\|\mathbf{\Pi}(x)-\mathbf{\Pi}(y)\|_{2}^{z}}{\|x-y\|_{2}^{z}}-1\right)^{+}\right]\leq\dfrac{(1+\varepsilon)^{z}-1}{100}.$

###### Proof.

We note that by the 2-stability of the Gaussian distribution, we have
$\|\mathbf{\Pi}(x)-\mathbf{\Pi}(y)\|_{2}^{2}$ is equivalently distributed as
$\|\boldsymbol{g}\|_{2}^{2}\cdot\|x-y\|_{2}^{2}$, where
$\boldsymbol{g}\sim\mathcal{N}(0,I_{t}/t)$. Therefore, we have that for any
$\lambda>0$ which we will optimize shortly to be a small constant times
$\varepsilon$,

$\displaystyle\mathop{{\bf
E}\/}_{\mathbf{\Pi}\sim\mathcal{J}(d,t)}\left[\left(\dfrac{\|\mathbf{\Pi}(x)-\mathbf{\Pi}(y)\|_{2}^{z}}{\|x-y\|_{2}^{z}}-1\right)^{+}\right]$
$\displaystyle\leq(1+\lambda)^{z}-1+\mathop{{\bf
E}\/}_{\boldsymbol{g}\sim\mathcal{N}(0,I_{t}/t)}\left[(\|\boldsymbol{g}\|_{2}^{z}-(1+\lambda)^{z})^{+}\right].$

Furthermore,

$\displaystyle\mathop{{\bf
E}\/}_{\boldsymbol{g}\sim\mathcal{N}(0,I_{t}/t)}\left[\left(\|\boldsymbol{g}\|_{2}^{z}-(1+\lambda)^{z}\right)^{+}\right]$
$\displaystyle=\int_{u:(1+\lambda)^{z}}^{\infty}\mathop{{\bf
Pr}\/}\left[\|\boldsymbol{g}\|_{2}^{z}\geq
u\right]du=\frac{z}{2}\int_{v:(1+\lambda)^{2}}^{\infty}\mathop{{\bf
Pr}\/}\left[\|\boldsymbol{g}\|_{2}^{2}\geq v\right]\cdot v^{z/2-1}dv.$

We will upper bound the probability that $\|\boldsymbol{g}\|_{2}^{2}$ exceeds
$v$ by the Chernoff-Hoeffding method. In particular, recall that
$\|\boldsymbol{g}\|_{2}^{2}$ when $\mathcal{N}(0,I_{t}/t)$ is distributed as a
$\chi^{2}$-random variable with $t$ degrees of freedom, rescaled by $1/t$,
such that the moment generating function of $\|\boldsymbol{g}\|_{2}^{2}$ has
the following closed form solution whenever $\alpha<t/2$:

$\log\left(\mathop{{\bf
E}\/}_{\boldsymbol{g}\sim\mathcal{N}(0,I_{t}/t)}\left[\exp\left(\alpha\|\boldsymbol{g}\|_{2}^{2}\right)\right]\right)=-\frac{t}{2}\log\left(1-\frac{2\alpha}{t}\right)\leq\alpha+\frac{2\alpha^{2}}{t}$

In particular, for any $\alpha<t/2$, we may upper bound

$\displaystyle\frac{z}{2}\int_{v:(1+\lambda)^{2}}^{\infty}\mathop{{\bf
Pr}\/}\left[\|\boldsymbol{g}\|_{2}^{2}\geq v\right]v^{z/2-1}$
$\displaystyle\leq\frac{z}{2}\cdot\exp\left(\alpha+\frac{2\alpha^{2}}{t}\right)\int_{v:(1+\lambda)^{2}}^{\infty}\exp\left(-\left(\alpha-\frac{z}{2}-1\right)v\right)dv$
$\displaystyle\leq\dfrac{z}{2\alpha-z-2}\cdot\exp\left(\frac{2\alpha^{2}}{t}-\alpha\lambda+(1+\lambda)(z/2+1)\right)<\frac{\lambda}{100},$

by letting setting $\alpha=t\lambda/10$ whenever $t\gtrsim z/\lambda^{2}$.
Setting $\lambda$ to be a small constant of $\varepsilon$ gives the desired
guarantees. ∎

######  Definition 3.2 (Subspace Embeddings).

Let $d\in\mathbbm{N}$ and $A\subset\mathbbm{R}^{d}$ denote a subspace of
$\mathbbm{R}^{d}$. For $\varepsilon>0$, a map
$f\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ is an $\varepsilon$-subspace
embedding of $A$ if, for any $x\in A$,

$\frac{1}{1+\varepsilon}\cdot\|f(x)\|_{2}\leq\|x\|_{2}\leq(1+\varepsilon)\cdot\|f(x)\|_{2}.$

######  Lemma 3.3.

Let $d\in\mathbbm{N}$ and $A\subset\mathbbm{R}^{d}$ be a subspace of dimension
at most $k$. For $\varepsilon,\delta\in(0,1/2)$, let $\mathcal{J}_{d,t}$
denote a Johnson-Lindenstrauss distribution over maps
$\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ given by a matrix multiplication on the
left by a $t\times d$ matrix of i.i.d draws of $\mathcal{N}(0,1/t)$. If
$t\sim(k+\log(1/\delta))/\varepsilon^{2}$, then
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ is an $\varepsilon$-subspace embedding of
$A$ with probability at least $1-\delta$.

##  4 Center-based $(k,z)$-clustering

In the $(k,z)$-clustering problems, for any set $C\subset\mathbbm{R}^{d}$ of
$k$ points, and point $x\in\mathbbm{R}^{d}$, we write

$\mathrm{cost}_{z}^{z}(x,C)=\min_{c\in C}\|x-c\|_{2}^{2},$

and for a subset $X\subset\mathbbm{R}^{d}$,

$\mathrm{cost}_{z}^{z}(X,C)=\sum_{x\in X}\mathrm{cost}(x,C)=\sum_{x\in
X}\min_{c\in C}\|x-c\|_{2}^{z}.$

We extend the above notation to weighted subsets, where for a subset
$S\subset\mathbbm{R}^{d}$ with (non-negative) weights $w\colon
S\to\mathbbm{R}_{\geq 0}$, we write $\mathrm{cost}_{z}^{z}((S,w),C)=\sum_{x\in
S}w(x)\min_{c\in C}\|x-c\|_{2}^{z}$. The main result of this section is the
following theorem.

######  Theorem 4 (Johnson-Lindenstrauss for Center-Based Clustering).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points,
and let $C\subset\mathbbm{R}^{d}$ denote the optimal $(k,z)$-clustering of
$X$. For any $\varepsilon\in(0,1/2)$, suppose we let $\mathcal{J}_{d,t}$ be
the distribution over Johnson-Lindenstrauss maps where

$t\gtrsim\frac{\log k+z\log(1/\varepsilon)}{\varepsilon^{2}},$

Then, with probability at least $0.9$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\frac{1}{1+\varepsilon}\cdot\mathrm{cost}_{z}(X,C)\leq\min_{\begin{subarray}{c}C^{\prime}\subset\mathbbm{R}^{t}\\\
|C^{\prime}|=k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),C^{\prime})\leq(1+\varepsilon)\mathrm{cost}_{z}(X,C).$

There are two directions to showing dimension reduction: (1) the optimal
clustering in the _reduced space_ is not too expensive, and (2) the optimal
clustering in the reduced space is not too cheap. We note that (1) is simple
because we can exhibit a clustering in the reduced space whose cost is not too
high; however, (2) is much trickier, since we need to rule out a too-good-to-
be-true clustering in the reduced space.

###  4.1 Easy Direction: Optimum Cost Does Not Increase

######  Lemma 4.1.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points and
let $C\subset\mathbbm{R}^{d}$ of size $k$ be the centers of the optimal
$(k,z)$-clustering of $X$. We let $\mathcal{J}_{d,t}$ be the distribution over
Johnson-Lindenstrauss maps. If $t\gtrsim z/\varepsilon^{2}$, then with
probability at least $0.99$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\left(\sum_{x\in
X}\|\mathbf{\Pi}(x)-\mathbf{\Pi}(c(x))\|_{2}^{z}\right)^{1/z}\leq(1+\varepsilon)\mathrm{cost}_{z}(X,C),$

and hence,

$\min_{\begin{subarray}{c}C^{\prime}\subset\mathbbm{R}^{t}\\\
|C^{\prime}|=k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),C^{\prime})\leq(1+\varepsilon)\min_{\begin{subarray}{c}C\subset\mathbbm{R}^{d}\\\
|C|=k\end{subarray}}\mathrm{cost}_{z}(X,C).$

###### Proof.

For $x\in X$, let $c(x)\in C$ denote the closest point from $C$ to $x$. We
compute the expected positive deviation from assigning $\mathbf{\Pi}(x)$ to
$\mathbf{\Pi}(c(x))$, and note that the
$\mathrm{cost}_{z}(\mathbf{\Pi}(X),\mathbf{\Pi}(C))$ can only be lower. Hence,
if we can show

$\displaystyle\dfrac{1}{\mathrm{cost}_{z}^{z}(X,C)}\mathop{{\bf
E}\/}_{\mathbf{\Pi}\sim\mathcal{J}_{d,t}}\left[\sum_{x\in
X}\left(\left\|\mathbf{\Pi}(x)-\mathbf{\Pi}(c(x))\right\|_{2}^{z}-\|x-c(x)\|_{2}^{z}\right)^{+}\right]\lesssim\dfrac{(1+\varepsilon)^{z}-1}{100},$
(10)

then by Markov’s inequality, we will obtain
$\mathrm{cost}_{z}^{z}(\mathbf{\Pi}(X),\mathbf{\Pi}(C))\leq(1+\varepsilon)^{z}\mathrm{cost}_{z}^{z}(X,C)$,
and obtain the desired bound when raising to power $1/z$. This last part
follows from Lemma 3.1. ∎

###  4.2 Hard Direction: Optimum Cost Does Not Decrease

We now show that after applying a Johnson-Lindenstrauss map, the cost of the
optimal clustering in the dimension-reduced space is not too cheap. This
section will be significantly more difficult, and will draw on the following
preliminaries.

####  4.2.1 Preliminaries

######  Definition 4.2 (Weak and Strong Coresets).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be a set of points. A
(weak) $\varepsilon$-_coreset_ of $X$ for $(k,z)$-clustering is a subset
$S\subset\mathbbm{R}^{d}$ of points with weights $w\colon
S\to\mathbbm{R}_{\geq 0}$ such that,

$\dfrac{1}{1+\varepsilon}\cdot\min_{\begin{subarray}{c}C\subset\mathbbm{R}^{d}\\\
|C|\leq
k\end{subarray}}\mathrm{cost}_{z}(X,C)\leq\min_{\begin{subarray}{c}C\subset\mathbbm{R}^{d}\\\
|C|\leq
k\end{subarray}}\mathrm{cost}_{z}((S,w),C)\leq(1+\varepsilon)\cdot\min_{\begin{subarray}{c}C\subset\mathbbm{R}^{d}\\\
|C|\leq k\end{subarray}}\mathrm{cost}_{z}(X,C).$

The coreset $(S,w)$ is a strong $\varepsilon$-coreset if, for all
$C=\\{c_{1},\dots,c_{k}\\}\subset\mathbbm{R}^{d}$, we have

$\dfrac{1}{1+\varepsilon}\cdot\mathrm{cost}_{z}(X,C)\leq\mathrm{cost}_{z}((S,w),C)\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}(X,C).$

Notice that Definition 4.2 gives an approach to finding an approximately
optimal $(k,z)$-clustering. Given $X\subset\mathbbm{R}^{d}$, we find a (weak)
$\varepsilon$-coreset $(S,w)$ and find the optimal clustering
$C\subset\mathbbm{R}^{d}$ with respect to the coreset $(S,w)$. Then, we can
deduce that a clustering which is optimal for the coreset is also
approximately optimal for the original point set. A common and useful
framework for building coresets is by utilizing the “sensitivity” sampling
framework.

######  Definition 4.3 (Sensitivities).

Let $n,d\in\mathbbm{N}$, and consider any set of points
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, as well as
$k\in\mathbbm{N}$, $z\geq 1$. A sensitivity function $\sigma\colon
X\to\mathbbm{R}_{\geq 0}$ for $(k,z)$-clustering $X$ in $\mathbbm{R}^{d}$ is a
function satisfying, that for all $x\in X$,

$\displaystyle\sup_{\begin{subarray}{c}C\subset\mathbbm{R}^{d}\\\ |C|\leq
k\end{subarray}}\dfrac{\mathrm{cost}_{z}^{z}(x,C)}{\mathrm{cost}_{z}^{z}(X,C)}\leq\sigma(x).$

The total sensitivity of the sensitivity function $\sigma$ is given by

$\mathfrak{S}_{\sigma}=\sum_{x\in X}\sigma(x).$

For a sensitivity function, we let $\tilde{\sigma}$ denote the sensitivity
sampling distribution, supported on $X$, which samples $x\in X$ with
probability proportional to $\sigma(x)$.

The following lemma gives a particularly simple sensitivity sampling
distribution, which will be useful for analyzing our dimension reduction
procedure. The proof below will follow from two applications of the triangle
inequality which we reproduce from Claim 5.6 in [HV20].

######  Lemma 4.4.

Let $n,d\in\mathbbm{N}$ and consider a set of points
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$. Let
$C\subset\mathbbm{R}^{d}$ of size $k$ be optimal $(k,z)$-clustering of $X$,
and let $c\colon X\to C$ denote the function which sends $x\in X$ to its
closest point in $C$, and let $X_{c}\subset X$ be the set of points where
$c(x)=c$. Then, the function $\sigma\colon X\to\mathbbm{R}_{\geq 0}$ given by

$\sigma(x)=2^{z-1}\cdot\dfrac{\|x-c(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,C)}+\dfrac{2^{2z-1}}{|X_{c(x)}|}$

is a sensitivity function for $(k,z)$-clustering $X$ in $\mathbbm{R}^{d}$,
satisfying

$\mathfrak{S}_{\sigma}=2^{z-1}+2^{2z-1}\cdot k$

###### Proof.

Consider any set $C^{\prime}\subset\mathbbm{R}^{d}$ of $k$ points, and let
$c^{\prime}\colon X\to C^{\prime}$ be the function which sends each $x\in X$
to its closest point in $C^{\prime}$. Then, we have

$\displaystyle\|x-c^{\prime}(x)\|_{2}^{z}$
$\displaystyle\leq\left(\|x-c(x)\|_{2}+\|c(x)-c^{\prime}(x)\|_{2}\right)^{z}\leq
2^{z-1}\|x-c(x)\|_{2}^{z}+2^{z-1}\|c(x)-c^{\prime}(x)\|_{2}^{z}$ (11)
$\displaystyle\leq
2^{z-1}\|x-c(x)\|_{2}^{z}+\dfrac{2^{z-1}}{|X_{c(x)}|}\sum_{x\in
X}\|c(x)-c^{\prime}(x)\|_{2}^{z}$ (12) $\displaystyle\leq
2^{z-1}\|x-c(x)\|_{2}^{z}+\frac{2^{2(z-1)}}{|X_{c(x)}|}\left(\mathrm{cost}_{z}^{z}(X,C)+\mathrm{cost}_{z}^{z}(X,C^{\prime})\right),$
(13)

where we used the triangle inequality and Hölder inequality in (11), and added
additional non-negative terms in (12), and we finally apply the triangle
inequality and Hölder’s inequality once more in (13). Hence, using the fact
that $C$ is the optimal clustering, we have

$\displaystyle\dfrac{\mathrm{cost}_{z}^{z}(x,C^{\prime})}{\mathrm{cost}_{z}^{z}(X,C^{\prime})}$
$\displaystyle\leq
2^{z-1}\cdot\dfrac{\|x-c(x)\|_{2}^{z}}{\mathrm{cost}(X,C^{\prime})}+\dfrac{2^{2(z-1)}}{|X_{c(x)}|}\left(\dfrac{\mathrm{cost}_{z}^{z}(X,C)}{\mathrm{cost}_{z}^{z}(X,C^{\prime})}+1\right)\leq
2^{z-1}\cdot\dfrac{\|x-c(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,C)}+\dfrac{2^{2z-1}}{|X_{c(x)}|}.$

The bound on $\mathfrak{S}_{\sigma}$ follows from summing over all $x\in X$,
noting the fact that $\sum_{x\in X}1/|X_{c(x)}|=k$. ∎

The main idea behind the sensitivity sampling framework for building coresets
is to sample from a sensitivity sampling distribution enough times in order to
build a coreset. For this work, it will be sufficient to consider the
following theorem of [HV20], which shows that
$\mathrm{poly}(k,1/\varepsilon^{z})$ draws from an appropriate sensitivity
sampling distribution suffices to build strong $\varepsilon$-coresets for
$(k,z)$-clustering in $\mathbbm{R}^{d}$.

######  Theorem 5 ($\varepsilon$-Strong Coresets from Sensitivity Sampling
[HV20]).

For any subset $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ and
$\varepsilon\in(0,1/2)$. Let $C\subset\mathbbm{R}^{d}$ of size $k$ be the
optimal $(k,z)$-clustering of $X$, and let $\tilde{\sigma}$ denote the
sensitivity sampling distribution of Lemma 4.4.

  * •

Let $(\mathbf{S},\boldsymbol{w})$ denote a random (multi-)set
$\mathbf{S}\subset X$ and $\boldsymbol{w}\colon\mathbf{S}\to\mathbbm{R}_{\geq
0}$ given by, for $m=\mathrm{poly}(k,1/\varepsilon^{z})$ iterations, sampling
$\boldsymbol{x}\sim\tilde{\sigma}$ i.i.d and letting
$\boldsymbol{w}(\boldsymbol{x})=1/(m\tilde{\sigma}(x))$.

  * •

Then, with probability $1-o(1)$ over the draw of
$(\mathbf{S},\boldsymbol{w})$, it is an $\varepsilon$-strong coreset for $X$.

######  Theorem 6 (Kirszbraun theorem).

Let $Y\subset\mathbbm{R}^{d_{1}}$ and $\phi\colon Y\to\mathbbm{R}^{d_{2}}$ be
an $L$-Lipschitz map (with respect to Euclidean norms on $\mathbbm{R}^{d_{1}}$
and $\mathbbm{R}^{d_{2}}$). There exists a map
$\tilde{\phi}\colon\mathbbm{R}^{d_{1}}\to\mathbbm{R}^{d_{2}}$ which is
$L$-Lipschitz extending $\phi$, i.e., $\phi(x)=\tilde{\phi}(x)$ for all $x\in
Y$.

###  4.3 The Important Events

We now define the important events which will allow us to prove that the
optimum $(k,z)$-clustering after dimension reduction does not decrease
substantially. We first define the events, and then we prove that if the
events are all satisfied, then we obtain our desired lower bound.

######  Definition 4.5 (The Events).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ and
$C\subset\mathbbm{R}^{d}$ of size $k$ be centers for an optimal
$(k,z)$-clustering of $X$, and $\tilde{\sigma}$ is the sensitivity sampling
distribution of $X$ with respect to $C$ as in Lemma 4.4. We will consider the
following experiment,

  1. 1.

We generate a sample $(\mathbf{S},\boldsymbol{w})$ by sampling from
$\tilde{\sigma}$ for $m=\mathrm{poly}(k,1/\varepsilon^{z})$ i.i.d iterations
$\boldsymbol{x}\sim\tilde{\sigma}$ and set
$\boldsymbol{w}(\boldsymbol{x})=1/(m\tilde{\sigma}(\boldsymbol{x}))$.

  2. 2.

Furthermore, we sample $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ which is a Johnson-
Lindenstrauss map $\mathbbm{R}^{d}\to\mathbbm{R}^{t}$.

  3. 3.

We let $\mathbf{S}^{\prime}=\mathbf{\Pi}(\mathbf{S})\subset\mathbbm{R}^{t}$
denote the image of $\mathbf{\Pi}$ on $\mathbf{S}$.

The events are the following:

  * •

$\mathbf{E}_{1}$ : The weighted (multi-)set $(\mathbf{S},\boldsymbol{w})$ is a
weak $\varepsilon$-coreset for $(k,z)$-clustering $X$ in $\mathbbm{R}^{d}$.

  * •

$\mathbf{E}_{2}$ : The map
$\mathbf{\Pi}\colon\mathbf{S}\to\mathbf{S}^{\prime}$, given by restricting
$\mathbf{\Pi}$ is $(1+\varepsilon)$-bi-Lipschitz.

  * •

$\mathbf{E}_{3}(\beta)$ : We let $\mathbf{C}^{\prime}\subset\mathbbm{R}^{t}$
of size $k$ be the optimal centers for $(k,z)$-clustering $\mathbf{\Pi}(X)$ in
$\mathbbm{R}^{t}$. The weighted (multi-)set
$(\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w})$ satisfies

$\mathrm{cost}_{z}^{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),\mathbf{C}^{\prime})\leq\beta\cdot\mathrm{cost}_{z}^{z}(\mathbf{\Pi}(X),\mathbf{C}^{\prime}).$

######  Lemma 4.6.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, and suppose
$(\mathbf{S},\boldsymbol{w})$ and
$\mathbf{\Pi}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ satisfy events
$\mathbf{E}_{1},\mathbf{E}_{2}$ and $\mathbf{E}_{3}(\beta)$, then,

$\displaystyle\min_{\begin{subarray}{c}C^{\prime}\subset\mathbbm{R}^{t}\\\
|C^{\prime}|=k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),C^{\prime})\geq\dfrac{1}{\beta^{1/z}(1+\varepsilon)^{1+1/z}}\cdot\min_{\begin{subarray}{c}C\subset\mathbbm{R}^{d}\\\
|C|=k\end{subarray}}\mathrm{cost}_{z}(X,C).$

###### Proof.

Let $\mathbf{C}^{\prime}\subset\mathbbm{R}^{t}$ of size $k$ denote the centers
which give the optimal $(k,z)$-clustering of $\mathbf{\Pi}(X)$ in
$\mathbbm{R}^{t}$. Then, by $\mathbf{E}_{3}$,

$\displaystyle\mathrm{cost}_{z}^{z}(\mathbf{\Pi}(X),\mathbf{C}^{\prime})\geq(1/\beta)\cdot\mathrm{cost}_{z}^{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),\mathbf{C}^{\prime}).$

Now, we use Kirszbraun’s Theorem, and extend
$\mathbf{\Pi}^{-1}\colon\mathbbm{R}^{t}\to\mathbbm{R}^{d}$ in a
$(1+\varepsilon)$-Lipschitz manner. Hence,

$\mathrm{cost}_{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),\mathbf{C}^{\prime})\geq\dfrac{1}{1+\varepsilon}\cdot\mathrm{cost}_{z}((\mathbf{S},\boldsymbol{w}),\mathbf{\Pi}^{-1}(\mathbf{C}^{\prime}))\geq\dfrac{1}{1+\varepsilon}\cdot\min_{\begin{subarray}{c}C^{\prime\prime}\subset\mathbbm{R}^{d}\\\
|C^{\prime\prime}|=k\end{subarray}}\mathrm{cost}_{z}((\mathbf{S},\boldsymbol{w}),C^{\prime\prime}).$

Finally, using the fact that $(\mathbf{S},\boldsymbol{w})$ is an
$\varepsilon$-weak coreset, we may conclude that

$\mathrm{cost}_{z}^{z}((\mathbf{S},\boldsymbol{w}),C^{\prime\prime})\geq\dfrac{1}{1+\varepsilon}\cdot\mathrm{cost}_{z}^{z}(X,C^{\prime\prime}).$

∎

We now turn to showing that an appropriate setting of parameters implies that
the events occur often. For the first event, Theorem 5 from [HV20] implies
event $\mathbf{E}_{1}$ occurs with probability $1-o(1)$. We state the usual
guarantees of the Johnson-Lindenstrauss transform, which is what we need for
event $\mathbf{E}_{2}$ to hold.

######  Lemma 4.7.

Let $S\subset\mathbbm{R}^{d}$ be any set of $m$ points, and
$\mathcal{J}_{d,t}$ denote the Johnson-Lindenstrauss map, with

$t\gtrsim\dfrac{\log m}{\varepsilon^{2}}.$

Then, with probability $0.99$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, $\mathbf{\Pi}\colon S\to\mathbf{\Pi}(S)$
is $(1\pm\varepsilon)$-bi-Lipschitz, and hence, $\mathbf{E}_{2}$ occurs with
probability $0.99$.

####  4.3.1 A Bad Approximation Guarantee

######  Lemma 4.8 (Warm-Up Lemma).

Fix any $\Pi\in\mathcal{J}_{d,t}$ and let $C^{\prime}\subset\mathbbm{R}^{t}$
denote the optimal centers for $(k,z)$-clustering of $\Pi(X)$, then with
probability at least $0.99$ over the draw of $(\mathbf{S},\boldsymbol{w})$ as
per Definition 4.5,

$\displaystyle\sum_{x\in\mathbf{S}}\boldsymbol{w}(x)\cdot\min_{c\in
C^{\prime}}\|\Pi(x)-c\|_{2}^{z}\leq
100\cdot\mathrm{cost}_{z}^{z}(\Pi(x),C^{\prime}),$

with probability at least $0.99$. In other words, $\mathbf{E}_{3}(100)$ holds
with probability at least $0.99$.

###### Proof.

For any $x\in X$, let $c^{\prime}(x)\in C^{\prime}$ denote the point in
$C^{\prime}$ closest to $\Pi(x)$. Then, we note

$\displaystyle\sum_{x\in\mathbf{S}}\boldsymbol{w}(x)\cdot\|\Pi(x)-c^{\prime}(x)\|_{2}^{z}=\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mathbf{S}}\left[\frac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\|\Pi(\boldsymbol{x})-c^{\prime}(\boldsymbol{x})\|_{2}^{z}\right],$
(14)

so that in expectation over $\mathbf{S}$, we have

$\displaystyle\mathop{{\bf E}\/}_{\mathbf{S}}\left[\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mathbf{S}}\left[\frac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\|\Pi(\boldsymbol{x})-c^{\prime}(\boldsymbol{x})\|_{2}^{z}\right]\right]=\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\tilde{\sigma}}\left[\frac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\|\Pi(\boldsymbol{x})-c^{\prime}(\boldsymbol{x})\|_{2}^{z}\right]=\mathrm{cost}_{z}^{z}(\Pi(X),C^{\prime}).$

By Markov’s inequality, we obtain our desired bound. ∎

######  Corollary 4.9.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points,
and $C\subset\mathbbm{R}^{d}$ of size $k$ be centers for optimally
$(k,z)$-clustering $X$. For any $\varepsilon\in(0,1/2)$, let
$\mathcal{J}_{d,t}$ be the Johnson-Lindenstrauss map with

$t\gtrsim\dfrac{z\log(1/\varepsilon)+\log k}{\varepsilon^{2}},$

Then, with probability at least $0.97$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\displaystyle\dfrac{1}{100^{1/z}(1+\varepsilon)^{1+1/z}}\cdot\mathrm{cost}_{z}\left(X,C\right)\leq\min_{\begin{subarray}{c}C^{\prime}\subset\mathbbm{R}^{t}\\\
|C^{\prime}|=k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),C^{\prime}).$
(15)

###### Proof.

We sample $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ and
$(\mathbf{S},\boldsymbol{w})$ as per Definition 4.5. By Lemma 4.7, Lemma 4.8,
Theorem 5, and a union bound, we have events $\mathbf{E}_{1}$,
$\mathbf{E}_{2}$, and $\mathbf{E}_{3}(100)$ hold with probability at least
$0.97$. Hence, we obtain the desired result from applying Lemma 4.6. ∎

####  4.3.2 Improving the Approximation

In what follows, we will improve upon the approximation of Corollary 4.9
significantly, to show that with large probability,
$\mathbf{E}_{3}(1+\varepsilon)$ holds. We let
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ and denote
$C\subset\mathbbm{R}^{d}$ of size $k$ to be the optimal $(k,z)$-clustering of
$X$. As before, we let $c\colon X\to C$ map each $x\in X$ to the point center
in $C$, and $\sigma\colon X\to\mathbbm{R}_{\geq 0}$ be the sensitivities of
$X$ with respect to $C$ as in Lemma 4.4, and $\tilde{\sigma}$ be the
sensitivity sampling distribution.

We define one more event, $\mathbf{E}_{4}$, with respect to the randomness of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$. First, we let
$\mathbf{D}_{x}\in\mathbbm{R}_{\geq 0}$ denote the random variable given by

$\displaystyle\mathbf{D}_{x}\stackrel{{\scriptstyle\rm
def}}{{=}}\dfrac{\|\mathbf{\Pi}(x)-\mathbf{\Pi}(c(x))\|_{2}}{\|x-c(x)\|_{2}}.$
(16)

Notice that when $\mathbf{\Pi}$ consists of i.i.d $\mathcal{N}(0,1/t)$, then
$t\mathbf{D}_{x}^{2}$ is distributed as $\chi^{2}$-random variable with $t$
degrees of freedom. We say event $\mathbf{E}_{4}$ holds whenever

$\displaystyle\sum_{x\in X}\mathbf{D}_{x}^{2z}\cdot\sigma(x)\leq
100(k+1)2^{z}.$ (17)

######  Claim 4.10.

With probability at least $0.99$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, event $\mathbf{E}_{4}$ holds.

###### Proof.

The proof will simply follow from computing the expectation of the left-hand
side of (17), and applying Markov’s inequality. In particular, for every $x\in
X$, we can apply Lemma LABEL:lem:guassian-guarantee to conclude have

$\displaystyle\mathop{{\bf
E}\/}_{\mathbf{\Pi}\sim\mathcal{J}_{d,t}}\left[\mathbf{D}_{x}^{2z}\right]\leq
2^{z}.$

The remaining part follows from the bound on $\mathfrak{S}_{\sigma}$. ∎

######  Lemma 4.11.

Let $\Pi\in\mathcal{J}_{d,t}$ be a Johnson-Lindenstrauss map where, for
$\alpha>1$, the following events holds:

  1. 1.

Guarantee from Lemma 4.1: $\sum_{x\in
X}\|\Pi(x)-\Pi(c(x))\|_{2}^{z}\leq\alpha\cdot\mathrm{cost}_{z}^{z}(X,C)$.

  2. 2.

Guarantee from Corollary 4.9: letting $C^{\prime}\subset\mathbbm{R}^{t}$ be
the optimal $(k,z)$-clustering of $\Pi(X)$, then
$\mathrm{cost}_{z}^{z}(\Pi(X),C^{\prime})\geq(1/\alpha)\cdot\mathrm{cost}_{z}^{z}(X,C)$.

  3. 3.

Event $\mathbf{E}_{4}$ holds.

Then, if we let $(\mathbf{S},\boldsymbol{w})$ denote
$m=\mathrm{poly}(k,2^{z},1/\varepsilon,\alpha)$ i.i.d draws from
$\tilde{\sigma}$ and $\boldsymbol{w}(x)=1/(m\tilde{\sigma}(x))$, with
probability at least $0.99$,

$\mathrm{cost}_{z}^{z}((\Pi(\mathbf{S}),\boldsymbol{w}),C^{\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}^{z}(\Pi(X),C^{\prime}).$

###### Proof.

The proof follows the same schema as Lemma 4.8. However, we give a bound on
the variance of the estimator in order to improve upon the use of Markov’s
inequality. Specifically, we compute the variance of a rescaling of (14).

$\displaystyle\mathop{\operatorname{{\bf Var}}}_{\mathbf{S}}\left[\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mathbf{S}}\left[\frac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\dfrac{\|\Pi(\boldsymbol{x})-c^{\prime}(\boldsymbol{x})\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(X),C^{\prime})}\right]\right]\leq\frac{1}{m}\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\tilde{\sigma}}\left[\left(\frac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\dfrac{\|\Pi(\boldsymbol{x})-c^{\prime}(\boldsymbol{x})\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(X),C^{\prime})}\right)^{2}\right]$
$\displaystyle\qquad\qquad\qquad\qquad=\frac{\mathfrak{S}_{\sigma}}{m}\sum_{x\in
X}\left(\frac{1}{\sigma(x)}\cdot\dfrac{\|\Pi(x)-c^{\prime}(x)\|_{2}^{2z}}{\mathrm{cost}_{z}^{2z}(\Pi(X),C^{\prime})}\right).$
(18)

By the same argument as in the proof of Lemma 4.4 (applying the triangle
inequality twice),

$\displaystyle\dfrac{\|\Pi(x)-c^{\prime}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(X),C^{\prime})}$
$\displaystyle\leq
2^{z-1}\cdot\dfrac{\|\Pi(x)-\Pi(c(x))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(X),C^{\prime})}+\dfrac{2^{2(z-1)}}{|X_{c(x)}|}\left(\dfrac{\mathrm{cost}_{z}^{z}(\Pi(X),\Pi(C))}{\mathrm{cost}_{z}^{z}(\Pi(X),C^{\prime})}+1\right).$
(19)

Recall that we have the lower bound (2) and the upper bound (1). Hence, along
with the definition of $D_{x}$ in (16) (we remove the bold-face as $\Pi$ is
fixed), we upper bound the left-hand side of (19) by

$\displaystyle\alpha\cdot
2^{z-1}\cdot\dfrac{D_{x}^{z}\cdot\|x-c(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,C)}+\dfrac{2^{2(z-1)}}{|X_{c(x)}|}\left(\alpha^{2}+1\right)\leq\alpha^{2}\cdot
2^{100z}(D_{x}^{z}+1)\cdot\sigma(x).$

In particular, we may plug this in to (32) and use the definition of
$\sigma(x)$. Specifically, one obtains the variance in (32) is upper bounded
by

$\displaystyle\frac{\mathfrak{S}_{\sigma}\cdot\alpha^{4}\cdot
2^{200z}}{m}\sum_{x\in X}(D_{x}^{z}+1)^{2}\cdot\sigma(x)$
$\displaystyle\leq\frac{4\mathfrak{S}_{\sigma}^{2}\cdot\alpha^{4}\cdot
2^{200z}}{m}+\frac{4\mathfrak{S}_{\sigma}\cdot\alpha^{4}\cdot
2^{200z}}{m}\sum_{x\in X}D_{x}^{2z}\cdot\sigma(x)$
$\displaystyle\leq\frac{1000\mathfrak{S}_{\sigma}^{2}\cdot\alpha^{4}\cdot
2^{300z}}{m},$

where in the final inequality, we used the fact that $\mathbf{E}_{4}$ holds.
Hence, letting $m$ be a large enough polynomial in
$\mathrm{poly}(k,2^{z},1/\varepsilon,\alpha)$ implies the variance is smaller
than $o(\varepsilon^{2})$, so we can apply Chebyshev’s inequality. ∎

######  Corollary 4.12.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ by any set of points,
and $C\subset\mathbbm{R}^{d}$ of size $k$ be centers for optimally
$(k,z)$-clustering $X$. For any $\varepsilon\in(0,1/2)$, let
$\mathcal{J}_{d,t}$ be the Johnson-Lindenstrauss map with

$t\gtrsim\frac{z\log(1/\varepsilon)+\log k}{\varepsilon^{2}}.$

Then, with probability at least $0.92$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\dfrac{1}{(1+\varepsilon)^{1+2/z}}\cdot\mathrm{cost}_{z}(X,C)\leq\min_{\begin{subarray}{c}C^{\prime}\subset\mathbbm{R}^{t}\\\
|C^{\prime}|\leq
k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),C^{\prime}).$

###### Proof.

We sample $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ and
$(\mathbf{S},\boldsymbol{w})$ as per Definition 4.5. Note that by Theorem 5
and the setting of $m$, event $\mathbf{E}_{1}$ holds with probability at least
$0.99$ over the draw of $(\mathbf{S},\boldsymbol{w})$. By Lemma 4.1, Corollary
4.9, and Claim 4.10, and the setting of $m$ and $t$, the conditions (1), (2)
and (3) of Lemma 4.11 hold with probability at least $0.95$, with $\alpha$
being set to a large enough constant, and hence event
$\mathbf{E}_{3}(1+\varepsilon)$ holds with probability at least $0.94$.
Finally, event $\mathbf{E}_{2}$ holds with probability $0.99$ by Lemma 4.7,
and taking a union bound and Lemma 4.6 gives the desired bound. ∎

##  5 Subspace Approximation

In the $(k,z)$-_subspace approximation_ problem, we consider a subspace
$R\subset\mathbbm{R}^{d}$ of dimension less than $k$, which we may encode by a
collection of at most $k$ orthonormal vectors $r_{1},\dots,r_{k}\in R$. We let
$\rho_{R}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{d}$ denote the map which sends
each vector $x\in\mathbbm{R}^{d}$ to its closest point in $R$, and note that

$\displaystyle\rho_{R}(x)$ $\displaystyle=\mathop{\mathrm{argmin}}_{z\in
R}\|x-z\|_{2}^{2}=\sum_{i=1}^{k}\langle x,r_{i}\rangle\cdot
r_{i}\in\mathbbm{R}^{d},$

For any subset $X\subset\mathbbm{R}^{d}$ and any $k$-dimensional subspace $R$,
we let

$\mathrm{cost}_{z}^{z}(X,R)=\sum_{x\in
X}\left\|x-\rho_{R}(x)\right\|_{2}^{z}.$

In this section, we will show that we may compute the optimum $k$-subspace
approximation after applying a Johnson-Lindenstrauss transform.

######  Theorem 7 (Johnson-Lindenstrauss for $k$-Subspace Approximation).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points,
and let $R$ denote the optimal $(k,z)$-subspace approximation of $X$. For any
$\varepsilon\in(0,1)$, suppose we let $\mathcal{J}_{d,t}$ be the distribution
over Johnson-Lindenstrauss maps where

$t\gtrsim\dfrac{z\cdot
k^{2}\cdot\mathrm{polylog}(k/\varepsilon)}{\varepsilon^{3}}.$

Then, with probability at least $0.9$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\displaystyle\dfrac{1}{1+\varepsilon}\cdot\mathrm{cost}_{z}(X,R)\leq\min_{\begin{subarray}{c}R^{\prime}\subset\mathbbm{R}^{t}\\\
\dim R^{\prime}\leq
k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),R^{\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}(X,R).$

The proof of the above theorem proceeds in two steps, and models the argument
in the previous section. First, we show that the cost of the optimum does not
increase substantially (the right-most inequality in the theorem). This is
done in the next subsection. The second step is showing that the optimum does
not decrease substantially (the left-most inequality in the theorem). The
second step is done in the subsequent subsection.

###  5.1 Easy Direction: Optimum Cost Does Not Increase

The first direction, which shows that the optimal $(k,z)$-subspace
approximation does not increase follows similarly to Lemma 4.1.

######  Lemma 5.1.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ by any set of points and
let $R\subset\mathbbm{R}^{d}$ be optimal $(k,z)$-subspace approximation of
$X$. For any $\varepsilon\in(0,1)$, we let $\mathcal{J}_{d,t}$ be the
distribution over Johnson-Lindenstrauss maps. If $t\gtrsim z/\varepsilon^{2}$,
then with probability at least $0.99$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\sum_{x\in
X}\|\mathbf{\Pi}(x)-\mathbf{\Pi}(\rho_{R}(x))\|_{2}^{z}\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}(X,R),$

and hence,

$\min_{\begin{subarray}{c}R^{\prime}\subset\mathbbm{R}^{t}\\\ \dim
R^{\prime}\leq
k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),R^{\prime})\leq(1+\varepsilon)\min_{\begin{subarray}{c}R\subset\mathbbm{R}^{d}\\\
\dim R\leq k\end{subarray}}\mathrm{cost}_{z}(X,R).$

###### Proof.

Note that $\mathbf{\Pi}$ is a linear map, so if we let $r_{1},\dots,r_{k}\in
R$ denote $k$ orthonormal unit vectors spanning $R$, then
$\mathbf{\Pi}(r_{1}),\dots,\mathbf{\Pi}(r_{k})\in\mathbbm{R}^{t}$ are $k$
vectors spanning the subspace $\mathbf{\Pi}(R)$. Furthermore, we may consider
the $k$-dimensional subspace

$\mathbf{\Pi}(R)\stackrel{{\scriptstyle\rm
def}}{{=}}\left\\{\sum_{i=1}^{k}\alpha_{i}\cdot\mathbf{\Pi}(r_{i})\in\mathbbm{R}^{t}:\alpha_{1},\dots,\alpha_{k}\in\mathbbm{R}\right\\}.$

Notice that for any $x\in\mathbbm{R}^{d}$, by linearity of $\mathbf{\Pi}$,

$\displaystyle\mathbf{\Pi}(\rho_{R}(x))$ $\displaystyle=\sum_{i=1}^{k}\langle
x-\tau,r_{i}\rangle\cdot\mathbf{\Pi}(r_{i})\in\mathbf{\Pi}(F),$

which means that we may always upper bound

$\displaystyle\min_{\begin{subarray}{c}R^{\prime}\subset\mathbbm{R}^{t}\\\
\dim R^{\prime}\leq
k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),R^{\prime})$
$\displaystyle\leq\left(\sum_{x\in
X}\left\|\mathbf{\Pi}(x)-\mathbf{\Pi}(\rho_{R}(x))\right\|_{2}^{z}\right)^{1/z}.$
(20)

It hence remains to upper bound the left-hand side of (20). We now use the
fact that $\mathbf{\Pi}$ is drawn from a Johnson-Lindenstrauss distribution.
Specifically, the lemma follows from applying Markov’s inequality once we show

$\dfrac{1}{\mathrm{cost}_{z}^{z}(X,F)}\mathop{{\bf
E}\/}_{\mathbf{\Pi}\sim\mathcal{J}_{d,t}}\left[\sum_{x\in
X}\left(\|\mathbf{\Pi}(x)-\mathbf{\Pi}(\rho_{F}(x))\|_{2}^{z}-\|x-\rho_{F}(x)\|_{2}^{z}\right)^{+}\right]\leq\dfrac{(1+\varepsilon)^{z}-1}{100},$

which follows from Lemma 3.1. ∎

###  5.2 Hard Direction: Optimum Cost Does Not Decrease

####  5.2.1 Preliminaries

In the $(k,z)$-subspace approximation problem, there will be a difference
between complexities of known strong coresets and weak coresets. Our argument
will only use weak coresets, which is important for us, as strong coresets
have a dependence on $d$ (which we are trying to avoid).

######  Definition 5.2 (Weak Coresets for $(k,z)$-subspace approximation).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be a set of points. A
weak $\varepsilon$-coreset of $X$ for $(k,z)$-subspace approximation is a
weighted subset $S\subset\mathbbm{R}^{d}$ of points with weights $w\colon
S\to\mathbbm{R}_{\geq 0}$ such that,

$\frac{1}{1+\varepsilon}\cdot\min_{\begin{subarray}{c}R\subset\mathbbm{R}^{d}\\\
\dim R\leq
k\end{subarray}}\mathrm{cost}_{z}(X,R)\leq\min_{\begin{subarray}{c}R\subset\mathbbm{R}^{d}\\\
\dim R\leq
k\end{subarray}}\mathrm{cost}_{z}((S,w),R)\leq(1+\varepsilon)\cdot\min_{\begin{subarray}{c}R\subset\mathbbm{R}^{d}\\\
\dim R\leq k\end{subarray}}\mathrm{cost}_{z}(X,R).$

Similarly to the case of $(k,z)$-clustering, algorithms for building weak
coresets proceed by sampling according to the sensitivity framework. We
proceed by defining sensitivity functions in the context of subspace
approximation, and then state a lemma which gives a sensitivity function that
we will use.

######  Definition 5.3 (Sensitivities).

Let $n,d\in\mathbbm{N}$, and consider any set of points
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, as well as
$k\in\mathbbm{N}$ and $z\geq 1$. A sensitivity function $\sigma\colon
X\to\mathbbm{R}_{\geq 0}$ for $(k,z)$-subspace approximation in
$\mathbbm{R}^{d}$ is a function satisfying that, for all $x\in X$,

$\displaystyle\sup_{\begin{subarray}{c}R\subset\mathbbm{R}^{d}\\\ \dim R\leq
k\end{subarray}}\dfrac{\|x-\rho_{R}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,R)}\leq\sigma(x).$

The total sensitivity of the sensitivity function $\sigma$ is given by

$\mathfrak{S}_{\sigma}=\sum_{x\in X}\sigma(x).$

For a sensitivity function, we let $\tilde{\sigma}$ denote the sensitivity
sampling distribution, supported on $X$, which samples $x\in X$ with
probability proportional to $\sigma(x)$.

We now state a specific sensitivity function that we will use. The proof will
closely follow a method for bounding the total sensitivity of [VX12b]. The
resulting weak $\varepsilon$-coreset will have a worse dependence than the
best-known coresets for this problem; however, the specific form of the
sensitivity function will be especially useful for us. Specifically, the non-
optimality of the sensitivity function will not significantly affect the final
bound on dimension reduction.

######  Lemma 5.4 (Theorem 18 of [VX12b]).

Let $n,d\in\mathbbm{N}$, and consider any set of points
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, as well as
$k\in\mathbbm{N}$ with $k<d$, and $z\geq 1$. Suppose $R\subset\mathbbm{R}^{d}$
is the optimal $(k,z)$-subspace approximation of $X$ in $\mathbbm{R}^{d}$.
Then, the function $\sigma\colon X\to\mathbbm{R}_{\geq 0}$ given by

$\displaystyle\sigma(x)=2^{z-1}\cdot\dfrac{\|x-\rho_{R}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,R)}+2^{2z-1}\cdot\sup_{u\in\mathbbm{R}^{d}}\dfrac{|\langle\rho_{R}(x),u\rangle|^{z}}{\sum_{x^{\prime}\in
X}|\langle\rho_{R}(x^{\prime}),u\rangle|^{z}}$

is a sensitivity function for $(k,z)$-subspace approximation of $X$ in
$\mathbbm{R}^{d}$, satisfying

$\mathfrak{S}_{\sigma}\leq 2^{z-1}+2^{2z-1}(k+1)^{1+z}.$

###### Proof.

Consider any subspace $R^{\prime}\subset\mathbbm{R}^{d}$ of dimension at most
$k$. Then, for any $x\in X$

$\displaystyle\|x-\rho_{R^{\prime}}(x)\|_{2}^{z}\leq\|x-\rho_{R^{\prime}}(\rho_{R}(x))\|_{2}^{z}\leq
2^{z-1}\left(\|x-\rho_{R}(x)\|_{2}^{z}+\|\rho_{R}(x)-\rho_{R^{\prime}}(\rho_{R}(x))\|_{2}^{z}\right)$
$\displaystyle\qquad\leq
2^{z-1}\left(\dfrac{\|x-\rho_{R}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,R)}\cdot\mathrm{cost}_{z}^{z}(X,R)+\dfrac{\|\rho_{R}(x)-\rho_{R^{\prime}}(\rho_{R}(x))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\rho_{R}(X),R^{\prime})}\cdot\mathrm{cost}_{z}^{z}(\rho_{R}(X),R^{\prime})\right).$
(21)

Notice that $\mathrm{cost}_{z}^{z}(\rho_{R}(X),R^{\prime})\leq
2^{z-1}(\mathrm{cost}_{z}^{z}(X,R)+\mathrm{cost}_{z}^{z}(X,R^{\prime}))$ by
the triangle inequality and Hölder’s inequality, and that
$\mathrm{cost}_{z}^{z}(X,R)\leq\mathrm{cost}_{z}^{z}(X,R^{\prime})$ since $R$
is the optimal $(k,z)$-subspace approximation. Hence, dividing the left- and
right-hand side of (21) we have

$\displaystyle\dfrac{\|x-\rho_{R^{\prime}}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,R^{\prime})}\leq
2^{z-1}\cdot\dfrac{\|x-\rho_{R}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,R)}+2^{2z-1}\cdot\dfrac{\|\rho_{R}(x)-\rho_{R^{\prime}}(\rho_{R}(x))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\rho_{R}(X),R^{\prime})}.$

It remains to show that, for any set of points $Y\subset\mathbbm{R}^{d}$ (in
particular, the set $\\{\rho_{R}(x):x\in X\\}$), and any $y\in Y$,

$\displaystyle\sup_{\begin{subarray}{c}R^{\prime}\subset\mathbbm{R}^{d}\\\
\dim R^{\prime}\leq
k\end{subarray}}\dfrac{\|y-\rho_{R^{\prime}}(y)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(Y,R^{\prime})}\leq\sup_{\begin{subarray}{c}H\subset\mathbbm{R}^{d}\\\
\dim
H=d-1\end{subarray}}\dfrac{\|y-\rho_{H}(y)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(Y,H)}=\sup_{u\in\mathbbm{R}^{d}}\dfrac{|\langle
y,u\rangle|^{z}}{\sum_{y^{\prime}\in Y}|\langle y^{\prime},u\rangle|^{z}}.$

In particular, note that for any subspace $R^{\prime}\subset\mathbbm{R}^{d}$
of dimension at most $k$, there exists a $(d-1)$-dimensional subspace
$H\subset\mathbbm{R}^{d}$ containing $R^{\prime}$ given by all vectors
orthogonal to $y-\rho_{R^{\prime}}(y)$. In particular,
$\mathrm{cost}_{z}^{z}(Y,H)\leq\mathrm{cost}_{z}^{z}(Y,R^{\prime})$ since
$R^{\prime}$ is contained in $H$, and
$\|y-\rho_{H}(y)\|_{2}=\|y-\rho_{R^{\prime}}(y)\|_{2}$ by the definition of
$H$. The bound on the total sensitivity then follows from Lemma 16 in [VX12b],
where we use the fact that $\\{\rho_{R}(x):x\in X\\}$ lies in a
$k$-dimensional subspace. ∎

We will use the following geometric theorem of [SV12] in our proof. The
theorem says that an approximately optimal $(k,z)$-subspace approximation lies
in the span of a small set of points. We state the lemma for weighted point
sets, even though [SV12] state it for unweighted points. We note that adding
weights can be simulated by replicating points.

######  Lemma 5.5 (Theorem 3.1 [SV12]).

Let $d,k\in\mathbbm{N}$, and consider a weighted set of points
$S\subset\mathbbm{R}^{d}$ with weights $w\colon S\to\mathbbm{R}_{\geq 0}$, as
well as $\varepsilon\in(0,1)$ and $z\geq 1$. There exists a subset $Q\subset
S$ of $O(k^{2}\log(k/\varepsilon)/\varepsilon)$ and a $k$-dimensional subspace
$R^{\prime}\subset\mathbbm{R}^{d}$ within the span of $Q$ satisfying

$\mathrm{cost}_{z}((S,w),R^{\prime})\leq(1+\varepsilon)\min_{\begin{subarray}{c}R\subset\mathbbm{R}^{d}\\\
\dim R\leq k\end{subarray}}\mathrm{cost}_{z}((S,w),R).$

Lemma 5.4 gives us an appropriate sensitivity function, and Lemma 5.5 limits
the search of the subspace to just a small set of points. Similarly to the
case of $(k,z)$-clustering, we can use this to construct weak
$\varepsilon$-coresets for $(k,z)$-subspace approximation. The following
theorem is Theorem 5.10 from [HV20]. We state the theorem with the sensitivity
function of Lemma 5.4.

######  Theorem 8 (Theorem 5.10 from [HV20]).

For any subset $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ and
$\varepsilon\in(0,1/2)$, let $\tilde{\sigma}$ denote the sensitivity sampling
distribution from the sensitivity function of Lemma 5.4.

  * •

Let $(\mathbf{S},\boldsymbol{w})$ denote the random (multi-)set
$\mathbf{S}\subset X$ and $\boldsymbol{w}\colon\mathbf{S}\to\mathbbm{R}_{\geq
0}$ given by, for

$m=\mathrm{poly}((k+1)^{z},1/\varepsilon)$

iterations, sampling $\boldsymbol{x}\sim\tilde{\sigma}$ i.i.d and letting
$\boldsymbol{w}(\boldsymbol{x})=1/(m\tilde{\sigma}(x))$.

  * •

Then, with probability $1-o(1)$ over the draw of
$(\mathbf{S},\boldsymbol{w})$, it is an $\varepsilon$-weak coreset for
$(k,z)$-subspace approximation of $X$.

###  5.3 The Important Events

Similarly to the previous section, we define the important events, over the
randomness in $\mathbf{\Pi}$ such that, if these are satisfied, then the
optimum of $(k,z)$-subspace approximation after dimension reduction does not
decrease substantially. We first define the events, and then we prove that if
the events are all satisfied, then we obtain our desired approximation.

######  Definition 5.6 (The Events).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, and $\tilde{\sigma}$
the sensitivity sampling distribution of $X$ from Lemma 5.4. We consider the
following experiment,

  1. 1.

We generate a sample $(\mathbf{S},\boldsymbol{w})$ by sampling from
$\tilde{\sigma}$ for $m=\mathrm{poly}(k^{z},1/\varepsilon)$ i.i.d iterations
$\boldsymbol{x}\sim\tilde{\sigma}$ and set
$\boldsymbol{w}(\boldsymbol{x})=1/(m\tilde{\sigma}(\boldsymbol{x}))$.

  2. 2.

Furthermore, we sample $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, which is a
Johnson-Lindenstrauss map $\mathbbm{R}^{d}\to\mathbbm{R}^{t}$.

  3. 3.

We let $\mathbf{S}^{\prime}=\mathbf{\Pi}(\mathbf{S})\subset\mathbbm{R}^{t}$
denote the image of $\mathbf{\Pi}$ on $\mathbf{S}$.

The events are the following:

  * •

$\mathbf{E}_{1}$ : The weighted (multi-)set $(\mathbf{S},\boldsymbol{w})$ is a
weak $\varepsilon$-coreset for $(k,z)$-subspace approximation of $X$ in
$\mathbbm{R}^{d}$.

  * •

$\mathbf{E}_{2}$ : The map
$\mathbf{\Pi}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ satisfies the following
condition. For any choice of $O(k^{2}\log(k/\varepsilon)/\varepsilon)$ points
of $\mathbf{S}$, $\mathbf{\Pi}$ is an $\varepsilon$-subspace embedding of the
subspace spanned by these points.

  * •

$\mathbf{E}_{3}(\beta)$ : Let $\mathbf{R}^{\prime}\subset\mathbbm{R}^{t}$
denote the $k$-dimensional subspace for optimal $(k,z)$-subspace approximation
of $\mathbf{\Pi}(X)$ in $\mathbbm{R}^{t}$. Then,

$\mathrm{cost}_{z}^{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),\mathbf{R}^{\prime})\leq\beta\cdot\mathrm{cost}_{z}^{z}(\mathbf{\Pi}(X),\mathbf{R}^{\prime}).$

######  Lemma 5.7.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, and suppose
$(\mathbf{S},\boldsymbol{w})$ and
$\mathbf{\Pi}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ satisfy events
$\mathbf{E}_{1}$, $\mathbf{E}_{2}$, and $\mathbf{E}_{3}(\beta)$. Then,

$\min_{\begin{subarray}{c}R^{\prime}\subset\mathbbm{R}^{t}\\\ \dim
R^{\prime}\leq
k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),R^{\prime})\geq\dfrac{1}{\beta^{1/z}(1+\varepsilon)^{3}}\cdot\min_{\begin{subarray}{c}R\subset\mathbbm{R}^{d}\\\
\dim R\leq k\end{subarray}}\mathrm{cost}_{z}(X,R).$

###### Proof.

Consider a fixed $\mathbf{\Pi}$ and $(\mathbf{S},\boldsymbol{w})$ satisfying
the three events of Definition 5.6. Let
$\mathbf{R}^{\prime}\subset\mathbbm{R}^{t}$ be the $k$-dimensional subspace
which minimizes $\mathrm{cost}_{z}^{z}(\mathbf{\Pi}(X),\mathbf{R}^{\prime})$.
Then, by event $\mathbf{E}_{3}(\beta)$, we have
$\mathrm{cost}_{z}^{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),\mathbf{R}^{\prime})\leq\beta\cdot\mathrm{cost}_{z}^{z}(\mathbf{\Pi}(X),\mathbf{R}^{\prime})$.
Now, we apply Lemma 5.5 to $(\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w})$, and we
obtain a subset $Q\subset\mathbf{S}$ of size
$O(k^{2}\log(k/\varepsilon)/\varepsilon)$ for which there exists a
$k$-dimensional subspace $R^{\prime\prime}\subset\mathbbm{R}^{t}$ within the
span of $\mathbf{\Pi}(Q)$ which satisfies

$\left(\sum_{x\in\mathbf{S}}\boldsymbol{w}(x)\cdot\|\mathbf{\Pi}(x)-\rho_{R^{\prime\prime}}(\mathbf{\Pi}(x))\|_{2}^{z}\right)^{1/z}=\mathrm{cost}_{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),R^{\prime\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),\mathbf{R}^{\prime}).$

Note that $R^{\prime\prime}$ is a $k$-dimensional subspace lying in the span
of $\mathbf{\Pi}(Q)$. For any $x\in\mathbf{S}$, we will use the fact that
$\mathbf{E}_{2}$ is satisfied to say that $\mathbf{\Pi}$ is an
$\varepsilon$-subspace embedding of the subspace spanned by $Q\cup\\{x\\}$.
This will enable us to find a subspace $U\subset\mathbbm{R}^{d}$ of dimension
$k$ whose cost of approximating $(\mathbf{S},\boldsymbol{w})$ is at most
$(1+\varepsilon)\cdot\mathrm{cost}_{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),R^{\prime\prime})$.

Specifically, we write $v_{1},\dots,v_{k}\in\mathbbm{R}^{t}$, as orthogonal
unit vectors which span $R^{\prime\prime}$. Because $R^{\prime\prime}$ lies in
the span of $\mathbf{\Pi}(Q)$, there are vectors
$u_{1},\dots,u_{k}\in\mathbbm{R}^{d}$ in the span of $Q$ which satisfy

$v_{\ell}=\mathbf{\Pi}(u_{\ell})\in\mathbbm{R}^{t}\qquad\text{for}\qquad
u_{\ell}=\sum_{y\in Q}c_{\ell,y}y\in\mathbbm{R}^{d}.$

Hence, the subspace $U$ given by the span of all vectors in $U$ is a
$k$-dimensional subspace lying in the span of $Q$. For $x\in\mathbf{S}$, we
may write the coefficients
$\gamma_{\ell}(x)=\langle\mathbf{\Pi}(x),v_{\ell}\rangle$, and we may express
projection $\rho_{R^{\prime\prime}}(\mathbf{\Pi}(x))\in\mathbbm{R}^{t}$ as

$\rho_{R^{\prime\prime}}(\mathbf{\Pi}(x))=\sum_{\ell=1}^{k}\gamma_{\ell}(x)\cdot
v_{\ell}=\mathbf{\Pi}\left(\sum_{y\in
Q}\left(\sum_{\ell=1}^{k}\gamma_{\ell}(x)c_{\ell,y}\right)\cdot
y\right)=\mathbf{\Pi}\left(\sum_{\ell=1}^{k}\gamma_{\ell}(x)u_{\ell}\right).$

which is a linear combination of $Q$. By event $\mathbf{E}_{2}$,
$\mathbf{\Pi}$ is an $\varepsilon$-subspace embedding of the subspace spanned
by $Q\cup\\{x\\}$, so

$\|x-\rho_{U}(x)\|_{2}\leq\left\|x-\sum_{\ell=1}^{k}\gamma_{\ell}(x)u_{\ell}\right\|_{2}\leq(1+\varepsilon)\|\mathbf{\Pi}(x)-\rho_{R^{\prime\prime}}(\mathbf{\Pi}(x))\|_{2}.$

Combining the inequalities, we have

$\mathrm{cost}_{z}\left((\mathbf{S},\boldsymbol{w}),U\right)\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}\left((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),R^{\prime\prime}\right),$

and finally, since $(\mathbf{S},\boldsymbol{w})$ is a $\varepsilon$-weak
coreset, we obtain the desired inequality. ∎

We note that event $\mathbf{E}_{1}$ will be satisfied with sufficiently high
probability from Theorem 8. Furthermore, event $\mathbf{E}_{2}$ is satisfied
with sufficiently high probability from the following simple lemma. All that
will remain is showing that event $\mathbf{E}_{3}(\beta)$ is satisfied.

######  Lemma 5.8.

Let $S\subset\mathbbm{R}^{d}$ be any set of $m$ points and
$\ell\in\mathbbm{N}$, and let $\mathcal{J}_{d,t}$ denote the Johnson-
Lindenstrauss map, with

$t\gtrsim\dfrac{\ell\log m}{\varepsilon^{2}}.$

Then, with probability $0.99$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, $\mathbf{\Pi}$ is an
$\varepsilon$-subspace embedding for all subspaces spanned by $\ell$ vectors
of $S$.

###### Proof.

There are at most $\binom{m}{\ell}$ subspaces spanned by $\ell$ vectors of
$S$. If $\mathbf{\Pi}$ is a subspace embedding for all of them, we obtain our
desired conclusion. We use Lemma 3.3 with $\delta$ to be a sufficiently small
constant factor of $1/m^{\ell}$ and union bound. ∎

####  5.3.1 A Bad Approximation Guarantee

######  Lemma 5.9 (Warm-Up Lemma).

Fix any $\Pi\in\mathcal{J}_{d,t}$ and let $R^{\prime}\subset\mathbbm{R}^{t}$
denote the $k$-dimensional subspace for optimal $(k,z)$-subspace approximation
of $\Pi(X)$ in $\mathbbm{R}^{t}$. Then, with probability at least $0.99$ over
the draw of $(\mathbf{S},\boldsymbol{w})$ as per Definition 5.6,

$\displaystyle\sum_{x\in\mathbf{S}}\boldsymbol{w}(x)\cdot\|\Pi(x)-\rho_{R^{\prime}}(\Pi(x))\|_{2}^{z}\leq
100\cdot\mathrm{cost}_{z}^{z}(\Pi(X),R^{\prime}).$

In other words, event $\mathbf{E}_{3}(100)$ holds with probability at least
$0.99$.

###### Proof.

Similarly to the proof of Lemma 4.8, we compute the expectation of the left-
hand side of the inequality and use Markov’s inequality.

$\displaystyle\mathop{{\bf E}\/}_{\mathbf{S}}\left[\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mathbf{S}}\left[\frac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\|\Pi(x)-\rho_{R^{\prime}}(\Pi(x))\|_{2}^{z}\right]\right]$
$\displaystyle=\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\tilde{\sigma}}\left[\frac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\|\Pi(x)-\rho_{R^{\prime}}(\Pi(x))\|_{2}^{z}\right]=\mathrm{cost}_{z}^{z}(\Pi(X),R^{\prime}).$
(22)

∎

######  Corollary 5.10.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points.
For any $\varepsilon\in(0,1/2)$, let $\mathcal{J}_{d,t}$ be the Johnson-
Lindenstrauss map with

$t\gtrsim\dfrac{z\cdot
k^{2}\cdot\mathrm{polylog}(k/\varepsilon)}{\varepsilon^{3}}.$

Then, with probability at least $0.97$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\displaystyle\dfrac{1}{100^{1/z}(1+\varepsilon)^{3}}\cdot\mathrm{cost}_{z}(X,R)\leq\min_{\begin{subarray}{c}R^{\prime}\subset\mathbbm{R}^{t}\\\
\dim R^{\prime}\leq
k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),R^{\prime}).$

###### Proof.

We sample $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ and
$(\mathbf{S},\boldsymbol{w})$ as per Definition 5.6. By Theorem 8 and Lemma
5.9, and a union bound, events $\mathbf{E}_{1}$ and $\mathbf{E}_{3}(100)$ hold
with probability at least $0.98$. Event $\mathbf{E}_{2}$ occurs with
probability at least $0.99$ by apply Lemma 5.8 with
$m=\mathrm{poly}(k^{z},1/\varepsilon)$ and
$\ell=O(k^{2}\log(k/\varepsilon)/\varepsilon)$. Hence, we apply Lemma 5.7. ∎

####  5.3.2 Improving the Approximation

We now improve on the approximation of Corollary 5.10 in a fashion similar to
that of Subsection 4.3.2. We will show that with large probability,
$\mathbf{E}_{3}(1+\varepsilon)$ holds. We let
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ and
$R\subset\mathbbm{R}^{d}$ be the subspace of dimension $k$ for optimal
$(k,z)$-subspace approximation of $X$ in $\mathbbm{R}^{d}$. As before, we let
$\sigma\colon X\to\mathbbm{R}_{\geq 0}$ be the sensitivities of $X$ with
respect to $R$ (as in Lemma 5.4), and $\tilde{\sigma}$ be the sensitivity
sampling distribution.

We define one more events, $\mathbf{E}_{4}$ with respect to the randomness in
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$. Let $\mathbf{D}_{x}\in\mathbbm{R}_{\geq
0}$ denote the random variable given by

$\displaystyle\mathbf{D}_{x}\stackrel{{\scriptstyle\rm
def}}{{=}}\dfrac{\|\mathbf{\Pi}(x)-\mathbf{\Pi}(\rho_{R}(x))\|_{2}}{\|x-\rho_{R}(x)\|_{2}}.$
(23)

We say event $\mathbf{E}_{4}$ holds whenever

$\displaystyle\sum_{x\in X}\mathbf{D}_{x}^{2z}\cdot\sigma(x)\leq 100\cdot
2^{z}\cdot\mathfrak{S}_{\sigma},$ (24)

which holds with probability at least $0.99$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, similarly to the proof of Claim 4.10 and
Lemma 5.4.

######  Lemma 5.11.

Let $\Pi\in\mathcal{J}_{d,t}$ be a Johnson-Lindenstrauss map where, for
$\alpha>1$, the follows events hold:

  1. 1.

Guarantee from Lemma 5.1: $\sum_{x\in
X}\|\Pi(x)-\Pi(\rho_{R}(x))\|_{2}^{z}\leq\alpha\cdot\mathrm{cost}_{z}^{z}(X,R)$.

  2. 2.

Guarantee from Corollary 5.10: letting $R^{\prime}\subset\mathbbm{R}^{t}$ be
the optimal $(k,z)$-subspace approximation of $\Pi(X)$, then
$\mathrm{cost}_{z}^{z}(X,R)\leq\alpha\mathrm{cost}_{z}^{z}(\Pi(X),R^{\prime})$.

  3. 3.

Event $\mathbf{E}_{4}$ holds.

Then, if we let $(\mathbf{S},\boldsymbol{w})$ denote
$m=\mathrm{poly}(k^{z},1/\varepsilon,\alpha)$ i.i.d draws from
$\tilde{\sigma}$ and $\boldsymbol{w}(x)=1/(m\tilde{\sigma}(x))$, with
probability at least $0.99$,

$\mathrm{cost}_{z}^{z}((\Pi(\mathbf{S}),\boldsymbol{w}),R^{\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}^{z}(\Pi(X),R^{\prime}).$

###### Proof.

Again, the proof is similar to that of Lemma 4.11, where we bound the variance
of the estimator to apply Chebyshev’s inequality. In particular, we have

$\displaystyle\mathop{\operatorname{{\bf Var}}}_{\mathbf{S}}\left[\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mathbf{S}}\left[\dfrac{1}{\tilde{\sigma}(\boldsymbol{x})}\cdot\dfrac{\|\Pi(\boldsymbol{x})-\rho_{R^{\prime}}(\Pi(\boldsymbol{x}))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(X),R^{\prime})}\right]\right]\leq\frac{\mathfrak{S}_{\sigma}}{m}\sum_{x\in
X}\left(\frac{1}{\sigma(x)}\cdot\dfrac{\|\Pi(x)-\rho_{R^{\prime}}(\Pi(x))\|_{2}^{2z}}{\mathrm{cost}_{z}^{2z}(\Pi(X),R^{\prime})}\right).$
(25)

Similarly to the proof of Lemma 4.11, we will upper bound

$\displaystyle\dfrac{\|\Pi(x)-\rho_{R^{\prime}}(\Pi(x))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(X),R)}$

as a function of $\sigma(x)$ and $D_{x}$ (given by (23) without boldface as
$\Pi$ is fixed). Toward this bound, we simplify the notation by letting
$y_{x}=\rho_{R}(x)\in\mathbbm{R}^{d}$ and $Y=\\{y_{x}:x\in X\\}$. Then, since
$\Pi\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ is a linear map, for any $x\in X$

$\displaystyle\sup_{v\in\mathbbm{R}^{t}}\dfrac{|\langle\Pi(y_{x}),v\rangle|^{z}}{\sum_{x^{\prime}\in
X}|\langle\Pi(y_{x^{\prime}}),v\rangle|^{z}}\leq\sup_{u\in\mathbbm{R}^{d}}\dfrac{|\langle
y_{x},u\rangle|^{z}}{\sum_{x^{\prime}\in X}|\langle
y_{x^{\prime}},u\rangle|^{z}}.$ (26)

In particular, if we let $M\in\mathbbm{R}^{n\times d}$ be the matrix given by
having the rows be points $y_{x}\in Y$, then writing
$\Pi\in\mathbbm{R}^{d\times t}$, we have $M\Pi\in\mathbbm{R}^{n\times t}$ is
the matrix whose rows are $\Pi(y_{x})$; in particular, one may compare the
left- and right-hand sides of (26) by letting $u=\Pi v\in\mathbbm{R}^{d}$.
Thus, we have

$\displaystyle\|\Pi(x)-\rho_{R^{\prime}}(\Pi(x))\|_{2}^{z}\leq\|\Pi(x)-\rho_{R^{\prime}}(\Pi(y_{x}))\|_{2}^{z}\leq
2^{z-1}\left(\|\Pi(x)-\Pi(y_{x})\|_{2}^{z}+\|\Pi(y_{x})-\rho_{R^{\prime}}(\Pi(y_{x}))\|_{2}^{z}\right)$
$\displaystyle\qquad\leq
2^{z-1}\left(D_{x}^{z}\cdot\dfrac{\|x-y_{x}\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,R)}\cdot\mathrm{cost}_{z}^{z}(X,R)+\dfrac{\|\Pi(y_{x})-\rho_{R^{\prime}}(\Pi(y_{x}))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(Y),R^{\prime})}\cdot\mathrm{cost}_{z}^{z}(\Pi(Y),R^{\prime})\right).$
(27)

We may now apply the triangle inequality, as well as (1) and (2), and we have

$\displaystyle\mathrm{cost}_{z}^{z}(\Pi(Y),R^{\prime})$ $\displaystyle\leq
2^{z-1}\left(\mathrm{cost}_{z}^{z}(\Pi(X),R^{\prime})+\sum_{x\in
X}\|\Pi(x)-\Pi(y_{x})\|_{2}^{z}\right)$ $\displaystyle\leq
2^{z-1}\left(\mathrm{cost}_{z}^{z}(\Pi(X),R^{\prime})+\alpha\cdot\mathrm{cost}_{z}^{z}(X,R)\right)\leq
2^{z-1}(1+\alpha^{2})\cdot\mathrm{cost}_{z}^{z}(\Pi(X),R^{\prime}).$ (28)

Finally, we note that, similarly to the proof of Lemma 5.4,

$\displaystyle\frac{\|\Pi(y_{x})-\rho_{R^{\prime}}(\Pi(y_{x}))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(Y),R^{\prime})}\leq\sup_{v\in\mathbbm{R}^{t}}\dfrac{|\langle\Pi(y_{x}),v\rangle|^{z}}{\sum_{x^{\prime}\in
X}|\langle\Pi(y_{x^{\prime}}),v\rangle|^{z}}.$ (29)

Continuing to upper-bound the left-hand side of (27) by plugging in (26), (29)
and (28),

$\displaystyle\dfrac{\|\Pi(x)-\rho_{R^{\prime}}(\Pi(x))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(X),R^{\prime})}$
$\displaystyle\leq
2^{z-1}\left(D_{x}^{z}\alpha\cdot\dfrac{\|x-y_{x}\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,Y)}+2^{z-1}(\alpha^{2}+1)\sup_{u\in\mathbbm{R}^{d}}\dfrac{|\langle
y_{x},u\rangle|^{z}}{\sum_{x^{\prime}\in X}|\langle
y_{x^{\prime}},u\rangle|^{z}}\right)$ $\displaystyle\leq
D_{x}^{z}\cdot(\alpha^{2}+1)\cdot\sigma(x).$

In particular, the bound on the variance in (25) is at most

$\dfrac{\mathfrak{S}_{\sigma}}{m}\cdot 2^{4z}(\alpha^{2}+1)^{2}\sum_{x\in
X}D_{x}^{2z}\sigma(x)\leq\dfrac{\mathfrak{S}_{\sigma}^{2}}{m}\cdot
2^{5z}(\alpha^{2}+1),$

so letting $m=\mathrm{poly}(k^{z},1/\varepsilon,\alpha)$ gives the desired
bound on the variance. ∎

######  Corollary 5.12.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points,
and let $R\subset\mathbbm{R}^{d}$ be the subspace for optimal $(k,z)$-subspace
approximation of $X$. For any $\varepsilon\in(0,1/2)$, let $\mathcal{J}_{d,t}$
be the Johnson-Lindenstrauss map with

$t\gtrsim\dfrac{z\cdot
k^{2}\cdot\mathrm{polylog}(k/\varepsilon)}{\varepsilon^{3}}.$

Then, with probability at least $0.92$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\dfrac{1}{(1+\varepsilon)^{3+1/z}}\cdot\mathrm{cost}_{z}(X,R)\leq\min_{\begin{subarray}{c}R^{\prime}\subset\mathbbm{R}^{t}\\\
\dim R^{\prime}\leq
k\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),R^{\prime}).$

###### Proof.

We sample $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$ and
$(\mathbf{S},\boldsymbol{w})$ as per Definition 5.6. Again, Theorem 8
guarantees that $\mathbf{E}_{1}$ occurs with probability at least $0.99$ over
the draw of $(\mathbf{S},\boldsymbol{w})$. By Lemma 5.1, Corollary 5.10 and
(24), the condition (1), (2), and (3) are satisfied with probability at least
$0.95$, so we may apply Lemma 5.11 and have $\mathbf{E}_{3}(1+\varepsilon)$
holds with probability at least $0.94$. Finally, event $\mathbf{E}_{2}$ holds
with probability at least $0.99$ by Lemma 5.8. Taking a union bound and
applying Lemma 5.7 gives the desired bound. ∎

##  6 $k$-Flat Approximation

In the $(k,z)$-_flat approximation_ problem, we consider subspace
$R\subset\mathbbm{R}^{d}$ of dimension less than $k$, which we may encode by a
collection of at most $k$ orthonormal vectors $r_{1},\dots,r_{k}\in R$, as
well as a translation vector $\tau\in\mathbbm{R}^{d}$. The $k$-flat specified
by $R$ and $\tau$ is given by the affine subspace

$F=\left\\{x+\tau\in\mathbbm{R}^{d}:x\in R\right\\}.$

We let $\rho_{F}\colon\mathbbm{R}^{d}\to\mathbbm{R}$ denote the map which
sends each $x\in\mathbbm{R}^{d}$ to its closest point on $F$, and we note that

$\displaystyle\rho_{F}(x)$ $\displaystyle=\mathop{\mathrm{argmin}}_{y\in
F}\|x-y\|_{2}^{2}=\tau+\sum_{i=1}^{r}\langle x-\tau,r_{i}\rangle r_{i}$

For any $X\subset\mathbbm{R}^{d}$, we let

$\mathrm{cost}_{z}^{z}(X,F)\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{x\in
X}\left\|x-\rho_{F}(x)\right\|_{2}^{z}.$

In this section, we show that we may find the optimal $k$-flat approximation
after applying a Johnson-Lindenstrauss map. The proof will be almost exactly
the same as the $(k,z)$-subspace approximation problem. Indeed, it only
remains to incorporate a translation vector.

######  Theorem 9 (Johnson-Lindenstrauss for $k$-Flat Approximation).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points,
and let $F\subset\mathbbm{R}^{d}$ denote the optimal $(k,z)$-flat
approximation of $X$. For any $\varepsilon\in(0,1)$, suppose we let
$\mathcal{J}_{d,t}$ be a distribution over a Johnson-Lindenstrauss maps where

$t\gtrsim\dfrac{z\cdot
k^{2}\cdot\mathrm{polylog}(k/\varepsilon)}{\varepsilon^{3}}.$

Then, with probability at least $0.9$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\dfrac{1}{1+\varepsilon}\cdot\mathrm{cost}_{z}(X,F)\leq\min_{\begin{subarray}{c}F^{\prime}\text{
$k$-flat}\\\ \text{in
$\mathbbm{R}^{t}$}\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),F^{\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}(X,F).$

###  6.1 Easy Direction: Optimum Cost Does Not Increase

######  Lemma 6.1.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ by any set of points and
let $F\subset\mathbbm{R}^{d}$ be the optimal $(k,z)$-flat approximation of
$X$. We let $\mathcal{J}_{d,t}$ be the distribution over Johnson-Lindenstrauss
maps. If $t\gtrsim z/\varepsilon^{2}$, then with probability at least $0.99$
over the draw of $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\sum_{x\in
X}\|\mathbf{\Pi}(x)-\mathbf{\Pi}(\rho_{F}(x))\|_{2}^{z}\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}^{z}(X,F),$

and hence,

$\min_{\begin{subarray}{c}F^{\prime}\text{ $k$-flat}\\\ \text{in
$\mathbbm{R}^{t}$}\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),F^{\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}(X,F).$

The proof follows in a similar fashion to Lemma 4.1 and Lemma 5.1. In
particular, there is a natural definition of a $k$-flat
$\mathbf{\Pi}(F)\subset\mathbbm{R}^{t}$, and the proof proceeds by upper
bounding the expected dilation of
$\|\mathbf{\Pi}(x)-\mathbf{\Pi}(\rho_{F}(x))\|_{2}^{z}$.

###  6.2 Hard Direction: Optimum Cost Does Not Decrease

####  6.2.1 Preliminaries

The proof in this section follows similarly to that of $(k,z)$-subspace
approximation.

######  Definition 6.2 (Weak Coresets for $(k,z)$-flat approximation).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be a set of points. A
weak $\varepsilon$-coreset of $X$ for $(k,z)$-flat approximation is a weighted
subset $S\subset\mathbbm{R}^{d}$ of points with weights $w\colon
S\to\mathbbm{R}_{\geq 0}$ such that,

$\dfrac{1}{1+\varepsilon}\cdot\min_{\begin{subarray}{c}F\text{ $k$-flat}\\\
\text{in
$\mathbbm{R}^{d}$}\end{subarray}}\mathrm{cost}_{z}(X,F)\leq\min_{\begin{subarray}{c}F\text{
$k$-flat}\\\ \text{in
$\mathbbm{R}^{d}$}\end{subarray}}\mathrm{cost}_{z}((S,w),F)\leq(1+\varepsilon)\cdot\min_{\begin{subarray}{c}F\text{
$k$-flat}\\\ \text{in $\mathbbm{R}^{d}$}\end{subarray}}\mathrm{cost}_{z}(X,F)$

######  Definition 6.3 (Sensitivities).

Let $n,d\in\mathbbm{N}$, and consider any set of points
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, as well as
$k\in\mathbbm{N}$ and $z\geq 1$. A sensitivity function $\sigma\colon
X\to\mathbbm{R}_{\geq 0}$ for $(k,z)$-flat approximation in $\mathbbm{R}^{d}$
is a function satisfying that, for all $x\in X$,

$\displaystyle\sup_{\begin{subarray}{c}F\subset\mathbbm{R}^{d}\\\
\text{$k$-flat}\end{subarray}}\dfrac{\|x-\rho_{F}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,F)}\leq\sigma(x).$

The total sensitivity of the senstivity function $\sigma$ is given by

$\mathfrak{S}_{\sigma}=\sum_{x\in X}\sigma(x).$

For a sensitivity function, we let $\tilde{\sigma}$ denote the sensitivity
sampling distribution, supported on $X$, which samples $x\in X$ with
probability proportional to $\sigma(x)$.

The sensitivity function we use here generalizes that of the previous section.
In particular, the proof will follow similarly, and we will defer to the
arguments in the previous section.

######  Lemma 6.4.

Let $n,d\in\mathbbm{N}$, and consider any set of points
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, as well as
$k\in\mathbbm{N}$ with $k<d$ and $z\geq 1$. Suppose $F\subset\mathbbm{R}^{d}$
is the optimal $(k,z)$-flat approximation of $X$ in $\mathbbm{R}^{d}$. Then,
the function $\sigma\colon X\to\mathbbm{R}_{\geq 0}$ given by

$\sigma(x)=2^{z-1}\cdot\dfrac{\|x-\rho_{F}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,F)}+2^{2z-1}\cdot\sup_{\begin{subarray}{c}u\in\mathbbm{R}^{d}\\\
\phi\in\mathbbm{R}\end{subarray}}\dfrac{|\langle\rho_{F}(x),u\rangle-\phi|^{z}}{\sum_{x^{\prime}\in
X}|\langle\rho_{F}(x^{\prime}),u\rangle-\phi|^{z}}$

is a sensitivity function for $(k,z)$-flat approximation of $X$ in
$\mathbbm{R}^{d}$, satisfying

$\mathfrak{S}_{\sigma}\leq 2^{z-1}+2^{2z-1}(k+2)^{1+z}.$

###### Proof.

Consider any $k$-flat $F^{\prime}\subset\mathbbm{R}^{d}$, given by a subspace
$R\subset\mathbbm{R}^{d}$ of dimension at most $k$, and a translation
$\tau\in\mathbbm{R}^{d}$. As in the proof of Lemma 5.4,

$\displaystyle\dfrac{\|x-\rho_{F^{\prime}}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,F^{\prime})}\leq
2^{z-1}\cdot\dfrac{\|x-\rho_{F}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,F)}+2^{2z-1}\cdot\dfrac{\|\rho_{F}(x)-\rho_{F^{\prime}}(\rho_{F}(x))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\rho_{F}(X),F^{\prime})}.$

We now have that for any $Y\subset\mathbbm{R}^{d}$, and any $y\in Y$,

$\displaystyle\sup_{\begin{subarray}{c}F^{\prime}\subset\mathbbm{R}^{d}\\\
\text{$k$-flat}\end{subarray}}\dfrac{\|y-\rho_{F^{\prime}}(y)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(Y,F^{\prime})}\leq\sup_{\tau\in\mathbbm{R}^{d}}\sup_{u\in\mathbbm{R}^{d}}\dfrac{|\langle
y-\tau,u\rangle|^{z}}{\sum_{y^{\prime}\in Y}|\langle
y^{\prime}-\tau,u\rangle|^{z}}.$

Finally, for each $y\in Y\subset\mathbbm{R}^{d}$, we may consider appending an
additional coordinate and consider $y^{*}\in\mathbbm{R}^{d+1}$ where the
$d+1$-th entry is $1$. Then, by linearity

$\sup_{\tau\in\mathbbm{R}^{d}}\sup_{u\in\mathbbm{R}^{d}}\dfrac{|\langle
y-\tau,u\rangle|^{z}}{\sum_{y^{\prime}\in Y}|\langle
y-\tau,u\rangle|^{z}}=\sup_{v\in\mathbbm{R}^{d+1}}\dfrac{|\langle
y^{*},v\rangle|^{z}}{\sum_{y^{\prime}\in Y}|\langle
y^{{}^{\prime}*},v\rangle|^{z}},$

and the bound on the total sensitivity follows from Lemma 5.4. ∎

In the $(k,z)$-subspace approximation section, we used a lemma (Lemma 5.5) to
narrow down the approximately optimal subspaces to those spanned by at most
$O(k^{2}\log(k/\varepsilon)/\varepsilon)$ points. Here, we use a similar lemma
in order to find an approximately optimal translation vector
$\tau\in\mathbbm{R}^{d}$, which is spanned by a small subset of points.

######  Lemma 6.5 (Lemma 3.3 [SV07]).

Let $d,k\in\mathbbm{N}$, and consider a weighted set of points
$S\subset\mathbbm{R}^{d}$ with weights $w\colon S\to\mathbbm{R}_{\geq 0}$, as
well as $\varepsilon\in(0,1)$ and $z\geq 1$. Suppose $F\subset\mathbbm{R}^{d}$
is the optimal $(k,z)$-flat approximation of $X$, encoded by a $k$-dimensional
subspace $R\subset\mathbbm{R}^{d}$ and translation vector
$\tau\in\mathbbm{R}^{d}$. There exists a subset $Q\subset S$ of size
$O(\log(1/\varepsilon)/\varepsilon)$ and a point
$\tau^{\prime}\in\mathrm{conv}(Q)$ such that the $k$-flat

$F^{\prime}=\left\\{\tau^{\prime}+y\in\mathbbm{R}^{d}:y\in R\right\\}$

satisfies

$\mathrm{cost}_{z}((S,w),F^{\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}((S,w),F).$

######  Theorem 10 ($\varepsilon$-Weak Coresets for $k$-Flats via Sensitivity
Sampling).

For any subset $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ and
$\varepsilon\in(0,1/2)$, let $\tilde{\sigma}$ denote the sensitivity sampling
distribution.

  * •

Let $(\mathbf{S},\boldsymbol{w})$ denote the random (multi-)set
$\mathbf{S}\subset X$ and $\boldsymbol{w}\colon\mathbf{S}\to\mathbbm{R}_{\geq
0}$ given by, for

$m=\mathrm{poly}((k+2)^{z},1/\varepsilon)$

iterations, sampling $\boldsymbol{x}\sim\tilde{\sigma}$ i.i.d and letting
$\boldsymbol{w}(\boldsymbol{x})=1/(m\tilde{\sigma}(x))$.

  * •

Then, with probability $1-o(1)$ over the draw of
$(\mathbf{S},\boldsymbol{w})$, it is an $\varepsilon$-weak coreset for
$(k,z)$-subspace approximation of $X$.

###  6.3 The Important Events

The important events we consider mirror those the subspace approximation
problem. The only event which would change is $\mathbf{E}_{2}$, where we
require $\mathbf{\Pi}$ to be an $\varepsilon$-subspace embedding for all
subsets of
$O(k^{2}\log(k/\varepsilon)/\varepsilon)+O(\log(1/\varepsilon)/\varepsilon)$
points from $\mathbf{S}$. This will allow us to incorporate the translation
$\tau^{\prime}$ from Lemma 6.5.

######  Definition 6.6 (The Events).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, and $\tilde{\sigma}$
the sensitivity sampling distribution of $X$ of Lemma 6.4. We consider the
following experiment,

  1. 1.

We generate a sample $(\mathbf{S},\boldsymbol{w})$ by sampling from
$\tilde{\sigma}$ for $m=\mathrm{poly}(k^{z},1/\varepsilon)$ i.i.d iterations
$\boldsymbol{x}\sim\tilde{\sigma}$ and set
$\boldsymbol{w}(\boldsymbol{x})=1/(m\tilde{\sigma}(\boldsymbol{x}))$.

  2. 2.

Furthermore, we sample $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$, which is a
Johnson-Lindenstrauss map $\mathbbm{R}^{d}\to\mathbbm{R}^{t}$.

  3. 3.

We let $\mathbf{S}^{\prime}=\mathbf{\Pi}(\mathbf{S})\subset\mathbbm{R}^{t}$
denote the image of $\mathbf{\Pi}$ on $\mathbf{S}$.

The events are the following:

  * •

$\mathbf{E}_{1}$ : The weighted (multi-)set $(\mathbf{S},\boldsymbol{w})$ is a
weak $\varepsilon$-coreset for $(k,z)$-flat approximation of $X$ in
$\mathbbm{R}^{d}$.

  * •

$\mathbf{E}_{2}$ : The map
$\mathbf{\Pi}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ satisfies the following
condition. For any choice of $O(k^{2}\log(k/\varepsilon)/\varepsilon)$ points
of $\mathbf{S}$, $\mathbf{\Pi}$ is an $\varepsilon$-subspace embedding of the
subspace spanned by these points.

  * •

$\mathbf{E}_{3}(\beta)$ : Let $\mathbf{F}^{\prime}\subset\mathbbm{R}^{t}$
denote the optimal $(k,z)$-flat approximation of $\mathbf{\Pi}(X)$ in
$\mathbbm{R}^{t}$. Then,

$\mathrm{cost}_{z}^{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),\mathbf{F}^{\prime})\leq\beta\cdot\mathrm{cost}_{z}^{z}(\mathbf{\Pi}(X),\mathbf{F}^{\prime}).$

######  Lemma 6.7.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, and suppose
$(\mathbf{S},\boldsymbol{w})$ and
$\mathbf{\Pi}\colon\mathbbm{R}^{d}\to\mathbbm{R}^{t}$ satisfy events
$\mathbf{E}_{1}$, $\mathbf{E}_{2}$, and $\mathbf{E}_{3}(\beta)$. Then,

$\min_{\begin{subarray}{c}F^{\prime}\text{ $k$-flat}\\\ \text{in
$\mathbbm{R}^{t}$}\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),F^{\prime})\geq\dfrac{1}{\beta^{1/z}(1+\varepsilon)^{4}}\cdot\min_{\begin{subarray}{c}F\text{
$k$-flat}\\\ \text{in
$\mathbbm{R}^{d}$}\end{subarray}}\mathrm{cost}_{z}(X,F).$

###### Proof.

Consider a fixed $\mathbf{\Pi}$ and $(\mathbf{S},\boldsymbol{w})$ satisfying
the three events of Definition 5.6. Let $F^{\prime}\subset\mathbbm{R}^{t}$ be
the $k$-flat which minimizes
$\mathrm{cost}_{z}^{z}(\mathbf{\Pi}(X),F^{\prime})$. Suppose that $F^{\prime}$
is specified by a $k$-dimensional subspace $R^{\prime}$ and a translation
$\tau^{\prime}$. Then, by event $\mathbf{E}_{3}(\beta)$, we have
$\mathrm{cost}_{z}^{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),F^{\prime})\leq\beta\cdot\mathrm{cost}_{z}^{z}(\mathbf{\Pi}(X),F^{\prime})$.
Now, we apply Lemma 6.5 to $(\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w})$, and we
obtain a subset $Q\subset\mathbf{S}$ of size
$O(\log(1/\varepsilon)/\varepsilon)$ for which there exists a translation
vector $\tau^{\prime\prime}\in\mathbbm{R}^{t}$ within the
$\mathrm{conv}(\mathbf{\Pi}(Q))$ such that $k$-flat $F^{\prime\prime}$ given
by $\tau^{\prime\prime}$ and $R^{\prime}$ satisfies

$\left(\sum_{x\in\mathbf{S}}\boldsymbol{w}(x)\cdot\|\mathbf{\Pi}(x)-\rho_{F^{\prime\prime}}(\mathbf{\Pi}(x))\|_{2}^{z}\right)^{1/z}=\mathrm{cost}_{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),F^{\prime\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),F^{\prime}).$

Furthermore, by Lemma 5.5 to the weighted vectors
$(\mathbf{\Pi}(\mathbf{S})-\tau^{\prime\prime},\boldsymbol{w})$,777Here, we
are using the short-hand
$\mathbf{\Pi}(\mathbf{S})-\tau^{\prime\prime}\stackrel{{\scriptstyle\rm
def}}{{=}}\left\\{\mathbf{\Pi}(x)-\tau^{\prime\prime}\in\mathbbm{R}^{t}:x\in\mathbf{S}\right\\}$.
there exists a subset
$Q^{\prime}\subset\mathbf{\Pi}(\mathbf{S})-\tau^{\prime\prime}$ of size
$O(k^{2}\log(k/\varepsilon)/\varepsilon)$ and a $k$-dimensional subspace
$R^{\prime\prime}\subset\mathbbm{R}^{d}$ within the span of $Q^{\prime}$ such
that the $k$-flat $F^{\prime\prime\prime}$ specified by $R^{\prime\prime}$ and
$\tau^{\prime\prime}$ satisfies

$\left(\sum_{x\in\mathbf{S}}\boldsymbol{w}(x)\cdot\|\mathbf{\Pi}(x)-\rho_{F^{\prime\prime\prime}}(\mathbf{\Pi}(x))\|_{2}^{z}\right)^{1/z}=\mathrm{cost}_{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),F^{\prime\prime\prime})\leq(1+\varepsilon)^{2}\cdot\mathrm{cost}_{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),F^{\prime}).$

Recall that (i) $R^{\prime\prime}$ is a $k$-dimensional subspace lying in the
span of $\mathbf{\Pi}(Q^{\prime})$, (ii)
$\tau^{\prime\prime}\in\mathbbm{R}^{t}$ is within
$\mathrm{conv}(\mathbf{\Pi}(Q))$, and (iii) for any $x\in\mathbf{S}$,
$\mathbf{\Pi}$ is an $\varepsilon$-subspace embedding of the span of $Q\cup
Q^{\prime}\cup\\{x\\}$. Similarly to Lemma 5.7, we may find a $k$-flat $U$
such that for every $x\in\mathbf{S}$,

$\|x-\rho_{U}(x)\|_{2}\leq(1+\varepsilon)\|\mathbf{\Pi}(x)-\rho_{F^{\prime\prime\prime}}(\mathbf{\Pi}(x))\|_{2},$

and hence

$\mathrm{cost}_{z}((\mathbf{S},\boldsymbol{w}),U)\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}((\mathbf{\Pi}(\mathbf{S}),\boldsymbol{w}),F^{\prime\prime\prime}).$

Finally, since $(\mathbf{S},\boldsymbol{w})$ is a $\varepsilon$-weak coreset,
we obtain the desired inequality. ∎

As in the previous section, events $\mathbf{E}_{1}$ and $\mathbf{E}_{2}$ hold
with sufficiently high probability. All that remains is showing that
$\mathbf{E}_{3}(1+\varepsilon)$ holds with sufficiently high probability. We
proceed in a similar fashion, where we first show a loose approximation
guarantee, and later improve on it.

######  Lemma 6.8.

Fix any $\Pi\in\mathcal{J}_{d,t}$ and let $F^{\prime}\subset\mathbbm{R}^{t}$
denote the $k$-flat for optimal $(k,z)$-flat approximation of $\Pi(X)$ in
$\mathbbm{R}^{t}$. Then with probability at least $0.99$ over the draw of
$(\mathbf{S},\boldsymbol{w})$ as per Definition 6.6,

$\sum_{x\in\mathbf{S}}\boldsymbol{w}(x)\cdot\|\Pi(x)-\rho_{F^{\prime}}(\Pi(x))\|_{2}^{z}\leq
100\cdot\mathrm{cost}_{z}^{z}(\Pi(X),F^{\prime}).$

In other words, event $\mathbf{E}_{3}(100)$ holds with probability at least
$0.99$.

######  Corollary 6.9.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points.
For any $\varepsilon\in(0,1/2)$, let $\mathcal{J}_{d,t}$ be the Johnson-
Lindenstrauss map with

$t\gtrsim\dfrac{z\cdot
k^{2}\cdot\mathrm{polylog}(k/\varepsilon)}{\varepsilon^{3}}.$

Then, with probability at least $0.97$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\dfrac{1}{100^{1/z}(1+\varepsilon)^{4}}\cdot\min_{\begin{subarray}{c}F\subset\mathbbm{R}^{d}\\\
\text{$k$-flat}\end{subarray}}\mathrm{cost}_{z}(X,F)\leq\min_{\begin{subarray}{c}F^{\prime}\subset\mathbbm{R}^{t}\\\
\text{$k$-flat}\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),F^{\prime}).$

####  6.3.1 Improving the approximation

The improvement of the approximation, follows from upper bounding the
variance, as in the $(k,z)$-clustering problem, and the $(k,z)$-subspace
approximation problem. In particular, we show that
$\mathbf{E}_{3}(1+\varepsilon)$ holds. Fix
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ and
$F\subset\mathbbm{R}^{d}$ be the optimal $(k,z)$-flat approximation of $X$ in
$\mathbbm{R}^{d}$. The sensitivity function $\sigma\colon
X\to\mathbbm{R}_{\geq 0}$ specified in Lemma 6.4 specify the sensitivity
sampling distribution $\tilde{\sigma}$.

We let $\mathbf{E}_{4}$ denote the following event with respect to the
randomness in $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$. For each $x\in X$, we let
$\mathbf{D}_{x}\in\mathbbm{R}_{\geq 0}$ denote the random variable

$\mathbf{D}_{x}\stackrel{{\scriptstyle\rm
def}}{{=}}\dfrac{\|\mathbf{\Pi}(x)-\mathbf{\Pi}(\rho_{F}(x))\|_{2}}{\|x-\rho_{F}(x)\|_{2}},$

and as in (23) and (24), event $\mathbf{E}_{4}$, which occurs with probability
at least $0.99$, whenever

$\sum_{x\in X}\mathbf{D}_{x}^{2z}\cdot\sigma(x)\leq 100\cdot
2^{z}\cdot\mathfrak{S}_{\sigma}.$

######  Lemma 6.10.

Let $\Pi\in\mathcal{J}_{d,t}$ be a Johnson-Lindensrauss map where, for
$\alpha>1$, the following events hold:

  1. 1.

Guarantee from Lemma 6.1: $\sum_{x\in
X}\|\Pi(x)-\Pi(\rho_{F}(x))\|_{2}^{z}\leq\alpha\cdot\mathrm{cost}_{z}^{z}(X,F)$.

  2. 2.

Guarantee from Corollary 6.9: letting $F^{\prime}\subset\mathbbm{R}^{t}$ be
the optimal $(k,z)$-flat approximation of $\Pi(X)$, then
$\mathrm{cost}_{z}^{z}(X,F)\leq\alpha\mathrm{cost}_{z}^{z}(\Pi(X),F^{\prime})$.

  3. 3.

Event $\mathbf{E}_{4}$ holds.

Then, if we let $(\mathbf{S},\boldsymbol{w})$ denote
$m=\mathrm{poly}(k^{z},1/\varepsilon,\alpha)$ i.i.d draws from
$\tilde{\sigma}$ and $\boldsymbol{w}(x)=1/(m\tilde{\sigma}(x))$, with
probability at least $0.99$,

$\mathrm{cost}_{z}^{z}((\Pi(\mathbf{S}),\boldsymbol{w}),F^{\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}^{z}(\Pi(X),F^{\prime}).$

###### Proof.

We similarly bound the variance of

$\displaystyle\operatorname{{\bf Var}}_{\mathbf{S}}\left[\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim\mathbf{S}}\left[\dfrac{1}{\tilde{\sigma}(\boldsymbol{x})}\dfrac{\|\Pi(\boldsymbol{x})-\rho_{F^{\prime}}\left(\Pi(\boldsymbol{x})\right)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(X),F^{\prime})}\right]\right]\leq\dfrac{\mathfrak{S}_{\sigma}}{m}\sum_{x\in
X}\left(\dfrac{1}{\sigma(x)}\cdot\dfrac{\|\Pi(x)-\rho_{F^{\prime}}(\Pi(x))\|_{2}^{z}}{\mathrm{cost}_{z}^{2z}(\Pi(X),F^{\prime})}\right).$

It is not hard to show, as in the proof of Lemma 5.11, that writing
$y_{x}=\rho_{F}(x)\in\mathbbm{R}^{d}$ and $Y=\\{y_{x}:x\in X\\}$, that

$\displaystyle\dfrac{\|\Pi(x)-\rho_{F^{\prime}}(\Pi(x))\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(\Pi(X),F^{\prime})}\leq
2^{z-1}\alpha\mathbf{D}_{x}^{z}\cdot\dfrac{\|x-\rho_{F}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,F)}+2^{2z-2}(1+\alpha^{2})\sup_{\begin{subarray}{c}v\in\mathbbm{R}^{t}\\\
\mu\in\mathbbm{R}\end{subarray}}\dfrac{|\langle\Pi(y_{x}),v\rangle-\mu|^{z}}{\sum_{x^{\prime}\in
X}|\langle\Pi(y_{x^{\prime}}),v\rangle-\mu|^{z}},$

and similarly to before, we have

$\displaystyle\sup_{\begin{subarray}{c}v\in\mathbbm{R}^{t}\\\
\mu\in\mathbbm{R}\end{subarray}}\dfrac{|\langle\Pi(y_{x}),v\rangle-\mu|^{z}}{\sum_{x^{\prime}\in
X}|\langle\Pi(y_{x^{\prime}}),v\rangle-\mu|^{z}}\leq\sup_{\begin{subarray}{c}u\in\mathbbm{R}^{d}\\\
\phi\in R\end{subarray}}\dfrac{|\langle
y_{x},u\rangle-\phi|^{z}}{\sum_{x^{\prime}\in X}|\langle
y_{x^{\prime}},u\rangle-\phi|^{z}}.$

This implies that the variance is at most

$2^{4z-2}\cdot\dfrac{\mathfrak{S}_{\sigma}\alpha^{4}}{m}\cdot\sum_{x\in
X}\mathbf{D}_{x}^{2z}\cdot\sigma(x)\leq\varepsilon^{2}$

by setting $m=\mathrm{poly}((k+2)^{z},1/\varepsilon,\alpha)$ to be large
enough when $\mathbf{E}_{4}$ holds, and we apply Chebyshev’s inequality. ∎

######  Corollary 6.11.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points,
and let $F\subset\mathbbm{R}^{d}$ be the optimal $(k,z)$-flat approximation of
$X$. For any $\varepsilon\in(0,1/2)$, let $\mathcal{J}_{d,t}$ be the Johnson-
Lindenstrauss map with

$t\gtrsim\dfrac{z\cdot
k^{2}\cdot\mathrm{polylog}(k/\varepsilon)}{\varepsilon^{3}}.$

Then, with probability at least $0.92$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\dfrac{1}{(1+\varepsilon)^{4+1/z}}\cdot\mathrm{cost}_{z}(X,F)\leq\min_{\begin{subarray}{c}F^{\prime}\subset\mathbbm{R}^{t}\\\
\text{$k$-flat}\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),F^{\prime}).$

##  7 $k$-Line Approximation

In the $(k,z)$-_line approximation_ problem, we consider a collection of $k$
lines in $\mathbbm{R}^{d}$. A line is encoded by a vector
$v\in\mathbbm{R}^{d}$ and a unit vector $u\in S^{d-1}$, where we will write

$\ell(v,u)=\left\\{v+t\cdot u\in\mathbbm{R}^{d}:t\in\mathbbm{R}\right\\}.$

For a single line $\ell$ encoded by $v$ and $u$, we write
$\rho_{\ell}\colon\mathbbm{R}^{d}\to\mathbbm{R}$ as the orthogonal projection
of a point onto $\ell$, i.e., the closest vector which lies on the line, where

$\rho_{\ell}(x)=\mathop{\mathrm{argmin}}_{y\in\ell}\|x-y\|_{2}^{2}=v+\langle
x-v,u\rangle u.$

For any set of $k$ lines, $L=\\{\ell_{1},\dots,\ell_{k}\\}$, and a point $x\in
X$, we write

$\mathrm{cost}_{z}^{z}(x,L)=\min_{\ell\in L}\|x-\rho_{\ell}(x)\|_{2}^{z},$

and for any dataset $X\subset\mathbbm{R}^{d}$ and set of lines $L$, we
consider the map $\ell\colon X\to L$ which sends a point $x$ to its nearest
line in $L$. Then, we write

$\mathrm{cost}_{z}^{z}(X,L)=\sum_{x\in X}\|x-\rho_{\ell(x)}(x)\|_{2}^{z},$

as the cost of representing the points in $X$ according to the $k$ lines in
$L$. In this section, we show that we may find the optimal $(k,z)$-line
approximation after applying a Johnson-Lindenstrauss map. Specifically, we
prove:

######  Theorem 11 (Johnson-Lindenstrauss for $(k,z)$-Line Approximation).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points,
and let $L=\\{\ell_{1},\dots,\ell_{k}\\}$ denote a set of lines in
$\mathbbm{R}^{d}$ for optimally $(k,z)$-line approximation of $X$. For any
$\varepsilon\in(0,1)$, suppose we let $\mathcal{J}_{d,t}$ be a distribution
over Johnson-Lindenstrauss maps where

$t\gtrsim\dfrac{k\log\log n+z+\log(1/\varepsilon)}{\varepsilon^{3}}.$

Then, with probability at least $0.9$ over the draw of
$\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\dfrac{1}{1+\varepsilon}\cdot\mathrm{cost}_{z}(X,L)\leq\min_{\begin{subarray}{c}L^{\prime}\text{
$k$ lines}\\\ \text{in
$\mathbbm{R}^{t}$}\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),L^{\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}(X,L).$

###  7.1 Easy Direction: Optimum Cost Does Not Increase

######  Lemma 7.1.

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be any set of points and
let $L=\\{\ell_{1},\dots,\ell_{k}\\}$ be a set of $k$ lines in
$\mathbbm{R}^{d}$ for optimal $(k,z)$-line approximation of $X$, and for each
$x\in X$, let $\ell(x)\in L$ be the line assigned to $x$. We let
$\mathcal{J}_{d,t}$ be the distribution over Johnson-Lindenstrauss maps. If
$t\gtrsim z/\varepsilon^{2}$, then with probability at least $0.99$ over the
draw of $\mathbf{\Pi}\sim\mathcal{J}_{d,t}$,

$\left(\sum_{x\in
X}\|\mathbf{\Pi}(x)-\mathbf{\Pi}(\rho_{\ell(x)}(x))\|_{2}^{z}\right)^{1/z}\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}(X,L),$

and hence,

$\min_{\begin{subarray}{c}L^{\prime}\text{ $k$ lines}\\\ \text{in
$\mathbbm{R}^{t}$}\end{subarray}}\mathrm{cost}_{z}(\mathbf{\Pi}(X),L^{\prime})\leq(1+\varepsilon)\cdot\mathrm{cost}_{z}(X,L).$

By now, there is a straight-forward way to prove the above lemma. For each set
of $k$ lines $L=\\{\ell_{1},\dots,\ell_{k}\\}$ in $\mathbbm{R}^{d}$, there is
an analogous definition of $k$ lines $\mathbf{\Pi}(L)$ in $\mathbbm{R}^{t}$.
Hence, we use Lemma LABEL:lem:gaussians as in previous sections to upper bound
the cost $\mathrm{cost}_{z}(\mathbf{\Pi}(X),\mathbf{\Pi}(L))$.

###  7.2 Hard Direction: Optimum Cost Does Not Decrease

####  7.2.1 Preliminaries

At a high level, we proceed with the same argument as in previous sections: we
consider a sensitivity function for $(k,z)$-line approximation of $X$ in
$\mathbbm{R}^{d}$, and use it to build a weak coreset, as well as argue that
sensitivity sampling is a low-variance estimator of the optimal $(k,z)$-line
approximation in the projected space. The proof in this section will be
significantly more complicated than the previous section. Defining the
appropriate sensitivity functions, which will give a low-variance estimator in
the projected space, is considerably more difficult than the expressions of
Lemmas 4.4, 5.4, and 6.4. For this reason, will be proceed by assuming access
to a sensitivity function which we will define lated in the section.

######  Definition 7.2 (Weak Coresets for $(k,z)$-Line Approximation).

Let $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ be a set of points. A
weak $\varepsilon$-coreset of $X$ for $(k,z)$-line approximation is a weighted
subset $S\subset\mathbbm{R}^{d}$ of points with weights $w\colon
S\to\mathbbm{R}_{\geq 0}$ such that

$\displaystyle\frac{1}{1+\varepsilon}\cdot\min_{\begin{subarray}{c}L\text{ $k$
lines}\\\ \text{in
$\mathbbm{R}^{d}$}\end{subarray}}\mathrm{cost}_{z}(X,L)\leq\min_{\begin{subarray}{c}L\text{
$k$ lines}\\\ \text{in
$\mathbbm{R}^{d}$}\end{subarray}}\mathrm{cost}_{z}((S,w),L)\leq(1+\varepsilon)\cdot\min_{\begin{subarray}{c}L\text{
$k$ lines}\\\ \text{in
$\mathbbm{R}^{d}$}\end{subarray}}\mathrm{cost}_{z}(X,L)$

######  Definition 7.3 (Sensitivities).

Let $n,d\in\mathbbm{N}$, and consider any set of points
$X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$, as well as
$k\in\mathbbm{N}$ and $z\geq 1$. A sensitivity function $\sigma\colon
X\to\mathbbm{R}_{\geq 0}$ for $(k,z)$-line approximation in $\mathbbm{R}^{d}$
is a function which satisfies that, for all $x\in X$,

$\displaystyle\sup_{\begin{subarray}{c}L\text{: $k$ lines}\\\ \text{in
$\mathbbm{R}^{d}$}\end{subarray}}\dfrac{\|x-\rho_{\ell(x)}(x)\|_{2}^{z}}{\mathrm{cost}_{z}^{z}(X,L)}\leq\sigma(x).$

The total sensitivity of the sensitivity function $\sigma$ is given by

$\mathfrak{S}_{\sigma}=\sum_{x\in X}\sigma(x).$

For a sensitivity function, we let $\tilde{\sigma}$ denote the sensitivity
sampling distribution, supported on $X$, which samples $x\in X$ with
probability proportional to $\sigma(x)$.

Similarly to before, we first give a lemma which narrows down the space of the
optimal line approximations for a set of points. the following lemma is a re-
formulations of Lemma 5.5 and Lemma 6.5 catered to the case of $(k,z)$-line
approximation.

######  Lemma 7.4 (Theorem 3.1 and Lemma 3.3 of [SV12]).

Let $d\in\mathbbm{N}$ and $S\subset\mathbbm{R}^{d}$ be any set of points with
weights $w\colon S\to\mathbbm{R}_{\geq 0}$, $\varepsilon\in(0,1/2)$, and
$z\geq 1$. There exists a subset $Q\subset S$ of size
$O(\log(1/\varepsilon)/\varepsilon)$ and a line $\ell$ in $\mathbbm{R}^{d}$
within the span of $Q$ such that

$\mathrm{cost}_{z}((S,w),\\{\ell\\})\leq(1+\varepsilon)\min_{\begin{subarray}{c}\ell^{\prime}\text{
line}\\\ \text{in
$\mathbbm{R}^{d}$}\end{subarray}}\mathrm{cost}_{z}((S,w),\\{\ell^{\prime}\\}).$

######  Lemma 7.5 (Weak Coresets for $k$-Line Approximation [FL11, VX12b]).

For any subset $X=\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{d}$ and
$\varepsilon\in(0,1/2)$, let $\sigma$ denote a sensitivity function for
$(k,z)$-line approximation of $X$ with total sensitivity
$\mathfrak{S}_{\sigma}$ and let $\tilde{\sigma}$ its sensitivity sampling
distribution.

  * •