next up previous contents
Next: Dimensionality reduction with partial Up: Dimensionality reduction of Markov Previous: Constructing a 1D Markov   Contents

Approximations of dimensionality reduction

DR as introduced in Section 3.5.2 can still be computationally prohibitive, if it is used recursively as in Section 3.5.3. In this section, we introduce two new approximations in DR, namely DR-PI (Section 3.6.1) and DR-CI (Section 3.6.2), which can significantly reduce the computational complexity while keeping a reasonable accuracy. The key idea in our new approximations is that distributions $D_{i,j}$ (the sojourn time distribution in levels $\geq\kappa$ given event $E_{i,j}$) can be aggregated without losing too much information. In Section 3.6.3, we will discuss the computational complexity of DR, DR-PI, and DR-CI when they are used recursively.


Takayuki Osogami 2005-07-19