Terminal Dimension Reduction for Time Series with Applications

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Terminal Dimension Reduction for Time Series with Applications

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Terminal Dimension Reduction for Time Series with Applications Alexander Munteanu∗

Matteo Russo†

David Saulpic‡

Chris Schwiegelshohn§

July 13, 2026

Abstract

arXiv:2607.09490v1 [cs.DS] 10 Jul 2026

Terminal embeddings have emerged as a powerful tool for dimension reduction. Given a set of points P ⊂ Rd , a terminal embedding is a mapping f : Rd → Rt that preserves the pairwise distance between any pair of points p ∈ P and q ∈ Rd up to small distortion under this mapping. Terminal embeddings have been particularly fruitful for constructing k-means and k-median coresets, where the objective is to find a typically weighted subset Ω of P such that for any candidate solution, the cost of the clustering objective on Ω approximates the cost of the clustering objective on P up to small distortion. Unfortunately, these techniques have not been extended to more complicated structures such as clustering time-series data under common straight-line interpolation between measurements. The main issue is that terminal embeddings, arguably the central technique in this line of research, cannot be linear and are thus not immediately suitable to preserve linear structures. In this work, we develop a generalization of terminal embeddings to affine line-segments that overcomes this issue. We showcase their applicability by using our lines-preserving terminal embeddings to obtain the first dimension-free coresets for clustering time-series under the Fréchet distance. The underlying dimension reduction uses Johnson-Lindenstrauss (JL) embeddings, and our experiments indicate that terminal embeddings perform similarly to JL and favorably against PCA for synthetic and real-world time-series, while only terminal embeddings extend pairwise distance preservation to the full ambient space. Keywords: dimension reduction, terminal embeddings, time-series, Fréchet distance, coresets

∗

TU Dortmund, Germany EPFL, Switzerland ‡ CNRS & Université Paris Cité, IRIF, Paris, France § Aarhus University, Denmark †

Contents 1 Introduction 1.1 Goals and Problem Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Our Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 3 4

2 Preliminaries

3 Terminal Embeddings for Polygonal Curves

4 Experimental Illustration

A Further Related Work

B Omitted Proofs of the Main Part

C Coresets for Clustering Polygonal Curves under the Fréchet Distance C.1 Improved Coreset Size Bounds for the Cohen-Addad et al. [2021] Framework . . . . C.2 Centroid Sets for the Fréchet Distance . . . . . . . . . . . . . . . . . . . . . . . . . . C.3 A Warm Up: Parallel Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.3.1 Set Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.3.2 Construction of γe for Parallel Lines . . . . . . . . . . . . . . . . . . . . . . . . C.4 General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.4.1 Construction of N C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.4.2 Proof of Lemma C.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.4.3 Construction of γe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.4.4 Dealing with Border Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.4.5 Putting Everything Together: N C is an Approximate Centroid Set . . . . . .

21 22 23 24 24 24 26 26 26 27 29 31

D An Improved Coreset Construction Framework via Chaining D.1 Outline of the Argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Preliminary Facts and Considerations on Groups . . . . . . . . . . . . . . . . . . . . D.3 Group Sampling Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.4 The Cheap Group Doesn’t Matter . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.5 Coreset Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.6 Groups Estimates via Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.7 Estimating ∥v G,S − uG,S ∥1 : A Gaussian Process to Estimate Groups Costs . . . . . . D.7.1 Chaining for Main Groups GM . . . . . . . . . . . . . . . . . . . . . . . . . . D.7.2 Chaining for Outer Groups GO . . . . . . . . . . . . . . . . . . . . . . . . . . D.8 Estimating ∥uG,S ∥1 : Huge and Far Clusters Estimates . . . . . . . . . . . . . . . . . D.8.1 Analysis for Huge Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.8.2 Analysis for Far Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31 31 36 38 38 40 42 44 45 49 50 50 52

Introduction

Time-series and panel data are ubiquitous in the analysis of physical sensor networks, geo-, and weather-information systems, price forecasting, and the stock market [e.g. Zhang et al., 2007, Chapados and Bengio, 2008, Lucas et al., 2015, Zimmer et al., 2018, Huang et al., 2020, 2021, Wang et al., 2025]. Often one is not only interested in single-dimensional time-series, that represent one stock or one physical measurement, such as temperature, over time. Rather, we would like to model a large portfolio of stocks, or entire markets. Similarly, we are interested to combine all kinds of weather information into one single high-dimensional measurement at every time instant, to obtain high-dimensional time-series that represent and provide a holistic perspective on weather development over time. For standard machine learning approaches to work for such data, we face two main challenges, [cf. Paparrizos et al., 2024]: First, clustering algorithms were initially developed only for vectors. Standard vector embeddings fail to adequately model even one-dimensional time-series in the presence of asynchronous or missing measurements. Vector encodings of higher-dimensional time-series are even more problematic. Second, resources such as runtime, memory and sample complexity depend heavily on the volume and dimension of the data. As a solution to the first challenge, the fields of theoretical computer science and computational geometry model time-series data as polygonal curves. These connect single measurements or vertices by straight-line connections that implicitly interpolate linearly along the continuous timeline. Building upon this representation, they introduced clustering algorithms for time-series under the Fréchet distance with rigorous guarantees [Driemel et al., 2016], though initially limited to one-dimensional time-series. An intriguing direction thus remained open, namely an extension and dimension reduction for high-dimensional time-series to address the second of the above challenges. First random projections for preserving the Fréchet distance appeared in [Driemel and Krivosija, 2018], followed by a Johnson-Lindenstrauss (JL) equivalent for preserving pairwise distances between curves representing time-series [Meintrup et al., 2019]. Albeit with additive errors, this enabled efficient algorithms for metric k-median under the Fréchet distance, where centers were restricted to be input curves. Recently, the analysis was refined [Psarros and Rohde, 2023, 2025] to obtain multiplicative errors for preserving pairwise distances by applying JL-embeddings [Johnson and Lindenstrauss, 1984] to a skeleton of the curves. However, the method remained restricted to discrete clustering objectives, and estimating the clustering cost. To the best of our knowledge, no terminal embeddings exist for the problem, and these are the missing key to remove dimension dependence in continuous clustering of time-series and in data reduction via coresets. Terminal embeddings were originally introduced by [Elkin et al., 2017] and have emerged as an important tool for dimension reduction. Given a set of n points P ∈ Rd , a terminal embedding with distortion (1 ± ε) is a mapping f : Rd → Rt ensuring for any p ∈ P and q ∈ Rd , we have (1 − ε)∥p − q∥ ≤ ∥f (p) − f (q)∥ ≤ (1 + ε)∥p − q∥, 1/2

where ∥x∥ = ( di=1 x2i ) denotes the Euclidean norm. This guarantee is remarkably similar to the JL-lemma, where both p and q are terminals, i.e., elements of P . But in fact it is significantly stronger: in terminal embeddings, q may be an arbitrary query point from the ambient space. For points in Rd , a series of results [Elkin et al., 2017, Mahabadi et al., 2018] ultimately led to optimal terminal embeddings with reduced target dimension t = Θ(ε−2 log n) [Narayanan and Nelson, 2019, Cherapanamjeri and Nelson, 2024], matching lower bounds that even hold against the weaker JL-guarantee [Larsen and Nelson, 2017, Alon and Klartag, 2017]. The stronger guarantee given by terminal embeddings gave rise to several applications. Notably, terminal embeddings are at the forefront of data summaries known as coresets [Feldman, 2020, P

Munteanu and Schwiegelshohn, 2018] for the important k-means and k-median problems. Given a loss function cost(P, C), where C is a candidate solution, an ε-coreset is a (typically weighted) subset Ω ⊆ P such that cost(P, C) = (1 ± ε) cost(Ω, C), (1) for all candidate solutions C. For the (k, z)-clustering problem, specifically, C is a set of at most k P points and we have cost(P, C) = p∈P minc∈C ∥p − c∥z , where the special case z = 1 corresponds to k-median and z = 2 corresponds to k-means. Terminal embeddings have played a central role in constructing dimension independent coresets [Becchetti et al., 2019,Braverman et al., 2022, 2021, Huang and Vishnoi, 2020], including the optimal coreset bounds Õ kε−2 min(ε−z , k z/(z+2) ) due to [Cohen-Addad et al., 2022b, Huang et al., 2024]. Recently, terminal embeddings led to dimension-free learning rates for k-means/median for points, and for curves under discrete DTW and Fréchet distances [Bucarelli et al., 2023, Cohen-Addad et al., 2025b, Krivosija et al., 2025]. As remarked in [Huang and Vishnoi, 2020], the standard JL-guarantee seems insufficient to recover any of the above bounds, making terminal embeddings an indispensable technique for several algorithmic applications that crucially rely on strong dimension reduction guarantees. Unfortunately, the added power of terminal embeddings comes at a cost: the mapping f cannot be linear. To see this, consider that if f : Rd → Rt were a linear mapping and t < d, then there must exist a non-zero vector v in the nullspace of f . The difference vector p − q between any point p ∈ P to q := p + v ∈ Rd , whose norm is the non-zero distance that we would like to preserve, is thus mapped to 0, precluding any multiplicative approximation. If we only require the weaker JL-guarantee, the mapping can however be linear; indeed most efficient JL-variants are typically sampled from a distribution over random Gaussian or Rademacher matrices. This aspect of JL-transforms has made it a popular technique for many applications in randomized numerical linear algebra such as low-rank approximation and regression [Woodruff, 2014]. While research on both sketching algorithms for numerical linear algebra and coreset algorithms via terminal embeddings for clustering points have seen substantial progress and success for many tasks, there exists a collection of problems for which our knowledge of dimension reduction methods is currently less well developed. One specific example, which we want to focus in the remainder, is clustering time-series under the Fréchet distance. Given the importance that terminal embeddings have for point clustering objectives, the lack of progress can primarily be attributed to the lack of terminal embeddings for lines and line-segments. Unfortunately line-segments are linear structures and – as mentioned earlier – terminal embeddings are inherently non-linear. We thus ask the intriguing open research question: Can the framework of terminal embeddings be extended to preserving distances between lines and polygonal curves lying in d-dimensional Euclidean ambient space?

1.1

Goals and Problem Setting

The main goal of our work is to introduce new techniques that extend the guarantees of terminal embeddings for points to the setting of high-dimensional time-series. To this end, we aim to develop a terminal embedding framework for affine lines and polygonal curves in Rd . A polygonal curve π of complexity m can be formalized as an ordered sequence of vertices (p0 , . . . , pm ) ∈ Rd , where consecutive pairs of vertices are connected by straight-line segments. We view a polygonal curve π : [0, 1] → Rd by fixing m + 1 values 0 = t0 < . . . < tm = 1 such that t−ti π(ti ) = pi and defining π(t) = (1 − λ)pi + λpi+1 where λ = ti+1 −ti for ti ≤ t ≤ ti+1 . The (continuous) 2

Fréchet distance between two curves π1 and π2 is then defined as dF (π1 , π2 ) = inf

sup ∥π1 (α(t)) − π2 (β(t))∥,

α,β∈T t∈[0,1]

where T ⊆ {f : [0, 1] → [0, 1]} is a set of continuous, non-decreasing, and surjective mappings, that are called reparameterizations. Note that the straight-line segments of a polygonal curve are continuous connected compact subsets (closed intervals) in a collection of affine lines. Akin to JL-mappings, known constructions of standard point terminal embeddings do not apply to terminal sets of unbounded cardinality. We thus introduce the following generalization. Definition 1.1 (Terminal Embeddings for the Fréchet Distance). Let P be a set of n polygonal curves in Rd of complexity at most m and let Qℓ be the set of polygonal curves in Rd of complexity at most ℓ. A mapping f : Rd → Rt is an (ε, m, ℓ)-preserving terminal embedding for the Fréchet distance, if for all curves σ ∈ P and τ ∈ Qℓ it holds that dF (f (σ), f (τ )) = (1 ± ε) dF (σ, τ ) .

1.2

Our Results

We aim at terminal embeddings for preserving the Fréchet distance between high-dimensional time-series represented as polygonal curves. Instead of points, terminals as well as queries are (collections of) line-segments, requiring a different construction of the terminal embedding. We state our main result regarding terminal embeddings for curves with respect to the Fréchet distance. Theorem 1.2. There exist (ε, m, ℓ)-preserving terminal embeddings for the Fréchet distance with target dimension t ∈ O(ℓε−4 log(nm)). Consider (k, ℓ, z)-clustering under the Fréchet distance as an application. In light of Equation (1), the loss function is cost(P, C) =

X σ∈P

min dF (σ, τ )z , τ ∈C

where the |C| = k center curves τ ∈ C ⊆ Qℓ , have restricted complexity at most ℓ. Algorithms and coreset constructions for this problem received considerable attention recently [Braverman et al., 2022, Conradi et al., 2024, Cohen-Addad et al., 2025a]. The best existing coreset are built via an algorithm whose success rely solely on the existence of small enumerations over all candidate clusterings [Cohen-Addad et al., 2025a]. The terminal embeddings given in Theorem 1.2 allow, in a black-box manner, to remove the dependence on the dimension of those small enumeration. This black-box application yields the first dimension-free coresets of size Õ(k · ε−5−z · ℓ2 · log2 m). Unfortunately, such a naïve application degrades the dependence on the precision parameter ε severely from ε−1−z to ε−5−z . However, we improve the size bounds of the coreset construction framework due to Cohen-Addad et al. [2021], and hereby refine the coreset analysis to directly incorporate our terminal embedding, avoiding the additional loss. Again, this framework relies only on the existence of small enumerations over candidate clusterings, and does not need to actually compute them, and in particular it does not need to build the terminal embedding. This ultimately leads us to the following result.

Table 1: Resulting coreset sizes of applying our main result Theorem 1.2 to the (k, ℓ, z)-clustering problem on polygonal curves of complexity at most m and center curves of complexity at most ℓ under z-th power of Fréchet distance, and comparison to previous work.

Reference

Authors & Venue Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, Wu (FOCS’22) Cohen-Addad, Saulpic, Schwiegelshohn (FOCS’23) Conradi, Kolbe, Psarros, Rohde (SoCG’24) Cohen-Addad, Draganov, Russo, Saulpic, Schwiegelshohn (SODA’25) Our results (here)

Coreset Size

[Braverman et al., 2022]

Õ(k 3 · ε−3 · d · ℓ · log m)

[Cohen-Addad et al., 2023]

Õ(k 2 · ε−3 · d · ℓ · log m)

[Conradi et al., 2024]

Õ(k 2 · ε−2 · log n · d · ℓ · log m)

[Cohen-Addad et al., 2025a]

Õ(k · ε−1−z · d · ℓ · log m)

Direct application of Theorem 1.2

Õ(k · ε−5−z · ℓ2 · log2 m)

Final result in Theorem 1.3

Õ(k · ε−2−z · ℓ2 · log2 m)

Theorem 1.3. Given a set P of n curves in Rd of complexity m, there exists an ε-coreset of size Õ(kε−2−z ℓ2 log2 m) for (k, ℓ, z)-clustering under the Fréchet distance, with center curves in Rd of complexity at most ℓ. Notably, this bound is optimal for constant ℓ and m, as it recovers the optimal coreset bounds Ω(kε−2−z ) for (k, z)-clustering with centers being points [Huang et al., 2024, Zhu et al., 2024] whenever k ≫ ε−1 . Interestingly, coresets for clustering under the Fréchet distance was one of the only settings for which the framework of Cohen-Addad et al. [2021] failed to provide state-of-the-art bounds: our construction therefore provides the missing link and strengthens this framework. An overview and comparison of our result with previous results is given in Table 1 and details on related work can be found in Section A.

1.3

Our Techniques

Review of Terminal Embedding Constructions. Let us first review how normal terminal embeddings are constructed. That is, given a finite set of points P ⊂ Rd , we wish to preserve distances between any p ∈ P and any q ∈ Rd . The image Rt of the mapping f maps Rd to Rt−1 via a JL-type of embedding (typically a matrix of i.i.d. Gaussians or Rademachers) and adds one ancillary coordinate. For preserving distances between pairs of input points in P , we know that defining f to be the image of the JL-embedding along the first t − 1 coordinates suffices, and we can simply set the ancillary coordinate to 0. The embedding of an arbitrary point q can then be computed via semidefinite programming [Mahabadi et al., 2018, Narayanan and Nelson, 2019], typically resulting in the ancillary coordinate being non-zero. An alternative is to embed q as follows: find its nearest neighbor p in the input set and define f (q) = f (p) on the first t − 1 coordinates, and set the ancillary coordinate to ∥p − q∥. However, this simple trick only preserves distances up to a factor of 2 [Elkin et al., 2017]. In addition, such embeddings are far from preserving affine lines, as they exhibit strong discontinuities. Before continuing with the key steps of our analysis, we emphasize one specific novelty of our terminal embeddings: they are piecewise-linear. Their construction avoid sophisticated techniques such as solving semidefinite programs or building nearest neighbor data structures as in previous work [Mahabadi et al., 2018, Narayanan and Nelson, 2019, Cherapanamjeri and Nelson, 2024]. Our novel constructions thus enhance the simplicity of available algorithms as they merely rely 4

on oblivious random projections and data dependent orthogonal projections to low-dimensional subspaces. Terminal Embeddings for the Fréchet Distance. We actually aim for a stronger guarantee than just preserving the Fréchet distance. Observe that a polygonal curve of complexity ℓ is a sequence of ℓ line-segments, which is a subset of a collection of ℓ affine lines. Our goal is to preserve the distance between an arbitrary point on any input line-segment – belonging to one of the curves in P – to any possible point in any affine line that contains a line-segment of a query curve. Clearly, aiming for this stronger guarantee implies that the Fréchet distance is also preserved, since the Fréchet distance relies only on a subset of the point pairs whose distances are preserved. When attempting to extend the previous approaches for terminal embeddings to lines or linesegments, we can rely on the property that projecting with Gaussian matrices also preserves distances to subspaces. More specifically, given an arbitrary but fixed 1-dimensional affine query subspace V (i.e. an affine line) it is immediate from Lemma 2.1 (with j = O(1)) that if the number of columns of a Gaussian matrix S is in the order of O(ε−2 log(nm/δ)), then with probability at least 1 − δ, it holds for any point on a line of the input p ∈ P and any point on the query line q ∈ V that ∥S(p − q)∥ = (1 ± ε)∥p − q∥ .

(2)

The immediate idea of extending this guarantee by enumerating all possible 1-dimensional affine subspaces of Rd , and setting δ sufficiently small to apply a union bound over all of them clearly cannot work. Similarly to the case of points, as long as the rank of S is less than d, there exists an affine line V for which Equation (2) does not hold. Let us characterize the boundary cases when Equation (2) holds and when it might not hold. Denote by VP the set of affine lines spanned by point pairs in P , where we represent any line L as an orthonormal basis matrix V = [v0 , v1 ] ∈ Rd×2 , so that L is included in the span of v0 , v1 . Note that many lines could be represented by the same matrix, but preserving distances to any point in the columnspan of V is stronger than merely to L, and linear subspaces are analytically more tractable than affine lines. While we cannot extend the guarantee of Equation (2) to all lines in Rd , we can do a union-bound over all lines in VP : hence, we know that all distances between points in P and any point on a line V ∈ VP can be preserved with high probability. Now, intuitively, it seems that this should also be true for any query V ′ that is sufficiently close to some line V ∈ VP . Specifically, if there exists V ∈ VP such that for all p ∈ P ∥V ′T (I − V V T )p∥ ≤ ε · ∥(I − V V T )p∥ · ∥(I − V ′ V ′T )p∥ ,

(3)

then we can show that the Gaussian matrix also preserves distances between points p ∈ P on input lines and points q ∈ V ′ on the query line within the desired precision. More precisely, ∥(I − V ′ V ′T )p∥ is the minimum distance of p to any point of the subspace spanned by the line V ′ and Equation (3) ensures that there exists no vector v ′ on the line V ′ for which v ′T p is significantly different from v T p; in other words, V and V ′ are approximately aligned. When Equation (3) does not hold, suppose in the other extreme, that the line V ′ is orthogonal to any line V ∈ VP , and thus orthogonal to the entire span of line-segments in P . This situation can simply be handled using two ancillary coordinates: using the Pythagorean theorem, it holds that ∥p − q∥2 = ∥p∥2 + ∥q∥2 for any p ∈ P and q on the line V ′ . We can thus simply embed the entire line V ′ along the ancillary coordinates. Since we may assume that ∥Sp∥2 = (1 ± ε)∥p∥2 for all p ∈ P and the embedding of the line V ′ remains orthogonal to P , this immediately implies that ∥p − q∥2 is preserved up to a factor (1 ± ε). 5

Unfortunately, there is a significant gap between the two extreme cases sketched above, where a candidate line V ′ is either nearly identical to some line V ∈ VP or nearly orthogonal to all lines in VP . To overcome this gap, the main idea is to cover V ′ with a small union of lines in VP – in the sense that V ′ is close to the span of this union – such that if V ′ is not included in the cover up to small distortion, then it must be nearly orthogonal to all V ∈ VP . Our covering has some relationship with ε-nets for high-dimensional Euclidean balls, but it has a much stronger guarantee: in case of an ε-net, we would only obtain ∥V ′T (I − V V T )p∥ ≤ ε · ∥(I − V V T )p∥ which would only yield ∥p − q∥ = (1 ± ε)∥f (p) − f (q)∥ + ε · ∥p∥, i.e., an additive error approximation, while our covering yields the desired multiplicative error approximation guarantee ∥f (p) − f (q)∥ = (1 ± ε)∥p − q∥ . The size of a cover to enforce Equation (3) for a single line is only O(ε−2 ), but to extend our argument to the entire query, we need to construct a cover for each of ℓ lines in the query curve Q ∈ Qℓ . We then use the Gaussian matrix to preserve the distance between any p ∈ P and any point q ′ in the span of the cover. The remaining parts of V ′ ∈ Q that are (nearly) orthogonal to the cover are then embedded along O(ℓ) ancillary coordinates. Applications. An application of our terminal embedding is a new coreset construction for (k, ℓ, z)clustering of polygonal curves under the Fréchet distance. As mentioned earlier, at this stage in coreset research, we have a variety of frameworks that only leave the existence of small enumerations over candidate clusterings as a problem specific open question. Their mere existence is enough to guarantee the success of coreset algorithms. For describing our enumeration, let us first focus on a simple case: if the vertices of a candidate center curve are all close to a vertex in the union of input curves, then we can approximate the placement of the center curve’s vertices via standard discretization arguments for covering Euclidean balls. The more challenging task is to extend this construction to the case where we have a very long line-segment as part of a curve. Then a center curve may place a vertex somewhere along this line-segment, and this vertex may determine the Fréchet distance. This issue posed a problem with previous attempts at obtaining good dimension reduction methods for the Fréchet distance, see for example [Meintrup et al., 2019]. The easiest way to address this, is to discretize the long line-segments themselves and derive a coreset construction depending on bit complexity. An alternative, more commonly used in coreset construction, is based on using combinatorial measures such as the VC-dimension to enumerate over the set of all curves. This enumeration reduces the number of clusterings to roughly exp(k log k · d · ℓ · log m), see [Driemel et al., 2021, Brüning and Driemel, 2023, Cheng and Huang, 2024]. Even with the best available analysis of a VC-dimension driven approach [Cohen-Addad et al., 2025a], the authors could not do better than to replace d with our new target dimension, which fails to achieve a better than Õ(kε−5−z ℓ2 log2 m) coreset size. We address the challenge of enumeration by reducing the problem up to constants to the case where long line-segments of the center curve are parallel to some line-segment of the input. This enables an explicit enumeration in which we can parameterize our dimension reduction gradually. As a result, we obtain a sequence of increasingly finer enumerations. We can now perform a chaining analysis using this sequence, leading to tighter bounds on the metric entropy, akin to constructions that yield optimal coresets for k-median and k-means [Bansal et al., 2024, Cohen-Addad et al., 2022b, Huang et al., 2024, Zhu et al., 2024]. Integrating our terminal embeddings for the Fréchet distance into this construction finally leads to a coreset size bound of Õ(kε−2−z ℓ2 log2 m), that is optimal assuming ℓ and m are small, as the dependence on k and ε matches recent Ω(kε−2−z ) lower 6

bounds [Huang et al., 2024, Zhu et al., 2024] that hold whenever k ≫ ε−1 .

Preliminaries

For any non-negative numbers a and b, we use a = (1 ± ε) b to denote (1 − ε) b ≤ a ≤ (1 + ε) b. Given a set of points P , the linear subspace Q spanned by P is the set of all points that can be written as linear combinations of points in P . We say that a matrix U is an orthonormal basis of Q if each column of U has unit Euclidean norm, the columns of U are pairwise orthogonal, and the P columns of U span Q. For any vector x ∈ Rd , we denote its Euclidean norm by ∥x∥ = ( di=1 x2i )1/2 and the Euclidean distance between x, y ∈ Rd by ∥x − y∥. For any matrix X ∈ Rn×d we denote its spectral norm by ∥X∥2 = maxy∈Rd ,y̸=0 ∥Xy∥/∥y∥. We will use the notion of a subspace preserving sketch given in the following Lemma. Lemma 2.1 (Subspace preserving sketch [Woodruff, 2014]). Let ε, δ > 0 and let c be some absolute constant. There exists a distribution D over random r × d matrices such that if S ∼ D and r ≥ c · ε−2 · (j + log(1/δ)), then for any fixed matrix U ∈ Rd×j with orthonormal columns it holds with probability at least 1 − δ that S is a subspace preserving sketch for U . I.e., it holds that ∥U T U − U T S T SU ∥2 ≤ ε. We remark that the property of a subspace preserving sketch dates back to Sarlós [2006], and D is often chosen to be a distribution over matrices with i.i.d. Gaussian or Rademacher entries, √ rescaled by a factor 1/ r, [cf. Clarkson and Woodruff, 2009, Woodruff, 2014]. We note that sparser projections also exist that can be computed faster at the cost of a negligibly worse target dimension. We refer the interested reader to appropriate references [Kane and Nelson, 2014, Cohen, 2016, Chenakkod et al., 2024]. However, not all these variants yield advantages for the parameterizations considered in our paper; see Section 3 for more discussion.

Terminal Embeddings for Polygonal Curves

We are given a set of n polygonal curves of complexity at most m lying in d-dimensional Euclidean space. We will denote by P the set of input curves interpreted as the collection of all points lying on any of these input curves. We use Qℓ to denote the set of all polygonal curves of complexity at most ℓ. For the sake of presentation, we split into a mapping f acting on the input curves and g acting on the query curves. Both map Rd → Rt , so they can be combined to comply with Definition 1.1. We wish to construct a terminal embedding of the curves in P and query curves Qℓ that preserves the Fréchet distance with target dimension t. That is, we seek embeddings f, g : Rd → Rt such that for any curve σ ∈ P and any query τ ∈ Qℓ , • f maps σ to a curve of the same complexity m and g maps τ to a curve of the same complexity ℓ, and • dF (f (σ), g(τ )) = (1 ± ε) dF (σ, τ ). We restate our main theorem and prove it below. Theorem 1.2. There exist (ε, m, ℓ)-preserving terminal embeddings for the Fréchet distance with target dimension t ∈ O(ℓε−4 log(nm)). In fact, we will show a slightly more general result. We develop a dimension reduction that preserves distances from any point contained in line-segments of the input curves, to any point contained in the affine 1-dimensional subspaces, each induced by a line in a set of queries (possibly, 7

though not necessarily line-segments of a curve). To this end, for any line-segment in the query starting at point q1 and ending at point q2 , we let q be the affine 1-dimensional subspace that contains q1 and q2 . An entire set of ℓ affine 1-dimensional subspaces in the query will be denoted Qℓ . Specifically, we wish to find mappings f, g that act linearly on P, Qℓ , and show that for any point a contained in any line-segment of any curve in P and any point b contained in any affine 1-dimensional subspace q ∈ Qℓ , we have ∥f (a) − g(b)∥2 = (1 ± ε) · ∥a − b∥2 . Notice that this immediately implies that ∥f (a) − g(b)∥z = (1 ± ε) · ∥a − b∥z , when we rescale ε by a factor O(z); we thus focus on z = 2. Because f is linear on P and g on Qℓ , they preserve the complexity of curves: the image of a query curve Qℓ is a polygonal curve with complexity (at most) ℓ, and the image of an input curve in P has complexity (at most) m. Since all possible distances between points on two curves are hereby preserved up to (1 ± ε), it preserves in particular any distance between points matched by any reparameterization of the curves. This finally implies that the supremum that determines the continuous Fréchet distance is preserved up to a (1 ± ε) factor as well. We start with the following technical lemma. Lemma 3.1. Let V ⊆ Rd be an arbitrary set. For any set S ⊆ Rd , there exists a set SV ⊆ V , with |SV | = O(|S| · ε−2 ) and a corresponding matrix U with orthonormal columns that form a basis for the span of SV , such that ∀v ∈ V, s ∈ S : |v T (I − U U T )s| ≤ ε · ∥(I − U U T )v∥ · ∥s∥. Proof. Without loss of generality, let the vectors s ∈ S have unit Euclidean norm. The claim then follows for arbitrary vectors by scaling. We initialize S0 = ∅ and proceed in rounds. For a set Si , we define a matrix Ui with orthonormal columns that form a basis for the span of Si . If in round i, there exists a vector vi ∈ V such that T T |viT (I − Ui−1 Ui−1 )s| > ε · ∥(I − Ui−1 Ui−1 )vi ∥,

we say that there was a violation for s in round i, and add the point ui /∥ui ∥ to Ui−1 , where T )v . Suppose we have r rounds of violations for s. Note that u is orthogonal to ui = (I − Ui−1 Ui−1 i i the span of all previously added vectors. Thus, due to the Pythagorean theorem, we have 1 = ∥s∥ ≥ ∥Ur s∥ ≥ 2

X violation in round i∈{1...r}

T )s| |viT (I − Ui−1 Ui−1 T )v ∥ ∥(I − Ui−1 Ui−1 i

> r · ε2 .

Thus, we have that r ≤ ε−2 for any single s ∈ S. Overall, this implies that after at most |S| · ε−2 many rounds of violations, the claim of our lemma must hold. Our goal will be to find a low-dimensional subspace and the associated projection matrix Π that projects points onto this subspace with the properties given in the following lemma. Lemma 3.2. Let P be a set of n curves of complexity at most m. For any fixed query Qℓ of at most ℓ affine 1-dimensional subspaces, there exists a projection matrix Π onto the span of at most O(ℓε−2 ) line-segments of curves in P such that for all a ∈ P and any b ∈ q for q ∈ Qℓ , it holds that ∥a − b∥2 = (1 ± ε) ∥Π(a − b)∥2 + ∥(I − Π)a∥2 + ∥(I − Π)b∥2 8

This key lemma is proven in Section B. Some technical details may differ slightly from the high-level idea discussed in Section 1.3. The following result leans itself immediately. Corollary 3.3. Let P be a set of n curves of complexity at most m. Then there exists a collection −2 C of at most |C| = exp O(ℓε log(nm)) projection matrices with the following properties. 1. Each projection matrix Π ∈ C maps to a subspace that lies in the span of at most O(ℓε−2 ) line-segments of P . 2. For any set Qℓ of at most ℓ affine 1-dimensional subspaces, there exists Π ∈ C satisfying the properties asserted by Lemma 3.2. n·m Proof. There are ℓ·ε −2 many choices of Π, as we add both offset and direction of the affine line containing a point added in any repetition resp. iteration of Lemma 3.1. Therefore, there are n·m −2 · log(nm)) possible subspaces overall. (n · m) · ℓ·ε ≤ exp O(ℓ · ε −2

We are finally ready to prove our main result: Proof of Theorem 1.2. The embedding f acts only on the input P . It consists of a subspace preserving random projection matrix S (see Lemma 2.1) with a target dimension r that we will specify later. We denote these r coordinates by C1 . For the mapping g that acts on the query curves Qℓ , we have 2ℓ ancillary coordinates denoted by C2 . The total embedding target dimension is thus t = r + 2ℓ. Now, we describe how to accomplish the embedding f : P → Rt . Any input point a ∈ Rd , that is, any point contained in one of the input line-segments of curves in P , is mapped by f to Sa for the r coordinates in C1 and to 0 for all ancillary coordinates in C2 . For the embedding g : Rd → Rt the construction is more intricate. For any fixed curve Qℓ ∈ Qℓ , Item 1 of Corollary 3.3 yields the existence of a subspace Π ∈ C spanned by at most O(ℓ · ε−2 ) points. Then g maps the points b ∈ Qℓ lying on line-segments of Qℓ via SΠb for the coordinates in C1 . In addition, we map (I − Π)b to the coordinates in C2 . To see that both mappings are (piece-wise) linear, note that f is merely a random linear projection of the input curves in P . For the query curve Qℓ , and any b ∈ Qℓ , the mapping g consists of two projections SΠb and (I − Π)b that are both linear mappings to the coordinates C1 and C2 , respectively. Error Guarantee. Assuming that S is a subspace preserving sketch (see Lemma 2.1) simultaneously for all Π ∈ C and for every line-segment in P containing a point a, then ∥S(a − Πb)∥2 = (1 ± ε) · ∥a − Πb∥2

= (1 ± ε) · ∥(I − Π)a∥2 + ∥Π(a − b)∥2 .

(4)

By Item 2 of Corollary 3.3 each Π ∈ C satisfies the equation asserted in Lemma 3.2. Moreover, (I − Π)b is contained in a 2ℓ-dimensional subspace, so our mapping of (I − Π)b to the ancillary coordinates C2 preserves ∥(I − Π)b∥2 exactly. We thus conclude ∥f (a) − g(b)∥2 = ∥S(a − Πb)∥2 + ∥(I − Π)b∥2 (4)

= (1 ± ε) ∥(I − Π)a∥2 + ∥Π(a − b)∥2 + ∥(I − Π)b∥2

(3.2)

= (1 ± ε)2 ∥a − b∥2 = (1 ± 3ε) ∥a − b∥2 . 9

The desired (1 ± ε) approximation now follows by rescaling ε by a factor 3. The conclusion for preserving the Fréchet distance follows because the distances between any points on two curves that can possibly be mapped to each other via reparameterizations, are a subset of the distances preserved up to a factor (1 ± ε) by our embedding; the supremum that determines the Fréchet distance is thus also preserved. Target Dimension. Our arguments require a subspace preserving sketch (Lemma 2.1) for all segments of the input curves in P . There are O(nm) segments, and each of them lies in a 2-dimensional linear subspace. Using Lemma 2.1 and a union bound, we thus need only O(ε−2 log(nm/δ)) dimensions to embed all of them. Simultaneously, the subspace preserving sketch is required to hold for all possible subspaces of dimension bounded by O(ℓε−2 ) defined by Π ∈ C (see Corollary 3.3), which clearly dominates the embedding dimension. Setting the target dimension to

r ≥ c · ε−2 · ℓ · ε−2 + log exp ℓ · ε−2 · log(nm) /δ

for some absolute constant c and using Lemma 2.1 then guarantees that Equation (4) holds for all choices of Π ∈ C and all choices of a ∈ P and b ∈ Qℓ ∈ Qℓ with probability 1 − δ. Combining this with the 2ℓ coordinates of C2 ultimately yields the desired target dimension t ∈ O ℓ · ε−4 log(nm) + ε−2 log δ −1 . Running Time. We first emphasize the fact that most applications of terminal embeddings, in particular their application to coresets we focus on below, only require the existence of such an embedding and do not need an explicit construction. Nevertheless, it is possible to obtain the embeddings with reasonable efficiency. We state the running time for the specific range of parameters we studied here. Proposition 3.4. Let P be a set of n polygonal curves of complexity m. Consider the mappings f, g realizing the terminal embedding of Theorem 1.2. The mapping f (a) for any point a ∈ P , can be computed in time O(dℓε−4 log(nm)). For a given query polygonal curve Qℓ of complexity ℓ, the mapping g can be precomputed in time O(nmdℓ2 ε−6 log(nm)). Then g(b) for any b ∈ Qℓ can be computed in time O(dℓε−2 ). Proof. The mapping f (a) can be realized as an oblivious JL-transform Sa in time O(td) = O(dℓε−4 log(nm)). To compute the embedding g for a specific query Qℓ consisting of up to ℓ line-segments (or a collection of ℓ affine lines), the embedding algorithm needs to construct Π = U U T as asserted by Lemma 3.2 which works by executing the steps of Lemma 3.1 for nm choices of v, and ℓ choices of s. We thus have at most ℓ repetitions with r ≤ ε−2 iterations each, in

T )s v T (I−Ui−1 Ui−1 , T i−1 Ui−1 )vi ∥

i which we update Ui . In each iteration, we first compute the point pi = argmaxvi ∥(I−U

which takes time O(nmdi), since the rank of Ui−1 is i − 1. Subsequently, we update the basis T )p (I−Ui−1 Ui−1 i . T U i−1 i−1 )pi ∥

Ui to the subspace spanned by Ui−1 and ui = ∥(I−U

This takes time O(di), as we

T )p and normalize. The running time O(nmdℓ2 ε−4 ) for the merely have to compute (I − Ui−1 Ui−1 i construction of U then follows by summing these terms up over all ℓε−2 iterations. Now we can precompute SU in time O(tdℓε−2 ) = O(dℓ2 ε−6 log(nm)) which leads to O(O(nmdℓ2 ε−6 log(nm))) overall. Using standard multiplication, computing SΠb = (SU )(U T b) takes time O(dℓε−2 + tℓε−2 ), and (I − Π)b = b − U (U T b) takes time O(dℓε−2 + d). Since t < d, this results in a total running time of O(dℓε−2 ).

The proof focuses on dense-JL and standard matrix multiplication for simplicity; using improved JL-constructions or fast matrix multiplication improves the performance straightforwardly. The dependence on ε, for instance, can be improved to obtain a running time of O(ε · ndt) using sparse JL-transforms [Kane and Nelson, 2014, Høgsgaard et al., 2024]. Sparse subspace embeddings can also be applied, if the failure probability is small enough [Cohen, 2016, Chenakkod et al., 2024]. We remark that O(1)-sparse embeddings [Clarkson and Woodruff, 2013, Meng and Mahoney, 2013, Nelson and Nguyên, 2013] do not apply as they do not allow a union bound over exponentially many subspaces. Application to Coresets for Clustering under the Fréchet Distance. As discussed before and can be seen in Table 1, a direct application of our Theorem 1.2 to remove the dimension dependence in the best previous coreset construction of Cohen-Addad et al. [2025a] yields Õ(k · ε−5−z · ℓ2 · log2 m). The proof of Theorem 1.3 improves this to Õ(k · ε−2−z · ℓ2 · log2 m), optimal in both, k, ε, by integrating our terminal embedding more directly in an improved chaining coreset construction framework, originally due to Cohen-Addad et al. [2021]. The extensive details – in particular, how to build the approximate centroid set that allows to discretize the set of possible centers even further, required to apply the chaining framework – are entirely in Sections C and D.

Experimental Illustration

3 1

Approximation Ratio

Computing Device. All experiments were conducted on a commodity laptop with Intel(R) Core(TM) i7-8550U CPU, 4 cores at 1.80 GHz, 16 GB DDR4-3200 RAM.

TE5

JL5

PCA5

TE10

JL10

PCA10

TE20

JL20

PCA20

Method / Target Dimension

Figure 1: Comparison of the approximation ratios (lower is better) of 120 Fréchet distances between time-series, reduced by TE vs. JL and PCA to target dimensions t ∈ {5, 10, 20}.

Dataset. We use real-world data that consists of greenhouse gas (GHG) concentrations measured at different sites across California [Lucas et al., 2015]. We construct polygonal curves, representing n = 16 different GHG concentrations, measured in m = 327 regular time periods, each taken simultaneously at d = 2921 distinct locations. Additionally, to simulate query curves that are not

part of the input, we generated n = 10 curves, and a query curve, each of length m = 5, in d = 50 dimensions. All entries of the generated vertices were Gaussian. Methods. We illustrate the performance of terminal embeddings (TE) as in Theorem 1.2 using the orthogonal projection construction of Lemma 3.1 √ followed by a Johnson-Lindenstrauss (JL) embedding using matrices with i.i.d. Gaussian N (0, 1/ t) entries reducing from the source dimension d = 50 to a target dimension t ∈ {5, 10, 20}. This is compared to the performance of standard JL for reducing all vertices of curves from the original dimension d = 2921 to a target dimension t ∈ {5, 10, 20}. As another baseline, we used principal component analysis (PCA), reducing to the same target dimensions. For TE, we provide boxplots of the approximation factors of the Fréchet distances from the query curve to the input curves. For the two baseline methods JL and PCA, we provide boxplots of the approximation factors of the Fréchet distances across all pairs of input time-series. Research Question. We remark that our terminal embeddings are based on subspace embeddings via JL-transforms [Johnson and Lindenstrauss, 1984]. JL-transforms are the de-facto standard randomized oblivious dimension reduction technique, while PCA [Pearson, 1901] is the de-facto standard deterministic data-dependent dimension reduction technique not only for high-dimensional time-series data [cf. Paparrizos et al., 2024]. We thus address the following question: How do the extended dimension reduction abilities of terminal embeddings (TE) perform in comparison to standard Johnson-Lindenstrauss (JL) transforms and in comparison to PCA for preserving the Fréchet distance between time-series? Results. The results are displayed in Figure 1. For each target dimension, we compare the resulting approximation ratios for TE against plain JL and PCA. It can be seen that all three become better as the target dimension increases. TE and JL perform consistently better than PCA across all dimensions, in particular TE and JL perform very well already at much lower target dimensions than PCA. TE perform very similarly, though slightly worse than plain JL at the same target dimension. In this context it must be noted that in contrast to plain JL and PCA, only TE can preserve the Fréchet distance to arbitrary curves in ambient space. This comes at the price of the additional approximation component induced by the orthogonal projection which results in the slightly larger approximation ratios observed in Figure 1 in comparison to plain JL. As shown in our proof of Theorem 1.2, the errors of the orthogonal projection and the subsequent JL mapping accumulate only by (1 + ε)2 ≤ (1 + 3ε). The observed additional error (over plain JL) is thus bounded by a small constant and can be compensated by increasing the target dimension according to a constant rescaling of the approximation parameter ε.

Acknowledgements C.S. is supported by a Google Research Award. A.M. is supported by the German Research Foundation (DFG) – grant MU 4662/2-1 (535889065) and by the TU Dortmund – Center for Data Science and Simulation (DoDaS).

References Noga Alon and Bo’az Klartag. Optimal compression of approximate inner products and dimension reduction. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 639–650. IEEE Computer Society, 2017. URL https://doi.org/10.1109/FOCS.2017.65. Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk. Fréchet distance for curves, revisited. In European symposium on algorithms (ESA), pages 52–63. Springer, 2006. URL http://doi.org/10.1007/11841036_8. Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, and Chris Schwiegelshohn. Sensitivity sampling for k-means: worst case and stability optimal coreset bounds. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 1707–1723. IEEE, 2024. URL https://doi.org/10.1109/FOCS61266.2024. 00106. Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma. In Symposium on Theory of Computing, STOC, pages 1039–1050, 2019. URL https: //doi.org/10.1145/3313276.3316318. Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2679–2696. SIAM, 2021. URL https://doi.org/10.1137/1.9781611976465.159. Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 462–473. IEEE, 2022. URL https://doi.org/ 10.1109/FOCS54457.2022.00051. Frederik Brüning and Anne Driemel. Simplified and improved bounds on the VC-dimension for elastic distance measures. CoRR, abs/2308.05998, 2023. URL https://doi.org/10.48550/ arXiv.2308.05998. Maria Sofia Bucarelli, Matilde Fjeldsø Larsen, Chris Schwiegelshohn, and Mads Toftrup. On generalization bounds for projective clustering. In Advances in Neural Information Processing Systems, (NeurIPS), pages 71723–71754, 2023. Maike Buchin and Dennis Rohde. Coresets for (k, ℓ)-median clustering under the Fréchet distance. In Niranjan Balachandran and R. Inkulu, editors, Algorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022, Puducherry, India, February 10-12, 2022, Proceedings, volume 13179 of Lecture Notes in Computer Science, pages 167–180. Springer, 2022. URL https://doi.org/10.1007/978-3-030-95018-7_14. Maike Buchin, Anne Driemel, and Dennis Rohde. Approximating (k,)-median clustering for polygonal curves. ACM Trans. Algorithms, 19(1):4:1–4:32, 2023. URL https://doi.org/10.1145/3559764.

Nicolas Chapados and Yoshua Bengio. Augmented functional time series representation and forecasting with gaussian processes. In Advances in Neural Information Processing Systems 20, pages 265–272. , 2008. Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, and Mark Rudelson. Optimal embedding dimension for sparse subspace embeddings. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1106–1117. ACM, 2024. URL https: //doi.org/10.1145/3618260.3649762. Siu-Wing Cheng and Haoqiang Huang. Curve simplification and clustering under fréchet distance. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 1414–1432. SIAM, 2023. URL https://doi.org/10.1137/1.9781611977554.ch51. Siu-Wing Cheng and Haoqiang Huang. Solving Fréchet distance problems by algebraic geometric methods. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4502–4513. SIAM, 2024. URL https://doi.org/10.1137/1.9781611977912.158. Yeshwanth Cherapanamjeri and Jelani Nelson. Terminal embeddings in sublinear time. TheoretiCS, 3, 2024. URL https://doi.org/10.46298/theoretics.24.6. Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 205–214. ACM, 2009. URL https://doi.org/10.1145/1536414.1536445. Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 81–90. ACM, 2013. URL https://doi.org/10.1145/2488608.2488620. Michael B. Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 278–287. SIAM, 2016. URL https://doi.org/10.1137/1.9781611974331.ch21. Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 169–182. ACM, 2021. URL https://doi.org/10.1145/3406325.3451022. Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1038–1051. ACM, 2022a. URL https://doi.org/10. 1145/3519935.3519946. Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. Improved coresets for Euclidean k-means. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing 14

Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022b. Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. Deterministic clustering in high dimensional spaces: sketches and approximation. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1105–1130. IEEE, 2023. URL https://doi.org/10.1109/FOCS57990.2023.00066. Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, and Chris Schwiegelshohn. A tight VC-dimension analysis of clustering coresets with applications. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4783–4808. SIAM, 2025a. URL https://doi.org/10.1137/1.9781611978322.162. Vincent Cohen-Addad, Silvio Lattanzi, and Chris Schwiegelshohn. Almost optimal PAC learning for k-means. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 2019–2030. ACM, 2025b. doi:10.1145/3717823.3718180. URL https://doi.org/10.1145/ 3717823.3718180. Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros, and Dennis Rohde. Fast approximations and coresets for (k, ℓ)-median under dynamic time warping. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 42:1–42:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. URL https://doi.org/10.4230/LIPIcs.SoCG.2024.42. Anne Driemel and Amer Krivosija. Probabilistic embeddings of the Fréchet distance. In Leah Epstein and Thomas Erlebach, editors, Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers, volume 11312 of Lecture Notes in Computer Science, pages 218–237. Springer, 2018. URL https: //doi.org/10.1007/978-3-030-04693-4_14. Anne Driemel, Amer Krivosija, and Christian Sohler. Clustering time series under the Fréchet distance. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 766–785. SIAM, 2016. URL https://doi.org/10.1137/1.9781611974331.ch55. Anne Driemel, André Nusser, Jeff M. Phillips, and Ioannis Psarros. The VC dimension of metric balls under Fréchet and Hausdorff distances. Discrete and Computational Geometry, 66(4):1351–1381, 2021. URL https://doi.org/10.1007/s00454-021-00318-z. Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal embeddings. Theor. Comput. Sci., 697: 1–36, 2017. URL https://doi.org/10.1016/j.tcs.2017.06.021. Dan Feldman. Core-sets: An updated survey. WIREs Data Mining Knowl. Discov., 10(1), 2020. doi:10.1002/WIDM.1335. URL https://doi.org/10.1002/widm.1335. Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, and Chris Schwiegelshohn. Sparse dimensionality reduction revisited. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https://openreview.net/forum?id=ufgVvFmUom. 15

Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1416–1429. ACM, 2020. URL https://doi.org/10.1145/3357713.3384296. Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi. Coresets for regressions with panel data. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi. Coresets for time series clustering. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 22849–22862, 2021. Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for Euclidean (k, z)clustering. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1594–1604. ACM, 2024. URL https://doi.org/10.1145/3618260.3649707. William B Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability, volume 26, pages 189–206. American Mathematical Society, 1984. Daniel M. Kane and Jelani Nelson. Sparser Johnson-Lindenstrauss transforms. J. ACM, 61(1): 4:1–4:23, 2014. URL https://doi.org/10.1145/2559902. Amer Krivosija, Alexander Munteanu, André Nusser, and Chris Schwiegelshohn. Improved learning via k-dtw: A novel dissimilarity measure for curves. In Forty-second International Conference on Machine Learning (ICML), 2025. URL https://openreview.net/forum?id=VCjPjexvpM. Kasper Green Larsen and Jelani Nelson. Optimality of the Johnson-Lindenstrauss lemma. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 633–638. IEEE Computer Society, 2017. URL https://doi.org/10.1109/FOCS.2017.64. D. D. Lucas, C. Yver Kwok, P. Cameron-Smith, H. Graven, D. Bergmann, T. P. Guilderson, R. Weiss, and R. Keeling. Designing optimal greenhouse gas observing networks that consider performance and cost. Geoscientific Instrumentation, Methods and Data Systems, 4(1):121–137, 2015. doi:10.5194/gi-4-121-2015. URL https://www.geosci-instrum-method-data-syst.net/ 4/121/2015/. Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Nonlinear dimension reduction via outer Bi-Lipschitz extensions. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1088–1101. ACM, 2018. URL https://doi.org/10.1145/3188745.3188828.

Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of JohnsonLindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1027–1038, 2019. URL https://doi.org/10.1145/3313276.3316350. Pascal Massart. Exponential and Information Inequalities, chapter 2, pages 15–51. Springer Berlin Heidelberg, 2007. Stefan Meintrup, Alexander Munteanu, and Dennis Rohde. Random projections and sampling algorithms for clustering of high-dimensional polygonal curves. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 12807–12817, 2019. Xiangrui Meng and Michael W. Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 91–100. ACM, 2013. URL https://doi.org/10.1145/2488608. 2488621. Alexander Munteanu and Chris Schwiegelshohn. Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms. Künstliche Intell., 32(1):37–53, 2018. URL https://doi.org/10.1007/s13218-017-0519-3. Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in Euclidean space. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1064–1069. ACM, 2019. URL https://doi.org/10.1145/3313276.3316307. Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2013. John Paparrizos, Fan Yang, and Haojun Li. Bridging the gap: A decade review of time-series clustering methods. CoRR, abs/2412.20582, 2024. doi:10.48550/ARXIV.2412.20582. URL https://doi.org/10.48550/arXiv.2412.20582. Karl Pearson. LIII. on lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559–572, 1901. doi:10.1080/14786440109462720. URL https://doi.org/10.1080/14786440109462720. Ioannis Psarros and Dennis Rohde. Random projections for curves in high dimensions. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 of LIPIcs, pages 53:1–53:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL https://doi.org/ 10.4230/LIPIcs.SoCG.2023.53. Ioannis Psarros and Dennis Rohde. Random projections for curves in high dimensions. Discret. Comput. Geom., 74(2):374–398, 2025. URL https://doi.org/10.1007/s00454-024-00710-5.

Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant nearoptimal rate puncturings. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 764–773. ACM, 2014. URL https://doi.org/10.1145/2591796.2591797. Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 143–152. IEEE Computer Society, 2006. URL https://doi.org/10.1109/FOCS.2006.37. Michel Talagrand. Majorizing measures: The generic chaining. The Annals of Probability, 24(3): 1049–1103, 1996. ISSN 00911798, 2168894X. URL http://www.jstor.org/stable/2244967. Mengyu Wang, Tiejun Ma, and Shay B. Cohen. Pre-training time series models with stock data customization. In Luiza Antonie, Jian Pei, Xiaohui Yu, Flavio Chierichetti, Hady W. Lauw, Yizhou Sun, and Srinivasan Parthasarathy, editors, Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, V.2, KDD 2025, Toronto ON, Canada, August 3-7, 2025, pages 3019–3030. ACM, 2025. doi:10.1145/3711896.3737005. URL https: //doi.org/10.1145/3711896.3737005. David P. Woodruff. Sketching as a Tool for Numerical Linear Algebra. Found. Trends Theor. Comput. Sci., 10(1-2):1–157, 2014. URL https://doi.org/10.1561/0400000060. Jingxiong Zhang, David Roy, Sadashiva Devadiga, and Min Zheng. Anomaly detection in MODIS land products via time series analysis. Geo-spatial Information Science, 10(1):44–50, Mar 2007. ISSN 1993-5153. doi:10.1007/s11806-007-0003-6. URL https://doi.org/10.1007/ s11806-007-0003-6. Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, and Zengfeng Huang. Space complexity of Euclidean clustering. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 82:1–82:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. URL https: //doi.org/10.4230/LIPIcs.SoCG.2024.82. Christoph Zimmer, Mona Meister, and Duy Nguyen-Tuong. Safe active learning for time-series modeling with gaussian processes. In Advances in Neural Information Processing Systems 31, pages 2730–2739. , 2018.

Further Related Work

Terminal Embeddings. Terminal embeddings were introduced by Elkin, Filtser, Neiman (TCS’17) [Elkin et al., 2017]. For preserving all Euclidean distances of points in given finite point set P of size n, the original reference gave only a constant factor distortion guarantee using an embedding into O(log n) dimensions. This was soon extended by Mahabadi, Makarychev, Makarychev, Razenshteyn (STOC’18) [Mahabadi et al., 2018] to achieve a strict generalization of the Johnson-Lindenstrauss embedding with (1 ± ε) distortion and a target dimension of O(ε−4 log n). Finally, Narayanan & Nelson (STOC’19) [Narayanan and Nelson, 2019] proved that O(ε−2 log n) dimensions suffice, which is remarkable, since this matches the lower bound for the weaker JohnsonLindenstrauss guarantee of Larsen & Nelson (FOCS’17) [Larsen and Nelson, 2017]. However, the running time of the embedding was still dominated by solving a semidefinite program for each query point. This issue was resolved by Cherapanamjeri & Nelson (FOCS’21, TCS’24) [Cherapanamjeri and Nelson, 2024] providing sublinear time embeddings based on approximate nearest neighbor techniques. Coresets for (k, ℓ, z)-Clustering of Polygonal Curves under the Fréchet Distance. (k, ℓ, z)clustering of polygonal curves under the Fréchet distance was introduced by Driemel et al. in (SODA’16) [Driemel et al., 2016]. Although it gave no explicit coreset construction, it already contained similar discretization and approximation approaches used in the clustering theory of metric spaces with bounded doubling dimension. The next step towards coresets was taken by Driemel et al. (SoCG’19) [Driemel et al., 2021] by bounding the VC dimension and thus enabling the sensitivity framework to the problem. This gave rise to first but large coreset constructions and centroid sets by Buchin & Rohde [Buchin and Rohde, 2022], which were significantly improved recently by Braverman et al. (FOCS’22) [Braverman et al., 2022] Õ(k 3 · ε−3 · d · ℓ · log m), Conradi et al. (SoCG’24) [Conradi et al., 2024] Õ(k 2 · ε−2 · log n · d · ℓ · log m), and Cohen-Addad et al. (SODA’25) [Cohen-Addad et al., 2025a] Õ(k · ε−1−z · d · ℓ · log m) using more and more refined techniques. See also Table 1. For algorithms to compute a solution to (k, ℓ)-clustering, Buchin, Driemel & Rohde (SODA’21) [Buchin et al., 2023] presented a bi-criteria approximation scheme, and Cheng & Huang (SODA’23) [Cheng and Huang, 2023] improved it to find a proper approximation scheme. They use curve simplification techniques that seem orthogonal to ours. Dimension Reduction for Polygonal Curves. The first contribution of random projections for preserving Fréchet distance was given by Driemel & Krivošija [Driemel and Krivosija, 2018], followed by a Johnson-Lindenstrauss equivalent for preserving the pairwise distances of input curves, by Meintrup et al. (NeurIPS’19) [Meintrup et al., 2019] within O(ε−2 log(nm)) dimensions. Albeit introducing additive errors, this enabled efficient algorithms for k-median, where centers are restricted to the input curves. Recently, Psarros et al. (SoCG’24,DCG’25) [Psarros and Rohde, 2023, 2025] refined to multiplicative errors for the pairwise distances within the same target dimension applying Johnson-Lindenstrauss embeddings to a sophisticated ‘skeleton’ net construction. We note that the problem can be solved much simpler by embedding low dimensional subspaces containing line segments. However, the method is restricted to discrete clustering objectives, and estimating the clustering cost, as described in [Psarros and Rohde, 2023, 2025]. To our knowledge, no terminal embeddings exist for the problem, and these are the missing key methodology to remove dimension dependence in continuous clustering applications and coreset constructions.

Omitted Proofs of the Main Part

Lemma 3.2. Let P be a set of n curves of complexity at most m. For any fixed query Qℓ of at most ℓ affine 1-dimensional subspaces, there exists a projection matrix Π onto the span of at most O(ℓε−2 ) line-segments of curves in P such that for all a ∈ P and any b ∈ q for q ∈ Qℓ , it holds that ∥a − b∥2 = (1 ± ε) ∥Π(a − b)∥2 + ∥(I − Π)a∥2 + ∥(I − Π)b∥2 Proof of Lemma 3.2. Consider an arbitrary q ∈ Qℓ and fix an arbitrary a0 ∈ argmina∈P : b∈q,q∈Qℓ ∥a− b∥, that is, a0 is any point in P that is closest to q. Denote by b0 the projection of a0 onto q, that is b0 ∈ argminb∈q ∥a0 − b∥, ties are again resolved arbitrarily. Consider arbitrary points a ∈ P and b ∈ Qℓ . For any orthogonal projection matrix Π, we can write ∥a − b∥2 = ∥Π(a − b)∥2 + ∥(I − Π)a∥2 + ∥(I − Π)b∥2 − 2aT (I − Π)b.

(5)

For any point b ∈ q, we may write b = b0 + α · v = a0 + (b0 − a0 ) + α · v, where v is a unit vector and α is a scaling factor. Plugging this into Equation (5), we have ∥a − b∥2 = ∥Π(a − (b0 + α · v))∥2 + ∥(I − Π)(a − a0 )∥2 + ∥(I − Π)(b0 − a0 + α · v)∥2 − 2(a − a0 )T (I − Π)(b0 − a0 + α · v). If we always include the line-segment containing a0 to the set of points that define the span of Π, then (I − Π)a0 = 0 and the above term simplifies again to ∥a − b∥2 = ∥Π(a − b)∥2 + ∥(I − Π)a∥2 + ∥(I − Π)b∥2 − 2(a − a0 )T (I − Π)(b0 − a0 + α · v). Our goal thus reduces to select Π s.t. |2(a − a0 )T (I − Π)(b0 − a0 + α · v)| ≤ ε · ∥a − b∥2 , which implies the equation in Lemma 3.2 as desired. Specifically, by the triangle inequality and a suitable constant rescaling of ε, it suffices to show

and

|2(a − a0 )T (I − Π)(b0 − a0 )| ≤ ε · ∥(I − Π)(a − a0 )∥ · ∥a − b∥

(6)

|2(a − a0 )T (I − Π)α · v| ≤ ε · ∥(I − Π)(a − a0 )∥ · ∥a − b∥.

(7)

We first argue Equation (6). Define s = b0 − a0 . Notice that ∥s∥ = ∥a0 − b0 ∥ ≤ ∥a − b∥. Note that for Qℓ there exist at most ℓ such vectors. Therefore, invoking Lemma 3.1, there exists a U with |U | = O(ℓ · ε−2 ) such that |(a − a0 )T (I − U U T )s| ≤ ε · ∥(I − U U T )(a − a0 )∥ · ∥s∥ ≤ ε · ∥(I − U U T )(a − a0 )∥ · ∥a − b∥

(8)

For Equation (7), we require several additional arguments. First recall that b = b0 + α · v. Notice that ∥a − (a0 + α · v)∥ ≤ ∥a − (b0 + α · v)∥ + ∥a0 − b0 ∥ = ∥a − b∥ + ∥a0 − b0 ∥ ≤ 2∥a − b∥. Next, due to the Pythagorean theorem, we have the following lower bound ∥a − (a0 + α · v)∥2 = ∥(I − vv T )(a − a0 )∥2 + ∥v(v T (a − a0 ) − α)∥2 ≥ max(∥(I − vv T )(a − a0 )∥, ∥v(v T (a − a0 ) − α)∥)2 , 20

(9)

which together with Equation (9) implies

max ∥(I − vv T )(a − a0 )∥, ∥v(α − v T (a − a0 )∥ ≤ 2∥a − b∥.

(10)

Furthermore, we have (a − a0 )T (I − Π)α · v = (a − a0 )T (I − Π)(vv T (a − a0 ) + v(α − v T (a − a0 ))),

(11)

allowing us to control the left hand side via the two terms on the right hand side by means of Equation (10). For the latter term, we have using Lemma 3.1 and Equation (10) |(a − a0 )T (I − Π)v(α − v T (a − a0 )| ≤ ε · ∥(I − Π)(a − a0 )∥ · ∥v(α − v T (a − a0 )∥ ≤ 2ε · ∥(I − Π)(a − a0 )∥ · ∥a − b∥.

(12)

′

(a − a0 )(a − a0 )T I− ∥a − a0 ∥2

= ε · ∥(I − Π)(a − a0 )∥ · ∥(I − vv T )(a − a0 )∥ ·

v · |v T (a − a0 )|

|v T (a − a0 )| ∥a − a0 ∥

≤ ε · ∥(I − Π)(a − a0 )∥ · ∥(I − vv T )(a − a0 )∥ ≤ 2ε · ∥(I − Π)(a − a0 )∥ · ∥a − b∥,

(13)

where the final inequality follows from Equation (10). Combining Equations (11), (12) and (13), we then obtain |2(a − a0 )T (I − Π)v(α − v T (a − a0 ))| ≤ 8 · ε · ∥(I − Π)(a − a0 )∥ · ∥a − b∥ which by a suitable constant rescaling of ε implies Equation (7).

Coresets for Clustering Polygonal Curves under the Fréchet Distance

In this section, we give our improved coreset construction for the Fréchet distance. Our algorithm has the same running time as all existing coreset constructions for the Fréchet distance. That is, assuming that we are given a constant factor approximate clustering or a bicriteria approximation1 along with an assignment of input curves to centers of the solution, the algorithm runs in linear time. Conradi et al. Conradi et al. [2024] showed how to compute a suitable bicriteria approximation in O(nm2 poly(k)) running time, which, to the best of our knowledge, is the state of the art for our purposes. Since we aim to prove slightly better bounds than a black-box application of our terminal embedding could provide, we have to introduce and then refine a lot of the standard coreset machinery. 1

In this case, an (α, β)-bicriteria approximation means that the algorithm may use more than β · k clusters and that the clustering cost is within a factor of α of the optimal k-clustering

C.1

Improved Coreset Size Bounds for the Cohen-Addad et al. [2021] Framework

The coreset framework presented in Cohen-Addad et al. [2021] provided an algorithm for computing coresets and an enumeration condition which determines the coreset size. In order to enumerate over all solutions, the coreset framework presented by Cohen-Addad et al. [2021] uses a type of net they call an approximate centroid set defined as follows. Definition C.1 ((α, k, z)-approximate centroid set). Let M = (X , d) be a metric space, P a set of points, k, z two positive integers, and let α ∈ (0, 12 ) be a precision parameter. Consider an (optimal or approximate) solution A, and let C ∈ Mk be a set of (potentially infinite) k-clusterings for the (k, z)-clustering objective. We say that N is an (α, k, z, A)-approximate centroid set of P if, for every solution S ∈ C, there exists another solution S̃ ∈ N such that α |cost(p, S̃) − cost(p, S)| ≤ · (cost(p, S) + cost(p, A)), z log(z/α) for all p ∈ P with cost(p, S) ≤

4z α

· cost(p, A).

Given a bound |N | on the size of an (α, k, z, A) approximate centroid set, the analysis of Cohen-Addad et al. [2021] presents a coreset construction as follows. Theorem C.2 (Theorem 1 of Cohen-Addad et al. [2021]). Let M = (X , d) be a metric space. Assume that for any set of points P there exists an (ε, k, z, A)-approximate centroid set N . Then, there exists an (ε, k, z)-coreset of size

|Ω| ≤ Õ 2O(z log z) · k · (ε−2 + ε−z ) · log(|N |) . Unfortunately, this easy-to-use reduction is not always tight and it also turn out to not be tight here. A refinement of the analysis, based on the chaining technique from Gaussian process theory Talagrand [1996], yields the following theorem: Theorem C.3. Let M = (X , d) be a metric space, and let U ≥ 0 be a value inherent to the metric space and let c > 0 be an absolute constant. Assume that for any set of points P and for every h > 0, the (2−h , k, z, A)-approximate centroid set (succinctly denoted as) Nh satisfies

|Nh | ≤ exp U kz 2 log |P | · 2ch log 2h ε−1

Then, there exists an (ε, k, z)-coreset of size

|Ω| ≤ Õ 2O(z log z) · U k · (ε−c + ε−2 ) · min(ε−z , k) . Some of the arguments used to prove Theorem C.3 are implicit in previous works, most notably Cohen-Addad et al. [2022a], but were not given in full generality as expressed above. We provide a self-contained proof in Appendix D. We note that the space of polygonal curves equipped with the Fréchet distance is known to be a metric space. We stress that the above theorem goes beyond bounding coreset sizes for this notion of a Fréchet metric; it is, in fact, general and may be convenient for other researchers attempting to prove coreset bounds for other metrics of interest. The algorithm to build the coresets from Theorem C.2 and Theorem C.3 is the same, from Cohen-Addad et al. [2021]. A brief description of this algorithm is as follows. First, compute a bi-criteria approximate solution (with cost whithin a constant factor of the optimal cost, but using O(k) centers instead of exactly k), using Conradi et al. [2024]. Then, partition each cluster of that solution into annuli of exponentially growing radius. Group the radius of the different clusters into "group", where annulus in the same group have the same ratio of (radius of the annulus) / (average distance to the center in the cluster). In each of them, take a uniform sample: the union of those samples forms the desired coreset. 22

C.2

Centroid Sets for the Fréchet Distance

The difficulty in applying the above logic to the metric space of curves under the Fréchet distance is that modeling the points of the polygonal curve is no longer sufficient for the entire curve. For example, consider the setting where every curve is a long parallel line of only two vertices. Centers can now be somewhere in the middle of these long lines, making it challenging to enumerate over all potential center sites. Straightforward ways of limiting the number of candidate centers by imposing a discretization along the lines lose parameters depending on the bit complexity of the input. Notably, the VC dimension is our only tool of addressing this challenge, as it is scale-invariant and thus depends only on combinatorial parameters. Unfortunately, the scale-invariance loses a dependence on the ambient dimension d, which can be mitigated somewhat with dimension reduction techniques, but will never be optimal in ε. Despite these challenges, we will prove that we can efficiently enumerate over all potential solutions in a scale sensitive way: Lemma C.4. Let P be a set of n curves in Tdm and let A ∈ Tdm k be a candidate solution.Then there exists an (α, k, z, A)-approximate centroid set N for (k, z, ℓ)-clustering on P under the Fréchet distance such that |N | ≤ exp{O (ℓ(k log(nm) + kd log(ℓ/α))}. In the notation of Theorem C.3, the above bound can be written as |N | ≤ exp U k log n · log ℓα−1 , with U ∈ O(ℓd log m). Together, Theorem C.2 and Lemma C.4 imply the following:

Corollary C.5. Let P ∈ Tdm be a set of input curves to be clustered under the Fréchet distance. Then the (k, 1, ℓ)-clustering objective admits (ε, k, 1)-coresets of size

|Ω| ≤ Õ kε−2 · ℓd log m . Removing the Dependence on d. This corollary can be easily combined with the linear terminal embeddings, to get coreset of size independent of the dimension d. A first, direct corollary follows from Theorem 1.2. Indeed, if f is a terminal embedding, the pre-image of a coreset for f (P ) is a coreset for P Huang and Vishnoi [2020]. Thus, this directly replaces the dependence on d in Corollary C.5 by ℓε−4 log(nm). We can reduce even further the dependence on ℓ: instead of creating one embedding that works simultaneously for all center curves, we can use Corollary 3.3 to create exp(O(ℓε−2 log(nm))) many different embeddings, such that for each center curve there is one correct embedding. Building nets for each embedding then yields a net for the original space with the benefit of saving an ε−2 factor. Theorem 1.3. Given a set P of n curves in Rd of complexity m, there exists an ε-coreset of size Õ(kε−2−z ℓ2 log2 m) for (k, ℓ, z)-clustering under the Fréchet distance, with center curves in Rd of complexity at most ℓ. Proof. Corollary 3.3 provides a collection S of exp(O(ℓε−2 log(nm))) projection matrices such that, for any σ ∈ Tdℓ , there is a matrix Π ∈ S such that the equation of Lemma 3.1 hold. For fixed Π ∈ S and σ ∈ Tdℓ , we can build on the equation of Lemma 3.1 to compute linear mappings f (independent of σ) and g such that, for any point a in an input line and any b ∈ σ, −2 ∥f (a) − g(b)∥ = (1 ± ε)∥a − b∥. For this, f and g map Rd to Rℓε +2 : it is merely enough to add 2 ancillary coordinates to encode ∥(I − Π)a∥ and ∥(I − Π)b∥. Hence, it is enough to build a net in a space of dimension ℓε−2 + 2. For this, we use Lemma C.4 as a black-box, to get a net of size n

|NΠ | ≤ exp O ℓ(k log(nm) + kℓε−2 log(ℓ/α) 23

This net is valid only for the curves in Tdℓ that respect the equation of Lemma 3.1 with this particular Π. To geta net for all curves in Tdℓ , it is enough to take the union of nets for all the exp O(ℓε−2 log(nm)) many Π, hence providing a net with size n

|N | ≤ exp O ℓε−2 log(nm)

· exp O ℓ(k log(nm) + kℓε−2 log(ℓ/α)

Combined with the chaining framework provided in Theorem C.3, this provides the desired coreset size. The remainder of this section is dedicated to providing a proof of Lemma C.4. Throughout this section, we use dF (a, b) to indicate the Fréchet distance.

C.3

A Warm Up: Parallel Lines

As a warm-up for the Fréchet distance, we will show how to build an approximate centroid set in the particular case where all input curves are parallel. C.3.1

Set Up

Assume that there is a single center γ, and that all input curves satisfy dF (pi , γ) ≤ α8 dF (pi , A). Let ∆ = min dF (pi , A) = dF (pmin , A), and assume that all input curves are at distance at most ∆α−2 from γ. We will see later that those assumptions are without loss of generality. If all vertices of γ were close to input vertices, then a simpler discretization of the Euclidean balls centered input vertices is sufficient. Hence, the issue is when some vertex from γ is far from every input vertex. This implies that all input curves have "long" edges, and the center’s vertices are in the middle of those long edges. Furthermore, those edges are at distance at most ∆α−2 from the corresponding edge of pmin : the angle between those segments is therefore somewhat tiny, and we will assume for now the segments are even parallel. We will show later how it is possible to reduce to that case. All those assumptions simplify the input: it simply consists of parallel segments of same length. p1 −p1 Also, suppose that pmin = p1 = ⟨p11 , p12 ⟩. Let e := ∥p21 −p11 ∥ be the common direction of the segments 2

pi . C.3.2

Construction of γe for Parallel Lines

For a given center curve γ, our goal will be to construct a curve γe with the same distance to any segment as γ, but where all vertices are "close" to the vertex p11 . That way, it will be possible to take a net of the space close to p11 , so as to bound the number of possible curves γe . For that, we start by breaking the cylinder Cyl(p1 , ∆α−1 ) (all points at distance at most ∆α−1 from p1 ) into pieces of length 3∆α−1 . Call each piece a "chunk", an let A1 , A2 , ... be the chunks taken in order – from p11 to p12 . Since γ has ℓ vertices, at most ℓ chunks contain one vertex from γ. 1 −1 Note that since dF (p1 , γ) ≤ 8∆ α , all vertices from γ are in Cyl(p , ∆α ). Our construction of γe removes area Ai if neither Ai−1 nor Ai contain a vertex from γ. By "removing", we mean that the vertices from subsequent chunks are shifted by 3∆ α · e. More precisely, the construction is as follows: for any i, let Ri be the number of chunks Aj such that j < i and Aj−1 , Aj do not contain any vertex from γ. γe is now defined as follows: its i-th vertex is ′ γi − Ri′ · 3∆ α · e, where i is the chunk that contains γi . Furthermore, we complete the curve by adding a copy of the last vertex of γ at the end of γe . The key property of that construction is the following: 24

Fact C.1. All vertices of γe are at distance at most 9ℓ · ∆α−1 of p11 . Proof. All areas have diameter at most 3∆α−1 , and all areas containing vertices of γe are separated by at most 2 empty chunks: therefore, they are all among the first 3ℓ areas. Note that γe may be far from γ: we can nonetheless show it has same distance to every input curve, which is enough for our purposes. This is done in the following lemma. Lemma C.6. For any input segment pi and any continuous bijection h : [0, 1] → [0, 1] with maxt∈[0,1] ∥pi (h(t)) − γ(t)∥ ≤ ∆α−1 , there exists a continuous bijection h̃ : [0, 1] → [0, 1] such that max ∥pi (h̃(t)) − γe (t)∥ ≤ max ∥pi (h(t)) − γ(t)∥.

t∈[0,1]

Similarly, for all h : [0, 1] → [0, 1] with maxt∈[0,1] ∥pi (h(t)) − γe (t)∥ ≤ ∆α−1 , there exists a continuous bijection h̄ : [0, 1] → [0, 1] such that max ∥pi (h̄(t)) − γ(t)∥ ≤ max ∥pi (h(t)) − γe (t)∥.

t∈[0,1]

Proof. For simplicity, we drop the superscript i: p := pi . We also assume that the segment p is parameterized linearly: p(t) = p(0) + (p(1) − p(0)) · t. Let ti such that ti = γ −1 (γi ). We assume, up to reparameterization, that γe verifies γe (ti ) = γei −e γi and that γe is parameterized linearly between vertices: ∀t ∈ [ti , ti+1 ), γe (t) = γei + eγti+1 · (t − ti ) – i+1 −ti and we do the same assumptions for γ. Combined with Thales’ theorem, this ensures the following property: ∀t, ∥γ(t) − p(Πγ(t) )∥ = ∥γe (t) − p(Πeγ (t) )∥, where Π is defined such that p(Πx ) is the orthogonal projection of x onto p. In order to define h̃, let us defines zones: a zone is a maximal group of consecutive non-removed chunks, i.e., Ai and Aj are in the same zone if, for any i′ ∈ [i, j], Ai′ or Ai′ −1 contain a vertex of γ. All vertices from a zone have the same shift, defined as Ri = Rj . Let us now define h̃. For all t such that t ∈ [ti , ti+1 ] and ti , ti+1 are in the same zone with shift R, let h̃(t) = h(t) − R · 3∆ α . Hence, on those intervals, both the curves and their traversal are simply shifted by the same constant, and we get an equality ∥p(h̃(t)) − γe (t)∥ = ∥p(h(t)) − γ(t)∥. For times t ∈ (ti , ti+1 ) such that ti and ti+1 are not in the same zone, we need to proceed differently. We consider intervals (ti , ti+1 ) in increasing order of i. In particular, this implies that h̃(ti ) is defined we constructing h̃ for t ∈ (ti , ti+1 ). We would ideally like to set h̃(t) = Πeγ (t) , so that ∥p(h̃(t)) − γe (t)∥ = ∥p(Πγ(t) ) − γ(t)∥ ≤ ∥p(h(t)) − γ(t)∥, as the maximum is more than the distance from any point to its projection on p. This however may break continuity, as it may be that Πγ(ti ) ̸= h(ti ) or Πγ(ti+1 ) ̸= h(ti+1 ). We therefore construct h̃ the following way. For all t where Πγ(t) ≤ h(ti ), we let h̃(t) = h̃(ti ). This only decreases the distance, compared to h: indeed, it holds that Πγ(t) ≤ h(ti ) ≤ t, so it must be that ∥γ(t) − p(h(ti ))∥ ≤ ∥γ(t) − p(h(t))∥. This handles the case where Πγ(ti ) < h(ti ). For the case Πγ(ti ) > h(ti ), we proceed similarly: for all t with h(t) ≤ Πγ(ti ) , define h̃(t) = h(ti ). This also ensures that ∥γ(t) − p(h(ti ))∥ ≤ ∥γ(t) − p(h(t))∥. The case Πγ(ti+1 ) = ̸ h(ti+1 ) is handled exactly the same way. For all t where Πγ(t) ≥ h(ti+1 ), we let h̃(t) = h̃(ti+1 ), and for all t with h(t) > Πγ(ti+1 ) , define h̃(t) = h(ti+1 ). In those cases, we get ∥p(h̃(t)) − γe (t)∥ ≤ ∥p(h(t)) − γ(t)∥. For all other t, we let h̃(t) = Πeγ (t) . By property of orthogonal projection, this ensures that ∥p(h̃(t)) − γe (t)∥ = ∥γ(t) − p(Πγ(t) )∥ ≤ 25

maxt∈[0,1] ∥p(h(t))−γ(t)∥, as the maximum is more than the distance from any point to its projection on p. The function h̃ defined that way is non-decreasing and continuous: when ti and ti+1 are in the same zone, this is a direct consequence of the monotonicity and continuity of h. When they are not in the same zone, the first property holds because Πγ(·) is non-increasing on [ti , ti+1 ]. Indeed, when γi and γi+1 are not in two consecutive areas, it must be that Πγi+1 > Πγi , as otherwise either ∥p(h(ti )) − γi ∥ > ∆α−1 or ∥p(h(ti+1 )) − γi+1 ∥ > ∆α−1 . Last, continuity holds at ti and ti+1 by our construction, and in between by continuity of Πγ(t) . Hence, we get max ∥pi (h̃(t)) − γe (t)∥ ≤ max ∥pi (h(t)) − γ(t)∥.

t∈[0,1]

The definition of h̄ is completely symmetric.

C.4

General Case

We now turn to the general case, and show the main lemma C.4. We first describe how the set N C is constructed, to then prove it is an approximate centroid set. C.4.1

Construction of N C

To build N C , we first discretize the potential locations of vertices from the center curves. We first build a set C consisting of those. For all input curves pmin (consisting of a “guess" of the closest input curve to the center curve), we add several sets to C, as follows. Let ∆ = dF (pmin , A). • First, to handle the case where all vertices from the center curves are close to input vertices, we first add to C precise nets around each input vertex: for all input curves pi and every vertex pij on it, let Ni,j be an α∆-net of B(pij , ℓ · 100∆α−2 ). • Next, for the case where vertices from the center curves are far away from input vertices, we proceed as follows. Fix a segment smin of pmin : we first construct a set N Csmin of points of smin . For any segment s from another input curve. Let I be the projection of s onto smin and let I1 , ..., I100/α3 be 1/α points regularly spaced on I. Add those points to N Csmin . Further, let s′ be the projection of smin onto s, and I ′ the projection of s′ onto smin : add to N Csmin 100/α3 points regularly spaced on I ′ . Now, for each point v ∈ CNsmin , let Nsmin ,v be an α∆-net of B(v, 100ℓ · ∆α−2 ) (v is the “center" for net Nsmin ,v , hence the name N Csmin for “net centers"). C is now made the union of all Ni,j ’s and all Nsmin ,v ’s. The approximate centroid set N C consists of all curves consisting of ℓ vertices from C. In other words, we restrict the candidate centers to have ℓ vertices from C. C.4.2

Proof of Lemma C.4

We can now show the proof of our main lemma C.4, by showing N C has small size and is an approximate centroid set. We first show the size guarantee. kℓ ℓ O(dkℓ) . ·

Lemma C.7. N C has size n2 m

O(d)

Proof. There are n curves pmin , hence n2 m many different Ni,j . Each of them has size αℓ . min Similarly, there are nm many segments s , and for each of them the set N Csmin contains at most O(d)

O(d)

2nm/α many points. Each net Nsmin ,v has size αℓ . Hence, in total, there are n2 m · αℓ many points in C. Since the approximate centroid set N C is constructed by choosing k curves made of ℓ vertices from C for each candidate solution, it has size at most n2 m

kℓ ℓ O(dkℓ) . · α

To show that N C is an approximate centroid set, we proceed as follows. First, we fix a center curve γ: we want to construct γe whose vertices are all in C such that, for any input curve p with dF (p, γ) ≤ α8 dF (p, A), then |dF (p, γ) − dF (p, γe )| ≤

α (dF (p, γ) + dF (p, A)). log(1/α)

Doing so for all the k curves in a candidate solution S shows the existence of the solution S̃ from the approximate centroid set that approximates S. We assume for simplicity that all input curves satisfy dF (p, γ) ≤ α8 dF (p, A): there is nothing to prove for the others. Next, we let pmin be the curve closest to A, and let ∆ = dF (pmin , A). are dealt with easily. First, we note that all curves p with dF (p, γ) ≥ 25∆ α2 Lemma C.8. If dF (pmin , γ) = (1 ± α)dF (pmin , γe ) + α∆, then for all curves p with dF (p, γ) ≥ 25∆ , α2 it holds that dF (p, γe ) ∈ (1 ± α)dF (p, γ). Proof. The assumption implies that dF (γ, γe ) ≤ dF (γ, pmin ) + dF (γe , pmin ) ≤ 3dF (γ, pmin ) + α∆ ≤ 25 α ∆. 2 Hence, if ∆ ≤ α25 dF (p, γ), then it directly holds that dF (p, γe ) ∈ (1 ± α)dF (p, γ). . Thus, from now on, we may assume all input curves satisfy dF (p, γ) ≤ 25∆ α2 C.4.3

Construction of γe

We construct γe as follows. For each vertex γv of γ, we distinguish two cases. First, if γv is in some B(pij , ℓ · 100∆α−2 ) we simply define γev to be the closest point to γv in Ni,j ⊂ C. Let γe 1 be the curve obtained after all those replacements. Fact C.2. dF (γ, γe 1 ) ≤ α∆. Proof. By construction of γe 1 , we can map each vertex of γ with one of γe 1 such that pair of vertices are at distance at most α∆. It is well-known (see e.g. Section 2 in Aronov et al. [2006]) that this is an upper-bound on Fréchet distance. Now, we deal from the vertices of γe 1 that are not in any ball B(pij , ℓ · 100∆α−2 ), by using the construction of Section C.3. We start by making some simplifying assumptions and fixing some notations. For any input curve pi let hi a bijection such that dF (pi , γe ) = maxt∈[0,1] ∥γe (t) − pi (hi (t))∥. Up to parameterizing each input curve pi differently, we can assume hi to be the identity. This implies the following: Fact C.3. For any t, ∥pmin (t) − p(t)∥ ≤ 33∆ . α2 27

Figure 2: Illustration of the natural conditions. smin is the top segment, s the lower one.

Proof. By the parameterization chosen above, it holds that ∥pmin (t) − γ(t)∥ ≤ dF (pmin , γ) ≤ 8∆ α and ∥p(t) − γ(t)∥ ≤ dF (p, γ) ≤ 25∆ . We conclude with triangle inequality. α2 Let γev1 be a vertex not in any ball B(pij , ℓ · 100∆α−2 ), and let t be such that γe 1 (t) = γev1 = γv . Let smin be the segment of pmin that is traveled along at time t, and let smin and smin be its two 1 2 min min min min endpoints. For i = 1, 2, let ti be such that p (ti ) = si . We parameterize smin such that min min (t′ ) = pmin (t′ ). ∀t′ ∈ [tmin 1 , t2 ], s Let tp (as predecessor) and ts (as successor) such that smin (tp ) and smin (ts ) are the points from N Csmin that are respectively the last point of N Csmin before t, and the first one after t. The idea of our analysis is that, if γev1 is far from smin (tp ) and smin (ts ) (which corresponds to our assumption on γev1 ), then each input curve can be made parallel to smin , in between time tp and ts . This allows us to apply Lemma C.6. For that, we introduce three conditions, that are satisfied by any “natural" input (and we will see afterwards how to deal with the particular cases where they are not fulfilled). For any input curve p and segment s on p that is traveled along at time t, we have: (i). The projection of s onto smin intersects smin (tp , ts ). (ii). s[tp : ts ] is an α3 /33-fraction of s. (iii). Let s1 and s2 be the extremities of s: it holds that dist(s1 , smin ) ≤ 33∆α−2 and dist(s2 , smin ) ≤ 33∆α−2 . Those conditions are illustrated in Figure 2. Our main conceptual idea here is that, when for all such s the three conditions are fulfilled, then it is possible to reduce to the case where all segments are parallel. We show later how to handle the case where they are not fulfilled. Lemma C.9. Assume that, for all input curves pi and segment si on p that is traveled along at time t, the three conditions (i), (ii) and (iii) are fulfilled. Then, there exists curves p̃i such that ∀i, dF (pi , p̃i ) ≤ α∆, and p̃i is parallel to smin between time tp and ts . Proof. We focus on a curve pi that fulfills conditions (i), (ii) and (iii). We drop the index i for simplicity. To build p̃, we simply replace the curve between p(tp ) and p(ts ) by a segment of same length parallel to smin that starts at p(tp ). We claim that maxt∈[0,1] ∥p(t) − p̃(t)∥ ≤ α∆. For this, it is enough to focus on t ∈ [tp , ts ]: further, by construction, the maximal distance is attained at ts . We show that the ∥p(ts ) − p̃(ts )∥ is at most an α3 /33-fraction of the projected distance to smin , which is at most 33∆α−2 by condition (iii): this would conclude. 28

This turns out to be a direct consequence of Thales’ theorem. Indeed, by condition (iii), s[tp : ts ] is a α3 /33 fraction of s, and p(ts ) − p̃(ts ) is orthogonal to smin . Therefore, Thales’ theorem shows that ∥p(ts ) − p̃(ts )∥ is an α3 /33 fraction of the maximum distance between the points of s projected onto the orthogonal of smin . By condition (iii), this maximum distance is at most 33∆α−2 , which concludes the lemma. As a direct corollary of this lemma, one can apply Lemma C.6 with curves p̃i to build the curve γe between time tp and ts : by Lemma C.9, this curve γe will at the same distance as γ to all pi . We give more details in Section C.4.5. C.4.4

Dealing with Border Cases

We now turn to the cases where the natural conditions are not satisfied. In that case, we can show that the point γev1 is actually in some ball B(pij , ℓ · 100∆α−2 ), which contradicts its definition. For the following lemmas, we consider for all input curves p the segment s that is traveled along at time t (i.e., p(t) ∈ s).

Lemma C.10. If condition (i) is not satisfied for some segment s, then either γv ∈ B pmin (tp ), 60∆ , α2

or γv ∈ B pmin (ts ), 60∆ . α2 Proof. The projection of s onto smin falls either before or after smin (tp , ts ). Up to considering a symmetric input, we can assume it falls before. For i = 1, 2 let ti such that s(ti ) = si (where s1 and s2 are the two extremities of s). We define τ1 = max(t1 , tp ) and τ2 = min(t2 , ts ). Note that the time t such that γ(t) = γv is comprised in the interval [τ1 , τ2 ], as it is both in [t1 , t2 ] and [tp , ts ]. Our first step is to show that, for i = 1, 2: ∥smin (tp ) − s(τi )∥ ≤ 34∆α−2 .

(14)

If τ1 = tp , Equation (14) holds by Observation C.3. In the other case, we use the fact that the projection of s1 = s(τ1 ) onto smin is before smin (tp ) on the segment smin (which holds by the lemma’s assumption), which is itself before smin (τ1 ) (by definition of τ1 ): therefore, ∥s(τ1 ) − smin (tp )∥ ≤ ∥s(τ1 ) − smin (τ1 )∥ ≤ 34∆α−2 , where the last inequality follows from Observation C.3. Hence, Equation (14) holds for i = 1. Consider now the case i = 2. The projection of s(τ2 ) lies before smin (t1 ), and τ2 ≥ t1 (since τ2 ≥ t ≥ t1 ): hence, as previously, ∥smin (t1 ) − s(τ2 )∥ ≤ ∥smin (τ2 ) − s(τ2 )∥ ≤ 33∆α−2 . This concludes the proof of Equation (14). Now, we conclude the lemma: since s is a segment, and t ∈ [τ1 , τ2 ], it holds that ∥s(t) − smin (tp )∥ ≤ max ∥smin (tp ) − s(τi )∥ ≤ 33∆α−2 . i

Therefore, ∥γ(t) − smin (tp )∥ ≤ ∥γ(t) − s(t)∥ + ∥s(t) − smin (tp )∥ ≤ 25∆α−2 + 33∆α−2 . This concludes the proof. Lemma C.11. If there is a segment (i) is fulfilled but (ii) is not, then either s such that condition 140∆ 140∆ min min γv ∈ B p (tp ), α2 , or γv ∈ B p (ts ), α2 . 29

Proof. Since condition (i) holds, the projection of s onto smin intersects smin [tp : ts ]. By maximality of tp and minimality of ts , this implies that smin [tp : ts ] is included in the projection, and is at most an α3 /100-fraction of it (by construction of tp and ts ). Our first claim is that ∥Projsmin (s(tp )) − smin (tp )∥ ≥ ∥smin (tp ) − smin (ts )∥ or ∥Projsmin (s(ts )) − s

min

(ts )∥ ≥ ∥s

min

(tp ) − s

min

(ts )∥.

(15) (16)

If both equation did not hold, then by triangle inequality we would have ∥Projsmin (s(ts )) − Projsmin (s(tp )) ∥ ≤ 3∥smin (tp )−smin (ts )∥, and therefore it would be a α3 /33 fraction of the projection of s onto smin . This would contradict the assumption. Hence, one of Equation (15) and Equation (16) does not hold: assume without loss of generality that Equation (15) does not hold. We use this equation to bound the following: ∥s(tp ) − smin (t)∥ ≤ ∥s(tp ) − smin (tp )∥ + ∥smin (tp ) − smin (t)∥ 33∆ ≤ 2 + ∥smin (tp ) − smin (ts )∥ (Observation C.3) α 33∆ ≤ 2 + ∥Projsmin (s(tp )) − smin (tp )∥ (Equation (15)) α 33∆ ≤ 2 + ∥Projsmin (s(tp )) − s(tp )∥ + ∥s(tp ) − smin (tp )∥ α 33∆ ≤ 2 + 2∥s(tp ) − smin (tp )∥ α 99∆ ≤ 2 . α We conclude with the triangle inequality: ∥smin (tp ) − γ(t)∥ ≤ ∥smin (tp ) − s(tp )∥ + ∥s(tp ) − smin (t)∥ + ∥smin (t) − γ(t)∥ 33∆ 99∆ 8∆ ≤ 2 + 2 + α α α 140∆ ≤ . α2 Lemma C.12. s such that condition (iii) is not fulfilled, then If thereis an input p with segment 66∆ 66∆ min min either γv ∈ B s1 , α2 , or γv ∈ B s2 , α2 , or (1) condition (iii) holds for s′ , the projection of smin onto s, and (2) s(t) ∈ s′ . Proof. We first start with an observation. For i = 1, 2, let ti such that s(ti ) = si (where s1 and s2 min min ) ≤ ∥s(t ) − smin (t )∥ ≤ 33∆ (from are the two extremities of s). If ti ∈ [tmin i i 1 , t2 ], then dist(si , s α2 min ] or t ∈ min , tmin ]. Observation C.3) and condition (iii) is fulfilled. Hence, either t1 ∈ / [tmin , t / [t 2 1 2 1 2 Focus on the first case. Our key (simple) observation is that tmin ∈ [t1 , t2 ]: indeed, t is in both 1 min min ≤ t ≤ t . Furthermore, s′ = Proj smin . Hence, [t1 , t2 ] and [tmin 2 s 1 , t2 ], so it holds that t1 ≤ t1 1 1 33∆ min ′ min min dist(s1 , s ) ≤ ∥s1 − s(t1 )∥ ≤ α2 , so condition (1) is satisfied. If condition (2) is satisfied as well, we are done. Otherwise, we can show that γv is close to smin 1 . min min Indeed, in that case, it holds that p(t) = s(t) ∈ [s(t1 ), Projs s1 ]. Hence,

min ∥smin − s(t)∥ ≤ ∥smin − s(tmin − Projs smin ∥ 1 1 1 )∥ + ∥s1 1

≤ 2∥smin − s(tmin 1 1 )∥ 30

≤

66∆ , α2

where the second inequality holds by property of the projection. This concludes. C.4.5

Putting Everything Together: N C is an Approximate Centroid Set

We now combine the previous lemmas to show how to build the curve γe with vertices in N C , and that |dF (pi , γe ) − dF (pi , γ)| ≤ α(dF (pi , γ) + ∆), which concludes that C is an approximate centroid set. As explained, start by constructing γe 1 , the curve obtained by replacing all vertices of γ that are in some B(pij , ℓ · 100∆α−2 ) by their closest point Ni,j ⊂ C. Fact C.2 shows that this transformation preserves all distances from input curves to γ. Let γv be a vertex that is outside of all balls B(pij , ℓ · 100∆α−2 ), t be such that γ(t) = γv , and smin the segment of pmin that is traveled along at time t. We define tp and ts such that smin (tp ) and smin (ts ) are the points from N Csmin that are respectively the last point of N Csmin before t, and the first one after t, and we restrict all input curves to [tp : ts ]. Lemma C.9 shows that, when the three conditions (i), (ii) and (iii) are satisfied, then we can consider all those segments are parallel. We furthermore restrict those segments to have same length as follows: let L be the smallest of their length. Restrict each segment to one of length L, that starts at a point of N C and contains t. The following Fact C.4 shows that this restriction is doable. We then build γ ′ using Lemma C.6: with this construction, distances between γ ′ and all input segments are preserved, and Fact C.1 shows that all vertices of γ ′ are at distance at most 9ℓ · ∆α−1 of an input vertex: they can therefore be replaced by points of C that are close-by, preserving the Fréchet distance up to an additive α∆. Applying this strategy for all vertices of γ outside of all balls B(pij , ℓ · 100∆α−2 ), this builds a curve γe with same distance as γ to every input curve, up to an additive α∆. Now, Lemma C.10 and Lemma C.11 shows that the first two conditions are satisfied for all input segments. Lemma C.12 shows that either the third is satisfied, it is satisfied for a subsegment s′ of s that contains s(t). In that case, we can simply replace s by s′ in the application of Lemma C.6 – as our construction of C ensures that there are net points regularly placed on s′ as well. Fact C.4. Let p[tp : ts ] be an input segment. Then, there is a point of N Cp at distance less than L from p(t). Proof. Triangle inequality ensures that, for any i, ∥pi (tp ) − p(tp )∥ ≤ 16∆α−1 , and ∥pi (ts ) − p(ts )∥ ≤ 16∆α−1 . Hence, the length of p[tp : ts ] is at most L + 32∆α−1 , which is at most 2L as otherwise the vertex of γv would be close to an input point. Thus, points of N Cp are placed at distance at most α3 L/50 along the segments, and there is one length L segment starting at this point containing p(t).

An Improved Coreset Construction Framework via Chaining

D.1

Outline of the Argument

In our setting, let P be a set of points in a metric space M = (X , d), admitting an (ε, k, z)-clustering net (as per Definition D.5), whose size is function of some ε > 0 (but does not grow too fast in ε). The goal is to describe a framework that, given a metric space and the size of its (ε, k, z)-clustering net, yields small and good coresets. Formally, we prove Theorem D.8, for which we provide an implication diagram for the reader to go back to as well as an outline of the argument below. 31

Theorem D.8

Lemma D.9

Lemma D.10

Lemma D.15

Lemma D.11

Lemma D.13

Lemma D.16

Lemma D.14

Figure 3: Proof overview of the coreset construction framework guarantee: Theorem D.8 is implied by Lemmas D.9, D.10, D.11. In turn, Lemma D.10 is implied by Lemmas D.15, D.13 and Lemma D.11 by Lemmas D.16, D.14.

To prove Theorem D.8, we generalize the conditions under which clustering nets give coresets in general metric spaces. Although parts of this analysis are available elsewhere in the literature (see e.g., Cohen-Addad et al. [2022a]), we provide the framework in its entirety in this section in hopes that it may help readers entering this field. We now present an overview of the arguments. In order to show Theorem D.8, we first start from a constant factor approximation A of the (k, z)-clustering objective for point set P on space M. We refer to a cluster in the approximation as Ci , which represents the set of points that are closest to center ci ∈ A. We then deconstruct the dataset into several non-overlapping groups such that they have two properties. First, the intersection of any cluster in A with a group has roughly equal cost. Second, every point in a group constitutes a roughly equal percentage of its cluster’s cost. These conditions ensure2 that a point 1 from cluster Ci in the group gets sampled with probability roughly k|C . Furthermore, there are a i| logarithmic number of such groups (as well as a set of outliers that do not satisfy these properties). Thus, by the fact that coreset property is preserved under composition, if we make a coreset for each group and one for the outliers then we have a coreset for the full dataset. We thus want to show that sampling from a group gives us a coreset for that group. First, we define the smallest group so that it only induces an O(ε) fraction of the cost, so each point in this smallest group can be snapped to its closest center without breaking the coreset requirement. Similarly, some clusters in a group will only induce an O(ε)-fraction of the entire cost of A. These can be handled accordingly. The union of those points that can be handled in this way is discussed in Lemma D.9. What remains are those clusters that constitute a significant amount of the cost (the ‘standard’ groups) and the outliers of the clusters (which we call the ‘outer’ groups), both of which generally follow a similar argument. We therefore restrict ourselves to the standard groups for the purposes of this exposition. Given any solution S, each point in the group has a cost with respect to A and a cost with respect to S. It is the cost with respect to S that we would like to approximate via the coreset. To do this, we will subdivide every cluster in our group into two sub-types, conditioned on S. The (relatively) easy type consists of those points who have significantly larger cost to S than to A, by at least a factor of O(ε−2 ). Intuitively, these points are much closer to each other than they are to their center in S. Thus, as long as we sample enough points from this type, its cost with respect to S should be well-approximated. Lemma D.11 states that they are sampled sufficiently and that their cost is therefore well-approximated. Thus, those points which incur a huge cost with respect 2

To see this, consider that we are picking a point from k clusters of equal cost and, conditioned on having picked cluster Ci , there are then |Ci | points to pick from.

to solution S are approximated by the sampling. It remains to show that we appropriately represent those centers that have roughly equal cost in S and A. This is the most involved part of the analysis. For it, we consider a infinite nested set of clustering nets over the costs of those centers in S that are in the O(ε−2 ) range. Specifically, we define a 12 -net, a 14 -net, and so on. Since the limit of these nets will approach any point, it must be the case that the we can approximate the cost of a center by summing the difference from the first net to the second, from the second to the third, and so on. That is, since the clustering nets give the point in the limit and everything in this telescoping sum cancels, this is equal to the cost of the center with respect to any point. This equality between nested clustering nets and the cost vectors is precisely what we exploit to make the analysis go through: if we can bound the differences in costs between ever-finer epsilon nets, then we can bound the amount that our cost is distorted. We first model the expected error over the telescoping nets as a Gaussian variable. In this sense, the supremum over the Gaussian variable bounds our desired term. Furthermore, this variable’s supremum is less than the sum of suprema over each element in the telescoping sum. Thus, if we can bound the amount of variation at each step in this telescoping sum, we can bound the entire sum and, by extension, the expected error of our center. A single step in the telescoping sum is expressed by all the possible interactions between the −i 2 -net and the 2−(i+1) net. Thus, we use the fact that the maximum of a set of random variables is bounded by their variance times the logarithm of the number of variables: "

E max |gp | ≤ 2σ log n. p

p∈[n]

where there are n random variables gi with maximum variance σ. In our setting, n is the size of the 2−i net times the size of the 2−(i+1) net. It therefore suffices to bound σ – the variance in cost when shifting from an ε-net to a ( 2ε )-net. Our analysis concludes by doing precisely this. Rings.

i ,A) Let ∆Ci = cost(C be the average cluster cost and define for each cluster: |Ci |

• Ring Rij = {p ∈ Ci | 2j ∆Ci ≤ cost(p, A) ≤ 2j+1 ∆Ci }, i.e., the set of points that have roughly the same multiple (up to a factor of 2) of the average point’s cost in that cluster in the approximate solution. • Inner ring RI (Ci ) = j≤z log(ε/z) Rij , i.e., the set of points whose cost in the approximate solution is significantly smaller than the average point’s cost in that cluster. We write S RI = i∈[k] RI (Ci ). S

• Outer ring RO (Ci ) = j>2z log(z/ε) Rij , i.e., the set of points whose cost in the approximate solution is much larger than the average cost of the cluster they belong to. We write S RO = i∈[k] RO (Ci ). S

• All those rings that are neither inner nor outer are the main rings. In particular, we let S Rj = i∈[k] Rij , that is the set of points that contribute roughly the same amount of cost to their respective cluster centers. The fundamental property of any ring Rij is that every point in it contributes roughly the same amount to cost(A).

Groups. Before proceeding with the formal definition of a group G, we first give an intuition as to how they are constructed. Each group is comprised of sets of rings. Consider the set of j-th rings Rj around the centers in A. Then each ring Rij has some total cost over all of its points. A group Gjb is then the subset of these j-th rings that have roughly the same total cost (where the b subscript determines how large this cost is). This means that a group Gjb is comprised of the j-th rings around some subset of the centers in our approximate solution. As a result, groups satisfy the following two properties: • Each point contributes roughly the same amount to its cluster’s cost. • Each group’s cost is evenly divided over the clusters that comprise it. Formally, main rings are partitioned into main groups as follows. For each j, a group is defined as

Gjb = p | ∃ i s.t. p ∈ Rij and

2b k

ε 4z

≤

cost(Rij , A) 2b+1 ≤ cost(Rj , A) k

ε 4z

Similarly to rings, we define the “cheap” groups GM min to be the union of all groups with b < 0. That S S M is, Gmin = j b≤0 Gjb . S S The “main” groups are all those that are not cheap, i.e. GM = j b>0 Gjb . With this definition, we say that a ring Rij “belongs” to a group Gjb if it contributes roughly the same amount to the total cost as all the other rings in Gjb . We visualize this in the following diagram: RO (C3)

RO (C1)

R3j

R1j RI (C1 )

RI (C3)

RO (C2)

RI (C2 )

c2 R2j

Figure 4: We plot the sample rings for A = {c1 , c2 , c3 } in which cost(C1 ) = cost(C2 ) < cost(C3 ). We have labeled the rings R1j , R2j and R3j for j = 1 – note that the width of each ring is proportional to the cost of its cluster. Now let us assume that R1j and R3j have equal densities of points but that R2j has higher density (as evidenced by the shading). Then we might have Gjb = R1j and Gjb′ = R2j ∪ R3j for b′ > b, since rings R2j and R3j each have a higher total cost than R1j .

Analogous definitions can be given for outer rings:

GO b = p | ∃ i, p ∈ Rij and

2b k

ε 4z

≤

cost(RO (Ci ), A) 2b+1 ≤ cost(RO , A) k

ε 4z

O M M above. That is, GO is the set of all outer groups GO min and G are defined similarly to Gmin and G that are not cheap. For an outer group G ∈ GO , let P G = {p | ∃C, p ∈ C and C ∩ G ̸= ∅} be the set of points belonging to the union of clusters that intersect the group. We define the “cheap” O group to be Gmin = GM min ∪ Gmin ∪ RI .

Cluster Types. When building coresets, we must show that the cost is preserved with respect to every solution. It proves useful, however, to consider these solutions in two separate types. Namely, consider a candidate solution S with respect to cluster Ci ∩ G, for Ci ∈ A. If the cost of every point in Ci ∩ G is roughly similar in S as in A, then it implies that there is a candidate center in S somewhere near center Ci . This setting must be handled with care and is what necessitates the upcoming net arguments. We therefore provide the following definition: Definition D.1 (Interesting Clusters). Consider an arbitrary solution S and a main group G ∈ GM . A cluster Ci ∩ Ginduced by S is said to be interesting if there exists a point p ∈ Ci ∩ G such that z · cost(p, A). cost(p, S) ≤ 4z ε On the other hand, if the cost of every point in Ci ∩ G is significantly larger with respect to S than it is to center ci , then it implies that every center S is far outside of the radius of Ci ∩ G. In this case, every point is roughly equivalent in terms of cost(P, S) and it is straightforward to show that we preserve their cost if we sample them sufficiently. We therefore provide the following definitions of these clusters in the main and outer groups: Definition D.2 (Huge Clusters). Consider an arbitrary solution S and a main group G ∈ GM . A cluster Ci∩ G z induced by S is said to be huge if there exists a point p ∈ Ci ∩ G such that 4z · cost(p, A). The set of all huge clusters induced by S in G is indicated by HG,S . cost(p, S) ≥ ε Definition D.3 (Far Clusters). Consider an arbitrary solution S and an outer group G ∈ GO . A cluster Ci ∩ G induced by S is said to be far if there exists a point p ∈ Ci ∩ G such that cost(p, S) ≥ 4z · cost(p, A). The set of all far clusters induced by S in G is indicated by FG,S . Approximate Centroid Sets, (ε, k, z)-Clustering Nets and (ε, k, z)-Coresets. For readability’s sake, we restate the definition of (ε, k, z, A)-approximate centroid sets, and we introduce another fundamental notion, that of (ε, k, z)-clustering nets, which will prove crucial for the analysis of the coreset construction. Definition D.4 ((ε, k, z, A)-approximate centroid set, restatement of Definition C.1). Let M = (X , d) be a metric space, P a set of points, k, z two positive integers, and let ε ∈ (0, 12 ) be a precision parameter. Consider an (optimal or approximate) solution A, and let C ∈ Mk be a set of (potentially infinite) k-clusterings for the (k, z)-clustering objective. We say that N is an (ε, k, z, A)-approximate centroid set of P if, for every solution S ∈ C, there exists another solution S̃ ∈ N such that |cost(p, S̃) − cost(p, S)| ≤ for all p ∈ P with cost(p, S) ≤

4z ε

ε · (cost(p, S) + cost(p, A)), z log(z/ε)

· cost(p, A).

Definition D.5 ((ε, k, z)-clustering net). Let M = (X , d) be a metric space, P a set of points, k, z two positive integers, and let ε ∈ (0, 21 ) be a precision parameter. For a given (optimal or approximate) solution A, let G be a group. Let C ∈ Mk be a set of (potentially infinite) k-clusterings for the (k, z)-clustering objective. We say that a set of cost vectors N ∈ R|P | is an (ε, k, z, A)clustering net if, for every solution S ∈ C, there exists a vector v ∈ N such that the following conditions hold: |vp − cost(p, S)| ≤ ε · (cost(p, S) + cost(p, A)), vp = 0,

∀p ∈ C ∩ G and C ∈ / HG,S ∪ FG,S ∀p ∈ C ∩ G and C ∈ HG,S ∪ FG,S .

Remark D.6. We remark that one could always obtain an (ε, k, z, A)-clustering net from an (ε, k, z, A)approximate centroid set, since the latter further requires a solution S̃, while the former only a set of vectors N . In the later, we will drop mention of A in the mention of approximate centroid set and clustering nets, as it is a fixed constant-factor approximation. Definition D.7 ((ε, k, z)-coreset). Let M = (X , d) be a metric space, P a set of points, k, z two positive integers, and let ε > 0 be a precision parameter. A (weighted) subset Ω ⊆ P with weights w : Ω → R is said to be an (ε, k, z)-coreset if, for every solution S to the (k, z)-clustering problem, it satisfies X

wp cost(p, S) ∈ (1 ± ε)cost(P, S).

p∈Ω

With this setup at hand, we can state the main coreset framework theorem, this time in terms of (ε, k, z)-clustering nets as opposed to (ε, k, z)-approximate centroid sets, due to Remark D.6: Theorem D.8 (Restatement of Theorem C.3). Let M = (X , d) be a metric space, and let U, c ≥ 0 be two constants inherent to the metric space. Assume that P is a set of points such that, for every h > 0, the (2−h , k, z)-clustering net (succinctly denoted as) Nh satisfies

|Nh | ≤ exp U kz 2 log |P | · 2ch log 2h ε−1

Then, there exists an (ε, k, z)-coreset of size

|Ω| ≤ O 2O(z log z) · U k · (ε−c + ε−2 ) · min(ε−z , k) · log6 ε−1 · log(U k) .

D.2

Preliminary Facts and Considerations on Groups

We list a series of well-known bounds that will be useful in the remainder: Fact D.1 (Bernstein’s Concentration Inequality). Let X1 , . . . , Xω be ω ∈ N non-negative independent P random variables. Let S = ωi=1 Xi . If there exists an almost-sure upper bound M ≥ Xi , then !

t2 P [|S − E[S]| ≥ t] ≤ exp − Pω . 2 i=1 V [Xi ] + 23 M t Fact D.2 (Maximum of Independent Gaussian Random Variables, Lemma 2.3 in Massart [2007]). Let gp ∼ N(0, σp ) be one of n independent normal random variables with σp ≤ σ almost surely. It holds that " # E max |gp | ≤ 2σ log n. p

p∈[n]

Fact D.3 (Triangle Inequality for Powers Makarychev et al. [2019]). Let p, q, r be three arbitrary points in a metric space M = (X , d) and let z be a positive integer. Then, for any ϑ > 0, dz (p, q) ≤ (1 + ϑ)z−1 · dz (p, r) + |d (p, q) − d (p, r)| ≤ ε · d (p, r) + z

z+ϑ ϑ

1+ϑ ϑ

z−1

· dz (q, r).

· dz (q, r)

We also provide the following properties of the decomposition into groups: Observation D.1. Since 2b ∈ [0, z log(4z/ε)] and 2j ∈ [2z log(ε/z), 2z log(z/ε)], there are at most O(z 2 log2 (z/ε)) groups. Claim D.1. Let G ∈ GM and C be an arbitrary cluster such that C ∩ G ̸= ∅. Then, cost(G, A) ≤ 2k · cost(C ∩ G, A) ≤ 4k · |C ∩ G| · cost(p, A), for all points p ∈ C ∩ G. Proof. Without loss of generality, let G be Gjb for some j and b and let C be Ci and recall that G ⊆ Rj . Then Rij = G ∩ Ci and, by the definition of groups, we have 2b k

ε 4z

≤

cost(G ∩ Ci , A) 2b+1 ≤ cost(Rj , A) k

ε 4z

Now let Rℓj be the cheapest ring in Rj that is also in group Gjb . So cost(Rℓj , A) ≤ cost(Rij , A). Then 2b k

ε 4z

cost(Rj , A) ≤ cost(Rℓj , A)

and

cost(Rij , A) ≤

2b+1 k

ε 4z

cost(Rj , A),

which, rearranged, give k cost(Rj , A) ≤ b 2

4z ε

cost(Rℓj , A)

and

k 2b+1

4z ε

cost(Rij , A) ≤ cost(Rj , A).

Since Rℓj is cheaper than Rij , we can then write k 2b+1

4z ε

4z z k cost(Rℓj , A) ≤ b+1 cost(Rij , A) ≤ b 2 ε 2 cost(Rℓj , A) ≤ cost(Rij , A) ≤ 2cost(Rℓj , A) k

4z ε

cost(Rℓj , A)

This immediately gives us the first inequality: cost(G, A) ≤ cost(Rj , A) =

cost(Raj , A)

a∈[k]

≤

2cost(Rℓj , A) ≤ 2k · cost(Rij , A) = 2k · cost(Ci ∩ G, A).

a∈[k]

For the second inequality, recall the definition of ring Rij : for all p ∈ Rij , it holds that 2j ∆Ci ≤ cost(p, A) ≤ 2j+1 ∆Ci . We can again do a similar argument as above: let q be the cheapest point in Rij , so that cost(q, A) ≤ cost(p, A) for all p ∈ Ci ∩ G. As was the case above, this implies that cost(p, A) ≤ 2cost(q, A). Now observe that 2k · cost(Ci ∩ G, A) = 2k ·

cost(p, A) ≤ 4k · |Ci ∩ G| · cost(q, A) ≤ 4k · |Ci ∩ G| · cost(p, A).

p∈Ci ∩G

This concludes the proof.

Algorithm 1 Group Sampling Input: Dataset P , approximate solution A and number of clusters k Output: A coreset Ω of points and weights 1: Let ω = 2λz log z · U kz 2 · ε−c log3 ε−1 · min(ε−z , k) 2: Initialize Ω ← ∅ 3: for i = 1, . . . , k do 4: Let wci = |Ci ∩ Gmin | 5: Update Ω ← Ω ∪ {(ci , wci )} 6: end for 7: for G ∈ GM ∪ GO do 8: for t = 1, . . . , ω do cost(p,A) 9: Sample point p ∈ G with probability cost(G,A) cost(G,A) Let wp = ω·cost(p,A) 11: Update Ω ← Ω ∪ {(p, wp )} 12: end for 13: end for 14: Return Ω

10:

D.3

Group Sampling Algorithm

In the previous section, we observed that there are at most O(z 2 log2 (zε−1 )) groups. Thus, the idea is to construct coresets ΩG for each such group and then output the union of all these coresets. As groups are well-structured and points in them contribute about the same to their overall cost, a sensitivity sampling procedure is all we need to build small coresets. Algorithm 1 has two main steps. We first take all of the points in the ‘cheap’ group and collapse them onto the centers of our approximate solution. We then perform sensitivity sampling on the remaining main and outer groups.

D.4

The Cheap Group Doesn’t Matter

We first observe that we can collapse the points in the cheap group to their closest cluster centers in A. Lemma D.9 (Cheap Group Estimate). Let P be a set of points in a metric space M = (X , d), and let S be an arbitrary solution for (k, z)-clustering. Then, cost(Gmin , S) −

|Ci ∩ Gmin | · cost(ci , S) ≤ ε (cost(P, S) + cost(P, A)) .

i∈[k]

Proof. Recall that the cheap group consists of three different subsets: the cheap rings RI , the cheap O main groups GM min and the cheap outer groups Gmin . Let S be any solution and let cost(Gmin , S) be the cost of the cheap group with respect to S. Let p be any point in Gmin such that p ∈ Ci . Then, by the triangle inequality for powers with ϑ = ε, we can upper bound cost(p, S) ≤ (1 + 1/ε)z−1 cost(p, ci ) + (1 + ε)z−1 cost(ci , S). Doing this for all such points in Ci ∩ Gmin gives us 1 cost(Ci ∩ Gmin , S) ≤ 1 + ε

z−1

cost(Ci ∩ Gmin , A) + (1 + ε)z−1 |Ci ∩ Gmin | · cost(ci , S).

Applying this over all centers in A leads to

1 ε

z−1

1 ε

z−1

cost(Gmin , S) ≤ 1 + ≤ 1+

cost(Gmin , A) + (1 + ε)z−1

|Ci ∩ Gmin | · cost(ci , S)

X i∈[k]

cost(Gmin , A) + (1 + z z+1 ε)

|Ci ∩ Gmin | · cost(ci , S),

i∈[k]

where the inequality holds because (1 + ε)z−1 ≤ 1 + z z+1 ε for 0 ≤ ε < 1. We now plug this into the statement from the lemma: cost(Gmin , S) −

|Ci ∩ Gmin | · cost(ci , S) ≤z z+1 ε

i∈[k]

|Ci ∩ Gmin | · cost(ci , S)

X i∈[k]

1 + 1+ ε

z−1

cost(Gmin , A),

which implies cost(Gmin , S) −

|Ci ∩ Gmin | · cost(ci , S) ≤z z+1 ε

|Ci ∩ Gmin | · cost(ci , S)

(17)

i∈[k]

1 + 1+ ε

z−1

cost(Gmin , A).

(18)

It remains to show that Equation (17) is less than O(ε)cost(P, S) and that Equation (18) is less P than O(ε)cost(P, A). The former is trivial to show, since i∈[k] |Ci ∩ Gmin | · cost(ci , S) ≤ cost(P, S). For the latter, we break it up into its constituent components and show that each one is very cheap: Consider the sets comprising Gmin . For the inner rings RI , we have for any p ∈ RI ∩ Ci cost(p, A) ≤ 2z log(ε/z) ∆Ci =

ε z

cost(Ci , A) . |Ci |

Therefore, cost(RI ∩ Ci , A) ≤

ε z

cost(Ci , A) =⇒ cost(RI , A) ≤

ε z

cost(P, A) = 4

ε 4z

For the inner main groups, we have for any Rij ∈ GM min ∩ Rj cost(Rij , A) 2 ≤ cost(Rj , A) k

2 =⇒ cost(Rij , A) ≤ k

ε z cost(Rj , A) ≤ 4z 4z We can similarly show for the outer groups that

ε 4z

and thus,

cost(GM min ∩ Rj , A) ≤ 2

z cost(GM min ∩ RO , A) ≤ 4

ε 4z

cost(Rj , A),

cost(Rj , A).

cost(RO , A).

O Since Gmin = RI ∪ GM min ∪ Gmin , we therefore have

cost(Gmin , A) ≤ 4z

ε 4z





cost(P, A) +

X j

cost(Rj , A) + cost(RO , A)

cost(P, A).

≤ 22z ≤

ε 4z

· 2 · cost(P, A)

2 z ε cost(P, A). zz

Hence,

1 1+ ε

z−1

1 cost(Gmin , A) ≤ 1 + ε

It is a matter of algebra3 to show that 1 + 1ε

1 ε

z−1

2 z ε cost(P, A). zz

2 z z z ε ≤ 2zε. Thus, we have

cost(Gmin , A) ≤ 2zε · cost(P, A)

(19)

We can now plug this into Equation (18) to obtain cost(Gmin , S) −

|Ci ∩ Gmin | · cost(ci , S) ≤ z z+1 ε · cost(P, S) + 2zε · cost(P, A)

i∈[k]

≤ 2z z+1 ε · (cost(P, S) + cost(P, A)). Rescaling ε then gives the desired result. This implies, in turn, that the remainder of the paper will only ever consider “main” or “outer” groups.

D.5

Coreset Validity

Given a solution S and a coreset Ω for a group G ∈ G, Algorithm 1 returns an estimated cost equal P to p∈G∩Ω wp cost(p, S), and so we are interested in studying the error estimator DSΩ (G) =

wp cost(p, S) − cost(G, S) .

p∈G∩Ω

The following lemmas state how significant (in terms of a specified accuracy) the deviation of the estimated cost from the true cost can be for main and outer groups. Lemma D.10 (Main Groups Estimate). Let G ⊆ GM be a main group, and let λ > 4 be an appropriately chosen constant. Then, for ω = 2λz log z · U kz 2 · (ε−c + ε−2 ) · min(ε−z , k) · log4 ε−1 · log(U kz), Algorithm 1 yields DSΩ (G) E sup ≤ ε. S cost(G, S) + cost(G, A) "

Lemma D.11 (Outer Groups Estimate). Let G ⊆ GO be an outer group, and let λ > 4 be an appropriately chosen constant. Then, for ω = 2λz log z · U kz 2 · (ε−c + ε−2 ) · min(ε−z , k) · log4 ε−1 · log(U kz), Algorithm 1 yields DSΩ (G) E sup ≤ ε. G G S cost(P , S) + cost(P , A) "

To see this, consider that (1 + 1/ε)z−1 has a binomial expansion where every term has a binomial coefficient less than z z and the terms themselves are powers of 1/ε. Thus, dividing by z z and multiplying by εz means that each term is less than ε. There are at most z such terms. 3

We prove these lemmas in the following sections, but show why they imply Theorem D.8 next. Proof of Theorem D.8. Let us consider ΩG as the coreset returned by Algorithm 1 for a group G ∈ G. Similarly, let ΩG be the union of all such coresets. We have: Ω

DS G (P ∩ G) E sup S cost(P, S) + cost(P, A) "





X X 1 = E sup · wp cost(p, S) − cost(G, S)  S cost(P, S) + cost(P, A) G∈G p∈Ω G





X Ω 1 ≤ E sup · DS G (G) S cost(P, S) + cost(P, A) G∈G "

≤ E sup S

DSΩG (G) · E sup cost(P, S) + cost(P, A) S cost(G, S) + cost(G, A) M

X cost(G, S) + cost(G, A) G∈G

cost(P, S) + cost(P, A)

DSΩG (G) · E sup G G S cost(P , S) + cost(P , A)

X cost(G, S) + cost(G, A)

X cost(P G , S) + cost(P G , A)

X cost(P G , S) + cost(P G , A) G∈GO



≤ E sup S

G∈GM

cost(P, S) + cost(P, A)

·ε+

G∈GO

cost(P, S) + cost(P, A)



· ε

(Lemmas D.10 and D.11) ≤ 2ε. By Markov’s inequality, we thus have that Ω

Ω

DS G (P ∩ G) DS G (P ∩ G) 1 3 P sup ≤ 8ε ≥ 1 − · E sup ≥ . 8ε 4 S cost(P, S) + cost(P, A) S cost(P, S) + cost(P, A) "

Ω

That is, DS G (P ∩ G) ≤ 8ε · (cost(P, S) + cost(P, A)) for all S, with probability at least 34 . We also need to take into account all points that do not belong to any group, and their corresponding cost estimator. It holds that Ω

DSΩ (P ) ≤ DS G (P ∩ G) + cost(P \ G, S) −

|P \ G ∩ Ci | · cost(ci , S)

i∈[k]

≤ 9ε · (cost(P, S) + cost(P, A)),

(Lemma D.9)

again for all S, with probability at least 34 . Since cost(P, A) ≤ α · OPT ≤ α · cost(P, S) for any S, where α is the approximation factor of solution A, it suffices to rescale ε by a factor 9(1 + α) to get that DSΩ (P ) ≤ ε · cost(P, S) as required. We are left to bound the coreset size. To this end, we recall from Lemmas D.10 and D.11 that ω = 2λz log z · U kz 2 · (ε−c + ε−2 ) · min(ε−z , k) · log4 ε−1 · log(U kz) for each group. Since, by Observation D.1, there at at most O(z 2 log2 (zε−1 )) many such groups, then the coreset size is simply

|Ω| ≤ O 2O(z log z) · U k · (ε−c + ε−2 ) · min(ε−z , k) · log6 ε−1 · log(U k) , which concludes the proof. 41

D.6

Groups Estimates via Chaining

To show Lemma D.10 and Lemma D.11, we need to show concentration of the error estimator DSΩ (G) around 0, whether G is a main or an outer group. In both cases, however, the cost estimator P S p∈G∩Ω wp cost(p, S) has too large a variance. To simplify the exposition, let vp = cost(p, S) be a |P |-dimensional cost vector for all p ∈ P and any fixed solution S; subsequently, let vpG,S = vpS · 1{p∈G} . Furthermore, we denote by uG,S = cost(p, S) · 1{p∈C∩G and C∈HG,S } , ∀G ∈ GM p uG,S = cost(p, S) · 1{p∈C∩G and C∈FG,S } , ∀G ∈ GO , p where HG,S and FG,S are given in Definitions D.2 and D.3. Now, as mentioned, we do not want to estimate ∥v G,S ∥1 directly, but instead, we split it as G,S v = v G,S − uG,S + uG,S . This allows us to estimate ∥v G,S − uG,S ∥1 and ∥uG,S ∥1 separately since ∥v G,S ∥1 = ∥v G,S − uG,S ∥1 + ∥uG,S ∥1 , which derives from v G,S , uG,S having nonnegative entries only. Well-Behaved Clusters. We use a chaining argument to estimate ∥v G,S − uG,S ∥1 , which is articulated as follows: Consider an infinite sequence of |P |-dimensional vectors v S,1 , v S,2 , . . ., where v S,h is such that |cost(p, S) − vpS,h | ≤ 2−h · (cost(p, S) + cost(p, A)), if p ∈ C ∩ G and C ∩ G ∈ / HG,S ∪ FG,S , and vpS,h = 0 otherwise. In other words, v S,h is a vector −h belonging to a 2 -net Nh approximating cost vector v G,S − uG,S . Let us now consider random variables YG,p,S = wp vpS,1 +

∞ X

wp (vpS,h+1 − vpS,h )

h=1

YG,S =

YG,p,S .

p∈Ω

Since vpS,h → vpG,S − uG,S so that the sum is well-defined, and YG,p,S = wp vpG,S − uG,S as the p p h→∞

sum telescopes, we observe that E [YG,S ] = ∥v G,S − uG,S ∥1 . This means that we can estimate ∥v G,S − uG,S ∥1 through YG,S . In turn, we can write the conditions to be proven in Lemma D.10 and Lemma D.11 as YG,S − E [YG,S ] ≤ε cost(G, S) + cost(G, A) S YG,S − E [YG,S ] E sup ≤ ε. G G S cost(P , S) + cost(P , A)

E sup

It is not immediate how to exploit a chaining argument via weighted Boolean variables. We, thus, make use of the following symmetrization argument for which we define Gaussian random variables XG,S , whose cost estimates do not deviate from the ones of YG,S by too much. Formally, let us define P

XG,S =

p∈Ω

gp · wp vpS,1 +

P∞

S,h+1 − v S,h ) p h=1 gp · wp (vp

cost(G, S) + cost(G, A) 42

, ∀G ∈ GM

p∈Ω

XG,S =

P∞

gp · wp vpS,1 +

S,h+1 − v S,h ) p h=1 gp · wp (vp G G cost(P , S) + cost(P , A)

, ∀G ∈ GO ,

where gp ∼ N(0, 1) is one of ω independent standard normal random variables. It holds that: Lemma D.12 (Cost Symmetrization, Appendix B.3 in Rudra and Wootters [2014]). Let T = 1 1 cost(G,S)+cost(G,A) or T = cost(P G ,S)+cost(P G ,A) . Then, 



EΩ sup S

T · (YG,p,S − E [YG,p,S ])  ≤

√

2π · EΩ,g sup |XG,S | . S

p∈Ω

With these at hand, our goal will be to show the following lemmas: Lemma D.13 (Gaussian Process for Main Groups Cost). Let G ∈ GM . For ω = 2λz log z · U kz 2 · (ε−c + ε−2 ) · min(ε−z , k) · log4 ε−1 · log(U kz), we have

EΩ,g sup |XG,S | ≤ ε. S

Lemma D.14 (Gaussian Process for Outer Groups Cost). Let G ∈ GO . For ω = 2λz log z · U kz 2 · (ε−c + ε−2 ) · min(ε−z , k) · log4 ε−1 · log(U kz), we have

EΩ,g sup |XG,S | ≤ ε. S

Huge and far clusters. Estimating ∥uG,S ∥1 does not require a chaining argument but a refined control over the estimator’s variance. Specifically, we will show the following lemmas: Lemma D.15 (Huge Clusters Estimate). Let G ∈ GM . For ω = 2λz log z · U kz 2 · (ε−c + ε−2 ) · min(ε−z , k) · log4 ε−1 · log(U kz), we have "

EΩ sup S

G,S − ∥uG,S ∥ 1 p∈Ω wp up

cost(G, S) + cost(G, A)

≤ ε.

Lemma D.16 (Far Clusters Estimate). Let G ∈ GO . For ω = 2λz log z · U kz 2 · (ε−c + ε−2 ) · min(ε−z , k) · log4 ε−1 · log(U kz), we have "

EΩ sup S

G,S − ∥uG,S ∥ 1 p∈Ω wp up cost(P G , S) + cost(P G , A)

≤ ε.

Proving Lemmas D.13, D.14, D.15, D.16 is the crux of the analysis. Before proceeding with those, we show how they imply, together with Lemma D.12, Lemma D.10 and Lemma D.11. Proof of Lemma D.10. We have that "

EΩ

DSΩ (G) sup S cost(G, S) + cost(G, A) 

= EΩ sup S

∥v G,S − uG,S ∥1 + ∥uG,S ∥1 −

p∈Ω

cost(G, S) + cost(G, A) 43



wp uG,S + wp (vpG,S − uG,S p p )



G,S − ∥uG,S ∥ 1 p∈Ω wp up

≤ EΩ sup

G,S − ∥uG,S ∥ 1 p∈Ω wp up sup cost(G, S) + cost(G, A) S G,S − ∥uG,S ∥ 1 p∈Ω wp up

≤ EΩ sup ≤ε+

√

G,S − uG,S ) − ∥v G,S − uG,S ∥ 1 p p∈Ω wp (vp

cost(G, S) + cost(G, A)





YG,p,S − E [YG,p,S ]  + EΩ sup S p∈Ω cost(G, S) + cost(G, A) X

cost(G, S) + cost(G, A)

+ EΩ sup

cost(G, S) + cost(G, A)

≤ EΩ

√

2π · EΩ,g sup |XG,S |

(Lemma D.12)

2πε.

(Lemmas D.15 and D.13)

Rescaling ε by a 1 +

√

2π factor concludes the proof.

We, thus, turn our attention to outer groups GO , where the proof is completely identical to the above, with P G in place of G, and Lemmas D.16, D.14 in place of Lemmas D.15, D.13 respectively: Proof of Lemma D.11. We have that DSΩ (G) sup G G S cost(P , S) + cost(P , A)

EΩ



= EΩ sup

∥v G,S − uG,S ∥1 + ∥uG,S ∥1 − G,S − ∥uG,S ∥ 1 p∈Ω wp up G G cost(P , S) + cost(P , A)

G,S − ∥uG,S ∥ 1 p∈Ω wp up sup G G cost(P , S) + cost(P , A) S

G,S − ∥uG,S ∥ 1 p∈Ω wp up cost(P G , S) + cost(P G , A)

≤ EΩ sup S

≤ EΩ

≤ EΩ sup S

≤ε+

√

wp uG,S + wp (vpG,S − uG,S p p )

+ EΩ sup S

 

G,S − uG,S ) − ∥v G,S − uG,S ∥ 1 p p∈Ω wp (vp G G cost(P , S) + cost(P , A)





YG,p,S − E [YG,p,S ]  + EΩ sup G G S p∈Ω cost(P , S) + cost(P , A) X

√

2π · EΩ,g sup |XG,S |

(Lemma D.12)

2πε.

(Lemmas D.16 and D.14)

Rescaling ε by a 1 +

D.7

p∈Ω G cost(P , S) + cost(P G , A)

√

2π factor concludes the proof.

Estimating ∥v G,S − uG,S ∥1 : A Gaussian Process to Estimate Groups Costs

In this section, we set out to show Lemmas D.13 and D.14. For both of them, i.e., whether G ∈ GM or G ∈ GO , we define the following random variables starting from the definition of XG,S : XG,S,0 =

S,h+1 − v S,h ) p p∈Ω gp · wp (vp

S,1 p∈Ω gp · wp vp

and XG,S,h = , ∀G ∈ GM cost(G, S) + cost(G, A) cost(G, S) + cost(G, A) P P S,1 S,h+1 − v S,h ) p p∈Ω gp · wp vp p∈Ω gp · wp (vp XG,S,0 = and X = , ∀G ∈ GO . G,S,h cost(P G , S) + cost(P G , A) cost(P G , S) + cost(P G , A) We may observe that

EΩ,g sup |XG,S | ≤ S

∞ X h=0

EΩ,g sup |XG,S,h | . S

(20)

Therefore, we need to have a handle on the number of distinct v S,h ’s vectors as well as on the variance of each single XG,S,h in order to be able to bound the above quantity. Specifically, we will show the lemmas through the following considerations: (i). XG,S,h is a Gaussian random variable with variance equal to X wp (vpS,h+1 − vpS,h ) wp (vpS,h+1 − vpS,h ) ≤ σ or ≤ σ, cost(G, S) + cost(G, A) cost(P G , S) + cost(P G , A) p∈Ω p∈Ω X

depending on whether we are dealing with main or outer groups, and for some σ we will compute; (ii). There are at most |Nh−1 | · |Nh | many distinct v S,h ’s vectors that cover S; (iii). It is a standard fact that

√ E max |gi | ≤ 2σ ln n, "

i∈[n]

for n Gaussian random variables gi , whose variance is at most σ (see Fact D.2). The above proof skeleton allows us to show the desired bounds for both main and outer groups. The former, however, requires a more careful analysis, while the latter is much simpler. We formalize the arguments for the former next and for the latter at the end of this section. The reason why the two analyses have to be treated separately is that, in the case of outer groups GO , the variance bound σ we are able to obtain is much better than the one achievable for main groups GM in the worst case. Even more importantly, the worst-case variance bound for GM is not enough by itself to guarantee the promised inequality of Lemma D.13. We, thus, need to split the proof for main groups into two cases: One where the estimator is good for the size of every cluster in A with high probability. The other where the estimator is far from being accurate, but the probability of this happening is vanishingly small. D.7.1

Chaining for Main Groups GM

As mentioned, we next show that |C ∩ G| is well approximated for all clusters C, provided enough points are sampled, with high probability. To this end, define M EG =

 

∀i ∈ [k],



wp =

X p∈Ci ∩G∩Ω

 

cost(G, A) ∈ (1 ± ε) · |Ci ∩ G| .  ω · cost(p, A) p∈C ∩G∩Ω X i

Lemma D.17. Let G ∈ GM . Then, h

M EG

ε2 ω ≥ 1 − k · exp − 9k

. i

Proof. First note that for every cluster C in A, E p∈Ci ∩G∩Ω wp = |C ∩ G|. Hence, we need to show that these estimators concentrate around their expectation simultaneously. Consider the j-th sampled point pj in coreset Ω, and let wpj ,C = wp · 1{pj ∈C∩G} . Then, h

V wpj ,C ≤ E wp2j ,C =

wp2 · P [p ∈ Ω] =

p∈C∩G

cost(G, A) ω · cost(p, A) p∈C∩G X

≤

2k · cost(C ∩ G, A) 4k · |C ∩ G|2 ≤ , ω · cost(p, A) ω2 p∈C∩G X

where the second line of inequalities follows from Claim D.1. Similarly, Claim D.1 also implies wpj ,C =

cost(G, A) 4k · |C ∩ G| ≤ . ω · cost(pj , A) ω

Thus, using Bernstein’s Inequality (Fact D.1), we obtain 



P



wp − |C ∩ G| > ε · |C ∩ G| ≤ exp −

p∈C∩Ω

ε2 · |C ∩ G|2



2ω · 4k·|C∩G| + 32 · 4k·|C∩G| · ε · |C ∩ G| ω ω2



ε2 ω ≤ exp − 9k

A union bound over all clusters in A yields the lemma. Lemma D.18. Let G ∈ GM and S be an arbitrary fixed solution. Then, XG,S,h is a Gaussian random variable with mean 0 and variance wp (vpS,h+1 − vpS,h ) cost(G, S) + cost(G, A)

X p∈Ω

≤

2−2h+2 · 24z log z −2z ·ε . ω

M, X Moreover, conditioned on event EG G,S,h ’s variance is

wp (vpS,h+1 − vpS,h ) cost(G, S) + cost(G, A)

X p∈Ω

2−2h+2 · 24z log z · min(ε−z , k). ω

≤

Before proving the above lemma, let us show how it implies, together with Lemma D.17, Lemma D.13. Proof of Lemma D.13. Let us recall Equation (20). Consequently, we only need to focus on terms of the form EΩ,g [supS |XG,S,h |], which, by the Law of Total Expectation, can be written as

(21)

M . First, we note that P E M ≤ 1. Moreover, by Lemma 2 of [Cohen-Addad Conditioning on EG G et al., 2021], it is enough to consider a chain up to t ≤ log 2ε−1 , as the entire solution is captured by an (ε, k, z)-approximate centroid set. Using Fact D.2 and the fact that there are at most |Nh−1 | · |Nh | many distinct XG,S,h ’s, we have

M EΩ,g sup |XG,S,h | | EG S

M · ≤ 2 V XG,S,h | EG

≤2 s

≤2

2 log(|Nh−1 | · |Nh |)

2−2h+2 · 24z log z · min(ε−z , k) · 4 log |Nh | ω

(Lemma D.18)

2(c−2)h · 24(z log z+1) · min(ε−z , k) · U kz 2 log(2h ε−1 ) . (Assumption) ω log−1 ω 46

The last inequality, in particular, is obtained since, for any point set of size ω,

|Nh | ≤ exp U kz 2 log ω · 2ch log 2h ε−1

Note that when c ≤ 2, the numerator above is maximized at h = 0, and otherwise at h = t = log 2ε−1 . Hence, as long as ω ≥ 24(z log z+2) · U kz 2 · (ε−c + ε−2 ) log3 ε−1 · min(ε−z , k), log ω we get

M EΩ,g sup |XG,S,h | | EG S

≤

2ε . log ε−1

Using that, for all a, b ≥ 1 such that a ≥ 2b log b, then a ≥ b log a, we would need ω ≥ 2ω ′ · log ω ′ , where ω ′ = 24(z log z+2) · U kz 2 · (ε−c + ε−2 ) · min(ε−z , k) · log3 ε−1 . Hence, it is sufficient to choose ω = 2λz log z · U kz 2 · (ε−c + ε−2 ) · min(ε−z , k) · log4 ε−1 · log(U kz), for some (large enough) constant λ > 4. As we are considering a chain up until log 2ε−1 , we get logX 2ε−1

h=0 M. Conditioning on ĒG us that

M ≤ 4ε. EΩ,g sup |XG,S,h | | EG

Lemma D.17 and a union bound over all z 2 log2 (z/ε) many groups gives h

M ĒG

−1

≤ k · z log (zε 2

ε2 ω ) · exp − 9k

≤ ε2z ,

where the last inequality follows by an appropriate choice of λ in the ω expression. We will usei the h M . In worse of the two variance bounds given in Lemma D.18 for the term EΩ,g supS |XG,S,h | | ĒG particular, we have that ε M . EΩ,g sup |XG,S,h | | ĒG ≤ 2ε−z log ε−1 S Thus, logX 2ε−1 h=0

M EΩ,g sup |XG,S,h | | ĒG S

≤ 4ε−z+1 ,

analogously to the above derivation. Summing the obtained upper bound on the terms of Equation 21, we get ∞ X h=0

EΩ,g sup |XG,S,h | ≤ 4(ε + ε−z+1 · ε2z ) ≤ 8ε. S

We rescale ε by a factor 8 to conclude. We are now ready to prove Lemma D.18.

Proof of Lemma D.18. We start by observing that XG,S,h is a sum of standard normal random P variables multiplied by other (scalar) terms, succinctly p ap · gp . As such, it is itself a centered P 2 Gaussian random variable with variance p ap . Namely, V [XG,S,h ] =

X p∈Ω

≤

X p∈Ω

wp (vpS,h+1 − vpS,h ) cost(G, S) + cost(G, A)

wp (vpS,h+1 − cost(p, S) + cost(p, S) − vpS,h ) cost(G, S) + cost(G, A) wp · 3 · 2−h−1 · cost(p, S) cost(G, S) + cost(G, A)

= 9 · 2−2h−2 ·



cost(G,A) ω·cost(p,A) · cost(p, S)



cost(G, S) + cost(G, A)

X p∈Ω

2

(22)

 ,

where the second inequality follows because vpS,h ∈ (1 ± 2−h ) · cost(p, S) since the vector v S,h ∈ Nh , and similarly for v S,h+1 ∈ Nh+1 . Thefirst bound on variance directly follows since, by assumption, z cost(p,S) . p∈C∈ / HG,S , that is cost(p,A) ≤ 4z ε M , so that we have a good estimate of cluster For the second bound, we make use of the event EG size for all clusters C. Consider q ∈ arg minp∈C cost(p, S) to cheapest point in the cluster. Then, by Fact D.3, for any point p and any solution S, it holds that

cost(p, S) ≤ (d(q, S) + d(p, q))z ≤

2z · cost(C ∩ G, S) + 4z · cost(C ∩ G, A) . |C ∩ G|

(23)

We now bound the expression in Equation 22 from above in the εz < k case, and vice versa. In the first case, we have 9 · 2−2h−2 ·



cost(G,A) ω·cost(p,A) · cost(p, S)

2



cost(G, S) + cost(G, A)



X p∈Ω

≤

· cost(G, A) X cost(G, A) · · cost(p, S) ω · (cost(G, S) + cost(G, A))2 p∈Ω ω · cost(p, A)

≤

· cost(G, A) X 2z · cost(C ∩ G, S) + 4z · cost(C ∩ G, A) · ω · (cost(G, S) + cost(G, A))2 C |C ∩ G|

9 · 2−2h−2 ·

4z ε

(p ∈ C ∈ / HG,S )

cost(G, A) · ω · cost(p, A) p∈C∩G∩Ω

(Equation 23) ≤

≤

9 · 2−2h−2 ·

4z ε

· cost(G, A)

· (1 + ε) · (2z · cost(C ∩ G, S) + 4z · cost(C ∩ G, A)) ω · (cost(G, S) + cost(G, A))2 C M holds) (EG 2−2h+2 ·

· cost(G, A)

ω · (cost(G, S) + cost(G, A))2

· 4z · (cost(G, S) + cost(G, A)) 48

(9(1 + ε) ≤ 16)

≤

2−2h+2 ·

4z ε

· 4z

(cost(G, A)) ≤ cost(G, S) + cost(G, A))

In the second case, we seek to obtain a bound depending on k. By Claim D.1, we know that cost(G, A) ≤ 2k · cost(C ∩ G, A) ≤ 4k · |C ∩ G| · cost(p, A), for all points p ∈ C ∩ G. Thus, 9 · 2−2h−2 ·

p∈Ω

≤



cost(G,A) ω·cost(p,A) · cost(p, S)

2



cost(G, S) + cost(G, A)



X X 9 · 2−2h−2 4k · |C ∩ G| · cost(p, A) · · cost2 (p, S) (Claim D.1) 2 ω · (cost(G, S) + cost(G, A)) ω · cost(p, A) C p∈C∩G∩Ω

X 9 · 2−2h · k ≤ · |C ∩ G| · ω · (cost(G, S) + cost(G, A))2 C

2 · cost(C ∩ G, S) + 4z · cost(C ∩ G, A) |C ∩ G|

cost(G, A) · ω · cost(p, A) p∈C∩G∩Ω

(Equation 23)

≤

X 9 · 2−2h · k · (1 + ε) · (2z · cost(C ∩ G, S) + 4z · cost(C ∩ G, A))2 ω · (cost(G, S) + cost(G, A))2 C M holds) (EG !2

X 2−2h+4 · k ≤ · 2z · cost(C ∩ G, S) + 4z · cost(C ∩ G, A) ω · (cost(G, S) + cost(G, A))2 C

≤

2−2h+2 · k · 16z . ω

(9(1 + ε) ≤ 16)

(cost(G, A)) ≤ cost(G, S) + cost(G, A))

This concludes the proof. D.7.2

Chaining for Outer Groups GO

We first state and prove an analog of the variance bound in Lemma D.18, but only in the worst-case, as this is sufficient. We, then, almost identically derive a proof of Lemma D.14, as we did for Lemma D.13. Lemma D.19. Let G ∈ GO and S be an arbitrary fixed solution. Then, XG,S,h is a Gaussian random variable with mean 0 and variance X p∈Ω

wp (vpS,h+1 − vpS,h ) cost(P G , S) + cost(P G , A)

≤

2−2h+2 · 16z . ω

Proof. Akin to Lemma D.18, we start by observing that XG,S,h is a sum of standard normal random P variables multiplied by other (scalar) terms, succinctly p ap · gp . As such, it is itself a centered P Gaussian random variable with variance p a2p . Namely, V [XG,S,h ] =

X p∈Ω

wp (vpS,h+1 − vpS,h ) cost(P G , S) + cost(P G , A) 49

X p∈Ω

≤

X p∈Ω

wp (vpS,h+1 − cost(p, S) + cost(p, S) − vpS,h ) cost(P G , S) + cost(P G , A) wp · 3 · 2−h−1 · cost(p, S) cost(P G , S) + cost(P G , A)

2 cost(G,A) · cost(p, S) ω·cost(p,A)   cost(P G , S) + cost(P G , A)



= 9 · 2−2h−2 ·

X p∈Ω

≤

2−2h+2 · 16z ω



where the first inequality follows because vpS,h ∈ (1 ± 2−h ) · cost(p, S) since the vector v S,h ∈ Nh , and similarly for v S,h+1 ∈ Nh+1 . The second inequality follows since, for all p ∈ C ∩ G, we must have cost(p, S) ≤ 4z · cost(p, A), since C ∈ / FG,S . We are left to show how the above implies Lemma D.14. Proof of Lemma D.14. Akin to Lemma D.13, we use Fact D.2 and the fact that there are at most |Nh−1 | · |Nh | many distinct XG,S,h ’s. Indentical calculations with respect to the ones in Lemma D.13, with a much smaller variance provided by Lemma D.19, yields ∞ X

EΩ,g sup |XG,S,h | ≤ O(ε),

h=0

which concludes the proof by a rescaling of ε.

D.8

Estimating ∥uG,S ∥1 : Huge and Far Clusters Estimates

The goal of this section is to show Lemmas D.15 and D.16. We begin with the former as its proof is shorter and, yet, conveys the main ideas that will be applied in the proof of the latter. D.8.1

Analysis for Huge Clusters

Let us recall that we consider points p ∈ C ∩ G where C ∈ HG,S , i.e., their cost in the current solution S is much larger than the cost they have in the approximate starting solution A, as per Definition D.2. By virtue of the point being so expensive, we have that its cost is roughly identical to the average cost of the entire cluster induced by S on G, so long as all induced cluster sizes are well-estimated. Lemma D.20. Let G ∈ GM and let ε < 12 . Then, for any solution S and any point p ∈ C ∩ G such that C ∈ HG,S , it holds that 

EΩ 

 X

M wp uG,S − cost(C ∩ G, S) EG ≤ 5ε · cost(C ∩ G, S). p

p∈Ω

Proof. Let us consider two points p, p′ ∈ C ∩ G such that C ∈ HG,S . Since they belong to the same group, it must hold that cost(p′ , S) ≤ cost(p, S) ≤ 2cost(p′ , S). 2 50

Then, by applying Fact D.3 with ϑ = 1, we get that cost(p, p′ ) ≤ 2z−1 · cost(p, A) + cost(p′ , A) ≤ 2z+1 · cost(p′ , A).

Now, applying Fact D.3 again with ϑ = ε, we obtain z + ε z−1 · cost(p, p′ ) z z + ε z−1 z+1 ′ ≤ (1 + ε) · cost(p , S) + ·2 · cost(p′ , A) z z z + ε z−1 z+1 ε ≤ (1 + ε) · cost(p′ , S) + ·2 · · cost(p′ , S) z 4z (p′ ∈ C ∩ G where C ∈ HG,S )

cost(p, S) ≤ (1 + ε) · cost(p′ , S) +

≤ (1 + 2ε) · cost(p′ , S). Similarly, z + ε z−1 · cost(p, p′ ) z z + ε z−1 z+1 ·2 · cost(p′ , A) ≤ (1 + ε) · cost(p, S) + z z z + ε z−1 z+1 ε ≤ (1 + ε) · cost(p, S) + ·2 · · cost(p′ , S) z 4z (p′ ∈ C ∩ G where C ∈ HG,S )

cost(p′ , S) ≤ (1 + ε) · cost(p, S) +

≤ (1 + ε) · cost(p, S) + ε · cost(p′ , S). M Hence, cost(p, S) ∈ (1 ± 2ε) · cost(p′ , S), since 1−ε 1+ε ≥ 1 − 2ε. Therefore, under event EG , we can upper bound the estimated induced cluster cost as follows:

wp · cost(p, S) ≤ (1 + 2ε) ·

p∈C∩G∩Ω

wp · cost(p′ , S)

p∈C∩G∩Ω

≤ (1 + ε)(1 + 2ε) · |C ∩ G| · cost(p′ , S) (1 + ε)(1 + 2ε) ≤ · cost(C ∩ G, S), (1 − 2ε)

M holds) (EG

M holds. Analogously, where the second inequality holds for all clusters C simultaneously since event EG we have the following lower bound:

wp · cost(p, S) ≥ (1 − 2ε) ·

p∈C∩G∩Ω

wp · cost(p′ , S)

p∈C∩G∩Ω

≥ (1 − ε)(1 − 2ε) · |C ∩ G| · cost(p′ , S) (1 − ε)(1 − 2ε) ≥ · cost(C ∩ G, S). (1 + 2ε)

M holds) (EG

The lemma follows by recognizing that, for ε < 1/2, (1+ε)(1+2ε) ≤ 1 = 5ε and (1−ε)(1−2ε) ≥ 1−5ε. (1−2ε) (1+2ε) We proceed with the proof of Lemma D.15.

Proof of Lemma D.15. By Law of Total Expectation, we write "

EΩ sup S

G,S − ∥uG,S ∥ 1 p∈Ω wp up

cost(G, S) + cost(G, A)

= EΩ sup S

+ EΩ sup S

G,S − ∥uG,S ∥ 1 p∈Ω wp up

cost(G, S) + cost(G, A) G,S − ∥uG,S ∥ 1 p∈Ω wp up

M EG

(24)

(25)

cost(G, S) + cost(G, A)

M · P EG

M M ĒG · P ĒG .

M ≤ 1 and, conditioned on E , Trivially, P EG G

wp uG,S ∈ (1 ± 5ε) · p

C∈HG,S p∈C∩G∩Ω

cost(p, S),

C∈HG,S p∈C∩G∩Ω

by Lemma D.20. Since ∥uG,S ∥1 ≤ cost(G, S) and given that all entries in uG,S with p ∈ C ∩ G and C∈ / HG,S are zero, we obtain (24) ≤ 5ε. On the other hand, suppose that

G,S ≤ ∥uG,S ∥ , then it easily follows that 1 p∈Ω wp up

G,S − ∥uG,S ∥ 1 p∈Ω wp up

cost(G, S) + cost(G, A) Otherwise,

≤

∥uG,S ∥1 ≤ 1. cost(G, S) + cost(G, A)

G,S > ∥uG,S ∥ , and 1 p∈Ω wp up

wp uG,S = p

X C∈HG,S

p∈Ω

≤

cost(G, A) · uG,S p ω · cost(p, A) p∈C∩G∩Ω X

4k · |C ∩ G| · cost(G, A) G,S · up ω · cost(p, A) C p∈C∩G∩Ω

(Claim D.1)

≤ 4k · ∥uG,S ∥1 , which yields

G,S − ∥uG,S ∥ 1 p∈Ω wp up

≤

cost(G, S) + cost(G, A)

4k · ∥uG,S ∥1 ≤ 4k. cost(G, S) + cost(G, A) h

M ≤ ε/4k, and thus, As long as ω ≥ 9ε−2 k log 4k 2 /ε , Lemma D.17 guarantees that P ĒG

(25) ≤ ε. Rescaling ε by a factor 6 concludes the proof. D.8.2

Analysis for Far Clusters

The following derivation is similar to the previous section, with the difference that C ∈ FG,S . We first state and prove an analog of Lemma D.17, defining O FG =

  

∀i ∈ [k],

X p∈Ci ∩G∩Ω

wp =

 

cost(G, A) ∈ (1 ± ε) · cost(Ci ∩ G, A) .  ω · cost(p, A) p∈C ∩G∩Ω X i

Lemma D.21. Let G ∈ GO . Then, h

O FG

ε2 ω ≥ 1 − k · exp − 5k

Proof. We need to show that these estimators concentrate around their expectation simultaneously. Consider the j-th sampled point pj in coreset Ω, and let wpj ,C = wp · 1{pj ∈C∩G} . Then, h

V wpj ,C ≤ E wp2j ,C =

wp2 · P [p ∈ Ω] =

X p∈C∩G

≤

cost(G, A) X cost(p, A) · ω2 p∈C∩G

cost(G, A) 2k · cost2 (C ∩ G, A) · cost(C ∩ G, A) ≤ , ω2 ω2

where the second line of inequalities follows from Claim D.1. Similarly, Claim D.1 also implies wpj ,C ≤

2k · cost2 (C ∩ G, A) . ω2

Thus, using Bernstein’s Inequality (Fact D.1), we obtain P [|cost(C ∩ G ∩ Ω, A) − cost(C ∩ G, A)| > ε · cost(C ∩ G, A)] 

≤ exp −



ε2 · cost2 (C ∩ G, A) 2

+ 32 · 2k·cost(C∩G,A) 2ω · 2k·cost ω(C∩G,A) · ε · cost(C ∩ G, A) 2 ω

 ≤ exp −

ε2 ω 5k

A union bound over all clusters in A yields the lemma. Lemma D.22. Let G ∈ GO . Then, for any solution S and any point p ∈ C ∩ G such that C ∈ FG,S , it holds that 



EΩ cost(C ∩ G, S) +

O wp · cost(p, S) FG ≤ ε · cost(C, S).

X p∈C∩G∩Ω

Proof. Let us consider a point p ∈ C ∩ G such that C ∈ A, and let c be the center serving it. We know that cost(p, S) > 4z · cost(p, c) and thus, by triangle inequality, d(c, S) ≥ d(p, S) − d(p, c) ≥ 4d(p, c) − d(p, c) ≥ d(p, c). This implies cost(c, S) ≥

4z ε

′

. We now define as · cost(C,c) |C| ′

′

C = p ∈ C | cost(p , c) ≤

2z ε

cost(C, c) · . |C|

Then, for any p′ ∈ C ′ , applying Fact D.3 with ϑ = ε gives z + ε z−1 · cost(p′ , c) z z z + ε z−1 2z cost(C, c) ′ ≤ (1 + ε) · cost(p , S) + · · z ε |C|

cost(c, S) ≤ (1 + ε) · cost(p′ , S) +

′

≤ (1 + ε) · cost(p , S) + 53

4z ε

2z−1

· cost(C,c) |C|

cost(p, c)

· cost(p, c)

(p′ ∈ C ′ )

≤ (1 + ε) · cost(p′ , S) + ε · cost(p, c)

(p ∈ G where G ∈ GO )

≤ (1 + ε) · cost(p′ , S) + ε · cost(c, S), which, in turn, means cost(p′ , S) ≥

1−ε · cost(c, S). 1+ε

Moreover, we have that, for any C ∈ FG,S , cost(C, S) ≥ cost(C ′ , S) =

cost(p′ , S) ≥ |C ′ | ·

p′ ∈C ′

1−ε ≥ |C | · · 1+ε ′

4z ε

cost(C, c) · ≥ |C|

1−ε · cost(c, S) 1+ε

(26)

4z ε

(27)

2z−1

· cost(C, c),

where the third and last inequalities follow from the fact that |C ∩ G| ≤ (1 − ε) · |C| by Markov’s inequality. We, thus, have cost(C ∩ G, S) ≤ (1 + ε) ·

cost(c, S) +

p∈C∩G∩Ω

2z + ε ε

z−1

ε 2z · |C| and |C ′ | ≥ 4z

· cost(p, c)

(Fact D.3)

2z + ε z−1 ≤ |C ∩ G| · (1 + ε) · cost(c, S) + · cost(C ∩ G, c) ε 2z ε 2z + ε z−1 ≤ · |C| · (1 + ε) · cost(c, S) + · cost(C ∩ G, c) 4z ε (Markov’s Inequality)

≤

ε 4z

· |C ′ | ·

1+ε · cost(c, S) + 1−ε

2z + ε ε

z−1

· cost(C ∩ G, c) (Markov’s Inequality)

1+ε ε 2z + ε · · cost(C, S) + · cost(C ∩ G, c) (Equation 26) 1−ε 4z ε 2z 2z−1 1+ε 2 ε 2z + ε z−1 ε ≤ · · cost(C, S) + · · cost(C, S) 1−ε 4z ε 4z (Equation 27)

z−1

≤

≤ ε · cost(C, S).

(28)

We would now like to bound the overall cost contribution of points in C ∩ G ∩ Ω: To that end, observe that cost(G, A) ≤ ω · cost(p, A) p∈C∩G∩Ω X

ε 2z

|C| · cost(G, A) cost(C, A)

( 2z ε

ε 2z |C| ≤ (1 + ε) · · · cost(C ∩ G, A) 2z cost(C, A) 2z ε ≤ (1 + ε) · · |C|. 2z

· cost(C,A) ≤ cost(p, A)) |C|

(29)

O , we can upper bound the estimated induced cluster cost as follows: Therefore, under event FG

cost(C ∩ G ∩ Ω, S) =

cost(G, A) · cost(p, S) ω · cost(p, A) p∈C∩G∩Ω X

cost(G, A) ≤ · (1 + ε) · cost(c, S) + ω · cost(p, A) p∈C∩G∩Ω X

z+ε ε

z−1

· cost(p, c) (Fact D.3)

≤ (1 + ε) · cost(c, S) · +

z+ε ε

z−1

cost(G, A) ω · cost(p, A) p∈C∩G∩Ω X

· (1 + ε) · cost(C ∩ G, A)

≤ (1 + ε) · cost(c, S) · 2

z+ε ε

z−1

ε 2z

O holds) (FG

(Equation 29)

· |C|

· (1 + ε) · cost(C ∩ G, A)| |

≤cost(C,c)

}

≤ ε · cost(C, S),

(30)

O holds, and the where the second inequality holds for all clusters C simultaneously since event FG last by an identical derivation to the one yielding cost(C ∩ G, S) ≤ ε · cost(C, S) above. The lemma follows by summing (28) + (30) ≤ 2ε · cost(C, S),

and rescaling ε by a factor 2. We proceed with the proof of Lemma D.16. Proof of Lemma D.16. By Law of Total Expectation, we write "

EΩ sup S

G,S − ∥uG,S ∥ 1 p∈Ω wp up cost(P G , S) + cost(P G , A)

= EΩ sup S

G,S − ∥uG,S ∥ 1 p∈Ω wp up cost(P G , S) + cost(P G , A)

O FG

G,S − ∥uG,S ∥ 1 p∈Ω wp up cost(P G , S) + cost(P G , A)

O F̄G

+ EΩ sup S

O · P FG

(31)

O · P F̄G .

(32) h

O ≤ 1 and, conditioned on F , Trivially, P FG G

wp uG,S − ∥uG,S ∥1 = p

C∈FG,S p∈C∩G∩Ω

p∈Ω

≤ε·

wp uG,S + p

cost(p, S)

p∈C∩G

cost(C ∩ G, S) = ε · cost(P G , S),

X C∈FG,S

by Lemma D.22. Since ∥uG,S ∥1 ≤ cost(G, S) and given that all entries in uG,S with p ∈ C ∩ G and C∈ / FG,S are zero, we obtain (31) ≤ ε. On the other hand, suppose that

G,S ≤ ∥uG,S ∥ , then it easily follows that 1 p∈Ω wp up

G,S − ∥uG,S ∥ 1 p∈Ω wp up G G cost(P , S) + cost(P , A)

≤

∥uG,S ∥1 ≤ 1. cost(P G , S) + cost(P G , A)

cost(p,S) Otherwise, p∈Ω wp uG,S > ∥uG,S ∥1 , and consider the maximum ratio rC = maxp∈C∩G cost(p,A) > 4z p as well as the corresponding maximizing point p∗ . We have that

1/z

d(c, S) ≥ d(p∗ , S) − d(p∗ , c) ≥ (rC − 1) · d(p∗ , c), cost(c,S) i.e., rC ≤ 2z · cost(p ∗ ,c) . Thus,

wp uG,S = p

X C∈FG,S

p∈Ω

cost(G, A) · uG,S p ω · cost(p, A) p∈C∩G∩Ω X

2k · cost(C ∩ G, A) · cost(p, S) ω · cost(p, A) C p∈C∩G∩Ω

≤

2k X · |C ∩ G ∩ Ω| · rC · cost(C ∩ G, A) ω C

≤ 2k ·

(Claim D.1)

rC · cost(C ∩ G, A)

≤ 2z+1 k ·

X cost(C ∩ G, A)

cost(p∗ , A)

≤ 2z+1 k ·

X ε 2z

≤ 22z+1 k ·

· cost(c, S)

|C| · cost(c, S)

(Markov’s Inequality)

(cost(C, S) + cost(C, A))

(Fact D.3)

≤ 22z+1 k · (cost(P G , S) + cost(P G , A)). This yields G,S − ∥uG,S ∥ 1 p∈Ω wp up G G cost(P , S) + cost(P , A)

As long as ω ≥ 5k log

≤ 22z+1 k ·

cost(P G , S) + cost(P G , A) = 22z+1 k. cost(P G , S) + cost(P G , A)

ε O ≤ , and thus, , Lemma D.21 guarantees that P F̄G 22z+1 ε 22z+1 k

(32) ≤ ε. Rescaling ε by a factor 2 concludes the proof.

Record · ID 361444 · SHA-256 ba4b59ad25527a57
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.