Database Reference
In-Depth Information
In general, if the trend does not consist of exact copies, the power will
not be zero, but it will still exhibit a sharp drop. We exploit precisely
this fact to choose the “right” window.
Choosing the window
Next, we state the steps for interpreting the
power profile to choose the appropriate window that best captures the
main trends: (i) Compute the power profile
π
(
w
)
versus
w
; (ii) Look
for the first window
w
0
that exhibits a sharp drop in
π
(
w
0
)
and ignore
all other drops occurring at windows
w ≈ iw
0
,
i
=2
,
3
,...
that are
approximately multiples of
w
0
; (iii) If there are several sharp drops at
windows
w
i
that are
not
multiples of each other, then any of these is
suitable. We simply choose the smallest one; alternatively, we could
choose based on prior knowledge about the domain if available, but
that is not necessary; (iv) If there are no sharp drops, then no strong
periodic/cyclic components are present. However, the local patterns at
any window can still be examined to gain a picture of the time series
behavior.
8.2 Multiple-Scale Patterns
In this section we tackle the following question: how do we eciently
compute the optimal local patterns for multiple windows (as well as the
associated power profiles), so as to quickly zero in to the “best” window
size? First, we can choose a geometric progression of window sizes:
rather than estimating the patterns for windows of length
w
0
,
w
0
+1,
w
0
+2,
w
0
+3
,...
, we estimate them for windows of
w
0
,2
w
0
,4
w
0
,...
or,
more generally, for windows of length
w
l
:=
w
0
· W
l
for
l
=0
,
1
,
2
,...
.
Thus, the size of the window set
W
we need to examine is dramatically
reduced. Still, this is (i) computationally expensive (for each window we
still need
O
(
ktw
) time and, even worse, (ii) still requires buffering all the
points (needed for large window sizes, close to the time series length).
Next, we show how we can reduce complexity even further.
8.2.1 Hierarchical SVD.
The main idea of our approach to
solve this problem is shown in
Figure 5.6
.
Let us assume that we have,
say
k
= 2 local patterns for a window size of
w
0
= 100 and we want
to compute the patterns for window
w
(100
,
1)
= 100
2
1
= 200. The
naive approach is to construct
X
(200)
from scratch and compute the
SVD. However, we can reuse the patterns found from
X
(100)
.Usingthe
k
= 2 patterns
v
(100
1
and
v
(100
2
we can reduce the first
w
0
= 100 points
x
1
,x
2
,...,x
100
into just two points, namely their projections
p
(100)
·
1
,
1
and
p
(100)
onto
v
(100)
and
v
(100)
, respectively. Similarly, we can reduce
1
,
2
1
2
