Database Reference
In-Depth Information
An additional complication is that we often have missing values, for
several reasons: either failure of the system, or delayed arrival of some
measurements. For example, the sensor network may get overloaded
and fail to report some of the chlorine measurements in time or some
sensor may temporarily black-out. At the very least, we want to continue
processing the rest of the measurements.
6.1 Tracking the Hidden Variables
The first step is, for a given
k
, to incrementally update the
k
partic-
ipation weight vectors
w
i
,1
k
, so as to summarise the original
streams with only a few numbers (the hidden variables). In Section 6.2,
we describe the complete method, which also adapts
k
.
For the moment, assume that the number of hidden variables
k
is
given. Furthermore, our goal is to minimise the average reconstruction
≤
i
≤
error
t
2
. In this case, the desired weight vectors
w
i
,
1
k
are the principal directions and it turns out that we can estimate them
incrementally.
We use an algorithm based on adaptive filtering techniques [56, 27],
which have been tried and tested in practice, performing well in a variety
of settings and applications (e.g., image compression and signal tracking
for antenna arrays). We experimented with several alternatives [41,
14] and found this particular method to have the best properties for
our setting: it is very ecient in terms of computational and memory
requirements, while converging quickly, with no special parameters to
tune. The main idea behind the algorithm is to read in the new values
x
t
+1
≡
[
x
(
t
+1)
,
1
,...,x
(
t
+1)
,n
]
T
x
t
−
x
t
≤
i
≤
from the
n
streams at time
t
+1, and
perform three steps:
1 Compute the hidden variables
y
t
+1
,i
,
1
≤ i ≤ k
, based on the
current
weights
w
i
,
1
≤ i ≤ k
, by projecting
x
t
+1
onto these.
2 Estimate the reconstruction error (
e
i
below) and the energy, based
on the
y
t
+1
,i
values.
3 Update the estimates of
w
i
,
1
≤ i ≤ k
and output the
actual
hidden variables
y
t
+1
,i
for time
t
+1.
x
t
+1
enter the system. Intuitively, the goal is to adaptively update
w
i
so that it quickly converges to the “truth.” In particular, we want to
update
w
i
more when
e
i
is large. However, the magnitude of the update
should also take into account the past data currently “captured” by
w
i
.
For this reason, the update is inversely proportional to the current
energy
