Description (general)

A "multifractal spectrum" is a way to summarize special statistics about some data, related to its smoothness and regularity. Multifractals are now used in many areas of physics, biology, finance, geology... This algorithm computes the "spectrum" very fast. It can also update it when new data become available.

Description (detailed)

An algorithm is presented to update the multi-fractal spectrum of a time series in constant time when new data arrives. The discrete wavelet transform (DWT) of the time series is first updated for the new data value. This is done optimally in terms of sharing previous computations, in O(L) constant time, with L the number of levels of decomposition. The multi-fractal spectrum is then updated also in constant-time. New pre-computation techniques are presented to further accelerate this process. All possible 2^L data alignments are taken into account in the course of the incremental updates. The resulting spectrum estimate is more stable, compared to the current DWT method using only one dyadic frame, as precise, and more efficient. It is adapted for real-time on-line updates of the time series.

A pre-print article is available. It describes how this works in details.

Source code

The latest source code implementing this algorithm can be downloaded here. See the history section if you need older versions.

Several programs are provided:

• incremfa: Processes an analysis over a data file. Type "incremfa" without parameters for help. This program run through the whole data file, the initialization stage uses non-incremental analysis, and the remaining points are processed incrementally.
• numericalStability: Code for the corresponding experiment in the article. 30 independent runs of 10 million updates are processed to monitor the floating point computation drift between the non-incremental and the incremental versions.
• performanceTest: Code for the corresponding experiment in the article. Different configurations are tested with number of levels, size of higher level. The time it takes to process an update is measured for both incremental and non-incremental versions of the algorithm. There is a variance in the update times due to the OS multitasking. The measures are thus made over a large number of updates.
• performanceTestReducedNq: Same as above, but with a reduced range of q: from -5 to 5 instead of -10..10.
• precisionExperiment: Test the multifractal analysis precision on theoretical monofractal series with known values: H=0.5 for Brownian motion, H=1.0 for integrated pink noise. The influence of many parameters is tested: number of levels, size of higher level, but also frame averaging, weighting scheme, etc. Average and variance of the results over 30 independent runs are computed.
• memVSCPUValidation: Checks the difference between the versions of the algorithm using more Memory (faster) or more CPU (slower). Due to the CPU working internally on 80 bits whereas double values are stored on 64 bits, there might be small differences between the 2 algorithm versions. You may use long doubles, but then on some systems this incurs a cost that outweights the MEM vs CPU advantage. The difference is only non-negligible for large negative q exponents.

Revisions and History

Since the writing of the article preprint, a number of versions were created. The original code, necessary to reproduce exactly the experiments, corresponds to the version 1.0. Version 1.2 may not give exactly the same numerical values due to 64bit vs 80bit floating point precision (see this comment).

• 1.3: Cleanup of the code and the source repository.
• 1.2:
  • Replaced squared error by the more reliable correlation coefficient as an indicator of the quality of the exponential fits (hence for the confidence one may have in the h(q) values). Added detection of NaN values, mapped to a correlation of 0.0.
  • Implemented the MEM version of the algorithm, now the default, for a performance gain of about 25% to 30%.
  • Code cleanup, easier to change q-exponents settings.
• 1.1: Added optional mean square error computation.
• 1.0: Initial code corresponding to the article preprint.