Algorithms for Piecewise Constant Signal Approximations. Bergerhoff, L., Weickert, J., & Dar, Y. In 2019 27th European Signal Processing Conference (EUSIPCO), pages 1-5, Sep., 2019.
Algorithms for Piecewise Constant Signal Approximations [pdf]Paper  doi  abstract   bibtex   
We consider the problem of finding optimal piecewise constant approximations of one-dimensional signals. These approximations should consist of a specified number of segments (samples) and minimise the mean squared error to the original signal. We formalise this goal as a discrete nonconvex optimisation problem, for which we study two algorithms. First we reformulate a recent adaptive sampling method by Dar and Bruckstein in a compact and transparent way. This allows us to analyse its limitations when it comes to violations of its three key assumptions: signal smoothness, local linearity, and error balancing. As a remedy, we propose a direct optimisation approach which does not rely on any of these assumptions and employs a particle swarm optimisation algorithm. Our experiments show that for nonsmooth signals or low sample numbers, the direct optimisation approach offers substantial qualitative advantages over the Dar-Bruckstein method. As a more general contribution, we disprove the optimality of the principle of error balancing for optimising data in the ℓ2 norm.

Downloads: 0