A fast algorithm for computing a matrix transform used to detect trends in noisy data

A recently discovered universal rank-based matrix method to extract trends from noisy time series is described in Ierley and Kostinski (2019) but the formula for the output matrix elements, implemented there as an open-access supplement MATLAB computer code, is O(N^4), with N the matrix dimension. This can become prohibitively large for time series with hundreds of sample points or more. Based on recurrence relations, here we derive a much faster O(N^2) algorithm and provide code implementations in MATLAB and in open-source JULIA. In some cases one has the output matrix and needs to solve an inverse problem to obtain the input matrix. A fast algorithm and code for this companion problem, also based on the recurrence relations, are given. Finally, in the narrower, but common, domains of (i) trend detection and (ii) parameter estimation of a linear trend, users require, not the individual matrix elements, but simply their accumulated mean value. For this latter case we provide a yet faster O(N) heuristic approximation that relies on a series of rank one matrices. These algorithms are illustrated on a time series of high energy cosmic rays with N > 4 x 10^4 .Ierley与Kostinski（2019）介绍了一种新近提出的通用基于秩的矩阵方法，可从含噪时间序列中提取趋势。但该研究中以开源补充材料形式提供的MATLAB计算机代码所实现的输出矩阵元素计算公式，其时间复杂度为O(N⁴)，其中N为矩阵维度。当处理含数百乃至更多采样点的时间序列时，该方法的计算开销会高到难以承受。本文基于递推关系，推导出复杂度大幅降低的O(N²)快速算法，并提供了MATLAB与开源JULIA语言的代码实现。在部分场景中，用户已获取输出矩阵，需通过求解逆问题得到输入矩阵，本文同样基于递推关系，针对该配套问题给出了快速算法与代码实现。最后，在虽范围较窄但应用广泛的两类场景——(i)趋势检测、(ii)线性趋势参数估计——中，用户无需获取单个矩阵元素，仅需其累计均值。针对该场景，本文提出了一种基于一系列秩1矩阵的更快O(N)启发式近似方法。本文通过N>4×10⁴的高能宇宙射线时间序列对上述所有算法进行了演示验证。