next up previous contents
Next: An Algorithm based on Up: Analysis of Real-World Data Previous: Basic Remarks about the   Contents

Topological Considerations

Schuster [15] proposed to base the choice of $\tau$ and $n$ on the idea that an embedding using delay coordinates is a topological mapping which preserves neighbourhood relations. This means that points on the attractor in $M$ which are near to each other should also be near in the embedding space ${\bf R}^n$. The distance of any two points $x_i, \ x_j\in {\bf R}^n$ cannot decrease but only increase when one increases the embedding dimension $n$. But if this distance increases under a change from $n$ to $n+1$ then it is clear that $n$ is not sufficiently large, as Fig. 6 shows.














$\textstyle \parbox{12cm}{
Figure 6.
Illustration of an embedding dimension ...
...r is shown
schematically in $n$- and $(n+1)$-dimensional embedding space.
}$
$n$ being too small means that the attractor is projected onto a space of lower dimensionality $n$ and this projection possibly destroys neighbourhood relations, resulting in some points appearing nearer to each other in the embedding space than they actually are. (For example, $x_j$ may be the nearest neighbour of $x_i$ in ${\bf R}^n$ although this is not true in the proper embedding space ${\bf R}^{n+1}$. See, again, Fig. 6 for an illustration of this observation.) If, on the other hand, $n$ is sufficiently large then the distance of any two points of the attractor in embedding space should stay the same when one changes $n$ into $n+1$. Applying this geometrical point of view, one can find the proper embedding dimension by choosing initially a small value of $n$ and then increasing it systematically. One knows that the proper value of $n$ is found when all distances between any two points $x_i$ and $x_j$ do not grow any more when increasing $n$. Practically, one constructs the quantity
\begin{displaymath}
\quad Q(i,k,n) = \frac{d_{n+1} \left( x_i(n+1),x(i,k,n+1) \right) }
{d_n \left( x_i(n) ,x(i,k,n) \right) } \quad,
\end{displaymath} (22)

where $x_i(n)$ is the $i$-th reconstructed vector in $n$-dimensional embedding space, $x_i(n)=\left( v_i,v_{i+1},\ldots,v_{i+n-1} \right)^T \in
{\bf R}^n$, and
\begin{displaymath}
\quad x(i,k,n) = \left\{ \begin{array}{c}
\mbox{ the $k$...
...dimensional embedding space }
\end{array}
\right\} \quad.
\end{displaymath} (23)

$Q(i,k,n)$ measures the increase of the distance between $x_i$ and its $k$-th nearest neighbour, as $n$ increases. ($d_n(.,.)$ is some appropriate, fixed metric in ${\bf R}^n$.) According to the observations stated above $Q$ should be greater than or equal to one. To get a notion what happens not only to the single point $x_i$ and its neighbours but to all the $x_i$ the next step is to calculate
\begin{displaymath}
\overline{W}(n) = \frac{1}{\tau N(N-1)} \sum_{i=1}^{N}
\sum_{k=1}^{N-1} \log Q(i,k,n)
\end{displaymath} (24)

which considers all $N$ reconstructed points in the embedding space and all the $N-1$ ``neighbours'' of these10 and adds up the logarithms of the ratios of the respective distances. (The number of the $x_i$ increases linearly with $\tau$, such that there would be a trivial linear $\tau$-dependence in $\overline{W}(n)$. This is removed by dividing by $\tau$.) Clearly, for $n$ equal to the proper embedding dimension and for the right sampling time $\tau$, $\overline{W}(n)$ should approach zero (within the experimental and numerical errors). Thus systematic variation of $n$ and $\tau$ seems to enable us to find sensible values for these quantities. In fact, numerical experiments done by Schuster [15] show that one can get reasonable results when using this method.

Footnotes

... these10
To save computing time it is also possible to consider not all the $N-1$ neighbours of each $x_i$ but only the $p$ nearest ones.

next up previous contents
Next: An Algorithm based on Up: Analysis of Real-World Data Previous: Basic Remarks about the   Contents
Martin_Engel 2000-05-25