Database Reference
In-Depth Information
(w)
time
x
X
delayed
coordinates
proj.
proj.
proj.
proj.
local patterns
v 1 (w)
and projections
v 2 (w)
local bases
(patterns)
Figure 5.4. Illustration of local patterns for a fixed window (here, w =4).
discovery and also lend themselves better to incremental, streaming es-
timation using limited resources.
More generally, the original time series does not have to be scalar,
but can also be vector-valued itself. We still do the same, only each row
of X ( w ) is now a concatenation of rows of X (instead of a concatenation
of scalar values). More precisely, we construct the general time-delay
coordinate matrix as follows:
m×n , w )
Procedure 1 Delay ( X R
m
and n
m/w
nw
m ×n
Output is X ( w )
R
{
not necessarily materialized
}
for t =1to m do
Row X ( w )
concatenation of rows
X (( t− 1) w +1) , X (( t− 1) w +2) ,
( t )
··· X ( tw )
end for
Incremental SVD The SVD update algorithm used in SPIRIT can
be applied incrementally to vectors that represent windows of the same
time series. As we have seen, its accuracy is good, while it does not
need to store the left singular vectors. Since our goal is to find patterns
at multiple scales without an upper bound on the window size, this is a
more suitable choice. Furthermore, if we need to place more emphasis on
recent trends, it is rather straightforward to incorporate an exponential
forgetting scheme, which works well in practice [44]. For each new row,
the algorithm updates k · n numbers, so total space requirements are
O ( nk ) and the time per update is also O ( nk ). Finally, the incremental
update algorithms need only the observed values and can therefore easily
handle missing values by imputing them based on current estimates of
the singular vectors.
 
 
Search WWH ::




Custom Search