Piecewise-Linear Approximations of Uncertain Functions

摘要

We study the problem of approximating a function F : R → R by a piecewise-linear function F when the values of F at {x_1,…,x_n} are given by a discrete probability distribution. Thus, for each x_I, we are given a discrete set y_I,1, …,yi,mi of possible function values with associated probabilities pi,j such that Pr[F(xi) = yi,j] = pi,j. We define the error of F as error(F,F) = max_I=1 E[|F(xi) - F(xi)]. Let m = Σ_I~n=1mi be the total number of potential values over all F(xj). We obtain the following two results: (Ⅰ) an O(m) algorithm that, given F and a maximum error e, computes a function F with the minimum number of links such that error(F,F) ≤ ε; (Ⅱ) an O(n~(4/3+δ) +mlog n) algorithm that, given F, an integer value 1 ≤ k ≤ n and any δ > 0, computes a function F of at most k links that minimizes error(F,F).