Phantom: Prediction of Human Motion with Distributed Body Sensors - Prediction and Classification of Respiratory Motion - page 50

Table 3.1 Comparison of the computational complexity (KF vs. IMME vs. MC-IMME)

Methods KF IMME MC-IMME

3

Complexity O(L 9 k 9 N ) O(L 9 k 9 T(N) O(L 9 k 9 T(N)

The computational complexity of KF for the upper bound is orders of growth
N 3 , where N represents the states estimated using the KF derived by Karlsson et al.
[ 44 ]. The computational complexity can be increased as a linear function of the
sensor number (L) and time k. Accordingly, the asymptotic upper bound of KF is
orders of growth L 9 k 9 N 3 .
IMME extends the complexity by defining T(N) as the asymptotic upper bound
of recursive computation based on the states estimated using IMME. In the IMME
the computational complexity is increased as a linear function of the independent
sensor number (L). In addition, IMME needs recursive computation based on time
k. Therefore, the asymptotic upper bound for the worst-case running time of
IMME is orders of growth L 9 k 9 T(N)[ 52 ].
Let us define T(L) as a upper bound of iteration execution time for k-means
clustering based on L points. Har-Peled et al. showed that the k-means heuristic
needs orders of growth L iterations for L points in the worst case [ 35 ]. In addition,
the adaptive grouping method needs to calculate the difference (D ADT (G)) of the
consecutive log-likelihood functions based on time sequential data (k) for the
appropriate group number selection. Therefore, the upper bound for the worst-case
running time of the adaptive grouping method is orders of growth L 9 k 9 T(L).
MC-IMME uses the same recursive computation as IMME with respect to the
estimated states. That means the running time of Stage 2 is the same as simple
IMME. MC-IMME also needs additional computation for the first Stage to make
grouping. Suppose that asymptotic upper bound of recursive computation (T(N)) is
equal to a upper bound of iteration execution time for k-means clustering (T(L)).
Then, the asymptotic upper bound for the computational complexity of Multiple-
channel is orders of growth L 9 k 9 T(N), because both Stage 1 and Stage 2 have
the same orders of growth L 9 k [ 53 ]. Please note that IMME and MC-IMME
have the identical computational complexity since distributed sensory systems
both have the same channel number L, and the same data length k.

3.5 Experimental Results

The motivation of this Chapter is to validate the proposed MC-IMME with
comprehensive experimental results. In Sect. 3.5.1 , we will describe the target
motions for the experimental tests (chest, head, and upper body). For each target
motion, the optimal cluster number based on the proposed grouping method is
selected in Sect. 3.5.2 , and this selection number is further investigated in com-
parison to grouping number methods using other clustering techniques in
Sect. 3.5.3 . The prediction accuracy of the proposed MC-IMME is evaluated with