Approximation of diagonal line based measures in recurrence quantification analysis

Given a trajectory of length N, recurrence quantification analysis (RQA) traditionally operates on the recurrence plot, whose calculation requires quadratic time and space (O(N-2)), leading to expensive computations and high memory usage for large N. However, if the similarity threshold epsilon is zero, we show that the recurrence rate (RR), the determinism (DET) and other diagonal line based RQA-measures can be obtained algorithmically taking O(N Iog(N)) time and O(N) space. Furthermore, for the case of epsilon > 0 we propose approximations to the RQA-measures that are computable with same complexity. Simulations with autoregressive systems, the logistic map and a Lorenz attractor suggest that the approximation error is small if the dimension of the trajectory and the minimum diagonal line length are small. When applying the approximate determinism to the problem of detecting dynamical transitions we observe that it performs as well as the exact determinism measure. (C) 2015 Elsevier B.V. All rights reserved.