Best piecewise constant approximation of a function of single variable (Q1111948): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: Wikidata QID (P12): Q61688029, #quickstatements; #temporary_batch_1707252663060 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q61688029 / rank | |||
Normal rank |
Revision as of 00:18, 7 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