0
$\begingroup$

I am trying to approximate a vector or a time series, in order to have as little changes as possible. To do so, I pretend to apply the Adaptive piecewise constant approximation (APCA) algorithm. Note: I can apply the PAA, but I prefer a method that allows different lengths for each segment of the approximated series.

The following paper Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases (pages 196-199) claims to have found a faster alternative to APCA, based on wavelets, but I can’t figure out how to apply it in R.

The data used in the example is the following:

library(wavelets)
x<-c(7, 5, 5, 3, 3, 3, 4, 6)
w <- dwt(x, filter="haar",n.levels = 3)

I run the above code, but i haven't even found the same wavelet coefficients. I'll appreciate any help finding the same wavelet coefficients of the example, as well as the a final approximation.

According to the paper, the final solution seems to be the vector y, described as

y<-c(6,6,3.5,3.5,3.5,3.5,5,5)

Implementations of the original APCA algorithm can also be useful. Although R code is preferred, Python implementations are also welcome.

$\endgroup$
  • $\begingroup$ Votes and best answer validation are required for this question $\endgroup$ – Laurent Duval Jul 28 at 12:05
0
$\begingroup$

Their wavelet coefficients $$W_c = [4.5, 0.5, 1, -1, 1, 1, 0, -1]$$ or $$W_c = [4.5, 0.5, 1/\sqrt{2},-1/\sqrt{2},1/2,1/2,0,-1/2]$$ look perfectly fine to me. In the first case, they use $a = (x+y)/2$ and $d = x-a$ repeatedly. What might differ is the overall scaling, to account for energy preservation. In Matlab for instance, I get the same result as their by dividing the $3$-level coefficients by $\sqrt{8} = \sqrt{2}^3$:

 wavedec([7, 5, 5, 3, 3, 3, 4, 6],3,'haar')/sqrt(8)

Their algorithm is quite well detailed in the paper, so it should be implementable quite easily. If you want additional help for Matlab like-code (which can be reinterpreted for R or Python), check the tutorial A practical Time-Series Tutorial with MATLAB, starting page 66.

$\endgroup$
  • $\begingroup$ Thanks for your help. In fact the "problem" lays in the different scaling used in the paper and in the wavelet R package. While in the paper the 3rd level coefficients are divided by 2, in the r wdt function are divided e by 2sqrt(2), and the same applies to remaining levels. While the 1st part(getting the same wavelet coefficients) of by problem are solved, I'm, still struggling to figure out how to find the final solution (reconstruct the original signal based on just 3 coefficients), even by hand. $\endgroup$ – Nelson May 23 '16 at 9:23
  • $\begingroup$ The link you send has in fact very detailed code for PAA (it is in fact very simple to implement, sice the segments have constant length) but I can't figure out how to do it for APCA (non constant segment lengths). The method is referred in page 72 but with no details. $\endgroup$ – Nelson May 23 '16 at 9:28
  • $\begingroup$ @Nelson OK, APCA seemed quite simple to me to implement, based on the Figures $\endgroup$ – Laurent Duval May 26 '16 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.