Database Reference
In-Depth Information
shows
w
1
after the update for
x
t
+1
.
Algorithm 1
TrackW
Initialise the
k
hidden variables
w
i
to unit vectors
w
1
=[10
0]
T
,
···
0]
T
,etc.
Initialise
d
i
(
i
=1
,...k
) to a small positive value. Then:
As each point
x
t
+1
arrives, initialise
x
1
:=
x
t
+1
.
for
1
≤ i ≤ k
do
y
i
:=
w
i
x
i
{
w
2
= [010
···
(
y
t
+1
,i
= projection onto
w
i
}
λd
i
+
y
i
{
i
-th eigenval. of
X
t
X
t
}
d
i
←
energy
∝
e
i
:=
x
i
−
error,
e
i
⊥
w
i
}
w
i
←
w
i
+
d
i
y
i
e
i
{
y
i
w
i
{
}
x
i
+1
:=
x
i
− y
i
w
i
{
repeat with remainder of
x
t
}
end for
update PC estimate
The
forgetting factor
λ
will be discussed in Section 6.3 (for now, as-
sume
λ
=1).Foreach
i
,
d
i
=
tE
t,i
and
x
i
is the component of
x
t
+1
in the
orthogonal complement of the space spanned by the updated estimates
w
i
,
1
i
<i
of the participation weights. The vectors
w
i
,
1
k
are
in order of importance (more precisely, in order of decreasing eigenvalue
or energy). It can be shown that, under stationarity assumptions, these
w
i
in these equations converge to the true principal directions.
≤
≤
i
≤
Complexity
We only need to keep the
k
weight vectors
w
i
(1
k
),
each
n
-dimensional. Thus the total cost is
O
(
nk
), both in time and of
space. The update cost does not depend on
t
. This is a tremendous
gain, compared to the usual PCA computation cost of
O
(
tn
2
).
≤
i
≤
6.2 Detecting the Number of Hidden Variables
In practice, we do not know the number
k
of hidden variables. We
propose to estimate
k
on the fly, so that we maintain a high percentage
f
E
of the
energy
E
t
. Energy thresholding is a common method to de-
termine how many principal components are needed [33]. Formally, the
energy
E
t
(at time
t
) of the sequence of
x
t
is defined as
E
t
:=
t
τ
=1
x
τ
2
=
t
τ
=1
i
=1
x
τ,i
.
Similarly, the energy
E
t
of the reconstruction
x
is defined as
E
t
:=
t
τ
=1
2
.
x
τ
