Department of Computer Science, University of Bonn, Germany Hausdorff Center
for Mathematics, University of Bonn, Germany The University of Texas at San
Antonio, partially supported by NSF CCF 2110075 Department of Computer
Science, University of Bonn, Germany [500] Theory of computation Design and
analysis of algorithms Frederik Brüning, Anne Driemel, Alperen Ergür and Heiko
Röglin

# On the number of iterations of the DBA algorithm

Frederik Brüning  Anne Driemel  Alperen Ergür  Heiko Röglin

###### Abstract

The DTW Barycenter Averaging (DBA) algorithm is a widely used algorithm for
estimating the mean of a given set of point sequences. In this context, the
mean is defined as a point sequence that minimises the sum of dynamic time
warping distances (DTW). The algorithm is similar to the $k$-means algorithm
in the sense that it alternately repeats two steps: (1) computing an optimal
assignment to the points of the current mean, and (2) computing an optimal
mean under the current assignment. The popularity of DBA can be attributed to
the fact that it works well in practice, despite any theoretical guarantees to
be known. In our paper, we aim to initiate a theoretical study of the number
of iterations that DBA performs until convergence. We assume the algorithm is
given $n$ sequences of $m$ points in ${\mathbb{R}}^{d}$ and a parameter $k$
that specifies the length of the mean sequence to be computed. We show that,
in contrast to its fast running time in practice, the number of iterations can
be exponential in $k$ in the worst case — even if the number of input
sequences is $n=2$. We complement these findings with experiments on real-
world data that suggest this worst-case behaviour is likely degenerate. To
better understand the performance of the algorithm on non-degenerate input, we
study DBA in the model of smoothed analysis, upper-bounding the expected
number of iterations in the worst case under random perturbations of the
input. Our smoothed upper bound is polynomial in $k$, $n$ and $d$, and for
constant $n$, it is also polynomial in $m$. For our analysis, we adapt the set
of techniques that were developed for analysing $k$-means and observe that
this set of techniques is not sufficient to obtain tight bounds for general
$n$.

###### keywords:

Dynamic Time Warping, Smoothed Analysis, Time Series, Clustering

Keywords Dynamic Time Warping, Smoothed Analysis, Time Series, Clustering

##  1 Introduction

The DTW Barycenter Averaging (DBA) algorithm [26] was introduced by Petitjean,
Ketterlin and Gançarski in 2011 and has since been used in many applications
for clustering time series data. The objective is to find a representative
time series that optimally summarizes a given set of input time series. Here,
the optimality is measured using the sum of DTW distances to the input
sequences, in the sense that, the smaller these distances are, the more
fitting the representation is. The dynamic time warping distance (DTW) was
introduced by Sakoe and Chiba [27] in the 1970s to capture similarities of
time series in speech recognition and belongs to the family of elastic
distance measures. It was later rediscovered by Berndt and Clifford [4] and
popularized by Keogh and Ratanamahatana [20]. By now it has long been a staple
in the area of time series classification and is often used as a baseline
comparison [21]. DTW has been used in a variety of applications from signature
verification and touch screen authentication to gait analysis and
classification of surgical processes [12, 15, 17, 30]. The DBA algorithm has
found application in the context of optimization of energy systems [32],
forecasting of household electricity demand [31], and human activity
recognition [29] to name a few. The representation computed by DBA is used to
speed up classification tasks on time series [25] and to improve the training
of neural networks [14, 16]. The original paper by Petitjean et al. [26] that
introduced DBA has more than 800 citations giving witness to the fact that DBA
is widely successful and popular across different application areas.

DBA consists of two update steps that are repeated in a loop after
initialization of the representative sequence. The first step computes an
optimal warping path (refer to Section 1.1 for a precise description) for each
input sequence with respect to current representative sequence. These warping
paths induce an order-preserving assignment of the points of the input
sequences to the points of the current representative sequence. In the second
update step, each point of the representative sequence is updated with the
mean of the group of points assigned to it. This process is repeated until the
algorithm converges to a stable solution. Despite its popularity, DBA is a
heuristic in the double meaning that it neither comes with any guarantees on
the quality of the solution nor on the running time. It may converge in a
local minimum that is far from the global optimum that minimizes the sum of
distances. Historically, this popularity may be due to the fact that the
underlying optimization problem it tries to solve, which is sometimes referred
to as DTW-MEAN, is NP-hard [7, 9] and there are no efficient approximization
algorithms known. We briefly summarize what is known on the computational
complexity. Bulteau et al. show that the problem is also not fixed-parameter
tractable in the number of sequences [9]. Using dynamic programming one can
find a time series that minimizes the sum of the DTW distances to $n$ time
series in $O(m^{2n+1}2^{n}n)$ time, as shown by Brill et al. [5], where $m$
denotes an upper bound on the length of each time series. This approach
readily extends to point sequences in higher dimensions leading to a running
time of $O(dm^{2n+1}2^{n}n)$. Using an implementation of their exact
algorithm, Brill et al. empirically study properties like uniqueness and
length of the representative sequence and discuss the effect of fixing the
length in advance, as it is done in DBA. They conclude that “choosing a mean
length that is larger than the optimal value induces only a small structural
error in most cases.” Buchin et al. [8] consider the problem variant where the
set of feasible solutions is restricted to sequences of a given length $k$ or
shorter. They call this the length-restricted mean under DTW and present an
exact algorithm with running time $O(n^{2dk}m^{8dk^{2}})$, where the input are
$n$ sequences of $m$ points in ${\mathbb{R}}^{d}$.

##### Objective

In this paper, we initiate a study of the number of iterations that DBA
performs until convergence. While convergence properties of the algorithm have
been studied before [28], it seems that the running time of the algorithm has
not been the subject of rigorous study up to now. We follow a line of thought
that has proved successful for a closely related algorithm—the well-known
$k$-means algorithm by Stuart Lloyd [22]. For this algorithm it is known that
the number of iterations in the worst case is exponential [2, 18, 19, 33].
However, on most practical instances the $k$-means algorithm is reported to
converge very fast. Moreover, using smoothed analysis, it has been shown that
the expected running time under random perturbations of the input is merely
polynomial [1]. This raises the question, to which extent these techniques may
be applied in the analysis of DBA.

##### Overview

In Section 2 we give two different upper bounds for the number of iterations
of DBA in the worst-case. The first one is an exponential upper bound that is
based on techniques from real algebraic geometry and uses specific properties
of the space of dynamic time warping paths. The second bound is based on a
potential function argument and it depends on certain geometric properties of
the input data. More precisely, we obtain a worst-case upper bound that is
linear in the length of the point sequences, and linear in
$\frac{1}{\varepsilon}$. Here $\varepsilon$ is the minimal distance between
any two mean point sequences that may be visited in the iterations of DBA.

In Section 3 we present our upper bounds for the expected number of iterations
in a semi-random data model. More precisely, we perform smoothed analysis of
the number of iterations of DBA under Gaussian perturbation (with any variance
$\sigma^{2}$) of deterministic data. The techniques we use for the smoothed
analysis are quite versatile, i.e. anti-concentration estimates and standard
tail bounds for the norm of a random vector. So the obtained results can be
easily generalised to broader distributions, e.g. sub-gaussian random
variables. However, we prefer to present the ideas in a less technical manner
on Gaussian perturbations. We show that the expected number of iterations
until DBA converges is at most
$\widetilde{O}\left(n^{2}m^{8\frac{n}{d}+6}d^{4}k^{6}\sigma^{-2}\right)$,
where the $\widetilde{O}(\cdot)$-notation omits logarithmic factors.

These upper bounds are complemented by an exponential worst-case lower bound
in Section 4. In particular, we show that there is an instance of two point
sequences with length $m=\Theta(k)$ in the plane such that DBA needs
$2^{\Omega(k)}$ iterations to converge. The techniques in this section borrow
from earlier work of Vattani [33]. Interestingly, our lower bound shows this
behaviour already for only $n=2$ sequences. In this setting, there also exists
a dynamic programming algorithm that solves the same problem in $O(k^{5})$
time [5], as mentioned above. Furthermore, we observe in Section 5 that, when
applied to real-world data, the number of iterations that DBA performs on
average is much lower than our theoretical analysis suggests. In particular,
we observe only sublinear dependencies on any of the parameters $n,m$ and $k$.
These empirical results support the implicit assumptions in our theoretical
study of the algorithm, as the smoothed analysis under randomly perturbed
instances avoids artificially constructed boundary cases and corresponding
artificially high lower bounds.

###  1.1 Preliminaries

For $n\in{\mathbb{N}}$, we define $[n]$ as the set $\\{1,\dots,n\\}$. We call
an ordered sequence of points $p_{1},\dots,p_{m}$ in ${\mathbb{R}}^{d}$ a
point sequence of length $m$. For two points $p,q$ in ${\mathbb{R}}^{d}$, we
denote with $\lVert p-q\rVert^{2}$ the squared Euclidean distance, where
$\lVert.\rVert$ is the standard Euclidean norm. For
$m_{1},m_{2}\in{\mathbb{N}}$, each sequence
$(1,1)=(i_{1},j_{1}),(i_{2},j_{2}),\dots,(i_{M},j_{M})=(m_{1},m_{2})$ such
that $i_{k}-i_{k-1}$ and $j_{k}-j_{k-1}$ are either $0$ or $1$ for all $k$ is
a warping path from $(1,1)$ to $(m_{1},m_{2})$. We denote with
${\mathcal{W}}_{m_{1},m_{2}}$ the set of all warping paths from $(1,1)$ to
$(m_{1},m_{2})$. For any two point sequences
$\gamma_{1}=(\gamma_{1,1},\ldots,\gamma_{1,m_{1}})\in({\mathbb{R}}^{d})^{m_{1}}$
and
$\gamma_{2}=(\gamma_{2,1},\ldots,\gamma_{2,m_{2}})\in({\mathbb{R}}^{d})^{m_{2}}$,
we also write
${\mathcal{W}}_{\gamma_{1},\gamma_{2}}={\mathcal{W}}_{m_{1},m_{2}}$, and call
elements of ${\mathcal{W}}_{\gamma_{1},\gamma_{2}}$ warping paths between
$\gamma_{1}$ and $\gamma_{2}$. The dynamic time warping distance between the
sequences $\gamma_{1}$ and $\gamma_{2}$ is defined as

$d_{\text{DTW}}(\gamma_{1},\gamma_{2})=\min_{w\in{\mathcal{W}}_{\gamma_{1},\gamma_{2}}}\sum_{(i,j)\in
w}\lVert\gamma_{1,i}-\gamma_{2,j}\rVert^{2}$

A warping path that attains the above minimum is called an optimal warping
path between $\gamma_{1}$ and $\gamma_{2}$. We denote with
${\mathcal{W}}_{m_{1},m_{2}}^{*}\subset{\mathcal{W}}_{m_{1},m_{2}}$ the set of
warping paths $w$ such that there exist point sequences
$\gamma_{1}\in({\mathbb{R}}^{d})^{m_{1}}$ and
$\gamma_{2}\in({\mathbb{R}}^{d})^{m_{2}}$ with optimum warping path $w$. Let
$X=\\{\gamma_{1},\dots,\gamma_{n}\\}\subset({\mathbb{R}}^{d})^{m}$ be a set of
$n$ point sequences of length $m$ and $C\in({\mathbb{R}}^{d})^{k}$ be a point
sequence of length $k$. We call a sequence $\pi$ of tuples $(p,c)$ where $p$
is an element of some point sequence in $X$ and $c$ is an element of the point
sequence $C$ an assignment map between $X$ and $C$. We call an assignment map
between $X$ and $C$ valid if for each $1\leq i\leq n$ the sequence of all
tuples $(p,c)$ of $\pi$ for which $p$ is a point of $\gamma_{i}$ forms a
warping path $w(\pi)_{i}$ between $\gamma_{i}$ and $C$. We call a valid
assignment map optimal if for each $1\leq i\leq n$ the formed warping path is
an optimal warping path. We define the cost of an assignment map $\pi$ as
$\Phi(\pi)=\sum_{(p,c)\in\pi}\lVert p-c\rVert^{2}$. Similarly, we define the
total warping distance of a valid assignment map $\pi$ with respect to a point
sequence $x=(x_{1},\dots,x_{k})$ as
$\Psi_{\pi}(x)=\sum_{i=1}^{n}\sum_{(j_{1},j_{2})\in
w(\pi)_{i}}\lVert\gamma_{i,j_{1}}-x_{j_{2}}\rVert^{2}$.

###  1.2 The DBA Algorithm

Let $X$ be a set of $n$ point sequences
$\gamma_{1},\dots,\gamma_{n}\in({\mathbb{R}}^{d})^{m}$. Let
$C\in({\mathbb{R}}^{d})^{k}$ be another point sequence and
$w^{(1)},\dots,w^{(n)}\in{\mathcal{W}}_{m,k}$ be chosen such that $w^{(i)}$ is
an optimal warping path between $\gamma_{i}$ and $C$. Then
$w^{(1)},\dots,w^{(n)}$ define an assignment map $\pi$ between $X$ and $C$.
The assignment map $\pi$ can be represented by sets
$S_{1}(\pi),\ldots,S_{k}(\pi)$, where

$S_{i}(\pi)=\cup_{j=1}^{n}\\{\gamma_{j,t}\mid(i,t)\in w^{(j)}\\}.$

By construction, $\pi$ minimizes the DTW distances between
$\gamma_{1},\dots,\gamma_{n}$ and $C$. In the opposite direction, the
following sequence $C_{\pi}$ minimizes the sum of squared distances for fixed
$\pi$.

$C_{\pi}=\left(c_{1}(\pi),c_{2}(\pi),c_{3}(\pi),\ldots,c_{k}(\pi)\right)$

where $c_{i}(\pi):=\frac{1}{\lvert S_{i}(\pi)\rvert}\sum_{p\in S_{i}(\pi)}p.$
DBA alternately computes such assignment maps and average point sequences as
follows.

  1. 1.

Let $\pi_{0}$ be an initial assignment map (e.g. randomly drawn
$w_{0}^{(1)},\dots,w_{0}^{(n)}$). Let $j\leftarrow 0$.

  2. 2.

Let $j\leftarrow j+1$. Compute the average point sequence $C_{\pi_{j-1}}$
based on $\pi_{j-1}$.

  3. 3.

Compute optimal warping paths $w^{(i)}_{j}$ between $\gamma_{i}$ and
$C_{\pi_{j-1}}$ for all $1\leq i\leq n$. The warping paths define an optimal
assignment map $\pi_{j}$ between $X$ and $C_{\pi_{j-1}}$.

  4. 4.

If $\Phi(\pi_{j})\neq\Phi(\pi_{j-1})$, then go to Step 2. Otherwise,
terminate.

##  2 Upper bounds

We present two different upper bounds on the number of steps performed by the
DBA algorithm. The first approach is based on a theorem from real algebraic
geometry and the resulting bound holds for any input data. The second approach
is based on a potential function argument and it uses a geometric assumption
on the input data.

###  2.1 An unconditional upper bound

In this section we will employ some classical tools from real algebraic
geometry to derive an upper bound on the number of steps performed by DBA. We
recall a special case of a general real algebraic geometry fact suited for our
purposes, see [3] for a more recent updated version of this result. First, we
need some definitions.

######  Definition 2.1.

A semi-algebraic set in $\mathbb{R}^{n}$ is a finite union of the sets of the
form

$\\{x\in\mathbb{R}^{n}:f_{1}(x),\dots,f_{\ell}(x)=0,g_{1}(x),\dots,g_{k}(x)>0\\}$

where $f_{i}$ and $g_{j}$ are polynomials with real coefficients. A semi-
algebraic set $X\subset\mathbb{R}^{n}$ is semi-algebraically connected if for
any semi-algebraic sets $X_{1}$ and $X_{2}$ that are closed in $X$, that are
disjoint, and $X=X_{1}\cup X_{2}$, then we have $X=X_{1}$ or $X=X_{2}$.

The prototypical example of a semi-algebraically connected set is the open
cube $(0,1)^{n}$, and every semi-algebraic set can be decomposed into semi-
algebraically connected components. The following is a special case of the
classical Oleinik-Petrovsky-Thom-Milnor result.

######  Theorem 2.2.

Let $Q_{1},\ldots,Q_{N}$ be quadratic polynomials with $s$ variables. The
number of semi-algebraically connected components of realizable sign
conditions of $Q_{1},\ldots,Q_{N}$ on $\mathbb{R}^{s}$ is
$O\left((2N)^{s}\right)$.

Figure 1: An arrangement of curves in the plane with the respective sign
vectors.

Now suppose the input point sequences to DBA are
$\gamma_{1},\gamma_{2},\ldots,\gamma_{n}$, and consider the set
${\mathcal{W}}^{*}_{m,k}$ of all possible optimal warping paths between a
point sequence of length $m$ and a point sequence of length $k$. We define
quadratic polynomials $F_{\gamma_{i},w}$ that encode the cost of a path
$w\in{\mathcal{W}}^{*}_{m,k}$ on the point sequence $\gamma_{i}$ as follows:

$F_{\gamma_{i},w}(x_{1},x_{2},\ldots,x_{k}):=\sum_{(j_{1},j_{2})\in
w}\lVert\gamma_{i,j_{1}}-x_{j_{2}}\rVert^{2}$

To be able to compare different warping paths between input point sequences
and an average point sequence $x$, we consider the following family of
quadratic polynomials.

$\mathcal{F}:=\\{F_{\gamma_{i},w}(x)-F_{\gamma_{i},v}(x):1\leq i\leq
n\;,\;w,v\in{\mathcal{W}}^{*}_{k,m}\\}$

We make a simple observation: If $w$ is an optimal warping path between
$\gamma_{i}$ and $C_{\pi}$ then for all $h\in{\mathcal{W}}^{*}_{m,k}$ we have
$F_{\gamma_{i},w}(C_{\pi})-F_{\gamma_{i},h}(C_{\pi})\leq 0$. Now suppose the
warping path $w$ between $\gamma_{i}$ and $C_{\alpha}\in\mathbb{R}^{dk}$ is
part of the optimal assignment map between input point sequences and
$C_{\alpha}$. Also suppose that DBA updates the warping path $w$ to another
path $v$ after the average point sequence is updated to $C_{\beta}$. This
means the following inequalities are true

$F_{\gamma_{i},v}(C_{\beta})-F_{\gamma_{i},w}(C_{\beta})\leq 0\leq
F_{\gamma_{i},v}(C_{\alpha})-F_{\gamma_{i},w}(C_{\alpha})$

Since the cost decreases at every step, both of the inequalities cannot be an
equality at the same time. In particular, the sign of quadratic polynomial
$F_{\gamma_{i},v}(x)-F_{\gamma_{i},w}(x)$ is different for the values
$x=C_{\alpha}$ and $x=C_{\beta}$. This implies that the sign configurations of
quadratic polynomials in $\mathcal{F}$ partition the space $\mathbb{R}^{dk}$
in such a way that two consecutive average point sequences computed by DBA are
separated.

We now argue that the algorithm visits any connected component at most once.

######  Lemma 2.3.

DBA does not visit a connected component of the realisable sign conditions of
$\mathcal{F}$ more than once (except for the very last step).

######  Proof 2.4.

Assume a connected component contains $C_{\pi_{i}}$ and $C_{\pi_{j}}$ where
$i<j$ and the algorithm does not converge in $C_{\pi_{j}}$. Because two
consecutive average point sequences computed by the algorithm are separated by
the realisable sign conditions of $\mathcal{F}$, we have $i+1<j$. Since the
cost decreases monotonically at every step of the algorithm, we have

$\Psi_{\pi_{i}}(C_{\pi_{i}})>\Psi_{\pi_{i+1}}(C_{\pi_{i+1}})>\Psi_{\pi_{j}}(C_{\pi_{j}})$

Observe that $\pi_{i+1}$ was computed based on $C_{\pi_{i}}$ and is thus an
optimal assignment map for $C_{\pi_{i}}$. Within every connected component,
the set of optimal warping paths remains unchanged. Therefore, $\pi_{i+1}$ is
also optimal for $C_{\pi_{j}}$. Since $C_{\pi_{i+1}}$ is optimal for
$\pi_{i+1}$, we have

$\Psi_{\pi_{j}}(C_{\pi_{j}})\geq\Psi_{\pi_{i+1}}(C_{\pi_{j}})\geq\Psi_{\pi_{i+1}}(C_{\pi_{i+1}}).$

This contradicts the statement that the cost decreases at every step.

Lemma 2.3 implies that the number of steps of DBA algorithm (except the very
last step) is upper bounded by the number of visited regions in the sign
realization of the family $\mathcal{F}$. Using the classical Oleinik-
Petrovsky-Thom-Milnor result (Theorem 2.2), we can give an upper bound on the
number of regions in $\mathbb{R}^{dk}$ determined by signs of the quadratic
forms $\mathcal{F}$.

######  Lemma 2.5.

The number of connected components of the realizable sign conditions of
$\mathcal{F}$ is $O((2n\lvert{\mathcal{W}}^{*}_{m,k}\rvert^{2})^{dk})$.

$\lvert{\mathcal{W}}^{*}_{m,k}\rvert\leq\binom{m+k-2}{m-1}\leq\min\\{m^{k-1},k^{m-1}\\}.$

######  Proof 2.6.

Indeed, the number of paths on an $m\times k$ grid that can take steps
$(i,j)\rightarrow(i+1,j)$ or $(i,j)\rightarrow(i,j+1)$ is given by
$\binom{m+k-2}{m-1}$, since any such path takes $m+k-2$ steps. However, our
warping paths may have diagonal steps of the form $(i,j)\rightarrow(i+1,j+1)$.
Note that such a diagonal step corresponds to ’omitting’ an assignment term
between two points from the total sum and therefore always leads to a decrease
in the cost. Thus, allowing diagonal steps does not increase the total number
of realisable warping paths.

Now, the bound in Lemma 2.5 together with Observation 2.1 immediately gives an
upper bound on the number of steps of DBA leading to the following theorem.

######  Theorem 2.7.

The number of iterations until DBA converges is in
$O((2n)^{dk}\binom{m+k-2}{m-1}^{2dk})$.

###  2.2 Upper bound based on geometric properties of the input data

We denote the set of valid assignment maps from $n$ input point sequences of
length $m$ to a point sequence of length $k$ with ${\mathcal{A}}_{n,m,k}$. It
is $\lvert{\mathcal{A}}_{n,m,k}\rvert\leq m^{kn}$. For an assignment map
$\pi\in{\mathcal{A}}_{n,m,k}$ and a point sequence
$x=(x_{1},x_{2},\ldots,x_{k})$ with $x_{i}\in\mathbb{R}^{d}$, we can rewrite
the total warping distance as

$\Psi_{\pi}(x):=\sum_{i=1}^{k}\sum_{y\in S_{i}(\pi)}\lVert y-x_{i}\rVert^{2}$

Our first observation is that for all $x$ we have
$\Psi_{\pi}(x)\geq\Psi_{\pi}(C_{\pi})$. We would like to express
$\Psi_{\pi}(x)$ in a way that resembles an inertia. We set
$I_{\pi}:=\sum_{i=1}^{k}\sum_{y\in S_{i}(\pi)}(\lVert y\rVert^{2}-\lVert
c_{i}(\pi)\rVert^{2})$. Observe that $I_{\pi}=\Psi_{\pi}(C_{\pi})$. We see
$I_{\pi}$ as the inertia of $\pi$, and we have

$\Psi_{\pi}(x)=I_{\pi}+\sum_{i=1}^{k}\lvert S_{i}(\pi)\rvert\;\lVert
x_{i}-c_{i}(\pi)\rVert^{2}$

We use the following geometric properties of the input:
Normalization Property: Let $B>0$. For any vector $y$ in any input point
sequence we have $\lVert y\rVert^{2}\leq B$.
Separation Property: Let $\varepsilon>0$. For any two different assignment
maps $\alpha,\beta\in{\mathcal{A}}_{n,m,k}$ we have

$\lVert
C_{\alpha}-C_{\beta}\rVert^{2}\coloneqq\sum_{i=1}^{k}(c_{i}(\alpha)-c_{i}(\beta))^{2}\geq\varepsilon$

With the help of the following lemma, we can derive an upper bound in Theorem
2.10.

######  Lemma 2.8.

For all $\alpha\in{\mathcal{A}}_{n,m,k}$, it is $I_{\alpha}\leq Bn(m+k)$.

######  Proof 2.9.

$I_{\alpha}=\sum_{i=1}^{k}\sum_{y\in S_{i}(\alpha)}(\lVert y\rVert^{2}-\lVert
c_{i}(\alpha)\rVert^{2})\leq B\sum_{i=1}^{k}\lvert S_{i}(\alpha)\rvert$

Note that every warping path between the average point sequence of length $k$
and an input point sequence of length $m$ consists of at most $m+k$ many
steps. This means every point sequence contributes to the sum
$\sum_{i=1}^{k}\lvert S_{i}(\alpha)\rvert$ with at most $m+k$ elements, and
hence we have $\sum_{i=1}^{k}\lvert S_{i}(\alpha)\rvert\leq n(m+k)$.

######  Theorem 2.10.

If the input data satisfies the normalization property with parameter $B$ and
separation property with parameter $\varepsilon$, then the number of steps
performed by DBA is at most

$\frac{B(m+k)}{\varepsilon}$

######  Proof 2.11.

Suppose DBA has started from assignment map $\pi_{0}$. If DBA takes a step
from some assignment map $\alpha$ to some assignment map $\beta$ this means

$\displaystyle I_{\alpha}$
$\displaystyle=\Psi_{\alpha}(C_{\alpha})>\Psi_{\beta}(C_{\alpha})$
$\displaystyle=I_{\beta}+\sum_{i=1}^{k}\lvert S_{i}(\beta)\rvert\;\lVert
c_{i}(\alpha)-c_{i}(\beta)\rVert^{2}$

Since $\lvert S_{i}(\beta)\rvert\geq n$ for all $i$, this implies
$I_{\alpha}>I_{\beta}+n\lVert C_{\alpha}-C_{\beta}\rVert^{2}$. Using the
seperation property of the data and Lemma 2.8 , we get

$I_{\alpha}>I_{\beta}+n\varepsilon\geq
I_{\beta}+\frac{\varepsilon}{B(m+k)}I_{\pi_{0}}$ (1)

Let $\pi_{T}$ be the assignment map after $T$ steps of DBA, then we have by
(1) that

$I_{\pi_{T}}<I_{\pi_{0}}-T\frac{\varepsilon}{B(m+k)}I_{\pi_{0}}$

##  3 Smoothed Analysis

Our randomness model is as follows: An adversary specifies an instance
$X^{\prime}\in([0,1]^{d})^{nm}$ of $n$ point sequences
$\gamma_{1},\dots,\gamma_{n}$ of length $m$ in $[0,1]^{d}$, where each
sequence $\gamma_{i}$ is given by its $m$ points
$\gamma_{i}=(\gamma_{i,1},\dots,\gamma_{i,m})$. Then we add to each point of
$X^{\prime}$ an $d$-dimensional random vector with independent Gaussian
coordinates of mean $0$ and standard deviation $\sigma$. The resulting vectors
form the input point sequences. We assume without loss of generality that
$\sigma\leq 1$, since the case $\sigma>1$ corresponds to a scaled down
instance $X^{\prime}\in([0,\frac{1}{\sigma}]^{d})^{nm}$ with additive
$d$-dimensional Gaussian random vectors with mean $0$ and standard deviation
$1$. We call this randomness model $m$-length sequences with
$\mathcal{N}(0,\sigma)$ perturbation.

We note that the results in this section hold for a more general family of
random input models (See Section 1.5 of [13] or Section 3.1 of [11]). We
conduct the analysis only for Gaussian perturbation for the sake of simplicity
and obtain the following theorem.

######  Theorem 3.1.

Suppose $d\geq 2$, then the expected number of iterations until DBA converges
is at most

$O\left(\frac{n^{2}m^{8\frac{n}{d}+6}d^{4}k^{6}\ln(nm)^{4}}{\sigma^{2}}\right).$

To proof Theorem 3.1, we first bound the probability that the normalization
property and the separation property hold for suitable parameters.

######  Lemma 3.2.

We have

$\mathbb{P}\\{\max_{1\leq i\leq n}\max_{y\in\gamma_{i}}\lVert
y\rVert\geq\sqrt{d}+t\sigma\sqrt{2d\ln nm}\\}\leq e^{1-t^{2}}$

######  Proof 3.3.

By our assumptions every vector in input sequences is given by $D+Y$ where $D$
is a deterministic vector with norm at most $\sqrt{d}$ and $Y$ is a random
vector with Gaussian i.i.d coordinates $\mathcal{N}(0,\sigma)$. By triangle
inequality $\lVert D+Y\rVert\leq\sqrt{d}+\lVert Y\rVert$. Since $Y$ has
Gaussian i.i.d coordinates $\mathcal{N}(0,\sigma)$, we can apply the standard
tail bound $\mathbb{P}\\{\lVert Y\rVert\geq t\sigma\sqrt{d}\\}\leq
e^{1-\frac{t^{2}}{2}}$.

######  Lemma 3.4.

Let $C_{\alpha}$ and $C_{\beta}$ be average point sequences corresponding to
two different assingment maps $\alpha$ and $\beta$. Then, we have
$\mathbb{P}\\{\lVert
C_{\alpha}-C_{\beta}\rVert^{2}\leq\varepsilon\\}\leq\left(\frac{nm\sqrt{\varepsilon}}{\sigma}\right)^{d}$.
Furthermore, the separation property with parameter $\varepsilon$ holds with
probability at least

$1-m^{4n}\left(\frac{nm\sqrt{\varepsilon}}{\sigma}\right)^{d}.$

######  Proof 3.5.

Since the instances are perturbed and the assignment maps are different, we
have with probability $1$ that there exists an $i\in[k]$ such that
$c_{i}(\alpha)\neq c_{i}(\beta)$. The event $\lVert
C_{\alpha}-C_{\beta}\rVert^{2}\leq\varepsilon$ further implies $\lVert
c_{i}(\alpha)-c_{i}(\beta)\rVert\leq\sqrt{\varepsilon}$. We bound the
probability that this event $\lVert
c_{i}(\alpha)-c_{i}(\beta)\rVert\leq\sqrt{\varepsilon}$ occurs for the fixed
$c_{i}(\alpha)$ and $c_{i}(\beta)$.

Let $S_{i}(\alpha)$ and $S_{i}(\beta)$ denote the sets of points in $X$ that
were assigned to $c_{i}(\alpha)$ and $c_{i}(\beta)$ respectively. Since
$c_{i}(\alpha)\neq c_{i}(\beta)$, it immediately follows that
$S_{i}(\alpha)\neq S_{i}(\beta)$. So we can fix a point $s\in
S_{i}(\alpha)\triangle S_{i}(\beta)$. We let an adversary fix all points in
$S_{i}(\alpha)\cup S_{i}(\beta)\setminus\\{s\\}$. In order for $c_{i}(\alpha)$
and $c_{i}(\beta)$ to be $\sqrt{\epsilon}$-close, we need $s$ to fall into a
hyperball of radius $nm\sqrt{\epsilon}$. Because $s$ is drawn from a Gaussian
distribution with standard deviation $\sigma$, this happens with probability
at most $\left(\frac{nm\sqrt{\epsilon}}{\sigma}\right)^{d}$. So in total, we
have $\mathbb{P}\\{\lVert
c_{i}(\alpha)-c_{i}(\beta)\rVert\leq\sqrt{\varepsilon}\\}\leq\left(\frac{nm\sqrt{\varepsilon}}{\sigma}\right)^{d}$
and therefore $\mathbb{P}\\{\lVert
C_{\alpha}-C_{\beta}\rVert^{2}\leq\sqrt{\varepsilon}\\}\leq\left(\frac{nm\sqrt{\varepsilon}}{\sigma}\right)^{d}$.

To prove the second claim, we apply a union bound over all possible choices
for $c_{i}(\alpha)$ and $c_{i}(\beta)$. Since each $c_{i}(\alpha)$ and
$c_{i}(\beta)$ is uniquely determined by its assigned points $S_{i}(\alpha)$
and $S_{i}(\beta)$ it suffices to bound these. For each input point sequence,
there are at most $\binom{m}{2}$ possible choices for the set of points that
get assigned to a fixed center point: This is the case since all points that
get assigned to the same center point have to be consecutive. So the points
that get assigned to the center point are uniquely determined by the first and
the last point that gets assigned to the center point. For $n$ input point
sequences all possible assignments to an arbitrary center point are therefore
bounded by $\binom{m}{2}^{n}$. Since we choose two center points
$c_{i}(\alpha)$ and $c_{i}(\beta)$, there are at most $\binom{m}{2}^{2n}\leq
m^{4n}$ possible choices for the assigned points $S_{i}(\alpha)$ and
$S_{i}(\beta)$ that determine $c_{i}(\alpha)$ and $c_{i}(\beta)$. The
statement follows by applying the union bound over possible choices for
$c_{i}(\alpha)$ and $c_{i}(\beta)$.

As a combination of Lemma 3.2 and Lemma 3.4, we get the following Lemma.

######  Lemma 3.6.

Let $\gamma_{1},\gamma_{2},\ldots,\gamma_{n}$ be independent $m$-length
sequences with $\mathcal{N}(0,\sigma)$ perturbation, and suppose $d\geq 2$ and
$k\leq m$. Then, the DBA algorithm implemented on the input data
$\gamma_{1},\gamma_{2},\ldots,\gamma_{n}$ converges in at most

$s\left(\frac{a_{1}n^{2}m^{8\frac{n}{d}+5}d^{3}k^{5}\ln(nm)^{3}}{\sigma^{2}}\right)$

steps with probability at least $1-s^{-\frac{d}{2}}-(2n)^{-dk}-2^{-8mdk^{2}}$
for all $s\geq 1$ where $a_{1}$ is constant.

######  Proof 3.7.

In Lemma 3.2, we set $t=2\ln((2n)^{dk}2^{8mdk^{2}})\leq 16mdk^{2}\ln(4n)$ to
get that the normalization property is fulfilled for some $B\leq
a_{2}\sigma^{2}d^{3}k^{4}m^{2}\ln(nm)^{3}$ with probability at least
$1-(2n)^{-dk}-2^{-8mdk^{2}}$ where $a_{2}$ is constant. Then we use Lemma 3.4
with $\varepsilon=\frac{\sigma^{2}}{sn^{2}m^{8\frac{n}{d}+2}}$ and apply
Theorem 2.10.

With the help of the Lemma 3.6, we are now ready to prove Theorem 3.1.

######  Proof 3.8 (Proof of Theorem 3.1).

Let $X$ be the number of steps that DBA performs. By Theorem 2.7, we have that
$X\leq a_{2}(2n)^{dk}2^{8mdk^{2}}$ for some constant $a_{2}$. We set
$M\coloneqq a_{2}(2n)^{dk}2^{8mdk^{2}}$ for simplicit and get

$\mathbb{E}[X]=\sum_{i=1}^{M}\mathbb{P}\\{X\;\geq i\\}\leq
K+\sum_{t=K}^{M}\mathbb{P}\\{X\;\geq t\\}$

for any $K$. We set $K\coloneqq
a_{1}n^{2}m^{8\frac{n}{d}+5}d^{3}k^{5}\ln(nm)^{3}$. By Lemma 3.6, it is

$\mathbb{P}\\{X\;\geq sK\\}\leq s^{-\frac{d}{2}}+(2n)^{-dk}+m^{-8mdk^{2}}$

for all $s\geq 1$. Therefore, we have

$\sum_{t=K}^{M}\mathbb{P}\\{X\geq t\\}\leq
K\cdot\sum_{s=1}^{\frac{M}{K}}s^{-\frac{d}{2}}+(2n)^{-dk}+m^{-8mdk^{2}}$

Since $d\geq 2$, we have $s^{\frac{-d}{2}}\leq\frac{1}{s}$. Moreover,
$\frac{M}{K}\left((2n)^{-dk}+m^{-8mdk^{2}}\right)\leq 1$. So, we have

$\sum_{t=K}^{M}\mathbb{P}\\{X\geq t\\}\leq
K\left(1+\sum_{s=1}^{\frac{M}{K}}\frac{1}{s}\right)\leq K+K\ln\frac{M}{K}$

Hence,

$\displaystyle\mathbb{E}X\leq 2K+K\ln\frac{M}{K}\leq
2K+Kmdk^{2}\ln\left(\frac{4a_{2}}{a_{1}}n\right)$

######  Remark 3.9.

Note that for the discrete case, where the positions of the points in the
center point sequence are restricted to the input points, we would get an
upper bound on the number of iterations which would be polynomial in $n$,
instead of exponential in $n$, since for the positions of $c_{i}(\alpha)$ and
$c_{i}(\beta)$ in the proof of Lemma 3.4, there are only ${\binom{nm}{2}}$
instead of ${\binom{m}{2}}^{2n}$ possible choices.

##  4 Lower bound

In this section we give a lower bound on the worst case number of iterations
until DBA converges for two input point sequences of length $m\in{\mathbb{N}}$
and an average point sequence of length $k=\Theta(m)$ in ${\mathbb{R}}^{2}$.
By duplicating the input point sequences this lower bound immediately yields a
lower bound for $n\in{\mathbb{N}}$ input point sequences of length $m$ and an
average point sequence of length $k=\Theta(m)$ in ${\mathbb{R}}^{d}$. To
construct the instance for our lower bound, we directly draw from the work of
Andrea Vattani on the lower bound for the worst case number of iterations of
the $k$-means method [33]. We take his exact construction and modify it to
suit our needs by connecting input points to point sequences and scaling up
the integer weights of the points by a constant factor. Here a point with
integer weight resembles multiple points in the same position that are
consecutive points of the corresponding point sequence. The resulting instance
will lead to a lower bound that is exponential in $m$.

###  4.1 Construction

Before we give a detailed construction, we give a motivation, why we modify a
$k$-means construction to show a lower bound for the number of iteration of
the DBA algorithm. The reason is that the algorithms are very similar. In
fact, we can observe that DBA can behave exactly like the $k$-means algorithm
and converge in the same number of iterations if in all iterations the optimal
$k$-means assignment maps are also valid DBA assignment maps.

To construct a suitable DBA instance, the idea is to connect the points of the
instance in [33] to point sequences such that this condition holds. This is
not directly possible, so we modify the instance such that we still get the
same number of iterations for both algorithms. A challenge here is that at
some steps of the algorithm some points of the average point sequence would
not get mapped to any point of one of the input point sequence by the
assignment map corresponding to $k$-means. This happens independent of the
choice of the point sequences and implies that the respective assignment maps
are not valid. Intuitively, the challenge is solved by letting the problematic
points on the average sequence "steal" points from neighbouring clusters. To
ensure that the general structure remains unchanged, we replace all points of
the input point sequences by multiple points in the same position. In the
following, we give a detailed description of the construction of the DBA
instance based on the instance in [33].

$P_{i}$$Q_{i}$$A_{i}$$B_{i}$$C_{i}$$D_{i}$$E_{i}$$r_{i}$$R_{i}$$P_{i}$$Q_{i}$$A_{i}$$B_{i}$$C_{i}$$D_{i}$$E_{i}$${\gamma_{1}}$${\gamma_{2}}$
Figure 2: Schematic drawing of gadget $G_{i}$ ($i\geq 1$) in $k$-means
instance (Left) and in DBA instance (Right).

The instance ${X^{\prime}}$ of Andrea Vattani consists of a sequence of
gadgets $G_{0},G_{1},\dots,G_{\lceil\frac{k-1}{2}\rceil}$. For each $i\neq 0$,
the gadget $G_{i}$ is given by a tuple
$({\mathcal{P}}_{i},{\mathcal{T}}_{i},r_{i},R_{i})$ where the set
${\mathcal{P}}_{i}=\\{P_{i},Q_{i},A_{i},B_{i},C_{i},D_{i},E_{i}\\}\subset{\mathbb{R}}^{2}$
determines the positions of the input points,
${\mathcal{T}}_{i}\subset{\mathbb{R}}^{2}$ determines the initial position of
two centers corresponding to the gadget and $r_{i}>0$ and $R_{i}>r_{i}$ are
the inner and outer radius of the gadget. In each position of
${\mathcal{P}}_{i}$ the gadget contains a constant number of points determined
by weights $w_{P},w_{Q},w_{A},w_{B},w_{C},w_{D},w_{E}$ that are independent of
the index $i$ (see Table 1 for the exact values). Note that for our use of the
instance, we scale the weights by a constant factor of $100M$, where
$M\in{\mathbb{N}}$ will be determined later. The positions of each gadget are
identical up to translation of the position $P_{i}$ and up to a scaling of the
relative distance of all other positions to $P_{i}$. The position can be seen
in Table 1. A $k$-means instance needs $k$ initial centers
$C=\\{c_{1},\dots,c_{k}\\}$. We say that a center point $c_{j}$ corresponds to
a gadget $G_{i}$, if $\lceil\frac{j-1}{2}\rceil=i$. The initial position
${\mathcal{T}}_{i}$ of the two centers corresponding to $G_{i}$ are determined
as the mean of the points in an initial cluster. The two initial clusters for
each gadget $G_{i}$ with $i\neq 0$ are defined as all points in the position
$A_{i}$ and all points in the positions $P_{i},Q_{i},B_{i},C_{i},D_{i},E_{i}$.
For an illustration of one Gadget $G_{i}$ of ${X^{\prime}}$ with $i\neq 0$ see
Figure 2. The gadget $G_{0}$ is given by $({\mathcal{P}}_{0},C_{0})$ where
${\mathcal{P}}_{0}=C_{0}=\\{F\\}$. So all the $w_{F}$ points in position
$F=(0,0)$ determine the position $(0,0)$ of the initial center $c_{1}$.

Weights | Positions ${\mathcal{P}}_{i}$ | Other values
---|---|---
$w_{P}=100M$ | $P_{i}=S_{i-1}+(1-\varepsilon)R_{i}(1,0)$ | $\varepsilon=10^{-6}$
$w_{Q}=1M$ | $Q_{i}=P_{i}+r_{i}(10^{-5},0)$ | $r_{1}=1$
$w_{A}=400M$ | $A_{i}=P_{i}+r_{i}(1,-0.5)$ | $r_{i}\approx 40.41608r_{i-1}$
$w_{B}=400M$ | $B_{i}=P_{i}+r_{i}(1,0.5)$ | $R_{i}=1.25r_{i}$
$w_{C}=1100M$ | $C_{i}\approx P_{i}+r_{i}(1,0.70223)$ | $w_{F}=5000M$
$w_{D}=3100M$ | $D_{i}\approx P_{i}+r_{i}(1,1.35739)$ | $F=S_{0}=(0,0)$
$w_{E}=27400M$ | $E_{i}=P_{i}+r_{i}(0,1)$ | $S_{i}\approx P_{i}+r_{i}(1,0,99607)$
Table 1:  Approximate weights and positions of the points in the $k$-means
instance ${X^{\prime}}$ of [33].

To construct an instance ${X}$ for DBA out of the instance ${X^{\prime}}$ for
the $k$-means algorithm, we just connect the points of the gadgets together to
form two input point sequences. The first point sequence ${\gamma_{1}}$ starts
with half of the points in position $F$ followed by all points in the
positions $E_{i},D_{i},C_{i},B_{i}$ and half of the points in position $A_{i}$
in the given order and in the natural order
$1,\dots,\lceil\frac{k-1}{2}\rceil$ of the gadgets $G_{i}$. The second point
sequence ${\gamma_{2}}$ starts with the other half of the points in position
$F$ followed by all points in the positions $P_{i},Q_{i}$ and the other half
of the points in position $A_{i}$ (see also Figure 2). The initial assignment
map is chosen as in the $k$-means instance so that the initial average point
sequence has its points $c_{1},\dots,c_{k}$ in the same position as the
centers of the $k$-means instance.

###  4.2 Analysis

For a run of the $k$-means algorithm on the instance ${X^{\prime}}$, all the
occurring assignment maps between points and centers in any step of the
algorithm are described in [33]. Directly from the positions of the center
points given by these assignment maps, we can observe the following properties
for any set of center points that is present in any iteration of the $k$-means
algorithm.

Let $C=\\{c_{1},\dots,c_{k}\\}$ be a set of center points present in any
iteration of the $k$-means algorithm on ${X^{\prime}}$. The following
properties hold for $C$ and any $0\leq i\leq\lceil\frac{k-1}{2}\rceil$:

  1. 1.

Let $p$ be a point that lies in the gadget $G_{i}$. Let $c_{j}\in C$ be the
closest center point to $p$ (i.e. $c_{j}=\operatorname*{arg\,min}_{c\in
C}\lVert p-c\rVert$). We have

$\max_{c\in\\{c_{j-1},c_{j},c_{j+1}\\}}\lVert p-c\rVert\leq\alpha r_{i}$

where $\alpha>0$ is a constant that is independent of $i,p$ and the number of
gadgets.

  2. 2.

Let $p$ be a point that lies in either one of the gadgets
$G_{i-1},G_{i},G_{i+1}$. Let further
$c^{\prime}=\operatorname*{arg\,min}_{c\in C}\lVert p-c\rVert$ be the closest
center point and $c^{\prime\prime}=\operatorname*{arg\,min}_{c\in
C\setminus\\{c^{\prime}\\}}\lVert p-c\rVert$ bet the second closest center
point. We have

$\lVert p-c^{\prime\prime}\rVert-\lVert p-c^{\prime}\rVert\geq\beta r_{i}$

where $\beta>0$ is a constant that is independent of $i,p$ and the number of
gadgets.

Furthermore, it is easy to check that the following method always creates a
valid assignment map to the center point sequence in any iteration of DBA on
the instance ${X}$, based on the assignment map in the same iteration of the
$k$-means algorithm.

Method for creating valid assignment map: Take a fixed iteration of the
$k$-means algorithm on ${X^{\prime}}$. Let
$C^{\prime}=(c^{\prime}_{1},\dots,c^{\prime}_{k})$ be the sequence of centers
in this iteration of the $k$-means algorithm and let $C=(c_{1},\dots,c_{k})$
be the points of the average point sequence in this iteration of DBA. Let
${\pi^{\prime}}$ be the assignment map that assigns each point in
${X^{\prime}}$ to its nearest neighbor in $C^{\prime}$. We can interpret
${\pi^{\prime}}$ also as an assignment map of ${X}$ that assigns points of
${X}$ that lie in the same position as points of ${X^{\prime}}$ to points of
the center point sequence $C$ that have the same index as the assigned centers
in $C^{\prime}$. Let $I$ be the set of the indices of all points in $C$ that
do not get assigned to any point of the point sequence ${\gamma_{2}}$ by this
assignment map ${\pi^{\prime}}$. Note that there are no $i,j\in I$ with
$i=j+1$. For each point $j\in I$ take the last point $p_{-}(c_{j})$ of
${\gamma_{2}}$ that got assigned to $c_{j-1}$ and the first point
$p_{+}(c_{j})$ of ${\gamma_{2}}$ that got assigned to $c_{j+1}$. Choose
$p(c_{j})=\operatorname*{arg\,min}_{p\in\\{p_{-}(c_{j}),p_{+}(c_{j})\\}}\lVert
c_{j}-p\rVert$. Replace the previous assignment of $p(c_{j})$ with $c_{j}$.
Since we scale up the instance ${\pi}$ by a constant factor $M$, there are at
least $M$ points of $Q$ at position $p(c_{j})$. Only reassign the first
respectively last of these points to $c_{j}$. Denote the new created
assignment map with ${\pi}$.

In the following, we prove that the created valid assignment map ${\pi}$ is
also always an optimal assignment map for the instance ${X}$ (scaled by a
suitable constant $M$) and its corresponding center point sequence. This
result then directly implies that DBA on ${X}$ needs as many iterations as the
$k$-means algorithm on ${X^{\prime}}$ to converge, since the assignment map
changes in each two consecutive iterations of DBA, in which the corresponding
assignment map of the $k$-means algorithm changes. So DBA only converges in
any iteration, in which the $k$-means algorithm converges.

######  Theorem 4.1.

Let $M>4\frac{\alpha}{\beta}+4\frac{\alpha^{2}}{\beta^{2}}$. For any iteration
of DBA on the instance $X$ scaled up by the factor $M$, the valid assignment
map ${\pi}$ is an optimal assignment map.

######  Proof 4.2.

Fix a iteration of the $k$-means algorithm on ${X^{\prime}}$. If we take the
first iteration, then the center points (that the new assignment map is based
on) are the same as the points of the average point sequence in the first
iteration of DBA. Otherwise let ${\pi^{\prime}}_{1}$ be the assignment map in
the previous iteration of the $k$-means algorithm and ${\pi}_{1}$ be the
corresponding assignment map in the previous iteration of DBA.

We first show that the center points of $C_{{\pi^{\prime}}_{1}}$ that
correspond to gadget $G_{i}$ differ from their corresponding center points of
$C_{{\pi}_{1}}$ by at most $\frac{\alpha}{M}r_{i}$. From the construction of
${\pi^{\prime}}_{1}$, we know that the assigned points to each center point
$c_{j}({\pi^{\prime}}_{1})$ in ${\pi^{\prime}}_{1}$ and $c_{j}({\pi}_{1})$ in
${\pi}_{1}$ differ by at most one point. Assume that $c_{j}({\pi}_{1})$ has
one more point $p$. We have

$\displaystyle\lVert c_{j}({\pi^{\prime}}_{1})-c_{j}({\pi}_{1})\rVert$
$\displaystyle=\lVert
c_{j}({\pi^{\prime}}_{1})-\frac{c_{j}({\pi^{\prime}}_{1})\cdot|S_{j}({\pi^{\prime}}_{1})|+p}{|S_{j}({\pi^{\prime}}_{1})|+1})\rVert$
$\displaystyle=\lVert\frac{c_{j}({\pi^{\prime}}_{1})-p}{|S_{j}({\pi^{\prime}})|+1}\rVert$
$\displaystyle\leq\frac{1}{M}\lVert c_{j}({\pi^{\prime}}_{1})-p\rVert$
$\displaystyle\leq\frac{\alpha}{M}r_{i}$

Here the second to last inequality follows by $|S_{j}(\pi^{\prime})|\geq M$
(at least one scaled up point is assigned) and the last inequality follows by
the first part of Observation 4.2. The case that $c_{j}({\pi^{\prime}}_{1})$
has one more point is analogous. By the second property of Observation 4.2, we
know that the difference between the distances of a point from gadget
$G_{i-1},G_{i}$ or $G_{i+1}$ to its closest center and its second closest
center on $C_{{\pi^{\prime}}_{1}}$ is at least $\beta r_{i}$. So, for
$M>2\frac{\alpha}{\beta}$, it holds that

$2\frac{\alpha}{M}r_{i}<\beta r_{i},$

and it is ensured that the closest center of each point in both assignment
maps ${\pi^{\prime}}_{1}$ and ${\pi}_{1}$ has the same index. It further holds
that the difference between the distances of a point from gadget
$G_{i-1},G_{i}$ or $G_{i+1}$ to its closest center $c^{\prime}$ and its second
closest center $c^{\prime\prime}$ on $C_{{\pi}_{1}}$ is at least

$\lVert c^{\prime\prime}-p\rVert-\lVert c^{\prime}-p\rVert\geq\beta
r_{i}-2\frac{\alpha}{M}r_{i}.$ (2)

This is an important property for showing the optimality of the new assignment
map.

Let ${\pi^{\prime}}$ be the assignment map in the fixed iteration of the
$k$-means algorithm corresponding to the assignment map ${\pi}$ in the same
iteration of DBA. We have to show that ${\pi}$ is an optimal assignment map
between the input point sequences the average point sequence $C_{{\pi}_{1}}$
generated from the assignment map of the previous iteration (or the starting
average point sequence in the first iteration). Let
$OPT=\sum_{p\in{X}}\min_{j}\lVert c_{j}({\pi}_{1})-p\rVert^{2}$ be the cost of
the assignment map ${\pi^{\prime}}$ between the input point sequences and
$C_{{\pi}_{1}}$. We know that this assignment map is optimal, if it is valid,
since each point of the input point sequence has to be assigned to at least
one point of the center point sequence and $\pi^{\prime}_{j}$ assigns each
point only to its nearest neighbor. But this assignment map is not valid,
since there are multiple points of $C_{{\pi}_{1}}$ that do not get assigned to
any point of the point sequence ${\gamma_{2}}$ in instance ${X}$. We denote
the index set of these center points with $I$ and denote the points of
$C_{{\pi}_{1}}$ simply with $c_{1},\dots,c_{k}$ instead of
$c_{1}({\pi}_{1}),\dots,c_{k}({\pi}_{1})$. We show that for suitable $M$ each
valid assignment map results in a greater cost than ${\pi}$, by comparing
their resulting costs to $OPT$. Fix an arbitrary subset $I^{\prime}$ of $I$.
The cost of any assignment map that does not assign any point $c_{j}$ with
$j\in I^{\prime}$ to either $p_{+}(c_{j})$ or $p_{-}(c_{j})$ is greater than
$OPT$ by at least

$\displaystyle M\sum_{c_{j}\in I^{\prime}}\min(\Delta_{+}(j),\Delta_{-}(j))$
$\displaystyle+\sum_{c_{j}\in I\setminus I^{\prime}}\lVert
c_{j}-p(c_{j})\rVert^{2}-\min_{t}(\lVert c_{t}-p(c_{j})\rVert^{2})$

where

$\displaystyle\Delta_{+}(j)$ $\displaystyle=\min_{t\neq j+1}(\lVert
c_{t}-p_{+}(c_{j})\rVert^{2})-\lVert c_{j+1}-p_{+}(c_{j})\rVert^{2},$
$\displaystyle\Delta_{-}(j)$ $\displaystyle=\min_{t\neq j-1}(\lVert
c_{t}-p_{-}(c_{j})\rVert^{2})-\lVert c_{j-1}-p_{-}(c_{j})\rVert^{2}.$

Here we use that for each $c_{j}\in I$, either all the $M$ points in position
$p_{+}(c_{j})$ or in position $p_{-}(c_{j})$ have to get reassigned to another
center point. The assignment map ${\pi}$ is the best assignment map that
assigns all $c_{j}\in I$ to either $p_{+}(c_{j})$ or $p_{-}(c_{j})$. The cost
of ${\pi}$ is exactly

$\sum_{c_{j}\in I}\lVert c_{j}-p(c_{j})\rVert^{2}-\min_{t}(\lVert
c_{t}-p(c_{j})\rVert^{2})$

greater than $OPT$. So, if $M$ is chosen such that

$M\min(\Delta_{+}(j),\Delta_{-}(j))>\lVert c_{j}-p(c_{j})\rVert^{2}$ (3)

then ${\pi}$ is an optimal assignment map. By the first part of Observation
4.2, we have $\lVert c_{j}({\pi^{\prime}}_{1})-p(c_{j})\rVert\leq\alpha
r_{i}$. Since the center points of $C_{{\pi^{\prime}}_{1}}$ that correspond to
gadget $G_{i}$ differ from their corresponding center points of
$C_{{\pi}_{1}}$ by at most $\frac{\alpha}{M}r_{i}\leq\alpha r_{i}$, we further
get by triangle inequality

$\lVert c_{j}-p(c_{j})\rVert\leq\lVert
c_{j}({\pi^{\prime}}_{1})-p(c_{j})\rVert+\lVert
c_{j}({\pi^{\prime}}_{1})-c_{j}\rVert\leq 2\alpha r_{i}$

Since $c_{j+1}$ is the closest center to $p_{+}(c_{j})$ and $c_{j-1}$ is the
closest center to $p_{-}(c_{j})$, we get by Equation (2) that

$\min(\Delta_{+}(j),\Delta_{-}(j)>(\beta-2\frac{\alpha}{M})^{2}r_{i}^{2}.$

Here we used that for any $a>b>0$ it is $(a-b)^{2}>a^{2}-b^{2}$. It remains to
show that $M(\beta-2\frac{\alpha}{M})^{2}>4\alpha^{2}$. We have

$\displaystyle M(\beta-2\frac{\alpha}{M})^{2}$
$\displaystyle=M\beta^{2}-4\beta\alpha+4\frac{\alpha^{2}}{M}$
$\displaystyle>M\beta^{2}-4\beta\alpha$ $\displaystyle>4\alpha^{2}$

The last inequality follows by the assumption of the theorem that
$M>4\frac{\alpha}{\beta}+4\frac{\alpha^{2}}{\beta^{2}}$. So Equation (3) is
fulfilled and ${\pi}$ is an optimal assignment map.

Since $M$ can be chosen as a constant independent of $k$ the point sequences
${\gamma_{1}}$ and ${\gamma_{2}}$ of ${X}$ have a length $\Theta(k)$ each. We
technically require that both point sequences have the same length. The
difference in length can easily be balanced by adding an extra gadget in front
of gadget $G_{0}$ far away from the other gadgets that contains one point of
the longer point sequence and the difference in length plus one points of the
smaller point sequence. Also add another center point corresponding to the
gadget and initialize it at the mean of all points in the gadget. If all the
points are far enough away from any other points of the instance, the
corresponding center point does not change its position and the gadget does
not interfere with any other gadget. By the results of [33], we know that the
$k$-means algorithm needs $2^{\Omega(k)}$ iterations on the instance
${X^{\prime}}$. As stated earlier, Theorem 4.1 implies that DBA on ${X}$ needs
the same amount of iterations. We therefore achieve the following lower bound.

######  Theorem 4.3.

Let $k\in{\mathbb{N}}$. There is an instance of two point sequences with
length $m=\Theta(k)$ in the plane such that DBA needs $2^{\Omega(k)}$
iterations to converge.

##  5 Experiments on the M5 data set

In this section, we present our empirical observations on the number of
iterations of DBA on real world data. We run our implementation of the
algorithm on real world data sets of time series and observe that in practice
it runs much faster than the theoretical guarantees ensure.

###  5.1 Research questions

We are interested in how the number of iterations of the DBA algorithm depend
on the complexity of the input and output for practical data sets. More
specifically, we ask the following research questions.

  * •

What is the dependency of the number of iterations on the number $n$ of input
point sequences?

  * •

What is the dependency of the number of iterations on the length $m$ of the
input point sequences?

  * •

What is the dependency of the number of iterations on the length $k$ of the
output center?

###  5.2 Data set(s)

To answer our research questions, we apply the DBA algorithm on the data set
from the M5 Competition [23]. Preliminary experiments on data sets from the
UCR Time Series Classification Archive [10] have not shown a clear dependency
on any of the quantities in question. We conjecture that that this result can
be attributed to the heterogeneity of the data sets and the relatively short
length of the studied input point sequences. For a more detailed analysis of
this preliminary experiments see Appendix A.

The data set of the M5 Competition consists of the unit sales of products from
10 different Walmart stores in the USA. The sold number of units was tracked
daily over 1942 days from 2011-01-29 to 2016-06-19 for each product aggregated
for each store separately. The products can be divided into the $7$ product
departments Hobbies 1-2, Foods 1-3 and Household 1-2. To create input
sequences for DBA, we take for each product the time series that consists of
the summed up daily sales of this product over all 10 stores. The number of
input sequences in each department is given in Table 2. In our experiments, we
run DBA on sets of subsequences of such input sequences.

Hobbies 1 | Hobbies 2 | Foods 1 | Foods 2 | Foods 3 | Household 1 | Household 2
---|---|---|---|---|---|---
416 | 149 | 216 | 398 | 823 | 532 | 515
Table 2: Number of input sequences (different products) per department.

###  5.3 Setup of the experiments

To perform experiments, DBA was implemented in C++. The implementation is
based on the python implementation of François Petitjean [24, 26] and can be
found at [6]. In the following, we describe the setup of the experiments. All
of our experiments use the same random initialization method to select the
first center point sequence.

####  5.3.1 Random initialization

We initialize the first center point sequence from a random valid assignment
of the input sequences. The valid assignment is created by a combination of
random walks consisting of one walk per input sequence. Such a random walk
starts with assigning the first point of the input series to the first point
of the center point sequence and then chooses the next assignment by either
moving forward on both input and center sequence or only moving forward on one
of them. Each option has probability $1/3$. If it reaches the end of one
sequence it continues to only move forward on the other one. After the random
assignment is computed, the center points are chosen as the arithmetic means
of the assigned points from the input series.

####  5.3.2 Experiment 1: Dependency on the number $n$ of input point
sequences

We run DBA on sets of subsequences of consecutive days with varying sizes. The
specific sizes of the sets are taken exponentially growing as 25, 50, 100,
200, 400, 800, 1600 and 3049. To choose the time series for a specific set of
size $s$, we draw a number $r$ between $1$ and $3049-s$ uniformly at random
and take the time series at the positions $r,r+1,\dots,r+s$. We perform the
experiment three times for three fixed values $100$, $300$ and $500$ for the
length of the subsequences. In each run of the experiment, we run DBA ten
times for each fixed size of input sets and for input subseries of the fixed
length, where we draw the starting day of the input subseries uniformly at
random (same starting day for all series in the same run). For each run of
DBA, we track the number of iterations.

####  5.3.3 Experiment 2: Dependency on the length $m$ of the input point
sequences

In this experiment, we run DBA on each product department separately. This
approach leads to a very natural division of the data set that creates data
sets of different sizes. To be able to analyse the dependency of the number of
iterations on the length of the time series, we run DBA on subsequences of
input sequences with different length. We explicitly choose for each input
sequence, one subsequences of consecutive days. The values for the length of
the subsequences are taken exponentially growing as $15\cdot 2^{i}$ for $0\leq
i\leq 7$ (15, 30, 60, 120, 240, 480, 960, 1920). We run DBA ten times for each
fixed value of the length, where we draw the starting day of the input
subseries uniformly at random (same starting day for all series in the same
run). For each run of DBA, we track the number of iterations.

####  5.3.4 Experiment 3: Dependency on the length $k$ of the output center

For the same reasons as in Experiment 2, we run the experiment on different
Product departments separately. For sake of a clearer presentation, we
restrict ourselfs to the product departments Foods 1, Foods 2 and Foods 3. As
input sequences, we take all time series that correspond the respective
product department. For each department, we run DBA for several length of the
output center, where we test each value of the length ten times. The values
for the length of the center are taken again as $15\cdot 2^{i}$ for $0\leq
i\leq 7$ (15, 30, 60, 120, 240, 480, 960, 1920). For each run of DBA, we track
the number of iterations.

##  6 Results of the experiments

In this section, we state the results of the described experiments. More
detailed tables and box plots of the exact results can be found in Appendix B.
The results of Experiment 1, 2 and 3 are depicted in Figure 3, 4 and 5. For
Experiment 1, the relation between the average number of iterations and the
number of the input point sequences is shown in Figure 3. For Experiment 2,
the relation between the average number of iterations and the length of the
input point sequences is shown in Figure 4 and for Experiment 3, the relation
between the average number of iterations and the length of the output center
is shown in Figure 5.

Figure 3: Depiction of the average number of iterations of the DBA algorithm
with respect to the number of time series in the chosen sets. Each function
graph corresponds to a fixed length of all time series in the sets. The left
graphic uses normal scales and the right graphic uses logarithmic scales on
both axes. Figure 4: Depiction of the average number of iterations of the DBA
algorithm with respect to the length of the series in the chosen sets. Each
function graph corresponds to one product department. The left graphic uses
normal scales and the right graphic uses logarithmic scales on both axes.
Figure 5: Depiction of the average number of iterations of the DBA algorithm
with respect to the length of the center point sequence. Each function graph
corresponds to one product department. The left graphic uses normal scales and
the right graphic uses logarithmic scales on both axes.

As we can see in all three figures, the dependency on each parameter seems to
be sublinear. Since the function graphs appear linear in the log-log plots,
the dependencies seem to be polynomial for exponents smaller $1$. Estimations
for the exponents which were computed with linear regression on the points in
the log-log-plots are given in Table 3, 4 and 5.

Length | 100 | 200 | 300
---|---|---|---
Exponent | 0.27 | 0.35 | 0.36
Table 3: Experiment 1: Estimations for the exponents of the dependency on the size of the input point sequences for each fixed length of the input point sequences. Dep. | Hobbies 1 | Hobbies 2 | Foods 1 | Foods 2 | Foods 3 | Household 1 | Household 2
---|---|---|---|---|---|---|---
Exp. | 0.50 | 0.38 | 0.42 | 0.47 | 0.50 | 0.51 | 0.50
Table 4: Experiment 2: Estimations for the exponents of the dependency on the length of the output center for each Department. Department | Foods 1 | Foods 2 | Foods 3
---|---|---|---
Exponent | 0.16 | 0.16 | 0.20
Table 5: Experiment 3: Estimations for the exponents of the dependency on the
length of the input point sequences for each Department.

##  7 Conclusions

Our experimental results show a gap between the theoretical bounds we were
able to prove for semi-random input models and the number of steps DBA takes
on real-world data. This suggests two directions for further research: (1)
developing refined worst-case bounds under realistic input models, and (2)
sharpening the obtained smoothed analysis estimates to better reflect
practical performance.

The structure of the DBA heuristic is very similar to the classical $k$-means
algorithm. One would naturally expect the techniques from the analysis of the
$k$-means algorithm to be useful for the analysis the DBA heuristic. This was
true for the geometric ideas of Vattani in the case of proving lower bounds in
Section 4. However, surprisingly, the techniques for smoothed analysis of
$k$-means were not effective in the smoothed analysis of DBA. The main
difference seems to be following: In every step of the $k$-means algorithm,
i.e. every change of assignment for a point from one center to another, the
distance decreases. This gives $k$-means a very monotonic behaviour. In DBA we
use dynamic time warping distance (DTW) and the behaviour is not necessarily
monotonic: A change in the assignment of a point $x$ in point sequence
$\gamma_{1}$ can increase the distance of the point $x$ while the total DTW
distance between point sequence $\gamma_{1}$ and the mean point sequence
decreases. This behaviour seems to rule out usage of most useful techniques
from [1]. Instead, we manage to exploit the specific properties of DBA, as it
requires the assignments between the points of an input sequence and the mean
point sequence to respect the ordering along the mean point sequence and along
the input sequence.

In Section 2, we use bounds on the complexity of arrangements of algebraic
curves.

A similar technique was used earlier by Buchin et al. [8] to derive an exact
exponential-time algorithm for the DTW-MEAN problem.

## References

  * [1] D. Arthur, B. Manthey, and H. Röglin.  Smoothed analysis of the k-means method.  J. ACM, 58(5), 2011.
  * [2] D. Arthur and S. Vassilvitskii.  How slow is the k-means method?  In Proc. Symp. on Computational Geometry, SCG ’06, page 144–153. ACM, 2006.
  * [3] S. Barone and S. Basu.  On a real analog of Bezout inequality and the number of connected components of sign conditions.  Proc. London Mathematical Society, 112(1):115–145, 2016.
  * [4] D. J. Berndt and J. Clifford.  Using dynamic time warping to find patterns in time series.  In KDD workshop, volume 10, pages 359–370, 1994.
  * [5] M. Brill, T. Fluschnik, V. Froese, B. Jain, R. Niedermeier, and D. Schultz.  Exact mean computation in dynamic time warping spaces.  Data Mining and Knowledge Discovery, 33(1):252–291, 2019.
  * [6] F. Brüning.  DBA implementation.  GitHub, 2022.  https://github.com/FrederikBruening/DBA.
  * [7] K. Buchin, A. Driemel, and M. Struijs.  On the hardness of computing an average curve.  In 17th Scandinavian Symp. and Workshops on Algorithm Theory, SWAT 2020, volume 162, pages 19:1–19:19, 2020.
  * [8] M. Buchin, A. Driemel, K. van Greevenbroek, I. Psarros, and D. Rohde.  Approximating length-restricted means under dynamic time warping.  In Approximation and Online Algorithms: 20th WAOA, 2022.
  * [9] L. Bulteau, V. Froese, and R. Niedermeier.  Tight hardness results for consensus problems on circular strings and time series.  SIAM Journal on Discrete Mathematics, 34(3):1854–1883, 2020.
  * [10] Y. Chen, E. Keogh, B. Hu, N. Begum, A. Bagnall, A. Mueen, and G. Batista.  The UCR time series classification archive, July 2015.  www.cs.ucr.edu/~eamonn/time_series_data/.
  * [11] F. Cucker, A. Ergür, and J. Tonelli-Cueto.  Plantinga-Vegter algorithm takes average polynomial time.  In Proc. of the 2019 on international symposium on symbolic and algebraic computation, pages 114–121, 2019.
  * [12] A. De Luca, A. Hang, F. Brudy, C. Lindner, and H. Hussmann.  Touch me once and i know it’s you! implicit authentication based on touch screen patterns.  Conference on Human Factors in Computing Systems - Proceedings, 05 2012.
  * [13] A. Ergür, G. Paouris, and J. Rojas.  Smoothed analysis for the condition number of structured real polynomial systems.  Mathematics of Computation, 2021.
  * [14] H. I. Fawaz, G. Forestier, J. Weber, L. Idoumghar, and P. Muller.  Data augmentation using synthetic data for time series classification with deep residual networks.  arXiv:1808.02455, 2018.
  * [15] G. Forestier, F. Lalys, L. Riffaud, B. Trelhu, and P. Jannin.  Classification of surgical processes using dynamic time warping.  Journal of biomedical informatics, 45(2):255–264, 2012.
  * [16] G. Forestier, F. Petitjean, H. A. Dau, G. I. Webb, and E. Keogh.  Generating synthetic time series to augment sparse datasets.  In 2017 IEEE international conference on data mining (ICDM), pages 865–870, 2017.
  * [17] D. M. Gavrila and L. S. Davis.  Towards 3-d model-based tracking and recognition of human movement: a multi-view approach.  In International Workshop on Automatic Face- and Gesture-Recognition. IEEE, pages 272–277, 1995.
  * [18] S. Har-Peled and B. Sadri.  How fast is the k-means method?  Algorithmica, 41(3):185–202, 2005.
  * [19] M. Inaba, N. Katoh, and H. Imai.  Variance-based k-clustering algorithms by voronoi diagrams and randomization.  IEICE Trans. on Information and Systems, 83(6):1199–1206, 2000.
  * [20] E. Keogh and C. A. Ratanamahatana.  Exact indexing of dynamic time warping.  Knowledge and information systems, 7(3):358–386, 2005.
  * [21] J. Lines and A. Bagnall.  Time series classification with ensembles of elastic distance measures.  Data Mining and Knowledge Discovery, 29(3):565–592, 2015.
  * [22] S. Lloyd.  Least Squares Quantization in PCM.  IEEE Trans. on information theory, 28(2):129–137, 1982.
  * [23] S. Makridakis, E. Spiliotis, and V. Assimakopoulos.  The M5 competition: Background, organization, and implementation.  International Journal of Forecasting, 38(4):1325–1336, 2022.  Special Issue: M5 competition.
  * [24] F. Petitjean.  DBA.  GitHub repository, 2014.  https://github.com/fpetitjean/DBA.git.
  * [25] F. Petitjean, G. Forestier, G. I. Webb, A. E. Nicholson, Y. Chen, and E. Keogh.  Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm.  Knowledge and Information Systems, 47(1):1–26, 2016.
  * [26] F. Petitjean, A. Ketterlin, and P. Gançarski.  A global averaging method for dynamic time warping, with applications to clustering.  Pattern Recognition, 44(3):678–693, 2011.
  * [27] H. Sakoe and S. Chiba.  Dynamic programming algorithm optimization for spoken word recognition.  IEEE Trans. on Acoustics, Speech, and Signal Processing, 26:43–49, 1978.
  * [28] D. Schultz and B. Jain.  Nonsmooth analysis and subgradient methods for averaging in dynamic time warping spaces.  Pattern Recognition, 74:340–358, 2018.
  * [29] S. Seto, W. Zhang, and Y. Zhou.  Multivariate time series classification using dynamic time warping template selection for human activity recognition.  In IEEE Symp. on comp. intelligence, pages 1399–1406, 2015.
  * [30] A. Shanker and A.N. Rajagopalan.  Off-line signature verification using DTW.  Pattern Recognition Letters, 28:1407–1414, 09 2007.
  * [31] T. Teeraratkul, D. O’Neill, and S. Lall.  Shape-based approach to household electric load curve clustering and prediction.  IEEE Trans. on Smart Grid, 9(5):5196–5206, 2017.
  * [32] H. Teichgraeber and A. R. Brandt.  Clustering methods to find representative periods for the optimization of energy systems: An initial framework and comparison.  Applied energy, 239:1283–1293, 2019.
  * [33] A. Vattani.  k-means requires exponentially many iterations even in the plane.  Discrete & Computational Geometry, 45(4):596–616, 2011.

##  Appendix A Experiments on the UCR Time Series Classification Archive

The UCR Time Series Classification Archive contains many data sets from
different areas. For our experiments, we selected the same subset of data sets
as Schultz and Jain [28]. For each data set, we merge the training and test
sets into a single data set. Each data set is divided into several classes and
only contains time series of identical length. In Table 6, we display the
name, the number $c$ of classes, the total number $n$ of time series, the
average number $n/c$ of time series per cluster and the length $m$ of each
data set.

Dataset | $c$ | $n$ | $n/c$ | $m$ | $\mu_{1}$ | $\sigma_{1}^{2}$ | $\mu_{2}$ | $\sigma_{2}^{2}$
---|---|---|---|---|---|---|---|---
50words | 50 | 905 | 18.10 | 270 | 50.66 | 49.56 | 45.41 | 45.86
Adiac | 37 | 781 | 21.11 | 176 | 3.24 | 3.93 | 38.05 | 9.45
Beef | 5 | 60 | 12.00 | 470 | 88.60 | 61.83 | 85.6 | 53.02
CBF | 3 | 930 | 310.00 | 128 | 98.00 | 39.30 | 67.77 | 18.93
ChlorineConcentration | 3 | 4307 | 1435.67 | 166 | 78.67 | 10.34 | 96.67 | 38.42
Coffee | 2 | 56 | 28.00 | 286 | 37.50 | 8.50 | 40.15 | 6.37
ECG200 | 2 | 200 | 100.00 | 96 | 65.50 | 12.50 | 53.40 | 9.53
ECG5000 | 5 | 5000 | 1000.00 | 140 | 110.40 | 80.50 | 136.50 | 144.87
ElectricDevices | 7 | 16637 | 2376.71 | 96 | 50.14 | 26.44 | 57.96 | 47.15
FaceAll | 14 | 2250 | 160.71 | 131 | 40.43 | 17.88 | 67.29 | 28.81
FaceFour | 4 | 112 | 28.00 | 350 | 29.50 | 9.96 | 33.45 | 7.89
Fish | 7 | 350 | 50.00 | 463 | 93.57 | 33.67 | 77.84 | 23.20
Gun_Point | 2 | 200 | 100.00 | 150 | 46.00 | 4.00 | 62.75 | 22.29
Lighting2 | 2 | 121 | 60.50 | 637 | 80.00 | 8.00 | 47.85 | 10.36
Lighting7 | 7 | 143 | 20.43 | 319 | 30.29 | 24.52 | 23.64 | 8.12
OliveOil | 4 | 60 | 15.00 | 570 | 34.75 | 21.09 | 49.90 | 20.10
OSULeaf | 6 | 441 | 73.50 | 427 | 164.00 | 54.99 | 126.63 | 120.17
PhalangesOutlineCorrect | 2 | 2658 | 1329.00 | 80 | 57.50 | 3.50 | 192.00 | 74.70
SwedishLeaf | 15 | 1125 | 75.00 | 128 | 28.34 | 11.01 | 55.82 | 15.36
synthetic_control | 6 | 600 | 100.00 | 60 | 32.00 | 8.52 | 31.05 | 10.45
Trace | 4 | 200 | 50.00 | 275 | 29.00 | 4.06 | 54.55 | 25.66
Two_Patterns | 4 | 5000 | 1250.00 | 128 | 104.25 | 23.59 | 81.53 | 28.97
wafer | 2 | 7164 | 3582.00 | 152 | 67.5 | 4.50 | 52.05 | 7.63
yoga | 2 | 3300 | 1650.00 | 426 | 672.5 | 197.5 | 563.95 | 292.07
Table 6: Characteristics of the UCR TS datasets and the results for applying
DBA. Here, $c$ stands for the number of classes, $n$ for the number of series,
$n/c$ is therefore the average number of series in a class and $m$ is the
length of each time series. The value $\mu_{i}$ stands for the average number
of iterations and $\sigma_{i}^{2}$ stands for the variance in the number of
iterations over all classes. Here the index $i=1$ stands for medoid
initialization and $i=2$ stands for random initialization.

We run the DBA algorithm on the chosen data sets for two different
initialization methods (medoid and random) and analyse the dependency of the
number of iterations on the number and length of the series. As input, we take
each class of the data set separately and track the number of iterations
needed by the DBA algorithm to converge. In the end, we compute the average
number of iterations over all classes and the corresponding variances.

For the medoid initialization, we take the input point sequence as the
starting center that minimizes the DTW distance to the other input point
sequences. For the random initialization, we construct the starting center
from a valid assignment of the input sequences. The valid assignment is
created by a combination of random walks consisting of one walk per input
sequence. Such a random walk starts with assigning the first point of the
input series to the first point of the center point sequence and then chooses
the next assignment by either going to the next point on the input series
while staying at the same point of the center point sequence, going to then
next point on the center point sequence while staying at the same point of the
input series or moving to the next point on both series. Each option is taken
with probability $1/3$. It can also happen, that there is only one valid
option remaining, which is then always chosen. After the random assignment is
computed, the center points are chosen as the arithmetic means of the assigned
points from the input series. In the case of the random initialization, we run
the DBA algorithm 10 times per cluster and calculate the average number of
iterations over all runs on all clusters.

For each data set, we depict the tracked average number of iterations of the
DBA algorithm and the corresponding variances in Table 6 and Figure 6. The
figures do not suggest any clear dependency of the number of iterations on the
number or length of the input point sequences for any of the two
initialization methods. We conjecture that that this result can be attributed
to the heterogeneity of the data sets.

Figure 6: Depiction of the average number of iterations of the DBA algorithm
with respect to the length and number of the series in the corresponding data
sets. Each color corresponds to one data set of the UCR Time Series
Clasification Archive. The graphics on the left side show the results for the
medoid initialization and the ones on the right side show the results for the
random initialization.

##  Appendix B Data of the experiments on the M5 data set

This chapter includes the detailed data of the experiments on the M5 data set.
The data of Experiment 1 about the Dependency on the number of input point
sequences is depicted in Table 7, Table 8 and Figure 8, the data of Experiment
2 about the Dependency on the length of the input point sequences is depicted
in Table 9, Table 10 and Figure 8 and the data of Experiment 3 about the
Dependency on the length of the output center is depicted in Table 11, Table
12 and Figure 9.

Mean of the number of iterations (Experiment 1)
---
Sequences | 25 | 50 | 100 | 200 | 400 | 800 | 1600 | 3149
Length |  |  |  |  |  |  |  |
100 | 14.1 | 21.2 | 26.9 | 28.5 | 38.5 | 42.9 | 55.9 | 51.5
300 | 18.3 | 28.9 | 42.3 | 57.9 | 72.2 | 78.4 | 113.2 | 97.3
500 | 25.7 | 32.2 | 51.1 | 60.6 | 80 | 115.5 | 116 | 141.4
Table 7: Mean of the number of iterations with respect to the number of input
point sequences. Each row corresponds to one fixed length of the input
sequences Variance of the number of iterations (Experiment 1)
---
Sequences | 25 | 50 | 100 | 200 | 400 | 800 | 1600 | 3149
Length |  |  |  |  |  |  |  |
100 | 2.88 | 4.73 | 7.53 | 5.41 | 8.67 | 11.94 | 22.87 | 17.25
300 | 5.64 | 6.99 | 8.82 | 14.02 | 25.72 | 26.75 | 57.45 | 29.33
500 | 8.94 | 6.90 | 7.62 | 17.49 | 21.67 | 34.80 | 34.35 | 44.50
Table 8: Variance of the number of iterations with respect to the number of
input point sequences. Each row corresponds to one fixed length of the input
sequences Figure 7: Experiment 1: Boxplots of the number of iterations for
each department and each number of input sequences. Each graphic corresponds
to one fixed length of the input sequences and has a logarithmic scale on the
horizontal axis. Only the last graphic has regular scale on the horizontal
axis. It depicts the mean of the number of iterations per number of input
sequences for each of the departments. Mean of the number of iterations
(Experiment 2)
---
Length | 15 | 30 | 60 | 120 | 240 | 480 | 960 | 1920
Department |  |  |  |  |  |  |  |
Hobbies 1 | 17.3 | 27.2 | 35.2 | 45.7 | 80 | 88.2 | 142.9 | 214
Hobbies 2 | 12.2 | 22.4 | 29.9 | 30.5 | 38 | 64.6 | 71.1 | 89.3
Foods 1 | 15 | 21.5 | 27.6 | 37 | 64.2 | 75.8 | 88.1 | 103.8
Foods 2 | 14 | 24.2 | 37.5 | 50.8 | 57.2 | 89 | 117.4 | 150.7
Foods 3 | 17.7 | 23.2 | 36 | 52 | 69.1 | 116.9 | 136.4 | 189.3
Household 1 | 16.4 | 21.6 | 30.2 | 52.3 | 76.7 | 75.8 | 126.1 | 203.5
Household 2 | 17.8 | 27.7 | 33.5 | 67 | 79.1 | 100.2 | 162.1 | 193.5
Table 9: Mean of the number of iterations with respect to the length of the
input point sequences. Each row corresponds to one product department.
Variance of the number of iterations (Experiment 2)
---
Length | 15 | 30 | 60 | 120 | 240 | 480 | 960 | 1920
Department |  |  |  |  |  |  |  |
Hobbies 1 | 3.38 | 11.12 | 12.66 | 15.47 | 30.43 | 20.36 | 44.97 | 70.87
Hobbies 2 | 2.56 | 9.31 | 18.56 | 8.09 | 11.06 | 12.86 | 7.99 | 28.43
Foods 1 | 4.47 | 5.57 | 10.34 | 12.17 | 15.07 | 21.89 | 10.19 | 27.32
Foods 2 | 3.16 | 7.00 | 11.81 | 19.72 | 14.61 | 27.66 | 20.19 | 54.80
Foods 3 | 6.42 | 6.08 | 11.33 | 19.44 | 37.63 | 45.65 | 41.44 | 33.05
Household 1 | 3.41 | 3.53 | 8.22 | 28.78 | 32.95 | 19.1405 | 47.66 | 68.82
Household 2 | 6.87 | 12.1 | 9.57 | 30.94 | 27.06 | 21.50 | 40.80 | 51.16
Table 10: Variance of the number of iterations with respect to the length of
the input point sequences. Each row corresponds to one product department
Figure 8: Experiment 2: Boxplots of the number of iterations for each
department and each length of input sequences. Each graphic corresponds to one
product department and has a logarithmic scale on the horizontal axis. Only
the last graphic has regular scale on the horizontal axis. It depicts the mean
of the number of iterations per length for each of the departments. Mean of
the number of iterations (Experiment 3)
---
Length of Center | 15 | 30 | 60 | 120 | 240 | 480 | 960 | 1920
Department |  |  |  |  |  |  |  |
Foods 1 | 52.5 | 64.5 | 85.2 | 98.9 | 93.5 | 93.1 | 124.6 | 123.6
Foods 2 | 62.3 | 84.1 | 97 | 101.1 | 115.1 | 132.9 | 143.4 | 139.2
Foods 3 | 83.9 | 100.3 | 116.5 | 126.7 | 160.1 | 157 | 201.3 | 226.8
Table 11: Mean of the number of iterations with respect to the length of the
output center. Each row corresponds to one product department. Variance of the
number of iterations (Experiment 3)
---
Length of Center | 15 | 30 | 60 | 120 | 240 | 480 | 960 | 1920
Department |  |  |  |  |  |  |  |
Foods 1 | 6.07 | 11.60 | 15.90 | 17.47 | 13.07 | 14.01 | 20.11 | 36.69
Foods 2 | 11.1 | 19.24 | 17.78 | 13.86 | 28.68 | 51.42 | 40.39 | 32.44
Foods 3 | 25.78 | 13.33 | 27.15 | 25.08 | 50.25 | 36.90 | 53.62 | 66.71
Table 12: Variance of the number of iterations with respect to the length of
the output center. Each row corresponds to one product department Figure 9:
Experiment 3: Boxplots of the number of iterations for each department and
each length of the output center. Each graphic corresponds to one product
department and has a logarithmic scale on the horizontal axis. Only the last
graphic has regular scale on the horizontal axis. It depicts the mean of the
number of iterations per fixed length of the output center for each of the
departments.