TurboLift: fast accuracy lifting for historical data recovery

Abstract

Historical data are frequently involved in situations where the available reports on time series are temporally aggregated at different levels, e.g., the monthly counts of people infected with measles. In real databases, the time periods covered by different reports can have overlaps (i.e., time-ticks covered by more than one reports) or gaps (i.e., time-ticks not covered by any report). However, data analysis and machine learning models require reconstructing the historical events in a finer granularity, e.g., the weekly patient counts, for elaborate analysis and prediction. Thus, data disaggregation algorithms are becoming increasingly important in various domains. Time series disaggregation methods commonly utilize domain knowledge about the data, e.g., smoothness, periodicity, or sparsity, to improve the reconstruction accuracy. In this paper, we propose a novel approach, called TurboLift, which aims to improve the quality of the solutions provided by existing disaggregation methods. Starting from a solution produced by a specific method, TurboLift finds a new solution that reduces the disaggregation error and is close to the initial one. We derive a closed-form solution to the proposed formulation of TurboLift that enables us to obtain an accurate reconstruction analytically, without performing resource and time-consuming iterations. Experiments on real data from different domains showcase the effectiveness of TurboLift in terms of disaggregation error, and outlier and anomaly detection.

A preliminaries of the analytical solution

In this section introduce some mathematical background to facilitate the understanding of the Lemma 1

• $\textbf{A}^T\textbf{A} \in \mathcal {R} ^ {N \times N}$ is a positive semi-definite matrix.

• The singular value decomposition (SVD) of $\textbf{A}^T\textbf{A}$ is $\textbf{U} {\varvec{\Sigma }} \textbf{U}^T$, where $\textbf{U} \in \mathcal {R}^{N\times N}$ contains a set of singular vectors of $\textbf{A}^T\textbf{A}$ and ${\varvec{\Sigma }} \in \mathcal {R}^{N\times N}$ is a diagonal matrix with non-negative singular values $\lambda _i >= 0$ $(i = 1,2,\ldots ,N)$ on the diagonal.

• The singular value matrix ${\varvec{\Sigma }}a$ can be written as a partitioned matrix $\begin{bmatrix} {\varvec{\Sigma }}_1 &{} 0 \\ 0 &{} 0 \end{bmatrix}$ where ${\varvec{\Sigma }}_1 \in \mathcal {R}^{M \times M}$ contains all nonzero singular values. Correspondingly the matrix $\textbf{U}$ can split into two parts $[\textbf{U}_1, \textbf{U}_2]$, where $\textbf{U}_1 \in \mathcal {R}^{N\times M}$ contains the singular vectors corresponding to the nonzero singular values, while $\textbf{U}_2 \in \mathcal {R}^{N\times (N-M)}$ contains the remaining part. Based on the property of a singular vector, $\textbf{U}_1 \perp \textbf{U}_2$ $(\textbf{U}_1^T\textbf{U}_2 = 0)$ and $\textbf{U}_2 \perp \textbf{A}^T$ $(\textbf{U}_2^T\textbf{A}^T = 0)$

• Suppose we have

  $$\begin{aligned} {\varvec{\Lambda }}&= {\varvec{\Sigma }} + \textbf{I}_n \\&= \begin{bmatrix} {\varvec{\Sigma }}_1 &{} \quad \textbf{0} \\ \textbf{0} &{} \quad \textbf{0} \end{bmatrix} + \begin{bmatrix} \textbf{I}_M &{}\quad \textbf{0} \\ \textbf{0} &{} \quad \textbf{I}_{N-M} \end{bmatrix} \\&= \begin{bmatrix} \lambda _1+1 &{} \quad ...&{} \quad 0 &{}\quad .&{}\quad .&{}\quad 0\\ ... &{} \quad . &{} \quad .&{} \quad . &{} \quad . &{} \quad ...\\ 0 &{} \quad ... &{} \quad \lambda _{M}+1&{} \quad .&{} \quad . &{} \quad 0\\ 0 &{} \quad ... &{} \quad 0 &{} \quad 1 &{} \quad ... &{} \quad 0\\ ... &{} \quad . &{} \quad .&{} \quad . &{} \quad . &{} \quad ...\\ 0 &{} \quad ... &{} \quad 0 &{} \quad 0 &{} \quad ... &{} \quad 1\\ \end{bmatrix} \end{aligned}$$

  where $\lambda _i + 1 > 1$ $(i = 1,2,\ldots ,M)$ and $\textbf{I}_n$ is the n-dimension identity matrix.

  From the geometric series,

  $$\begin{aligned} \frac{1}{\beta } + \left( \frac{1}{\beta }\right) ^2 + \cdots + \left( \frac{1}{\beta }\right) ^n&\\ =&\frac{1}{\beta }(1 + \cdots +\left( \frac{1}{\beta }\right) ^{n-1}) \\ =&\frac{1-\beta ^{-n}}{\beta -1} \end{aligned}$$

  With $n \rightarrow \infty$, if $\beta > 1$, the equation converge to $\frac{1}{\beta -1}$, while if $\beta = 1$, the equation equal to n.

  Then

  $$\begin{aligned} \lim _{n \rightarrow \infty }\sum _{k=1}^n{\varvec{\Lambda }}^{-k} =n \begin{bmatrix} \frac{1}{\lambda _1} &{} \quad ...&{} \quad 0 &{}\quad .&{}\quad .&{} \quad 0\\ ... &{} \quad . &{} \quad .&{}\quad . &{}\quad . &{} \quad ...\\ 0 &{} \quad ... &{} \quad \frac{1}{\lambda _{M}}&{} \quad .&{} \quad . &{} \quad 0\\ 0 &{} \quad ... &{} \quad 0 &{} \quad n &{} \quad ... &{} \quad 0\\ ... &{} \quad . &{} \quad .&{} \quad . &{} \quad . &{} \quad ...\\ 0 &{} \quad ... &{} \quad 0 &{} \quad 0 &{} \quad ... &{} \quad n\\ \end{bmatrix} \end{aligned}$$

• Since $\lim _{n \rightarrow \infty } \frac{1}{\beta ^n} = 0$, for $\beta > 1$,

  $$\begin{aligned}&\lim _{n \rightarrow \infty } {\varvec{\Lambda }} ^{-n} = \\&\lim _{n \rightarrow \infty }\begin{bmatrix} \frac{1}{(\lambda _1+1)^n} &{} \quad ...&{} \quad 0 &{}\quad .&{}\quad .&{} \quad 0\\ ... &{} \quad . &{} \quad .&{} \quad . &{} \quad . &{} \quad ...\\ 0 &{} \quad ... &{}\quad \frac{1}{(\lambda _{M}+1)^n}&{}\quad .&{} \quad . &{} \quad 0\\ 0 &{} \quad ... &{} \quad 0 &{} \quad 1 &{} \quad ... &{} \quad 0\\ ... &{} \quad . &{} \quad .&{} \quad . &{} \quad . &{} \quad ...\\ 0 &{} \quad ... &{} \quad 0 &{} \quad 0 &{} \quad ... &{} \quad 1\\ \end{bmatrix} \\&=\begin{bmatrix} 0 &{} \quad ...&{} \quad 0 &{}\quad .&{}\quad .&{} \quad 0\\ ... &{} \quad . &{} \quad .&{} \quad . &{} \quad . &{} \quad ...\\ 0 &{} \quad ... &{} \quad 0&{} \quad .&{} \quad . &{} \quad 0\\ 0 &{} \quad ... &{} \quad 0 &{} \quad 1 &{} \quad ... &{} \quad 0\\ ... &{} \quad . &{} \quad .&{} \quad . &{} \quad . &{} \quad ...\\ 0 &{} \quad ... &{} \quad 0 &{} \quad 0 &{} \quad ... &{} \quad 1\\ \end{bmatrix} = \begin{bmatrix} 0 &{}\quad 0 \\ 0 &{} \quad \textbf{I}_{N-M} \end{bmatrix} \end{aligned}$$