Fall 2006 Capstone Project: Math background for Lyapunov exponent algorithm
To understand the method for calculating the Lyapunov exponent of a human gait system several key characteristics found in the walking motion of humans should be mentioned. First it should be understood that human gait by nature, is a nonlinear dynamical system. In previous studies (England, et al) it has also been observed that human gait, in order to maintain stability must exhibit roughly periodic behavior. It is because of this non-linear, periodic behavior that the Lyapunov exponent is relevant in analysis of such a system.
The first step in calculating the Lyapunov exponent involves reconstructing a time series, $$X = \{ x_1, x_2, ... , x_N \}$$ which is a set of angle measurements, using the method of delays. The vectors obtained through this reconstruction are composed of values of the time series by taking an initial value in the time series followed by additional values of the time series as determined by the delay. For example, the 3-dimensional vector, $X_3$, with initial point $x_3$ and delay 5 would be $(x_3, x_8, x_{13})$. Expressed mathematically, $$\text{reconstructed } X = [X_1, X_2, ..., X_M>]^T,$$ where each $X_i$ is given by $$X_i = [x_i, x_{i+J}, x_{i+2J}, ..., x_{i+(m-1)J}],$$ where $J$ is the lag (or delay), and $m$ is the embedding dimension. The reconstructed attractor, $X$, can be expressed as an $(M × m)$ matrix in which the number of vectors created is equal to $$N-(m-1)J,$$ and the vectors are arranged in the order of their initial values.
The Lyapunov exponent measures the rate at which the subsequent orbits diverge, thus measuring the amount of stability or instability in the system or its sensitivity to initial conditions. A positive Lyapunov exponent indicates trajectory divergence and therefore orbital instability. A negative Lyapunov exponent indicates trajectory convergence and indicates the system is settling into a stable orbit.
The next step in calculating the Lyapunov Exponent is to find the nearest neighbors of each vector. Given a reference point, $X_j$, a vector’s nearest neighbor is denoted by $X_ĵ$. In other words, $$d_j(0) = \min_ĵ ║ X_j – X_ĵ║,$$ where $d_j(0)$ is the initial distance from the $j$th point to its nearest neighbor, and $║...║$ is the Euclidean norm. Mean period exclusion is used to determine which vectors are ineligible in determining nearest neighbors due to time series proximity. This ensures that the nearest neighbor is taken from a point on a different trajectory. For example, with a mean period of 5, the vector $X_7$ could be the nearest neighbor of $X_2$, but $X_3$ could not be.
Then for each $X_j$ and $X_ĵ$, a function $d_j(i)$ is set up to measure the rate at which the trajectories diverge, which is at a rate of $λ_1$, the largest Lyapunov exponent. This function can be expressed mathematically as $$d_j(i) ≈ C_j e^{λ_1(i∙∆t)},$$ where $C_j$ normalizes the separation of the neighbors. By taking the logarithm of the above equation, we get $$\ln d_j(i) ≈ \ln C_j + λ_1(i∙∆t).$$ In the process of taking the logarithm of each $d_j(i)$, the function is linearized such that each $d_j(i)$ is approximately parallel to every other $d_j(i)$ [for $j = 1, 2, ..., M$], thus giving a set of (approximately) parallel lines, each having a slope approximately equal to $λ_1$. The largest slope contained within this set of lines (i.e., $λ_1$) is calculated using a least-squares fit to the “average” line defined by $$y(i) = (1/∆t)‹ \ln d_j(i)›,$$ where $‹...›$ denotes the average over all values of $j$.