论文标题
用于计算用于检测嘈杂数据趋势的矩阵变换的快速算法
Fast Algorithm for computing a matrix transform used to detect trends in noisy data
论文作者
论文摘要
[1]中描述了一种最近发现的基于秩的矩阵方法，用于从嘈杂的时间序列中提取趋势，但是输出矩阵元素的公式（在此实现为开放式访问补充MATLAB计算机代码）为$ {\ cal o}（n^4）$，并带有$ N $。对于时间序列而言，这可能会变得非常大，并具有数百个或更多的样本点。基于复发关系，在这里，我们得出了更快的$ {\ cal o}（n^2）$算法，并在MATLAB和开源Julia中提供代码实现。在某些情况下，一个人具有输出矩阵，需要解决反问题以获得输入矩阵。也给出了基于上述复发关系的此伴侣问题的快速算法和代码。最后，在（i）趋势检测和（ii）线性趋势的参数估计中，用户需要的参数估计，而不是单个矩阵元素，而是仅仅是它们累积的平均值。对于后一种情况，我们提供了一个更快的$ {\ cal o}（n）$启发式近似，该近似依赖于一系列等级的矩阵。这些算法在具有$ n> 4 \ times 10^4 $的高能宇宙射线的时间序列上进行了说明。 [1]通用等级顺序变换，从嘈杂数据，Glenn Ierley和Alex Kostinski，Phys提取信号。修订版X 9 031039（2019）。
A recently discovered universal rank-based matrix method to extract trends from noisy time series is described in [1] but the formula for the output matrix elements, implemented there as an open-access supplement MATLAB computer code, is ${\cal 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 ${\cal 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 above 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 ${\cal 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 \times 10^4$. [1] Universal Rank-Order Transform to Extract Signals from Noisy Data, Glenn Ierley and Alex Kostinski, Phys. Rev. X 9 031039 (2019).
