# Adaptive Piecewise Constant Approximation (APCA) with wavelets/DWT

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.

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

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.