Efficient (piecewise) linear minmax approximation of digital signals

Marco Dalai, Riccardo LeonardiICASSP 2004 · OpenReview

Abstract

Efficient geometric algorithms are provided for the linear approximation of digital signals under the uniform norm. Given a set of n points (x/sub i/, y/sub i/), i=1..n, with x/sub i/<x/sub j/ if i<j, we give a new method to find the optimum linear approximation in O(n). Given also an error bound, we demonstrate how to construct in O(n) a non continuous piecewise solution such that the number, k, of segments is optimal. Furthermore, we show that for such a number of segments, the solution that is l/sub /spl infin// optimal can also be found in O(n) provided that n/k = O(1).
BibTeX
@inproceedings{dalai2004efficient,
  author = {Marco Dalai and Riccardo Leonardi},
  title = {{Efficient (piecewise) linear minmax approximation of digital signals}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2004},
  url = {https://openreview.net/forum?id=0eLDQ01A0e},
}

Loading related content...

Figure