Database Reference
In-Depth Information
(a) Original
w
1
(b) Update process (c) Resulting
w
1
Figure 5.3.
Illustration of updating
w
1
when a new point
x
t
+1
arrives.
Our approach might better be described as agnostic, rather than am-
nesic.
A very recent and interesting application of the same principles is on
correlation analysis of complex time series through change-point scores
[31]. Finally, related ideas have been used in other fields, such as in
image processing for image denoising [40, 30] and physics/climatology
for nonlinear prediction in phase space [59]. However, none of these
approaches address incremental computation in streams. More generally,
the potential of this general approach has not received attention in time
series and stream processing literature. We demonstrate that its power
can be harnessed at very small cost, no more than that of the widely
used wavelet transform.
The recently developed theory of
compressed sensing
(e.g., [16] and
[26]) studies the problem of signal summarization and reconstruction
based on observation of a subset of its values. More precisely, this work
develops a framework for estimating the projections of a signal into a
given set of basis functions from a small set of samples of its values.
3. Principal Component Analysis (PCA)
Here we give a brief overview of PCA [33], explaining the main in-
tuition. We use standard matrix algebra notation: vectors are lower-
case bold, matrices are upper-case bold, and scalars are in plain font.
The transpose of matrix
X
is denoted by
X
T
. In the following,
x
t
≡
[
x
t,
1
x
t,
2
··· x
t,n
]
T
n
is the column-vector. of stream values at time
t
. We adhere to the common convention of using column vectors and
writing them out in transposed form. The stream data can be viewed as
a continuously growing
t
∈
R
t×n
,where
one new row is added at each time tick
t
. In the chlorine example,
x
t
is the measurements column-vector at
t
over all the sensors, where
n
is
the number of chlorine sensors and
t
is the measurement time-stamp.
n
matrix
X
t
:= [
x
1
x
2
···
x
t
]
T
×
∈
R
