Best piecewise constant approximation of a function of single variable (Q1111948): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q178348 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Andrzej Nowak / rank | |||
Normal rank |
Revision as of 08:15, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Best piecewise constant approximation of a function of single variable |
scientific article |
Statements
Best piecewise constant approximation of a function of single variable (English)
0 references
1988
0 references
Let F(I) be a class of piecewise constant functions on an interval I. The following two problems are studied: (1) Given \(f\in F(I)\) and a positive constant \(\epsilon\), find \(g\in F(I)\) such that \(\| g-f\| \leq \epsilon\) and g has a minimal number of constant pieces. (2) Given \(f\in F(I)\) and a positive integer k, find \(g\in F(I)\) which minimizes \(\| g-f\|\) among all functions with the number of constant pieces less then k. These problems are solved by using shortest path and dynamic programming techniques, and polynomial time algorithms are proposed. Some applications are briefly described.
0 references
piecewise constant functions
0 references
shortest path
0 references
polynomial time algorithms
0 references