Last updated: 2017-07-26

Code version: 26dff77

The practical estimation of \(\varepsilon\)-complexity uses some family of approximation methods \(\mathcal{F}\) to successively downsample and approximate a function. At each step \(h\), only some proportion of the initial samples, \(S_h\), are used finding the minimum approximation error, \(\varepsilon_h\). A least squares fit \[ \log(S) \approx A + B\log(\varepsilon) \] determines the two parameters, \(A\) and \(B\), which characterize the \(\varepsilon-\)complexity of the function.

\(\varepsilon\)-complexity algorithm

Input: \(X\) a regularly sampled time series of length \(N\).
Input: \(\mathcal{F}\) a set of approximation methods \(f\).
Input: \(\mathcal{H}\) the set of spacings \(h\).
Output: The complexity coefficients \(A,B\).
foreach \(h\) in \(\mathcal{H}\) do

foreach \(f\) in \(\mathcal{F}\) do

Compute the approximation error
\(\varepsilon_{h,f} \leftarrow \frac{1}{N} \left|f_h - X_{h} \right|^2\)

end
Find minimium error over all \(f\)
epsilons\(_h\) \(\leftarrow \min \varepsilon_{h,f}\).

end
Fit a least squares linear model
\(A,B\) \(\leftarrow\) lm\(\left(\{ S_h \} \sim \{ \varepsilon_h \} \right)\).