In this work efficient geometric algorithms are provided for the linear approximation of digital signals under the uniform norm. Given a set of n points (xi, yi)i=1..n, with xi < xj 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 number of segments, the solution that is l∞ optimal can also be found in O(n) provided that n/k = O(1).
Efficient (Piecewise) Linear Minmax Approximation of Digital Signals
DALAI, Marco
Methodology
;LEONARDI, Riccardo
Conceptualization
2004-01-01
Abstract
In this work efficient geometric algorithms are provided for the linear approximation of digital signals under the uniform norm. Given a set of n points (xi, yi)i=1..n, with xi < xj 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 number of segments, the solution that is l∞ optimal can also be found in O(n) provided that n/k = O(1).File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
DL_ICASSP-2004_full-text.pdf
gestori archivio
Tipologia:
Full Text
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
199.92 kB
Formato
Adobe PDF
|
199.92 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
DL_ICASSP-2004_post-print.pdf
accesso aperto
Descrizione: DL_ICASSP-2004_post-print
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
82.3 kB
Formato
Adobe PDF
|
82.3 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.