Approximation algorithms for confidence bands for time series
This work addresses the problem of detecting abnormal time series for data analysts, offering algorithmic solutions with approximation guarantees, though it is incremental in improving existing confidence interval methods.
The paper tackles the NP-hard problem of finding optimal confidence bands for time series by introducing regularized bands solvable via minimum cut, achieving exact solutions for some k and an O(√n) approximation otherwise, with a 2-approximation for a variant minimizing maximum width.
Confidence intervals are a standard technique for analyzing data. When applied to time series, confidence intervals are computed for each time point separately. Alternatively, we can compute confidence bands, where we are required to find the smallest area enveloping $k$ time series, where $k$ is a user parameter. Confidence bands can be then used to detect abnormal time series, not just individual observations within the time series. We will show that despite being an NP-hard problem it is possible to find optimal confidence band for some $k$. We do this by considering a different problem: discovering regularized bands, where we minimize the envelope area minus the number of included time series weighted by a parameter $α$. Unlike normal confidence bands we can solve the problem exactly by using a minimum cut. By varying $α$ we can obtain solutions for various $k$. If we have a constraint $k$ for which we cannot find appropriate $α$, we demonstrate a simple algorithm that yields $O(\sqrt{n})$ approximation guarantee by connecting the problem to a minimum $k$-union problem. This connection also implies that we cannot approximate the problem better than $O(n^{1/4})$ under some (mild) assumptions. Finally, we consider a variant where instead of minimizing the area we minimize the maximum width. Here, we demonstrate a simple 2-approximation algorithm and show that we cannot achieve better approximation guarantee.