WorksMathematics
On the convergence of the False Nearest Neighbours algorithm
Abstract
The False Nearest Neighbours (FNN) algorithm is one of the most widely used methods for choosing the embedding dimension, i.e. the number of delay coordinates, in the time-delay reconstruction of a dynamical system from an observed scalar time series. We prove rigorous results on the behaviour of this algorithm for long time series. We consider a smooth dynamical system on a compact manifold and an invariant probability measure . For a typical measurement function and -almost every trajectory, we show that the proportion of false nearest neighbours tends to zero (provided that the tolerance threshold is large enough) once . On the other hand, for systems with super-polynomial decay of correlations, we prove that this proportion tends to one whenever is smaller than the Hausdorff dimension of . Consequently, in this case, the FNN algorithm (run for long enough time series) returns an embedding dimension satisfying . This is below the threshold required by the Takens embedding theorem, so the classical Takens embedding theory does not explain why reconstructions and predictions with chosen by the FNN algorithm work in practice. The explanation for this case is provided by a recent probabilistic theory of time-delay embeddings. We apply our results to the Hénon and Lorenz attractors, showing that the FNN algorithm typically returns for the Hénon map (in the chaotic case) and for the Lorenz system.