Guest lectures and seminars - Page 16
Online changepoint detection algorithms based on likelihood-ratio tests have excellent statistical properties. However, a simple exact online implementation is computationally infeasible as, at time T, it involves considering O(T) possible locations for the change. To improve on this, we use functional pruning ideas to reduce the set of changepoint locations that need to be stored at time T to approximately log T. Furthermore, we show how we need only maximise the likelihood-ratio test statistic over a small subset of these possible locations. Empirical results show that the resulting exact online algorithm, which can detect changes under a wide range of models, has a constant-per-iteration cost on average. We consider applications of this algorithm in the context of detecting increases in radiation count that represent astronomical or nuclear events of interest.
The Kolmogorov N-width describes the best possible error one can achieve by elements of an N-dimensional linear space. Its decay has extensively been studied in Approximation Theory and for the solution of Partial Differential Equations (PDEs). Particular interest has occurred within Model Order Reduction (MOR) of parameterized PDEs e.g. by the Reduced Basis Method (RBM). While it is known that the N-width decays exponentially fast (and thus admits efficient MOR) for certain problems, there are examples of the linear transport and the wave equation, where the decay rate deteriorates to N-1/2. On the other hand, it is widely accepted that a smooth parameter dependence admits a fast decay of the N-width. However, a detailed analysis of the influence of properties of the data (such as regularity or slope) on the rate of the N-width seems to lack. In this work, we use techniques from Fourier Analysis to derive exact representations of the N-width in terms of initial and boundary conditions of the linear transport equation modeled by some function g for half-wave symmetric data. For arbitrary functions g, we derive bounds and prove that these bounds are sharp. In particular, we prove that the N-width decays as cr N(-r-1/2) for functions in the Sobolev space, g ∈ Hr. Our theoretical investigations are complemented by numerical experiments which confirm the sharpness of our bounds and give additional quantitative insigh.
This talk will introduce a recent suite of research focussed on the statistical detection of anomalous structure in online data settings. The challenge of efficiently identifying anomalies in data sequences is an important statistical problem that now arises in many applications. Whilst there has been substantial work aimed at making statistical analyses robust to outliers, or point anomalies, there has been much less work on detecting anomalous segments, or collective anomalies, particularly in those settings where point anomalies might also occur. This is the challenge we seek to address, demonstrating theoretical results in both the offline and online settings as well as introducing some applied case studies.