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 $$ \widetilde{O} \left( n^2 m^{8\frac{n}{d}+6}d^4k^6\sigma ^{-2} \right) $$ , where $$\sigma $$ is the variance of the perturbation and the $$\widetilde{O}(\cdot )$$ -notation omits logarithmic factors. For our analysis, we adapt the set of techniques that were developed for analysing the k-means method and observe that this set of techniques is not sufficient to obtain tight bounds for general n.

Suppose f is a polynomial in n variables with degree d, exactly n + k monomial terms, coefficients in { ± 1, …, ±H} for some <?TeX $H\!\in \!\mathbb {N}$?> Math 1 , and Newton polytope of positive volume. Testing real feasibility of such an f is a fundamental task whose bit-complexity remains a mystery, even in the first non-trivial case k = 2: The fastest algorithms so far have deterministic bit-complexity (nlog (dH))O(n). We prove a significant speed-up that holds for all but a small collection of inputs in the k = 2 case: Bit complexity (nlog (dH))O(1) for all but a <?TeX $O\!\left(\frac{1}{2^n H}\right)$?> Math 2 -fraction of the f above, for any fixed support. Our result follows by combining a connection to diophantine approximation with a more recent anti-concentration result. In particular, we show that for random inputs, Baker’s famous theorem on linear forms in logarithms can be significantly sharpened. We also consider extensions beyond feasibility such as counting connected components and systems of circuit polynomials.

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 ℝ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.

Isolating the real roots of univariate polynomials is a fundamental problem in symbolic computation and it is arguably one of the most important problems in computational mathematics. The problem has a long history decorated with numerous ingenious algorithms and furnishes an active area of research. However, the worst-case analysis of root-finding algorithms does not correlate with their practical performance. We develop a smoothed analysis framework for polynomials with integer coefficients to bridge the gap between the complexity estimates and the practical performance. In this setting, we derive that the expected bit complexity of Descartes solver to isolate the real roots of a polynomial, with coefficients uniformly distributed, is ÕB(d2 + dτ), where d is the degree of the polynomial and τ the bitsize of the coefficients.

Motivated by applications in combinatorial geometry, we consider the following question: Let $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_m)$ be an $m$-partition of a positive integer $n$, $S_i \subseteq \mathbb{C}^{\lambda_i}$ be finite sets, and let $S:=S_1 \times S_2 \times \cdots \times S_m \subset \mathbb{C}^n$ be the multigrid defined by $S_i$. Suppose $p$ is an $n$-variate degree $d$ polynomial. How many zeros does $p$ have on $S$? We first develop a multivariate generalization of the combinatorial nullstellensatz that certifies existence of a point $t \in S$ so that $p(t) \neq 0$. Then we show that a natural multivariate generalization of the DeMillo--Lipton--Schwartz--Zippel lemma holds, except for a special family of polynomials that we call $\lambda$-reducible. This yields a simultaneous generalization of the Szemerédi--Trotter theorem and the Schwartz--Zippel lemma into higher dimensions, and has applications in incidence geometry. Finally, we develop a symbolic algorithm that identifies certain $\lambda$-reducible polynomials. More precisely, our symbolic algorithm detects polynomials that include a Cartesian product of hypersurfaces in their zero set. It is likely that using Chow forms the algorithm can be generalized to handle arbitrary $\lambda$-reducible polynomials, which we leave as an open problem.

We determine the rank of a random matrix A over an arbitrary field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes. This formula vindicates a conjecture of Lelarge [Proc. IEEE Information Theory Workshop 2013]. The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that likely diminishes the number of short linear relations.

We exhibit a condition-based analysis of the adaptive subdivision algorithm due to Plantinga and Vegter. The first complexity analysis of the \pv~Algorithm is due to Burr, Gao and Tsigaridas who proved a \mathcalO \big(2^τ d^4 łog d \big) worst-case cost bound for degree d plane curves with maximum coefficient bit-size~τ. This exponential bound, it was observed, is in stark contrast with the good performance of the algorithm in practice. More in line with this performance, we show that, with respect to a broad family of measures, the expected time complexity of the \pv~Algorithm is bounded by O(d^7) for real, degree d, plane curves. We also exhibit a smoothed analysis of the \pv~Algorithm that yields similar complexity estimates. To obtain these results we combine robust probabilistic techniques coming from geometric functional analysis with condition numbers and the continuous amortization paradigm introduced by Burr, Krahmer and Yap. We hope this will motivate a fruitful exchange of ideas between the different approaches to numerical computation.