1
$\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$
2
  • $\begingroup$ Votes and best answer validation are required for this question $\endgroup$ Jul 28, 2019 at 12:05
  • $\begingroup$ You may get better results with Total Variation based optimization problem. $\endgroup$
    – Royi
    May 14, 2021 at 10:04

1 Answer 1

-1
$\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$
3
  • $\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, 2016 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, 2016 at 9:28
  • $\begingroup$ @Nelson OK, APCA seemed quite simple to me to implement, based on the Figures $\endgroup$ May 26, 2016 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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