Approximation of diagonal line based measures in recurrence quantification analysis

• We propose fast computable approximations of RQA measures.
• If the similarity threshold is zero, the method is exact.
• If the data is one-dimensional, the approximation error is small.
• The approximation error increases with dimension of the data.
• The approximate determinism is able to find dynamical transitions.

Given a trajectory of length N  , recurrence quantification analysis (RQA) traditionally operates on the recurrence plot, whose calculation requires quadratic time and space (O(N2)O(N2)), leading to expensive computations and high memory usage for large N. However, if the similarity threshold ε 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(Nlog⁡(N))O(Nlog⁡(N)) time and O(N)O(N) space. Furthermore, for the case of ε>0ε>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.